PathWyse: a flexible, open-source library for the resource constrained shortest path problem

References

• S. Ahmadi, G. Tack, D.D. Harabor, and P. Kilby, A fast exact algorithm for the resource constrained shortest path problem, Proc AAAI Conf Artif Intell 35(14) (2021), pp. 12217–12224.
   Google Scholar
• E. Balas, The prize collecting traveling salesman problem, Networks 19(6) (1989), pp. 621–636.
   Web of Science ®Google Scholar
• R. Baldacci, A. Mingozzi, and R. Roberti, New route relaxation and pricing strategies for the vehicle routing problem, Oper. Res. 59(5) (2011), pp. 1269–1283.
   Web of Science ®Google Scholar
• J.E. Beasley and N. Christofides, An algorithm for the resource constrained shortest path problem, Networks 19(4) (1989), pp. 379–394.
   Web of Science ®Google Scholar
• biobj, A*-based path planners for WCSPP and BOSPP, repository. Available at https://bitbucket.org/s-ahmadi/biobj/src/master/, 2022. [Online; accessed 27-Oct-2022].
   Google Scholar
• T. Bulhões, R. Sadykov, and E. Uchoa, A branch-and-price algorithm for the minimum latency problem, Comput. Oper. Res. 93 (2018), pp. 66–78.
   Web of Science ®Google Scholar
• E.A. Cabral, E. Erkut, G. Laporte, and R.A. Patterson, The network design problem with relays, Eur. J. Oper. Res. 180(2) (2007), pp. 834–844.
   Web of Science ®Google Scholar
• N. Cabrera, A.L. Medaglia, L. Lozano, and D. Duque, An exact bidirectional pulse algorithm for the constrained shortest path, Networks 76(2) (2020), pp. 128–146.
   Web of Science ®Google Scholar
• W.M. Carlyle, J.O. Royset, and R.K. Wood, Lagrangian relaxation and enumeration for solving constrained shortest-path problems, Networks 52(4) (2008), pp. 256–270.
   Web of Science ®Google Scholar
• L. Costa, C. Contardo, G. Desaulniers, and D. Pecin, Selective arc-ng pricing for vehicle routing, Int. Trans. Oper. Res. 28(5) (2021), pp. 2633–2690.
   Web of Science ®Google Scholar
• CVRPLIB, Available at https://vrp.galgos.inf.puc-rio.br, 2014. [Online; accessed 27-Oct-2022].
   Google Scholar
• G. Desaulniers, J. Desrosiers, I. loachim, M.M. Solomon, F. Soumis, and D. Villeneuve, A unified framework for deterministic time constrained vehicle routing and crew scheduling problems, in Fleet Management and Logistics, T.G. Crainic and G. Laporte, eds., Springer US, Boston, MA, 1998, pp. 57–93.
   Google Scholar
• G. Desaulniers, J. Desrosiers, and M.M. Solomon, Column Generation, Springer, New York, NY, 2005.
   Google Scholar
• G. Desaulniers, F. Lessard, and A. Hadjar, Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows, Transp. Sci. 42(3) (2008), pp. 387–404.
   Web of Science ®Google Scholar
• M. Desrochers and F. Soumis, A generalized permanent labelling algorithm for the shortest path problem with time windows, INFOR Inf. Syst. Oper. Res. 26(3) (1988), pp. 191–212.
   Web of Science ®Google Scholar
• DIMACS, 9th DIMACS implementation challenge-–shortest paths. Available at https://www.diag.uniroma1.it/challenge9/download.shtml, 2005. [Online; accessed 27-Oct-2022].
   Google Scholar
• I. Dumitrescu and N. Boland, Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem, Networks 42(3) (2003), pp. 135–153.
   Web of Science ®Google Scholar
• S. Erdoğan and E. Miller-Hooks, A green vehicle routing problem, Transp. Res. E. Logist. Transp. Rev. 48(1) (2012), pp. 100–114. Select Papers from the 19th International Symposium on Transportation and Traffic Theory.
   Web of Science ®Google Scholar
• D. Feillet, P. Dejax, and M. Gendreau, Traveling salesman problems with profits, Transp. Sci. 39(2) (2005), pp. 188–205.
   Web of Science ®Google Scholar
• R. Fukasawa, J. Lysgaard, M.P. de Aragão, R. Marcelo, E. Uchoa, and R.F. Werneck, Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Math. Program. 106(3) (2006), pp. 491–511.
   Web of Science ®Google Scholar
• M. Gamache, F. Soumis, G. Marquis, and J. Desrosiers, A column generation approach for large-scale aircrew rostering problems, Oper. Res. 47(2) (1999), pp. 247–263.
   Web of Science ®Google Scholar
• D. Gavalas, C. Konstantopoulos, K. Mastakas, G. Pantziou, and N. Vathis, Approximation algorithms for the arc orienteering problem, Inf. Process. Lett. 115(2) (2015), pp. 313–315.
   Web of Science ®Google Scholar
• B.L. Golden, L. Levy, and R. Vohra, The orienteering problem, Nav. Res. Logist. 34(3) (1987), pp. 307–318.
   Web of Science ®Google Scholar
• A. Gunawan, H.C. Lau, and P. Vansteenwegen, Orienteering problem: A survey of recent variants, solution approaches and applications, Eur. J. Oper. Res. 255(2) (2016), pp. 315–332.
   Web of Science ®Google Scholar
• K. Haase, G. Desaulniers, and J. Desrosiers, Simultaneous vehicle and crew scheduling in urban mass transit systems, Transp. Sci. 35(3) (2001), pp. 286–303.
   Web of Science ®Google Scholar
• J. Halpern and I. Priess, Shortest path with time constraints on movement and parking, Networks4(3) (1974), pp. 241–253.
   Google Scholar
• P.E. Hart, N.J. Nilsson, and B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cybern. 4(2) (1968), pp. 100–107. 10.1109/TSSC.1968.300136.
   Web of Science ®Google Scholar
• J. Homberger and H. Gehring, A two-phase hybrid metaheuristic for the vehicle routing problem with time windows, Eur. J. Oper. Res. 162(1) (2005), pp. 220–238. Logistics: From Theory to Application.
   Web of Science ®Google Scholar
• S. Irnich and G. Desaulniers, Shortest Path Problems with Resource Constraints, Springer US, Boston, MA, 2005, pp. 33–65.
   Google Scholar
• S. Irnich and D. Villeneuve, The shortest-path problem with resource constraints and k-cycle elimination for k≥3, INFORMS. J. Comput. 18(3) (2006), pp. 391–406.
   Web of Science ®Google Scholar
• M. Jepsen, B. Petersen, and S. Spoorendonk, A branch-and-cut algorithm for the elementary shortest path problem with a capacity constraint. Technical Report 08/01, DIKU, University of Copenhagen, 2008.
   Google Scholar
• M. Jepsen, B. Petersen, S. Spoorendonk, and D. Pisinger, Subset-row inequalities applied to the vehicle-routing problem with time windows, Oper. Res. 56(2) (2008), pp. 497–511.
   Web of Science ®Google Scholar
• G. Laporte and S. Martello, The selective travelling salesman problem, Discret. Appl. Math. 26(2–3) (1990), pp. 193–207.
   Web of Science ®Google Scholar
• L. Lozano and A.L. Medaglia, On an exact method for the constrained shortest path problem, Comput. Oper. Res. 40(1) (2013), pp. 378–384.
   Web of Science ®Google Scholar
• S. Lu, B. He, Y. Li, and H. Fu, Accelerating exact constrained shortest paths on gpus, 14(4) (2020), pp. 547–559.
   Google Scholar
• A. Madkour, W.G. Aref, F.U. Rehman, M.A. Rahman, and S.M. Basalamah, A survey of shortest-path algorithms. CoRR, abs/1705.02044, 2017.
   Google Scholar
• R. Martinelli, D. Pecin, and M. Poggi, Efficient elementary and restricted non-elementary route pricing, Eur. J. Oper. Res. 239(1) (2014), pp. 102–111.
   Web of Science ®Google Scholar
• K. Mehlhorn and M. Ziegelmann, Resource constrained shortest paths, in Algorithms-–ESA 2000, Mike S. Paterson, ed., Springer, Berlin, Heidelberg, 2000, pp. 326–337.
   Google Scholar
• R. Montagné, D.T. Sanchez and H.O. Storbugt, Vrpy: A python package for solving a range of vehicle routing problems with a column generation approach, Journal of Open Source Software 5(55) (2020), pp. 2408.
   Google Scholar
• D. Pecin, A. Pessoa, M. Poggi, and E. Uchoa, Improved branch-cut-and-price for capacitated vehicle routing, Math. Program. Comput. 9(1) (2017), pp. 61–100.
   Google Scholar
• A.A. Pessoa, R. Sadykov, E. Uchoa, and F. Vanderbeck, A generic exact solver for vehicle routing and related problems, Math. Program. 183(1-2) (2020), pp. 483–523.
   Web of Science ®Google Scholar
• L.D.P. Pugliese and F. Guerriero, A survey of resource constrained shortest path problems: Exact solution approaches, Networks 62(3) (2013), pp. 183–200.
   Web of Science ®Google Scholar
• G. Righini and M. Salani, Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, Discret. Optim. 3(3) (2006), pp. 255–273. Graphs and Combinatorial Optimization.
   Web of Science ®Google Scholar
• G. Righini and M. Salani, New dynamic programming algorithms for the resource constrained elementary shortest path problem, Networks 51(3) (2008), pp. 155–170.
   Web of Science ®Google Scholar
• G. Righini and M. Salani, Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming, Comput. Oper. Res. 36(4) (2009), pp. 1191–1203.
   Web of Science ®Google Scholar
• R. Sadykov, E. Uchoa, and A. Pessoa, A bucket graph–based labeling algorithm with application to vehicle routing, Transp. Sci. 55(1) (2020), pp. 4–28.
   Web of Science ®Google Scholar
• D.T. Sanchez, cspy: A python package with a collection of algorithms for the (resource) constrained shortest path problem, J. Open Source Softw. 5(49) (2020), pp. 1655.
   Google Scholar
• E. Schede, J. Brandt, A. Tornede, M. Wever, V. Bengs, E. Hüllermeier, and K. Tierney, A survey of methods for automated algorithm configuration, J. Artif. Intell. Res. 75 (2022), pp. 425–487.
   Web of Science ®Google Scholar
• SPPRCLIB, Available at https://hjemmesider.diku.dk/spooren/spprclib.htm, 2008. [Online; accessed 27-Oct-2022].
   Google Scholar
• B.W. Thomas, T. Calogiuri, and M. Hewitt, An exact bidirectional a-star approach for solving resource-constrained shortest path problems, Networks 73(2) (2019), pp. 187–205.
   Web of Science ®Google Scholar
• C. Tilk, A.-K. Rothenbächer, T. Gschwind, and S. Irnich, Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster, Eur. J. Oper. Res. 261(2) (2017), pp. 530–539.
   Web of Science ®Google Scholar
• M. Zabarankin, S. Uryasev, and P. Pardalos. (2002). Optimal risk path algorithms, in Cooperative Control and Optimization: Applied Optimization, R. Murphey, P.M. Pardalos, eds., Springer, Boston, 2002.
   Google Scholar