Exact algorithms for multi-criteria multi-modal shortest path with transfer delaying and arriving time-window in urban transit network. (English) Zbl 1427.90283
Summary: This paper investigates the solution algorithms for the multi-criteria multi-modal shortest path problem (M-SPP), which belongs to the set of problems known as NP-hard, in urban transit network (UTN). The related M-SPP is one of the important and practical problems in several fields such as urban transportation system and freight transportation. The UTN is composed of multiple modes (e.g., automobile, bus, subway, light rail, pedestrian and so on). To get their destination, the passengers can alternate between different modes. As a special demand, the time-window is usually associated with the M-SPP. Because of the service time-limit of modes, the available modes at a stop are varied with the time. So the optimal M-SPP with arriving time-window cannot be simply obtained by finding the optimal M-SPP firstly and then reversely deducing the leaving time-window of the origin according to the arriving time-window of destination. In this paper, the M-SPP with arriving time-window is firstly proposed. To solve the multi-criteria M-SPPs (MM-SPP) with transfer delaying, an improved exact label correcting algorithm (LCA) is designed and, to solve the proposed MM-SPPs with both of transfer delaying and arriving time-window, an exact reverse LCA is designed. Finally, some computing examples are given to test the effectiveness of the designed algorithms.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90B10 | Deterministic network models in operations research |
| 90C29 | Multi-objective and goal programming |
Keywords:
network; algorithm; shortest path problem (SPP); multi-modal shortest path problem (M-SPP); urban transit network (UTN); label correcting algorithm (LCA)References:
| [1] | Dantzig, G. B., On the shortest route through a network, Manage. Sci., 7, 187-190 (1960) · Zbl 0995.90518 |
| [2] | Dijkstra, E. W., A note on two problems in connection with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002 |
| [3] | Pallottino, S.; Scutella, M. G., Shortest path algorithms in transportation models: Classical and innovative aspects, (Marcotte, P.; Nguyen, S., Equilibrium and Advanced Transportation Modelling (1998), Kluwer Academic: Kluwer Academic The Netherlands), 245-281 · Zbl 0972.90004 |
| [4] | Deo, N.; Pang, C., Shortest path algorithms: taxonomy and annotation, Networks, 14, 275-323 (1984) · Zbl 0542.90101 |
| [5] | Zografos, K. G.; Androutsopoulos, K. N., Algorithms for itinerary planning in multimodal transportation networks, Transp. Syst., 9, 175-184 (2008) |
| [6] | Bielli, M.; Boulmakoul, A.; Mouncif, H., Object modeling and path computation for multimodal travel systems, Eur. J. Oper. Res., 175, 1705-1730 (2006) · Zbl 1142.90367 |
| [7] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 |
| [8] | Hansen, P., On a multicriteria shortest path problem, (Fandel, G.; Gal, T., Multiple Criteria Decision Making Theory and Application. Multiple Criteria Decision Making Theory and Application, Lecture Notes in Economics and Mathematical Systems, vol. 177 (1979), Springer Verlag: Springer Verlag Berlin), 109-127 · Zbl 0444.90098 |
| [9] | Martins, E. Q.V., On a multicriteria shortest path problem, Eur. J. Oper. Res., 16, 236-245 (1984) · Zbl 0533.90090 |
| [10] | Mote, J.; Murthy, I.; Olson, D. L., A parametric approach to solving bicriterion shortest path problems, Eur. J. Oper. Res., 53, 81-92 (1991) · Zbl 0733.90073 |
| [11] | Skriver, A., A classification of bi-criteria shortest path (BST) algorithm, Asia-Pacific J. Oper. Res., 17, 199-212 (2000) · Zbl 1042.90633 |
| [12] | Crainic, T.; Rousseau, J. M., Multicommodity, multimode freight transportation: a general modeling and algorithmic framework for the service network design problem, Transp. Res. Part B, 20, 25-242 (1986) |
| [13] | Nguyen, S.; Morello, E.; Pallotino, S., Discrete time dynamic estimation model for passenger origin/destination matrices on transit networks, Transp. Res. Part B, 22, 251-260 (1988) |
| [14] | Nguyen, S.; Pallotino, S.; Malucelli, F., A modeling framework for the passenger assignment on a transport network with timetables, Transp. Sci., 35, 238-249 (2001) · Zbl 1041.90501 |
| [15] | Spiess, H.; Florian, M., Optimal strategies: a new assignment model for transit networks, Transp. Res. Part B, 23, 83-102 (1989) |
| [16] | Modesti, P.; Sciomachen, A., A utility measure for finding multi-objective shortest paths in urban multimodal transportation networks, Eur. J. Oper. Res., 111, 495-508 (1998) · Zbl 0948.90021 |
| [17] | Lozano, A.; Storchi, G., Shortest viable path in multimodal networks, Transp. Res. Part A, 35, 225-241 (2001) |
| [18] | Lozano, A.; Storchi, G., Shortest viable hyperpath in multimodal networks, Transp. Res. Part B, 36, 853-874 (2002) |
| [19] | Ayed, H.; Khadraoui, D.; Habbas, Z.; Bouvry, P.; Merche, J. F., Transfer graph approach for multimodal transport problems, (Hoai, L. T.; Bouvry, P.; Tao, P. D., Modelling, Computation and Optimization in Information Systems and Management Sciences. Modelling, Computation and Optimization in Information Systems and Management Sciences, Communications in Computer and Information Science, vol. 14 (2008), Springer: Springer Berlin Heidelberg), 538-547 · Zbl 1160.90311 |
| [20] | Rahim, A. A.; Farhad, S., An evolutionary solution for multimodal shortest path problem in metropolises, ComSIS, 7, 789-811 (2010) |
| [21] | Gen, M.; Cheng, R., Genetic Algorithms & Engineering Optimization (2000), Wiley: Wiley New York |
| [22] | Liu, L.; Mu, H., An oriented spanning tree based genetic algorithm for multi-criteria shortest path problems, Appl. Soft Comput., 12, 506-512 (2012) |
| [23] | Liu, L.; Mu, H.; Luo, H.; Li, X., A simulated annealing for multi-criteria network path problems, Comput. Oper. Res., 39, 3119-3135 (2012) · Zbl 1349.90861 |
| [24] | Ziliaskopoulos, A. K.; Wardell, W., An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays, Eur. J. Oper. Res., 125, 486-502 (2000) · Zbl 0967.90009 |
| [25] | Chang, E.; Floros, E.; Ziliaskopoulos, A., An intermodal time-dependent minimum cost path algorithm with an application to hazmat routing, (Zeimpekis, V.; Tarantilis, C. D.; Giaglis, G. M.; Minis, I., Dynamic Fleet Management, Concepts, Systems, Algorithms & Case Studies. Dynamic Fleet Management, Concepts, Systems, Algorithms & Case Studies, Operations Research/Computer Science Interfaces Series, vol. 38 (2007), Springer: Springer US), 113-132 · Zbl 1125.90002 |
| [26] | Galvez-Fernandez, C.; Khadraoui, D.; Ayed, H.; Habbas, Z.; Alba, E., Distributed approach for solving time-dependent problems in multimodal transport networks, Adv. Oper. Res., 2009, 1-15 (2009) · Zbl 1198.90053 |
| [27] | Horn, M. E.T., An extended model and procedural framework for planning multi-modal passenger journeys, Transp. Res. Part B, 37, 641-660 (2003) |
| [28] | Beuthe, M.; Jourquin, B.; Geerts, G. F.; Ha, C. K.N., Freight transportation demand elasticities: a geographic multimodal transportation network analysis, Transp. Res. Part E, 37, 253-266 (2001) |
| [29] | Skriver, A. J.V.; Andersen, K. A., A label correcting approach for solving bicriterion shortest-path problems, Comput. Oper. Res., 27, 507-524 (2000) · Zbl 0955.90144 |
| [30] | Guerriero, F.; Musmanno, R., Label correcting methods to solve multicriteria shortest path problems, J. Optim. Theory Appl., 111, 589-613 (2001) · Zbl 0984.90050 |
| [31] | Carlyle, W. M.; Wood, R. K., Near-shortest and \(k\)-shortest simple paths, Networks, 42, 98-109 (2005) · Zbl 1102.68090 |
| [32] | Curtin, K. M.; Biba, S., The transit route arc-node service maximization problem, Eur. J. Oper. Res., 208, 46-56 (2011) · Zbl 1206.90010 |
| [33] | Dell’Olmo, P.; Gentili, M.; Scozzari, A., Heuristics for the bi-objective path dissimilarity problem, Eur. J. Oper. Res., 162, 70-82 (2005) · Zbl 1132.90303 |
| [34] | Marti, R.; Velarde, J. L.G.; Duartec, A., Heuristics for the bi-objective path dissimilarity problem, Comput. Oper. Res., 36, 2905-2912 (2009) · Zbl 1162.90594 |
| [35] | Fan, W.; Machemehl, R. B., Optimal transit route network design problem with variable transit demand: genetic algorithm approach, J. Transp. Eng., 132, 40-51 (2006) |
| [36] | Fan, W.; Machemehl, R. B., Using a simulated annealing algorithm to solve the transit route network design problem, J. Transp. Eng., 132, 122-132 (2006) |
| [37] | Raith, A.; Ehrgott, M., A comparison of solution strategies for biobjective shortest path problems, Comput. Oper. Res., 30, 1299-1331 (2009) · Zbl 1162.90579 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
