An Efficient Label-Correcting Algorithm for the Multiobjective Shortest Path Problem

References

• Ahuja R, Magnanti T, Orlin J (1993) Network Flows: Theory, Algorithms, and Applications (Alfred P. Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA).Google Scholar
• Aneja Y, Nair K (1979) Bicriteria transportation problem. Management Sci. 25(1):73–78.Link, Google Scholar
• Azevedo J, Costa MEOS, Madeira JJES, Martins EQV (1993) An algorithm for the ranking of shortest paths. Eur. J. Oper. Res. 69(1):97–106.Crossref, Google Scholar
• Beasley JE, Christofides N (1989) An algorithm for the resource constrained shortest path problem. Networks 19(4):379–394.Crossref, Google Scholar
• Bellman R (1958) On a routing problem. Quart. Appl. Math. 16(1):87–90.Crossref, Google Scholar
• Bertsekas D (1998) Network Optimization: Continuous and Discrete Models (Athena Scientific, Belmont, MA).Google Scholar
• Bolívar MA, Lozano L, Medaglia AL (2014) Acceleration strategies for the weight constrained shortest path problem with replenishment. Optim. Lett. 8(8):2155–2172.Crossref, Google Scholar
• Brumbaugh-Smith J, Shier D (1989) An empirical investigation of some bicriterion shortest path algorithms. Eur. J. Oper. Res. 43(2):216–224.Crossref, Google Scholar
• Cabrera N, Medaglia AL, Lozano L, Duque D (2020) An exact bidirectional pulse algorithm for the constrained shortest path. Networks 76(2):128–146.Crossref, Google Scholar
• Carlyle W, Wood R (2005) Near-shortest and k-shortest simple paths. Networks 46(2):98–109.Crossref, Google Scholar
• Clímaco J, Martins E (1982) A bicriterion shortest path algorithm. Eur. J. Oper. Res. 11(4):399–404.Crossref, Google Scholar
• Clímaco JC, Craveirinha JM, Pascoal M (2003) A bicriterion approach for routing problems in multimedia networks. Networks 41(4):206–220.Crossref, Google Scholar
• Current J, ReVelle C, Cohon J (1987) The median shortest path problem: A multiobjective approach to analyze cost vs. accessibility in the design of transportation networks. Transportation Sci. 21(3):188–197.Link, Google Scholar
• Current J, ReVelle C, Cohon J (1988) The minimum-covering/shortest-path problem. Decision Sci. 19(3):490–503.Crossref, Google Scholar
• Demeyer S, Goedgebeur J, Audenaert P, Pickavet M, Demeester P (2013) Speeding up Martins algorithm for multiple objective shortest path problems. 4OR 11(4):323–348.Crossref, Google Scholar
• Deo N, Pang C (1984) Shortest-path algorithms: Taxonomy and annotation. Networks 14(2):275–323.Crossref, Google Scholar
• Dijkstra E (1959) A note on two problems in connection with graphs. Numerische Mathematik 1:269–271.Crossref, Google Scholar
• Dumitrescu I, Boland N (2003) Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem. Networks 42(3):135–153.Crossref, Google Scholar
• Duque D, Lozano L, Medaglia A (2015) An exact method for the biobjective shorstest path problem for large-scale road networks. Eur. J. Oper. Res. 242(3):788–797.Crossref, Google Scholar
• Ehrgott M (2005) Multicriteria Optimization, vol. 491 (Springer Science & Business Media, Berlin).Google Scholar
• Eiger A, Mirchandani PB, Soroush H (1985) Path preferences and optimal paths in probabilistic networks. Transportation Sci. 19(1):75–84.Link, Google Scholar
• Engineer FG, Nemhauser GL, Savelsbergh MW, Song JH (2012) The fixed-charge shortest-path problem. INFORMS J. Comput. 24(4):578–596.Link, Google Scholar
• Ford LR Jr, Fulkerson DR (2015) Flows in Networks (Princeton University Press).Google Scholar
• Gabrel V, Vanderpooten D (2002) Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite. Eur. J. Oper. Res. 139(3):533–542.Crossref, Google Scholar
• Galand L, Ismaili A, Perny P, Spanjaard O (2013) Bidirectional preference-based search for state space graph problems. Helmert M, Rüger G, eds. Proc. Sixth Annual Sympos. Combinatorial Search, Leavenworth, WA (AAAI Press), 80–88.Google Scholar
• Garroppo RG, Giordano S, Tavanti L (2010) A survey on multi-constrained optimal path computation: Exact and approximate algorithms. Comput. Networks 54(17):3081–3107.Crossref, Google Scholar
• Gavalas D, Konstantopoulos C, Mastakas K, Pantziou G (2014) A survey on algorithmic approaches for solving tourist trip design problems. J. Heuristics 20(3):291–328.Crossref, Google Scholar
• Geoffrion AM (1968) Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl. 22(3):618–630.Crossref, Google Scholar
• Guerriero F, Musmanno R (2001) Label correcting methods to solve multicriteria shortest path problems. J. Optim. Theory Appl. 111:589–613.Crossref, Google Scholar
• Hansen P (1980) Bicriterion path problems. Fandel G, Gal T, eds. Multiple Criteria Decision Making: Theory and Applications, 2nd ed. Lectures Notes in Economics and Mathematical Systems, vol. 177 (Springer, Heidelberg), 109–127.Crossref, Google Scholar
• Hart P, Nilsson N, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Sci. Cybernetics 4(2):100–107.Crossref, Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, New York), 33–65.Crossref, Google Scholar
• Lozano L, Medaglia AL (2013) On an exact method for the constrained shortest path problem. Comput. Oper. Res. 40(1):378–384.Crossref, Google Scholar
• Lozano L, Duque D, Medaglia AL (2015) An exact algorithm for the elementary shortest path problem with resource constraints. Transportation Sci. 50(1):348–357.Link, Google Scholar
• Machuca E, Mandow L (2011) Multiobjective route planning with precalculated heuristics. Proc. 15th Portuguese Conf. Artificial Intelligence, 98–107.Google Scholar
• Machuca E, Mandow L (2016) Lower bound sets for biobjective shortest path problems. J. Global Optim. 64(1):63–77.Crossref, Google Scholar
• Mandow L, Cruz JDL (2010) Multiobjective A* search with consistent heuristics. J. ACM 57(5):27.Crossref, Google Scholar
• Martins E (1984) On a multicriteria shortest path problem. Eur. J. Oper. Res. 16(2):236–245.Crossref, Google Scholar
• Mendoza JE, Guéret C, Hoskins M, Lobit H, Pillac V, Vidal T, Vigo D (2014) VRP-rep: The vehicle routing community repository. Third Meeting EURO Working Group Vehicle Routing Logist. Optim.Google Scholar
• Moore EF (1959) The shortest path through a maze. Proc. Internat. Sympos. Switching Theory, 285–292.Google Scholar
• Mote J, Murthy I, Olson DL (1991) A parametric approach to solving bicriterion shortest path problems. Eur. J. Oper. Res. 53(1):81–92.Crossref, Google Scholar
• Munoz JML (2004) Boost multi-index containers library. C/C++ Users J. 22(9):6.Google Scholar
• Ndiaye IA, Neron E, Jouglet A (2017) Macroscopic evacuation plans for natural disasters. OR Spectrum 39(1):231–272.Crossref, Google Scholar
• Paixão JM, Santos JL (2013) Labeling methods for the general case of the multi-objective shortest path problem–A computational study. Madureira A, Reis C, Marques V, eds. Intelligent Systems, Control and Automation: Science and Engineering. Computational Intelligence and Decision Making (Springer, The Netherlands), 489–502.Crossref, Google Scholar
• Parmentier A (2019) Algorithms for non-linear and stochastic resource constrained shortest path. Math. Methods Oper. Res. 89(2): 281–317.Crossref, Google Scholar
• PassMark Software (2019) CPU benchmarks. Accessed February 2020, https://www.cpubenchmark.net/.Google Scholar
• Raith A (2010) Speed-up of labelling algorithms for biobjective shortest path problems. Proc. 45th Annual Conf. ORSNZ, 313–322.Google Scholar
• Raith A, Ehrgott M (2009) A comparison of solution strategies for biobjective shortest path problems. Comput Oper. Res. 36(4):1299–1331.Crossref, Google Scholar
• Raith A, Schmidt M, Schöbel A, Thom L (2018) Extensions of labeling algorithms for multi-objective uncertain shortest path problems. Networks 72(1):84–127.Crossref, Google Scholar
• Sauvanet G, Neron E (2010) Search for the best compromise solution on multiobjective shortest path problem. Electronic Notes Discrete Math. 36:615–622.Crossref, Google Scholar
• Sedeño-Noda A, Colebrook M (2019) A biobjective Dijkstra algorithm. Eur. J. Oper. Res. 276(1):106–118.Crossref, Google Scholar
• Sedeño-Noda A, Raith A (2015) A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem. Comput. Oper. Res. 57:83–94.Crossref, Google Scholar
• Serafini P (1987) Some considerations about computational complexity for multiobjective combinatorial problems. Jahn J, Krabs W, eds. Recent Advances and Historical Development of Vector Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 294 (Springer, Berlin), 222–231.Google Scholar
• Sherali HD, Hobeika AG, Kangwalklai S (2003) Time-dependent, label-constrained shortest path problems with applications. Transportation Sci. 37(3):278–293.Link, Google Scholar
• Skriver A, Andersen K (2000) A label correcting approach for solving bicriterion shortest-path problems. Comput. Oper. Res. 27(6):507–524.Crossref, Google Scholar
• Tarapata Z (2007) Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms. Internat. J. Appl. Math. Comput. Sci. 17(2):269–287.Crossref, Google Scholar
• Thomas BW, Calogiuri T, Hewitt M (2019) An exact bidirectional A* approach for solving resource-constrained shortest path problems. Networks 73(2):187–205.Crossref, Google Scholar
• T’kindt V, Billaut JC (2006) Multicriteria Scheduling: Theory, Models and Algorithms (Springer Science & Business Media).Google Scholar
• Tung C, Chew K (1992) A multicriteria Pareto-optimal path algorithm. Eur. J. Oper. Res. 62(2):203–209.Crossref, Google Scholar
• Ulungu E, Teghem J (1994) Multi-objective combinatorial optimization problems: A survey. J. Multi-Criteria Decision Anal. 3(2): 83–104.Crossref, Google Scholar
• Ulungu E, Teghem J (1995) The two phases method: An efficient procedure to solve biobjective combinatorial optimization problems. Foundations Comput. Decision Sci. 20(2):149–165.Google Scholar