Abstract
Ibrahim et al. (Int Trans Oper Res 16:361–369, 2009) presented and analyzed two integer programming formulations for the elementary shortest-path problem (ESPP), which is known to be NP-hard if the underlying digraph contains negative cycles. In fact, the authors showed that a formulation based on multi-commodity flows possesses a significantly stronger LP relaxation than a formulation based on arc flow variables. Since the ESPP is essentially an integer problem, the contribution of our paper lies in extending this research by comparing the formulations with regard to the computation time and memory requirements required for their integer solution. Moreover, we assess the quality of the lower bounds provided by an integer relaxation of the multi-commodity flow formulation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahuja R, Magnanti T, Orlin J (1993) Network flows. Prentice-Hall, Upper Saddle River
Aráoz J, Fernández E, Meza O (2009) Solving the prize-collecting rural postman problem. Eur J Oper Res 196(3): 886–896. doi:10.1016/j.ejor.2008.04.037
Baldacci R, Mingozzi A, Roberti R (2012) Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. Eur J Oper Res 218: 1–6
Boland N, Dethridge J, Dumitrescu I (2006) Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper Res Lett 34(1): 58–68
Boost (2012) Boost graph library. http://www.boost.org
Crainic T, Ricciardi N, Storchi G (2009) Models for evaluating and planning city logistics systems. Transp Sci 43(4): 432–454. doi:10.1287/trsc.1090.0279
Desaulniers G, Desrosiers J, Ioachim I, Solomon M, Soumis F, Villeneuve D (1998) A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. In: Crainic T, Laporte G (eds) Fleet management and logistics. Kluwer, Boston, pp 57–93
Drexl M (2012) Synchronization in vehicle routing—a survey of VRPs with multiple synchronization constraints. Transp Sci. doi:10.1287/trsc.1110.0400
Feillet D, Dejax P, Gendreau M (2005) Traveling salesman problems with profits. Transp Sci 39(2): 188–205. doi:10.1287/trsc.1030.0079
Fukasawa R, Longo H, Lysgaard J, Poggide Arago M, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math Program Ser A 106(3): 491–511
Golden B, Raghavan S, Wasil E (eds) (2008) The vehicle routing problem: latest advances and new challenges. Operations research/computer science interfaces series, vol 43. Springer, Berlin
Gutin G, Punnen A (eds) (2002) The traveling salesman problem and its variations. Kluwer, Dordrecht
Ibrahim M, Maculan N, Minoux M (2009) A strong flow-based formulation for the shortest path problem in digraphs with negative cycles. Int Trans Oper Res 16(3): 361–369. doi:10.1111/j.1475-3995.2008.00681.x
Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon M (eds) Column generation. Springer, New York, pp 33–65
Irnich S, Villeneuve D (2006) The shortest path problem with resource constraints and k-cycle elimination for k ≥ 3. INFORMS J Comput 18(3): 391–406
Jepsen M, Petersen B, Spoorendonk S (2008) A branch-and-cut algorithm for the elementary shortest path problem with a capacity constraint. Technical report 08/01, Department of Computer Science, University of Copenhagen
Righini G, Salani M (2006) Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim 3(3): 255–273. doi:10.1016/j.disopt.2006.05.007
Skorobohatyj G (1999) Finding a minimum cut between all pairs of nodes in an undirected graph. http://elib.zib.de/pub/Packages/mathprog/mincut/all-pairs/index.html. Accessed 25 April 2012
Toth P, Vigo D (eds) (2002) The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia
Wayne K (2008) Union-find algorithms. http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf. Accessed 25 April 2012
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Drexl, M., Irnich, S. Solving elementary shortest-path problems as mixed-integer programs. OR Spectrum 36, 281–296 (2014). https://doi.org/10.1007/s00291-012-0302-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-012-0302-7