All Times EDT
Keywords: network optimization, optimal tour, tsp problem
Optimal public transportation is key for smart cities. Network optimization can be applied to better understand urban mobility and network topology, revealing critical routes to maintain accessibility in public transportation, optimal ways to flow passengers throughout the city, possible and best routes between pairs of locations or the optimal tour within the city considering all possible routes. This paper focus on an example of the traveling salesman problem in Paris based on a multi-modal transportation system. Many public transportation agencies and organizations around the globe open and share their data for application development and research. These data can be used to explore the network topology in order to optimize tasks in terms of public transportation offering. Optimization algorithms can be applied to better understand the urban mobility, particularly based on the transportation network topology. A set of algorithms will be used to evaluate the public transportation network in Paris. The Minimum Spanning Tree algorithm can reveal the most critical routes to be kept in order to maintain the same level of accessibility in the public transportation network. The Path algorithm can reveal all possible routes between any pair of locations. The Shortest Path can reveal an optimal route between any two locations in the city. The Transitive Closure algorithm identifies which pairs of locations are joined by some route. The Clique algorithm identifies all complete graphs within the transportation network. The Cycle algorithm identifies directed sub-networks starting and ending at the same point. The Pattern Match algorithm search for similar sub-graphs within the network considering a predefined topology. Finally, the Traveling Salesman Problem algorithm searches for the minimum-cost tour within the network. All these algorithms will be applied in this study to evaluate the transportation network and provide the best tour considering a multi-modal topology.