×

Exact solution of the soft-clustered vehicle-routing problem. (English) Zbl 1430.90090

Summary: The soft-clustered vehicle-routing problem (SoftCluVRP) extends the classical capacitated vehicle-routing problem by one additional constraint: the customers are partitioned into clusters and feasible routes must respect the soft-cluster constraint, that is, all customers of the same cluster must be served by the same vehicle. In this article, we design and analyze different branch-and-price algorithms for the exact solution of the SoftCluVRP. The algorithms differ in the way the column-generation subproblem, a variant of the shortest-path problem with resource constraints (SPPRC), is solved. The standard approach for SPPRCs is based on dynamic-programming labeling algorithms. We show that even with all the recent acceleration techniques (e.g., partial pricing, bidirectional labeling, decremental state space relaxation) available for SPPRC labeling algorithms, the solution of the subproblem remains extremely difficult. The main contribution is the modeling and solution of the subproblem using a branch-and-cut algorithm. The conducted computational experiments prove that branch-and-price equipped with this integer programming-based approach outperforms sophisticated labeling-based algorithms by one order of magnitude. The largest SoftCluVRP instances solved to optimality have more than 400 customers or more than 50 clusters.

MSC:

90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90C10 Integer programming
90C39 Dynamic programming
90C35 Programming involving graphs or networks

Software:

MAXFLOW; VRP
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Balas, E., The prize collecting traveling salesman problem, Networks, 19, 6, 621-636 (1989) · Zbl 0676.90089
[2] Baldacci, R.; Mingozzi, A.; Roberti, R., New route relaxation and pricing strategies for the vehicle routing problem, Operations Research, 59, 5, 1269-1283 (2011) · Zbl 1233.90059
[3] Barthélemy, T.; Rossi, A.; Sevaux, M.; Sörensen, K., Metaheuristic approach for the clustered VRP, Proceedings of the 10th anniversary of the metaheuristic community, EU/ME,Lorient, France, 3-4 (2010)
[4] Battarra, M.; Erdoǧan, G.; Vigo, D., Exact algorithms for the clustered vehicle routing problem, Operations Research, 62, 1, 58-71 (2014) · Zbl 1291.90030
[5] Bektaş, T.; Erdoǧan, G.; Ropke, S., Formulations and branch-and-cut algorithms for the generalized vehicle routing problem, Transportation Science, 45, 3, 299-316 (2011)
[6] Belenguer, J. M.; Benavent, E.; Irnich, S., The capacitated arc routing problem: Exact algorithms, Arc routing, chapter 9,, 183-221 (2014), Society for Industrial & Applied Mathematics (SIAM) · Zbl 1387.90256
[7] Bentley, J. J., Fast algorithms for geometric traveling salesman problems, ORSA Journal on Computing, 4, 4, 387-411 (1992) · Zbl 0758.90071
[8] Bode, C.; Irnich, S., Cut-first branch-and-price-second for the capacitated arc-routing problem, Operations Research, 60, 5, 1167-1182 (2012) · Zbl 1257.90008
[9] Boykov, Y.; Kolmogorov, V., An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, 26, 1124-1137 (2004)
[10] Butsch, A.; Kalcsics, J.; Laporte, G., Districting for arc routing, INFORMS Journal on Computing, 26, 4, 809-824 (2014) · Zbl 1304.90218
[11] Cherkesly, M.; Desaulniers, G.; Laporte, G., Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and last-in-first-out loading, Transportation Science, 49, 4, 752-766 (2015)
[12] Defryn, C.; Sörensen, K., A fast two-level variable neighborhood search for the clustered vehicle routing problem, Computers & Operations Research, 83, 78-94 (2017) · Zbl 1458.90609
[13] Desaulniers, G.; Desrosiers, J.; Ioachim, I.; Solomon, M. M.; Soumis, F.; Villeneuve, D., A unified framework for deterministic time constrained vehicle routing and crew scheduling problems, (Crainic, T. G.; Laporte, G., Fleet management and logistics, chapter 3, (1998), Kluwer Academic Publisher: Kluwer Academic Publisher Boston, Dordrecht, London), 57-93 · Zbl 0966.90007
[14] Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column Generation (2005), Springer: Springer New York, NY · Zbl 1084.90002
[15] Desaulniers, G.; Pecin, D.; Contardo, C., Selective pricing in branch-price-and-cut algorithms for vehicle routing, EURO Journal on Transportation and Logistics, 8, 2, 147-168 (2017)
[16] Drexl, M.; Irnich, S., Solving elementary shortest-path problems as mixed-integer programs, OR Spectrum, 36, 2, 281-296 (2012) · Zbl 1290.90082
[17] Dror, M., Note on the complexity of the shortest path models for column generation in VRPTW, Operations Reasearch, 42, 5, 977-978 (1994) · Zbl 0815.90064
[18] Dumas, Y.; Desrosiers, J.; Soumis, F., The pick-up and delivery problem with time windows, European Journal of Operational Research, 54, 7-22 (1991) · Zbl 0736.90028
[19] Expósito-Izquierdo, C.; Rossi, A.; Sevaux, M., A two-level solution approach to solve the clustered capacitated vehicle routing problem, Computers & Industrial Engineering, 91, 274-289 (2016)
[20] Feillet, D.; Dejax, P.; Gendreau, M., Traveling salesman problems with profits, Transportation Science, 39, 2, 188-205 (2005)
[21] Feillet, D.; Dejax, P.; Gendreau, M.; Guéguen, C., An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems, Networks, 44, 3, 216-229 (2004) · Zbl 1056.90014
[22] Fischetti, M.; González, J. J.S.; Toth, P., A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Operations Research, 45, 3, 378-394 (1997) · Zbl 0893.90164
[23] Goeke, D.; Gschwind, T.; Schneider, M., Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier, Discrete Applied Mathematics, 264, 43-61 (2019) · Zbl 1418.90032
[24] Golden, B. L.; Wasil, E. A.; Kelly, J. P.; Chao, I.-M., The impact of metaheuristics on solving the vehicle routing problem: Algorithms, problem sets, and computational results, (Crainic, T. G.; Laporte, G., Fleet management and logistics (1998), Springer: Springer US, Boston, MA), 33-56 · Zbl 0997.90021
[25] Gschwind, T.; Irnich, S.; Rothenbächer, A.-K.; Tilk, C., Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems, European Journal of Operational Research, 266, 521-530 (2017) · Zbl 1403.90114
[26] Gutin, G.; Punnen, A. P., The traveling salesman problem and its variations, Combinatorial optimization, 12 (2007), Springer: Springer New York · Zbl 1113.90134
[27] Hintsch, T.; Irnich, S., Large multiple neighborhood search for the clustered vehicle-routing problem, European Journal of Operational Research, 270, 1, 118-131 (2018) · Zbl 1403.90123
[28] Hoos, H. H.; Stü tzle, T., Stochastic local search: Foundations & applications (2004), Morgan Kaufmann
[29] Irnich, S.; Desaulniers, G., Shortest path problems with resource constraints, (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column generation, chapter 2, (2005), Springer), 33-65 · Zbl 1130.90315
[30] Irnich, S.; Funke, B.; Grünert, T., Sequential search and its application to vehicle-routing problems, Computers & Operations Research, 33, 8, 2405-2429 (2006) · Zbl 1086.90064
[31] Irnich, S.; Toth, P.; Vigo, D., The family of vehicle routing problems, (Vigo, D.; Toth, P., Vehicle routing, chapter 1, (2014), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA), 1-33 · Zbl 1305.90012
[32] Irnich, S.; Villeneuve, D., The shortest path problem with resource constraints and \(k\)-cycle elimination for \(k\) ≥ 3, INFORMS Journal on Computing, 18, 3, 391-406 (2006) · Zbl 1241.90161
[33] Izquierdo, C. E.; Rossi, A.; Sevaux, M., Modeling and solving the clustered capacitated vehicle routing problem, (Fink, A.; Geiger, M. J., Proceedings of the 14th EU/ME workshop, EU/ME, Hamburg, Germany, February, (2013)), 110-115
[34] Jepsen, M. K.; Petersen, B.; Spoorendonk, S., A branch-and-cut algorithm for the elementary shortest path problem with a capacity constraint (2008), Department of computer science: Department of computer science Kopenhagen, Denmark
[35] Lübbecke, M. E.; Desrosiers, J., Selected topics in column generation, Operations Research, 53, 6, 1007-1023 (2005) · Zbl 1165.90578
[36] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers & Operations Research, 24, 11, 1097-1100 (1997) · Zbl 0889.90119
[37] Pop, P. C.; Fuksz, L.; Marc, A. H.; Sabo, C., A novel two-level optimization approach for clustered vehicle routing problem, Computers & Industrial Engineering, 115, 304-318 (2018)
[38] Righini, G.; Salani, M., Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, Discrete Optimization, 3, 3, 255-273 (2006) · Zbl 1149.90167
[39] Righini, G.; Salani, M., New dynamic programming algorithms for the resource constrained elementary shortest path problem, Networks, 51, 3, 155-170 (2008) · Zbl 1144.90514
[40] Ropke, S.; Cordeau, J.-F., Branch and cut and price for the pickup and delivery problem with time windows, Transportation Science, 43, 3, 267-286 (2009)
[41] Ryan, D. M.; Foster, B. A., An integer programming approach to scheduling, (Wren, A., Computer scheduling of public transport: Urban passenger vehicle and crew scheduling, chapter 17, (1981), Elsevier: Elsevier North-Holland), 269-280
[42] Sevaux, M.; Sörensen, K., Hamiltonian paths in large clustered routing problems, Proceedings of the EU/MEeting workshop on metaheuristics for logistics and vehicle routing, EU/ME,Troyes, France, 4:1-4:7 (2008)
[43] Tarjan, R. E., A class of algorithms which require nonlinear time to maintain disjoint sets, Journal of Computer and System Sciences, 18, 2, 110-127 (1979) · Zbl 0413.68039
[44] Tilk, C.; Rothenbächer, A.-K.; Gschwind, T.; Irnich, S., Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster, European Journal of Operational Research, 261, 2, 530-539 (2017) · Zbl 1403.90212
[45] Vidal, T.; Battarra, M.; Subramanian, A.; Erdoǧan, G., Hybrid metaheuristics for the clustered vehicle routing problem, Computers & Operations Research, 58, 87-99 (2015) · Zbl 1348.90138
[46] Vigo, D.; Toth, P., Vehicle routing, MOS-SIAM series on optimization (2014), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 1305.90012
[47] Wolsey, L. A., Integer programming (1998), Wiley-Interscience: Wiley-Interscience New York, NY · Zbl 0930.90072
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.