The split delivery vehicle routing problem with three-dimensional loading constraints. (English) Zbl 1430.90062
Summary: The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints (3L-SDVRP) combines vehicle routing and three-dimensional loading with additional packing constraints. In the 3L-SDVRP splitting deliveries of customers is basically possible, i.e., a customer can be visited in two or more tours. We examine essential problem features and introduce two problem variants. In the first variant, called 3L-SDVRP with forced splitting, a delivery is only split if the demand of a customer cannot be transported by a single vehicle. In the second variant, termed 3L-SDVRP with optional splitting, splitting customer deliveries can be done any number of times. We propose a hybrid algorithm consisting of a local search algorithm for routing and a genetic algorithm and several construction heuristics for packing. Numerical experiments are conducted using three sets of instances with both industrial and academic origins. One of them was provided by an automotive logistics company in Shanghai; in this case some customers per instance have a total freight volume larger than the loading space of a vehicle. The results prove that splitting deliveries can be beneficial not only in the one-dimensional case but also when goods are modeled as three-dimensional items.
References:
| [1] | Archetti, C.; Bianchessi, N.; Speranza, M. G., A column generation approach for the split delivery vehicle routing problem, Networks, 58, 241-254 (2011) · Zbl 1231.90074 |
| [2] | Archetti, C.; Bianchessi, N.; Speranza, M. G., Branch-and-cut algorithms for the split delivery vehicle routing problem, European Journal of Operational Research, 238, 3, 685-698 (2014) · Zbl 1338.90042 |
| [3] | Archetti, C.; Savelsbergh, M. W.P.; Speranza, M. G., To split or not to split: That is the question, Transportation Research Part E: Logistics and Transportation Review, 44, 114-123 (2008) |
| [4] | Archetti, C.; Speranza, M. G., Vehicle routing problems with split deliveries, International Transactions in Operational Research, 19, 1-2, 3-22 (2012) · Zbl 1267.90030 |
| [5] | Archetti, C.; Speranza, M. G.; Hertz, A., A tabu search algorithm for the split delivery vehicle routing problem, Transportation science, 40, 1, 64-73 (2006) |
| [6] | Bartók, T.; Imre, C., Pickup and delivery vehicle routing with multidimensional loading constraints, Acta Cybernetica, 20, 17-33 (2011) · Zbl 1240.90037 |
| [7] | Belenguer, J. M.; Martinez, M. C.; Mota, E., A lower bound for the split delivery vehicle routing problem, Operations Research, 48, 801-810 (2000) · Zbl 1106.90380 |
| [8] | Berbotto, L.; García, S.; Nogales, F. J., A randomized granular tabu search heuristic for the split delivery vehicle routing problem, Annals of Operations Research, 222, 1, 153-173 (2014) · Zbl 1303.90008 |
| [9] | Bianchessi, N.; Irnich, S., Branch-and-cut for the split-delivery vehicle routing problem with time-windows, Transportation Science, 53, 2, 442-462 (2019) |
| [10] | Bischoff, E. E.; Ratcliff, M. S.W., Issues in the development of approaches to container loading, Omega, 23, 4, 377-390 (1995) |
| [11] | Bortfeldt, A., A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints, Computers & Operations Research, 39, 9, 2248-2257 (2012) · Zbl 1251.90013 |
| [12] | Bortfeldt, A.; Gehring, H., A hybrid genetic algorithm for the container loading problem, European Journal of Operational Research, 131, 1, 143-161 (2001) · Zbl 0979.90101 |
| [13] | Bortfeldt, A.; Wäscher, G., Constraints in container loading a state-of-the-art review, European Journal of Operational Research, 229, 1, 1-20 (2013) · Zbl 1317.90172 |
| [14] | Bruck, B. P.; Iori, M., Non-Elementary formulations for single vehicle routing problems with pickups and deliveries, Operations Research, 65, 9, 1597-1614 (2017) · Zbl 1382.90006 |
| [15] | Ceschia, S.; Schaerf, A.; Stützle, T., Local search techniques for a routing packing problem, Computers & Industrial Engineering, 66, 89-105 (2013) |
| [16] | Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (Christofides, N.; Mingozzi, A.; Toth, P.; Sandi, C., Combinatorial optimization (1979), John Wiley & Sons Ltd: John Wiley & Sons Ltd Chichester), 315-338 · Zbl 0413.90075 |
| [17] | Côté, J. F.; Guastaroba, G.; Speranza, M. G., The value of integrating loading and routing, European Journal of Operational Research, 2571, 1, 751-759 (2017) · Zbl 1394.90084 |
| [18] | Dror, M.; Laporte, G.; Trudeau, P., Vehicle routing with split deliveries, Discrete Applied Mathematics, 50, 3, 239-254 (1994) · Zbl 0801.90082 |
| [19] | Dror, M.; Trudeau, P., Savings by split delivery routing, Transportation Science, 23, 2, 141-145 (1989) · Zbl 0668.90044 |
| [20] | Dror, M.; Trudeau, P., Split delivery routing, Naval Research Logistics (NRL), 37, 3, 383-402 (1990) · Zbl 0692.90044 |
| [21] | Fuellerer, G.; Doerner, K. F.; Hartl, R. F.; Iori, M., Metaheuristics for vehicle routing problems with three-dimensional loading constraints, European Journal of Operational Research, 201, 3, 751-759 (2010) · Zbl 1173.90511 |
| [22] | Gendreau, M.; Iori, M.; Laporte, G.; Martello, S., A tabu search algorithm for a routing and container loading problem, Transportation Science, 40, 3, 342-350 (2006) |
| [23] | Helsgaun, K., General k-opt submoves for the lin-kernighan tsp heuristic, Mathematical Programming Computation, 1, 2-3 (2009) · Zbl 1180.90269 |
| [24] | Hokama, P.; Miyazawa, F. K.; Xavier, E. C., A branch-and-cut approach for the vehicle routing problem with loading constraints, Expert Systems with Applications, 47, 1-13 (2016) |
| [25] | Iori, M.; Martello, S., Routing problems with loading constraints, Top, 18, 1, 4-27 (2010) · Zbl 1279.90146 |
| [26] | Iori, M.; Martello, S., An annotated bibliography of combined routing and loading problems, Yugoslav Journal of Operations Research, 23, 3, 311-326 (2013) · Zbl 1313.90026 |
| [27] | Irnich, S.; Schneider, M.; Vigo, D., Chapter 9: four variants of the vehicle routing problem, Vehicle Routing: Problems, Methods, and Applications, 241-271 (2014), Society for Industrial and Applied Mathematics |
| [28] | Junqueira, L.; Oliveira, J. F.; Carravilla, M. A.; Morabito, R., An optimization model for the vehicle routing problem with practical three‐dimensional loading constraints, International Transactions in Operational Research, 20, 5, 645-666 (2013) · Zbl 1276.90012 |
| [29] | Koch, H.; Bortfeldt, A.; Wäscher, G., A hybrid algorithm for the vehicle routing problem with backhauls, time windows and three-dimensional loading constraints, OR Spectrum, 40, 1029-1075 (2018) |
| [30] | Li, X.; Yuan, M.; Chen, D.; Yao, J.; Zeng, J., A data-driven three-layer algorithm for split delivery vehicle routing problem with 3D container loading constraint, (Proceedings of the KDD ’18: The 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, United Kingdom. Proceedings of the KDD ’18: The 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, United Kingdom, New York, NY, USA (2018), ACM), 528-536, August 19-23 |
| [31] | Mahvash, B.; Awasthi, A.; Chauhan, S., A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints, International Journal of Production Research, 55, 6, 1730-1747 (2017) |
| [32] | Männel, D.; Bortfeldt, A., A hybrid algorithm for the vehicle routing problem with pickup and delivery and three-dimensional loading constraints, European Journal of Operational Research, 254, 3, 840-858 (2016) · Zbl 1346.90150 |
| [33] | Miao, L.; Ruan, Q.; Woghiren, K.; Ruo, Q., A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints, RAIRO-Operations Research, 46, 1, 63-82 (2012) · Zbl 1241.90015 |
| [34] | Moreno, L.; Poggi de Aragão, M.; Uchoa, E., Improved lower bounds for the split delivery vehicle routing problem, Operations Research Letters, 38, 302-306 (2010) · Zbl 1193.90068 |
| [35] | Moura, A., A model-based heuristic to the vehicle routing and loading problem, International Transactions in Operational Research, 26, 3, 888-907 (2019) · Zbl 07766333 |
| [36] | Moura, A.; Oliveira, J. F., An integrated approach to the vehicle routing and container loading problems, OR Spectrum, 31, 4, 775-800 (2009) · Zbl 1175.90045 |
| [37] | Ozbaygin, G.; Karasan, O.; Yaman, H., New exact solution approaches for the split delivery vehicle routing problem, EURO Journal on Computational Optimization, 6, 1, 85-115 (2018) · Zbl 1393.90015 |
| [38] | Pace, S.; Turky, A.; Moser, I.; Aleti, A., Distributing fibre boards: A practical application of the heterogeneous fleet vehicle routing problem with time windows and three-dimensional loading constraints, Procedia Computer Science, 51, 2257-2266 (2015) |
| [39] | Pollaris, H.; Braekers, K.; Caris, A.; Janssens, G. K.; Limbourg, S., Vehicle routing problems with loading constraints: state-of-the-art and future directions, OR Spectrum, 37, 2, 297-330 (2015) · Zbl 1311.90032 |
| [40] | Pollaris, H.; Braekers, K.; Caris, A.; Janssens, G. K.; Limbourg, S., Iterated local search for the capacitated vehicle routing problem with sequence: Based pallet loading and axle weight constraints, Networks, 69, 3, 304-316 (2017) |
| [41] | Qiu, M.; Fu, Z.; Eglese, R. W.; Tang, Q., A tabu search algorithm for the vehicle routing problem with discrete split deliveries and pickups, Computers & Operations Research, 100, 102-116 (2018) · Zbl 1458.90130 |
| [42] | Rajappa, G. P.; Wilck, J. H.; Bell, J. E., An ant colony optimization and hybrid metaheuristics algorithm to solve the split delivery vehicle routing problem, International Journal of Applied Industrial Engineering, 3, 1, 55-73 (2016) |
| [43] | Reil, S.; Bortfeldt, A.; Mönch, L., Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints, European Journal of Operational Research, 266, 3, 877-894 (2018) · Zbl 1403.90162 |
| [44] | Shi, J.; Zhang, J.; Wang, K.; Fang, X., Particle swarm optimization for split delivery vehicle routing problem, Asia-Pacific Journal of Operational Research, 35, 2, Article 1840006 pp. (2018) · Zbl 1393.90016 |
| [45] | Song, X.; Jones, D.; Asgari, N., Multi-objective vehicle routing and loading with time window constraints: A real-life application, Annals of Operations Research (2019) |
| [46] | Tao, Y.; Wang, F., An effective tabu search approach with improved loading algorithms for the 3L-CVRP, Computers & Operations Research, 55, 127-140 (2015) · Zbl 1348.90135 |
| [47] | Tarantilis, C. D.; Zachariadis, E. E.; Kiranoudis, C. T., A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem, IEEE Transactions on Intelligent Transportation Systems, 10, 2, 255-271 (2009) |
| [48] | Vega-Mejia, C. A.; Montoya-Torres, J. R.; Islam, S. M.N., A nonlinear optimization model for the balanced vehicle routing problem with loading constraints, International Transactions in Operational Research, 26, 3, 794-835 (2019) · Zbl 07766330 |
| [49] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., A unified solution framework for multi-attribute vehicle routing problems, European Journal of Operational Research, 234, 3, 658-673 (2014) · Zbl 1304.90004 |
| [50] | Wei, L.; Zhang, Z.; Lim, A., An adaptive variable neighborhood search for a heterogeneous fleet vehicle routing problem with three-dimensional loading constraints, IEEE Computational Intelligence Magazine, 9, 4, 18-30 (2014) |
| [51] | Wilck, J. H.; Cavalier, T. M., A genetic algorithm for the split delivery vehicle routing problem, American Journal of Operations Research, 2, 207-216 (2012) |
| [52] | Wisniewski, M.; Ritt, M.; Buriol, L. S., A tabu algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints, (Proceedings of the Anais do XLIII Simpósio Brasileiro de Pesquisa Operacional. Proceedings of the Anais do XLIII Simpósio Brasileiro de Pesquisa Operacional, Ubatuba, Brazil (2011)), 1502-1511 |
| [53] | Yi, J.; Bortfeldt, A., The capacitated vehicle routing problem with three-dimensional loading constraints and split delivery- A Case study, (Proceedings of the Operations Research. Proceedings of the Operations Research, Cham (2018), Springer), 351-356 |
| [54] | Zachariadis, E. E.; Tarantilis, C. D.; Kiranoudis, C. T., The pallet-packing vehicle routing problem, Transportation Science, 46, 3, 341-358 (2012) |
| [55] | Zhang, D.; Cai, S.; Ye, F.; Si, Y. W.; Nguyen, T. T., A hybrid algorithm for a vehicle routing problem with realistic constraints, Information Sciences, 394/395, 167-182 (2017) |
| [56] | Zhu, W.; Qin, H.; Lim, A.; Wang, L., A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP, Computers & Operations Research, 39, 9, 2178-2195 (2012) · Zbl 1251.90346 |
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.
