×

A branch-and-cut-and-price algorithm for the multi-trip separate pickup and delivery problem with time windows at customers and facilities. (English) Zbl 1430.90058

Summary: We study the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities (MT-PDTWCF), arising in two-tiered city logistics systems. The first tier refers to the transportation between the city distribution centers, in the outskirts of the city, and intermediate facilities, while the second tier refers to the transportation of goods between the intermediate facilities and the (pickup and delivery) customers. We focus on the second tier, and consider that customers and facilities have time windows in which they can be visited. Waiting is possible at waiting stations for free or at customers and facilities at a given cost or penalty. Therefore, it is relevant to coordinate the arrivals of vehicles at facilities and customers with the corresponding time windows. The MT-PDTWCF calls for determining minimum (fixed, routing and waiting) cost multi-trip routes, for a given fleet of vehicles, to service separately pickup and delivery customers, while taking into account vehicle capacity and time windows both at customers and facilities. We propose the first exact algorithm for MT-PDTWCF, namely a Branch-and-Cut-and-Price algorithm. It is based on column generation, where the pricing problem is solved by a bi-directional dynamic programming algorithm designed to cope with the features of the problem. Subset-row and rounded capacity inequalities are adapted to deal with MT-PDTWCF and inserted in the branch-and-cut-and-price algorithm. The performance of the proposed algorithm is tested on benchmark instances with up to 200 customers, showing its effectiveness.

MSC:

90B06 Transportation, logistics and supply chain management
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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
[2] Bettinelli, A.; Ceselli, A.; Righini, G., A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows, Mathematical Programming Computation, 6, 2, 171-197 (2014) · Zbl 1327.90251
[3] Bulhoes, T.; Sadykov, R.; Subramanian, A.; Uchoa, E., On the exact solution of a large class of parallel machine scheduling problems, Technical Report (2018), Universidade Federal Fluminense
[4] Cattaruzza, D.; Absi, N.; Feillet, D., The multi-trip vehicle routing problem with time windows and release dates, Transportation Science, 50, 2, 676-693 (2016)
[5] Cattaruzza, D.; Absi, N.; Feillet, D.; González-Feliu, J., Vehicle routing problems for city logistics, EURO Journal on Transportation and Logistics, 6, 1, 51-79 (2017)
[6] Cleophas, C.; Cottrill, C.; Ehmke, J. F.; Tierney, K., Collaborative urban transportation: Recent advances in theory and practice, European Journal of Operational Research, 273, 3, 801-816 (2019) · Zbl 1403.90095
[7] Cortés, C. E.; Matamala, M.; Contardo, C., The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method, European Journal of Operational Research, 200, 3, 711-724 (2010) · Zbl 1177.90412
[8] Crainic, T. G., City logistics, State-of-the-art decision-making tools in the information-intensive age, 181-212 (2008), INFORMS
[9] Crainic, T. G.; Errico, F.; Rei, W.; Ricciardi, N., Integrating c2e and c2c traffic into city logistics planning, Procedia-social and Behavioral Sciences, 39, 47-60 (2012)
[10] Crainic, T. G.; Errico, F.; Rei, W.; Ricciardi, N., Modeling demand uncertainty in two-tier city logistics tactical planning, Transportation Science, 50, 2, 559-578 (2015)
[11] Crainic, T. G.; Gajpal, Y.; Gendreau, M., Multi-zone multi-trip vehicle routing problem with time windows, INFOR: Information Systems and Operational Research, 53, 2, 49-67 (2015) · Zbl 07683463
[12] Crainic, T. G.; Nguyen, P. K.; Toulouse, M., Synchronized multi-trip multi-traffic pickup & delivery in city logistics, Transportation Research Procedia, 12, 26-39 (2016)
[13] Crainic, T. G.; Ricciardi, N.; Storchi, G., Models for evaluating and planning city logistics systems, Transportation science, 43, 4, 432-454 (2009)
[14] Crainic, T. G.; Sgalambro, A., Service network design models for two-tier city logistics, Optimization Letters, 8, 4, 1375-1387 (2014) · Zbl 1292.90043
[15] Dabia, S.; Ropke, S.; Van Woensel, T.; De Kok, T., Branch and price for the time-dependent vehicle routing problem with time windows, Transportation Science, 47, 3, 380-396 (2013)
[16] Dror, M., Note on the complexity of the shortest path models for column generation in vrptw, Operations Research, 42, 5, 977-978 (1994) · Zbl 0815.90064
[17] Fontaine, P.; Crainic, T. G.; Jabali, O.; Rei, W., The impact of combining inbound and outbound demand in city logistics systems, 41st ieee annual computer software and applications conference (compsac), 2, 766-770 (2016), IEEE
[18] Fontaine, P.; Crainic, T. G.; Jabali, O.; Rei, W., Scheduled service network design with resource management for two-tier multimodal city logistics, Publication Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport (2019), Université de Montréal: Université de Montréal Montréal, QC, Canada
[19] Ghilas, V.; Cordeau, J.-F.; Demir, E.; Woensel, T. V., Branch-and-price for the pickup and delivery problem with time windows and scheduled lines, Transportation Science, 52, 5, 1191-1210 (2018)
[20] Ghilas, V.; Demir, E.; Van Woensel, T., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows and scheduled lines, Computers & Operations Research, 72, 12-30 (2016) · Zbl 1349.90086
[21] Golden, B.; Baker, E.; Alfaro, J.; Schaffer, J., The vehicle routing problem with backhauling: Two approaches, Proceedings of the twenty-first annual meeting of the SE TIMS (1985)
[22] Grangier, P.; Gendreau, M.; Lehuédé, F.; Rousseau, L.-M., An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization, European Journal of Operational Research, 254, 1, 80-91 (2016) · Zbl 1346.90116
[23] Grangier, P.; Gendreau, M.; Lehuédé, F.; Rousseau, L.-M., A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking, Computers & Operations Research, 84, 116-126 (2017) · Zbl 1391.90061
[24] Guastaroba, G.; Speranza, M. G.; Vigo, D., Intermediate facilities in freight transportation planning: a survey, Transportation Science, 50, 3, 763-789 (2016)
[25] Hernandez, F.; Feillet, D.; Giroudeau, R.; Naud, O., Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows, European Journal of Operational Research, 249, 2, 551-559 (2016) · Zbl 1346.90123
[26] Irnich, S.; Schneider, M.; Vigo, D., Chapter 9: Four variants of the vehicle routing problem, Vehicle routing: Problems, methods, and applications, second edition, 241-271 (2014), SIAM, Philadephia
[27] Jepsen, M.; Petersen, B.; Spoorendonk, S.; Pisinger, D., Subset-row inequalities applied to the vehicle routing problem with time windows, Operations Research, 56, 497-511 (2008) · Zbl 1167.90413
[28] Lahyani, R.; Khemakhem, M.; Semet, F., Rich vehicle routing problems: From a taxonomy to a definition, European Journal of Operational Research, 241, 1, 1-14 (2015) · Zbl 1338.90007
[29] Liberatore, F.; Righini, G.; Salani, M., A column generation algorithm for the vehicle routing problem with soft time windows, 4OR, 9, 1, 49-82 (2011) · Zbl 1225.90110
[30] Maknoon, Y.; Laporte, G., Vehicle routing with cross-dock selection, Computers & Operations Research, 77, 254-266 (2017) · Zbl 1391.90073
[31] Masson, R.; Lehuédé, F.; Péton, O., An adaptive large neighborhood search for the pickup and delivery problem with transfers, Transportation Science, 47, 3, 344-355 (2013)
[32] Masson, R.; Trentini, A.; Lehuédé, F.; Malhéné, N.; Péton, O.; Tlahig, H., Optimization of a city logistics transportation system with mixed passengers and goods, EURO Journal on Transportation and Logistics, 6, 1, 81-109 (2017)
[33] Naddef, D.; Rinaldi, G., Branch-and-cut algorithms for the capacitated vrp, The vehicle routing problem, 53-84 (2002), SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia · Zbl 1076.90550
[34] Nguyen, P. K.; Crainic, T. G.; Toulouse, M., A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows, European Journal of Operational Research, 231, 1, 43-56 (2013) · Zbl 1317.90332
[35] Nguyen, P. K.; Crainic, T. G.; Toulouse, M., Multi-trip pickup and delivery problem with time windows and synchronization, Annals of Operations Research, 253, 2, 899-934 (2017) · Zbl 1380.90085
[36] 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
[37] 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
[38] Taş, D.; Gendreau, M.; Dellaert, N.; Van Woensel, T.; De Kok, A., Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach, European Journal of Operational Research, 236, 3, 789-799 (2014) · Zbl 1304.90044
[39] Toth, P.; Vigo, D., Vehicle routing: Problems, methods, and applications (2014), SIAM: SIAM Philadelphia, PA · Zbl 1305.90012
[40] Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., Heuristics for multi-attribute vehicle routing problems: A survey and synthesis, European Journal of Operational Research, 231, 1, 1-21 (2013) · Zbl 1317.90006
[41] Visser, T.; Spliet, R., Efficient move evaluations for time-dependent vehicle routing problems, Technical Report (2017), Erasmus University Rotterdam, The Netherlands
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.