Vehicle routing problem (VRP) is a fundamental combinatorial optimization and integer programming problem with several important applications. The VRP is usually solved by using branch-and-bound techniques requiring solving a shortest path problem with resource constraints (SPPRC) and the determination of a lower bound, which can be computed by using column generation. The SPPRC entails finding the minimum cost elementary path in a valuated graph that is subject to constraints on resource consumption. The proposed exact solutions to this hard NP-hard problem require an excessive computation time which increases with the number of resources. In this paper, we propose a new approximate resolution of the SPPRC for acyclic and cyclic graphs. Our method is based on a Lagrangian relaxation of a subset of the constraints and using dominance only on a subset of the resources. This reduces the search space and allows users to efficiently compute solutions used to improve the column generation procedure. Extensive evaluation and comparison to the classical exact method show that the proposed algorithm achieves a good compromise between efficiency and quality of the SPPRC and the VRP solutions. Thus, our method can be used for practical large-scale VRP applications.
Citation: Abdelkader Lamamri, Mohammed Hachama. Approximate solution of the shortest path problem with resource constraints and applications to vehicle routing problems[J]. Electronic Research Archive, 2023, 31(2): 615-632. doi: 10.3934/era.2023030
Vehicle routing problem (VRP) is a fundamental combinatorial optimization and integer programming problem with several important applications. The VRP is usually solved by using branch-and-bound techniques requiring solving a shortest path problem with resource constraints (SPPRC) and the determination of a lower bound, which can be computed by using column generation. The SPPRC entails finding the minimum cost elementary path in a valuated graph that is subject to constraints on resource consumption. The proposed exact solutions to this hard NP-hard problem require an excessive computation time which increases with the number of resources. In this paper, we propose a new approximate resolution of the SPPRC for acyclic and cyclic graphs. Our method is based on a Lagrangian relaxation of a subset of the constraints and using dominance only on a subset of the resources. This reduces the search space and allows users to efficiently compute solutions used to improve the column generation procedure. Extensive evaluation and comparison to the classical exact method show that the proposed algorithm achieves a good compromise between efficiency and quality of the SPPRC and the VRP solutions. Thus, our method can be used for practical large-scale VRP applications.
| [1] |
G. B. Dantzig, J. H. Ramser, The truck dispatching problem, Manage. Sci., 6 (1959), 80–91. https://doi.org/10.1287/mnsc.6.1.80 doi: 10.1287/mnsc.6.1.80
|
| [2] |
M. Desrochers, J. Desrosiers, M. Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Oper. Res., 40 (1982), 342–354. https://doi.org/10.1287/opre.40.2.342 doi: 10.1287/opre.40.2.342
|
| [3] |
J. Desrosiers, Y. Dumas, M. M. Solomon, F. Soumis, Time constrained routing and scheduling, Handbooks Oper. Res. Manage. Sci., 8 (1995), 35–139. https://doi.org/10.1016/S0927-0507(05)80106-9 doi: 10.1016/S0927-0507(05)80106-9
|
| [4] |
N. Kohl, J. Desrosiers, O. B. Madsen, M. M. Solomon, F. Soumis, 2-path cuts for the vehicle routing problem with time windows, Transp. Sci., 33 (1999), 101–116. https://doi.org/10.1287/trsc.33.1.101 doi: 10.1287/trsc.33.1.101
|
| [5] |
S. Irnich, D. Villeneuve, The shortest-path problem with resource constraints and k-cycle elimination for k $\ge$ 3, INFORMS J. Comput., 18 (2006), 391–406. https://doi.org/10.1287/ijoc.1040.0117 doi: 10.1287/ijoc.1040.0117
|
| [6] |
R. Sadykov, E. Uchoa, A. Pessoa, A bucket graph-based labeling algorithm with application to vehicle routing, Transp. Sci., 55 (2021), 4–28. https://doi.org/10.1287/trsc.2020.0985 doi: 10.1287/trsc.2020.0985
|
| [7] |
R. Baldacci, E. Bartolini, A. Mingozzi, R. Roberti, An exact solution framework for a broad class of vehicle routing problems, Comput. Manage. Sci., 7 (2010), 229–268. https://doi.org/10.1007/s10287-009-0118-3 doi: 10.1007/s10287-009-0118-3
|
| [8] |
R. Fukasawa, Q. He, Y. Song, A branch-cut-and-price algorithm for the energy minimization vehicle routing problem, Transp. Sci., 50 (2016), 23–34. https://doi.org/10.1287/trsc.2015.0593 doi: 10.1287/trsc.2015.0593
|
| [9] |
D. Pecin, A. Pessoa, M. Poggi, E. Uchoa, Improved branch-cut-and-price for capacitated vehicle routing, Math. Program. Comput., 9 (2017), 61–100. https://doi.org/10.1007/s12532-016-0108-8 doi: 10.1007/s12532-016-0108-8
|
| [10] |
R. Fukasawa, H. Longo, J. Lysgaard, M. P. D. Aragão, M. Reis, E. Uchoa, et al., Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Math. Program., 106 (2006), 491–511. https://doi.org/10.1007/s10107-005-0644-x doi: 10.1007/s10107-005-0644-x
|
| [11] |
R. Baldacci, N. Christofides, A. Mingozzi, An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, Math. Program., 115 (2008), 351–385. https://doi.org/10.1007/s10107-007-0178-5 doi: 10.1007/s10107-007-0178-5
|
| [12] |
R. Baldacci, A. Mingozzi, R. Roberti, New route relaxation and pricing strategies for the vehicle routing problem, Oper. Res., 59 (2011), 1269–1283. https://doi.org/10.1287/opre.1110.0975 doi: 10.1287/opre.1110.0975
|
| [13] |
S. Dabia, S. Ropke, T. V. Woensel, T. D. Kok, Branch and price for the time-dependent vehicle routing problem with time windows, Transp. Sci., 47 (2013), 380–396. https://doi.org/10.1287/trsc.1120.0445 doi: 10.1287/trsc.1120.0445
|
| [14] |
A. Nagih, F. Soumis, Nodal aggregation of resource constraints in a shortest path problem, Eur. J. Oper. Res., 172 (2006), 500–514. https://doi.org/10.1016/j.ejor.2004.09.052 doi: 10.1016/j.ejor.2004.09.052
|
| [15] |
I. Himmich, H. B. Amor, I. E. Hallaoui, F. Soumis, A primal adjacency-based algorithm for the shortest path problem with resource constraints, Transp. Sci., 54 (2020), 1153–1169. https://doi.org/10.1287/trsc.2019.0941 doi: 10.1287/trsc.2019.0941
|
| [16] |
M. Behnke, T. Kirschstein, C. Bierwirth, A column generation approach for an emission-oriented vehicle routing problem on a multigraph, Eur. J. Oper. Res., 288 (2021), 794–809. https://doi.org/10.1016/j.ejor.2020.06.035 doi: 10.1016/j.ejor.2020.06.035
|
| [17] | I. Mathlouthi, M. Gendreau, J. Y. Potvin, Branch-and-price for a multi-attribute technician routing and scheduling problem, in Operations Research Forum, Springer International Publishing, 2 (2021), 1–35. https://doi.org/10.1007/s43069-020-00044-x |
| [18] |
S. Y. Tan, W. C. Yeh, The vehicle routing problem: State-of-the-art classification and review, Appl. Sci., 11 (2021), 10295. https://doi.org/10.3390/app112110295 doi: 10.3390/app112110295
|
| [19] | P. Toth, D. Vigo, Vehicle Routing: Problems, Methods, and Applications, SIAM, 2014. |
| [20] |
L. Taccari, Integer programming formulations for the elementary shortest path problem, Eur. J. Oper. Res., 252 (2016), 122–130. https://doi.org/10.1016/j.ejor.2016.01.003 doi: 10.1016/j.ejor.2016.01.003
|
| [21] |
E. Manousakis, P. Repoussis, E. Zachariadis, C. Tarantilis, Improved branch-and-cut for the inventory routing problem based on a two-commodity flow formulation, Eur. J. Oper. Res., 290 (2021), 870–885. https://doi.org/10.1016/j.ejor.2020.08.047 doi: 10.1016/j.ejor.2020.08.047
|
| [22] |
G. Lera-Romero, J. J. Miranda-Bront, A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints, Eur. J. Oper. Res., 289 (2021), 879–896. https://doi.org/10.1016/j.ejor.2019.07.014 doi: 10.1016/j.ejor.2019.07.014
|
| [23] |
C. M. Damião, J. M. P. Silva, E. Uchoa, A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem, 4OR-Q. J. Oper. Res., 2021 (2021), 1–25. https://doi.org/10.1007/s10288-021-00498-7 doi: 10.1007/s10288-021-00498-7
|
| [24] |
H. B. Ticha, N. Absi, D. Feillet, A. Quilliot, Empirical analysis for the VRPTW with a multigraph representation for the road network, Comput. Oper. Res., 88 (2017), 103–116. https://doi.org/10.1016/j.cor.2017.06.024 doi: 10.1016/j.cor.2017.06.024
|
| [25] |
H. B. Ticha, N. Absi, D. Feillet, A. Quilliot, Vehicle routing problems with road-network information: State of the art, Networks, 72 (2018), 393–406. https://doi.org/10.1002/net.21808 doi: 10.1002/net.21808
|
| [26] |
H. B. Ticha, N. Absi, D. Feillet, A. Quilliot, T. V. Woensel, A branch-and-price algorithm for the vehicle routing problem with time windows on a road network, Networks, 73 (2019), 401–417. https://doi.org/10.1002/net.21852 doi: 10.1002/net.21852
|
| [27] |
C. Archetti, M. G. Speranza, A survey on matheuristics for routing problems, EURO J. Comput. Optim., 2 (2014), 223–246. https://doi.org/10.1007/s13675-014-0030-7 doi: 10.1007/s13675-014-0030-7
|
| [28] |
D. Pecin, C. Contardo, G. Desaulniers, E. Uchoa, New enhancements for the exact solution of the vehicle routing problem with time windows, INFORMS J. Comput., 29 (2017), 489–502. https://doi.org/10.1287/ijoc.2016.0744 doi: 10.1287/ijoc.2016.0744
|
| [29] | G. Desaulniers, J. Desrosiers, M. M. Solomon, Column Generation, Springer Science & Business Media, 2006. |
| [30] |
M. E. Lübbecke, J. Desrosiers, Selected topics in column generation, Oper. Res., 53 (2005), 1007–1023. https://doi.org/10.1287/opre.1050.0234 doi: 10.1287/opre.1050.0234
|
| [31] | M. Desrochers, La fabrication d'horaires de travail pour les conducteurs d'autobus par une méthode de génération de colonnes, Université de Montréal, Centre de recherche sur les transports, 1986. |
| [32] |
M. Desrochers, F. Soumis, A reoptimization algorithm for the shortest path problem with time windows, Eur. J. Oper. Res., 35 (1988), 242–254. https://doi.org/10.1016/0377-2217(88)90034-3 doi: 10.1016/0377-2217(88)90034-3
|
| [33] |
G. Desaulniers, D. Villeneuve, The shortest path problem with time windows and linear waiting costs, Transp. Sci., 34 (2000), 312–319. https://doi.org/10.1287/trsc.34.3.312.12298 doi: 10.1287/trsc.34.3.312.12298
|
| [34] |
D. Feillet, P. Dejax, M. Gendreau, C. Gueguen, An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems, Networks: Int. J., 44 (2004), 216–229. https://doi.org/10.1002/net.20033 doi: 10.1002/net.20033
|
| [35] |
G. Righini, M. Salani, Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, Discrete Optim., 3 (2006), 255–273. https://doi.org/10.1016/j.disopt.2006.05.007 doi: 10.1016/j.disopt.2006.05.007
|
| [36] |
A. Chabrier, Vehicle routing problem with elementary shortest path based column generation, Comput. Oper. Res., 33 (2006), 2972–2990. https://doi.org/10.1016/j.cor.2005.02.029 doi: 10.1016/j.cor.2005.02.029
|
| [37] |
D. Feillet, M. Gendreau, L. M. Rousseau, New refinements for the solution of vehicle routing problems with branch and price, INFOR: Inf. Syst. Oper. Res., 45 (2007), 239–256. https://doi.org/10.3138/infor.45.4.239 doi: 10.3138/infor.45.4.239
|
| [38] |
M. Tagmouti, M. Gendreau, J. Y. Potvin, Arc routing problems with time-dependent service costs, Eur. J. Oper. Res., 181 (2007), 30–39. https://doi.org/10.1016/j.ejor.2006.06.028 doi: 10.1016/j.ejor.2006.06.028
|
| [39] |
M. Jepsen, B. Petersen, S. Spoorendonk, D. Pisinger, Subset-row inequalities applied to the vehicle-routing problem with time windows, Oper. Res., 56 (2008), 497–511. https://doi.org/10.1287/opre.1070.0449 doi: 10.1287/opre.1070.0449
|
| [40] |
G. Righini, M. Salani, New dynamic programming algorithms for the resource constrained elementary shortest path problem, Networks: Int. J., 51 (2008), 155–170. https://doi.org/10.1002/net.20212 doi: 10.1002/net.20212
|
| [41] |
G. Desaulniers, F. Lessard, A. Hadjar, Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows, Transp. Sci., 42 (2008), 387–404. https://doi.org/10.1287/trsc.1070.0223 doi: 10.1287/trsc.1070.0223
|
| [42] |
A. Qureshi, E. Taniguchi, T. Yamada, An exact solution approach for vehicle routing and scheduling problems with soft time windows, Transp. Res. Part E Logist. Transp. Rev., 45 (2009), 960–977. https://doi.org/10.1016/j.tre.2009.04.007 doi: 10.1016/j.tre.2009.04.007
|
| [43] |
A. Bettinelli, A. Ceselli, G. Righini, A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows, Transp. Res. Part C Emerging Technol., 19 (2011), 723–740. https://doi.org/10.1016/j.trc.2010.07.008 doi: 10.1016/j.trc.2010.07.008
|
| [44] |
F. Liberatore, G. Righini, M. Salani, A column generation algorithm for the vehicle routing problem with soft time windows, 4OR, 9 (2011), 49–82. https://doi.org/10.1007/s10288-010-0136-6 doi: 10.1007/s10288-010-0136-6
|
| [45] |
D. Duque, L. Lozano, A. L. Medaglia, Solving the orienteering problem with time windows via the pulse framework, Comput. Oper. Res., 54 (2015), 168–176. https://doi.org/10.1016/j.cor.2014.08.019 doi: 10.1016/j.cor.2014.08.019
|
| [46] |
L. Lozano, D. Duque, A. L. Medaglia, An exact algorithm for the elementary shortest path problem with resource constraints, Transp. Sci., 50 (2016), 348–357. https://doi.org/10.1287/trsc.2014.0582 doi: 10.1287/trsc.2014.0582
|
| [47] |
G. Lera-Romero, J. J. Miranda-Bront, Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints, Electron. Notes Discrete Math., 69 (2018), 53–60. https://doi.org/10.1016/j.endm.2018.07.008 doi: 10.1016/j.endm.2018.07.008
|
| [48] |
K. Dalmeijer, G. Desaulniers, Addressing orientation symmetry in the time window assignment vehicle routing problem, INFORMS J. Comput., 33 (2021), 495–510. https://doi.org/10.1287/ijoc.2020.0974 doi: 10.1287/ijoc.2020.0974
|
| [49] |
D. Taş, Electric vehicle routing with flexible time windows: a column generation solution approach, Transp. Lett., 13 (2021), 97–103. https://doi.org/10.1080/19427867.2020.1711581 doi: 10.1080/19427867.2020.1711581
|
| [50] | M. Gendreau, J. Y. Potvin, O. Bräumlaysy, G. Hasle, A. Løkketangen, {Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography}, in The Vehicle Routing Problem: Latest Advances and New Challenges, Springer US, Boston, MA, (2008), 143–169. https://doi.org/10.1007/978-0-387-77778-8_7 |
| [51] |
J. Pasha, A. L. Nwodu, A. M. Fathollahi-Fard, G. Tian, Z. Li, H. Wang, et al., Exact and metaheuristic algorithms for the vehicle routing problem with a factory-in-a-box in multi-objective settings, Adv. Eng. Inf., 52 (2022), 101623. https://doi.org/10.1016/j.aei.2022.101623 doi: 10.1016/j.aei.2022.101623
|
| [52] |
H. Park, D. Son, B. Koo, B. Jeong, Waiting strategy for the vehicle routing problem with simultaneous pickup and delivery using genetic algorithm, Expert Syst. Appl., 165 (2021), 113959. https://doi.org/10.1016/j.eswa.2020.113959 doi: 10.1016/j.eswa.2020.113959
|
| [53] |
H. Fan, Y. Zhang, P. Tian, Y. Lv, H. Fan, Time-dependent multi-depot green vehicle routing problem with time windows considering temporal-spatial distance, Comput. Oper. Res., 129 (2021), 105211. https://doi.org/10.1016/j.cor.2021.105211 doi: 10.1016/j.cor.2021.105211
|
| [54] |
G. Srivastava, A. Singh, R. Mallipeddi, Nsga-ii with objective-specific variation operators for multiobjective vehicle routing problem with time windows, Expert Syst. Appl., 176 (2021), 114779. https://doi.org/10.1016/j.eswa.2021.114779 doi: 10.1016/j.eswa.2021.114779
|
| [55] |
W. C. Yeh, S. Y. Tan, Simplified swarm optimization for the heterogeneous fleet vehicle routing problem with time-varying continuous speed function, Electronics, 10 (2021). https://doi.org/10.3390/electronics10151775 doi: 10.3390/electronics10151775
|
| [56] |
M. A. Nguyen, G. T. Dang, M. H. Hà, M. T. Pham, The min-cost parallel drone scheduling vehicle routing problem, Eur. J. Oper. Res., 299 (2022), 910–930. https://doi.org/10.1016/j.ejor.2021.07.008 doi: 10.1016/j.ejor.2021.07.008
|
| [57] |
P. Sun, L. P. Veelenturf, S. Dabia, T. V. Woensel, The time-dependent capacitated profitable tour problem with time windows and precedence constraints, Eur. J. Oper. Res., 264 (2018), 1058–1073. https://doi.org/10.1016/j.ejor.2017.07.004 doi: 10.1016/j.ejor.2017.07.004
|
| [58] |
P. Sun, L. P. Veelenturf, M. Hewitt, T. V. Woensel, The time-dependent pickup and delivery problem with time windows, Transp. Res. Part B Methodol., 116 (2018), 1–24. https://doi.org/10.1016/j.trb.2018.07.002 doi: 10.1016/j.trb.2018.07.002
|
| [59] | M. M. Solomon, Vehicle Routing and Scheduling with Time Window Constraints: Models and Algorithms (Heuristics), PhD thesis, University of Pennsylvania, 1984. |
| [60] |
G. Clarke, J. W. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res., 12 (1964), 568–581. https://doi.org/10.1287/opre.12.4.568 doi: 10.1287/opre.12.4.568
|
Figures(1) / Tables(5)
Abdelkader Lamamri, Mohammed Hachama. Approximate solution of the shortest path problem with resource constraints and applications to vehicle routing problems[J]. Electronic Research Archive, 2023, 31(2): 615-632. doi: 10.3934/era.2023030
DownLoad: