×

zbMATH — the first resource for mathematics

A route decomposition approach for the single commodity split pickup and split delivery vehicle routing problem. (English) Zbl 07354504
Summary: We address a single commodity Pickup and Delivery Vehicle Routing Problem from the literature. A network of customer nodes is given with both travel times and costs. A fleet of vehicles of limited capacity is exploited to satisfy node demands, and a set of routes must be found such that the vehicle capacities are never exceeded, each route does not exceed time resource, and cost is minimized. The demands of both pickup and delivery nodes can be split, and each node can be visited more than once. We provide new theoretical insights. We propose a new formulation where routes are decomposed into sequences of simpler substructures called clusters, mitigating the combinatorial explosion of feasible solutions. We introduce valid inequalities, and design a branch-and-price algorithm, exploiting ad hoc pricing routines and branching strategies, and embedding a rounding heuristic to speed up pruning. An extensive experimental analysis shows our method to offer simultaneously more modelling flexibility and more computational effectiveness than previous attempts from the literature. Our investigation opens also interesting insights into the use of route decomposition strategies.
MSC:
90Bxx Operations research and management science
Software:
CPLEX; SCIP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T., Scip: solving constraint integer programs, Mathematical Programming Computation, 1, 1, 1-41 (2009) · Zbl 1171.90476
[2] Alvarez-Valdes, R.; Belenguer, J.; Benavent, E.; Bermudez, J.; MuȘoz, F.; Vercher, E.; Verdejo, F., Optimizing the level of service quality of a bike-sharing system, Omega, 62, 163-175 (2016)
[3] Baldacci, R.; Bartolini, E.; Mingozzi, A., An exact algorithm for the pickup and delivery problem with time windows, Operations Research, 59, 2, 414-426 (2011) · Zbl 1233.90058
[4] Battarra, M.; Cordeau, J.-F.; Iori, M., Chapter 6: Pickup-and-delivery problems for goods transportation, (Toth, P.; Vigo, D. (2014)), 161-191)
[5] Bulhões, T.; Subramanian, A.; Erdoğan, G.; Laporte, G., The static bike relocation problem with multiple vehicles and visits, European Journal of Operational Research, 264, 2, 508-523 (2018) · Zbl 1375.90034
[6] Casazza, M.; Ceselli, A., Mathematical programming algorithms for bin packing problems with item fragmentation, Computers & Operations Research, 46, 1-11 (2014) · Zbl 1348.90536
[7] Casazza, M.; Ceselli, A.; Chemla, D.; Meunier, F.; Wolfler Calvo, R., The multiple vehicle balancing problem, Networks, 72, 3, 337-357 (2018)
[8] Casazza, M., Ceselli, A., Chemla, D., Meunier, F., & Wolfler Calvo, R. (2018b). Multiple vehicle balancing problem instances. http://casazza.di.unimi.it/files/papers/spsdvrp.tar.gz.
[9] Joint EURO/ALIO International Conference 2018 on Applied Combinatorial Optimization (EURO/ALIO 2018)
[10] Chemla, D.; Meunier, F.; Wolfler Calvo, R., Bike sharing systems: Solving the static rebalancing problem, Discrete Optimization, 10, 2, 120-146 (2013) · Zbl 1284.90040
[11] CPLEX development team, IBM Ilog CPLEX Optimization Studio: CPLEX User’s Manual - Version 12 Release 6, Technical Report (2011), IBM corp.
[12] Desaulniers, G., Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows, Operations Research, 58, 1, 179-192 (2010) · Zbl 1233.90065
[13] Di Gaspero, L.; Rendl, A.; Urli, T., A Hybrid ACO+CP for Balancing Bicycle Sharing Systems, (Blesa, M.; Blum, C.; Festa, P.; Roli, A.; Sampels, M., Hybrid metaheuristics (2013), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 198-212
[14] Dror, M.; Trudeau, P., Split delivery routing, Naval Research Logistics, 37, 383-402 (1990) · Zbl 0692.90044
[15] Espegren, H.; Kristianslund, J.; Andersson, H.; Fagerholt, K., The Static Bicycle Repositioning Problem - Literature Survey and New Formulation, (Paias, A.; Ruthmair, M.; Voß, S., Computational logistics (2016), Springer International Publishing: Springer International Publishing Cham), 337-351
[16] Forma, I.; Raviv, T.; Tzur, M., A 3-step math heuristic for the static repositioning problem in bike-sharing systems, Transportation Research, Part B, 71, 230-247 (2015)
[17] 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, 2, 521-530 (2018) · Zbl 1403.90114
[18] Laporte, G.; Meunier, F.; Wolfler Calvo, R., Shared mobility systems, 4OR, 13, 341-360 (2015) · Zbl 1332.90001
[19] Pessoa, A.; Sadykov, R.; Uchoa, E.; Vanderbeck, F., A generic exact solver for vehicle routing and related problems, (Lodi, A.; Nagarajan, V., Integer programming and combinatorial optimization (2019), Springer International Publishing: Springer International Publishing Cham), 354-369 · Zbl 1436.90087
[20] Rainer-Harbach, M.; Papazek, P.; Hu, B.; Raidl, G., Balancing Bicycle Sharing Systems: A Variable Neighborhood Search Approach, (Middendorf, M.; Blum, C., Evolutionary computation in combinatorial optimization (2013), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 121-132
[21] Rainer-Harbach, M.; Papazek, P.; Raidl, G.; Hu, B.; Kloimüllner, C., PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems, Journal of Global Optimization, 63, 3, 597-629 (2015) · Zbl 1327.90019
[22] Raviv, T.; Tzur, M.; Forma, I., Static repositioning in a bike-sharing system: models and solution approaches, EURO Journal on Transportation and Logistics, 2, 187-229 (2013)
[23] 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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.