Product-oriented split delivery in the multi-compartment vehicle routing problem

Subject Areas : Routing and transportation planning

Mahnaz Shoeib ¹ , jafar Bagherinejad ² , Mahdi Bashiri ³

1 -
2 -
3 -

Received: 2024-11-10 Accepted : 2025-02-11

Keywords: Vehicle routing problem, Multi-compartment vehicles, Split delivery, Matheuristic, Adaptive large neighborhood search ,

Abstract :

This paper addresses split delivery in the multi-compartment vehicle routing problem in which the possibility of splitting delivery depends on the product type. For certain product types, split delivery is not allowed but for other ones is permitted under a certain condition. The arrival time consistency is considered as split delivery condition. If the time difference between vehicle arrivals to the customer does not exceed a certain limit, the consistency of arrival time is established and split delivery is allowed. A mathematical model is developed to describe the proposed problem and used to solve small sized instances. To solve large sized instances, an adaptive large neighborhood search and a matheuristic based on fixing a part of customer to route assignment variables are developed. Computational experiments are performed on the multi-compartment vehicle routing problem with and without product-oriented split delivery. The effect of capacity and compartments per vehicle on delivery mode is investigated. The results demonstrate that the matheuristic outperforms the adaptive large neighborhood search in term of quality and computational time. Furthermore, delivery mode does not have a significant effect on the proposed algorithms’ computational time and the number of vehicles is more affected by delivery mode than distance travelled. 

References:

Alinaghian, M., & Shokouhi, N. (2018). Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search. Omega, 76, 85–99.
Archetti, C., Savelsbergh, M. W. P., & Speranza, M. G. (2008). To split or not to split: That is the question. Transportation Research Part E: Logistics and Transportation Review, 44(1), 114–123.
Archetti, C., & Speranza, M. G. (2012). Vehicle routing problems with split deliveries. International Transactions in Operational Research, 19(1–2), 3–22.
Asawarungsaengkul, K., Rattanamanee, T., & Wuttipornpun, T. (2013). A Multi-Size Compartment Vehicle Routing Problem for Multi-Product Distribution: Models and Solution Procedures. International Journal of Artificial Intelligence, 11(A13), 237–256.
Bortfeldt, A., & Yi, J. (2020). The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints. European Journal of Operational Research, 282(2), 545–558.
Cattaruzza, D., Absi, N., Feillet, D., & González-Feliu, J.-J. (2017). Vehicle routing problems for city logistics. EURO Journal on Transportation and Logistics, 6(1), 51–79.
Chen, J., & Shi, J. (2019). A multi-compartment vehicle routing problem with time windows for urban distribution – A comparison study on particle swarm optimization algorithms. Computers & Industrial Engineering, 133, 95–106.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80–91.
Doan, T. T., Bostel, N., & Hà, M. H. (2021). The vehicle routing problem with relaxed priority rules. EURO Journal on Transportation and Logistics, 10, 100039.
Dror, M., & Trudeau, P. (1989). Savings by Split Delivery Routing. Transportation Science, 23(2), 141–145.
Dror, M., & Trudeau, P. (1990). Split Delivery Routing. Naval Research Logistics, 37(3), 383–402.
Dumez, D., Tilk, C., Irnich, S., Lehuédé, F., Olkis, K., & Péton, O. (2023). A Matheuristic for a 2-Echelon Vehicle Routing Problem with Capacitated Satellites and Reverse Flows. European Journal of Operational Research, 305(1), 64–84.
Elatar, S., Abouelmehdi, K., & Essaid, M. (2023). The vehicle routing problem in the last decade: variants , taxonomy The vehicle routing problem in the last decade: variants , taxonomy and metaheuristics. Procedia Computer Science, 220, 398–404.
Friedrich, C., & Elbert, R. (2022). Adaptive large neighborhood search for vehicle routing problems with transshipment facilities arising in city logistics. Computers and Operations Research, 137, 105491.
Goli, A., Aazami, A., & Jabbarzadeh, A. (2018). Accelerated cuckoo optimization algorithm for capacitated vehicle routing problem in competitive conditions. International Journal of Artificial Intelligence, 16(1), 88-112.
Gu, W., Archetti, C., Cattaruzza, D., Ogier, M., Semet, F., & Speranza, M. G. (2024). Vehicle routing problems with multiple commodities: A survey. European Journal of Operational Research, 317(1), 1–15.
Gulczynski, D., Golden, B., & Wasil, E. (2010). The split delivery vehicle routing problem with minimum delivery amounts. Transportation Research Part E: Logistics and Transportation Review, 46(5), 612–626.
Guo, F., Huang, Z., & Huang, W. (2021). Heuristic approaches for a vehicle routing problem with an incompatible loading constraint and splitting deliveries by order. Computers and Operations Research, 134, 105379.
Han, A. F., & Chu, Y. (2016). A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts. Transportation Research Part E: Logistics and Transportation Review, 88, 11–31.
Henke, T. (2018). Multi-compartment vehicle routing problems in the context of glass waste collection. Ph.D. thesis. Magdeburg, Germany: Otto-von-Guericke univresity Magdeburg.
Konstantakopoulos, G. D., Gayialis, S. P., & Kechagias, E. P. (2022). Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification. Operational Research, 22(3), 2033–2062.
Kou, S., Golden, B., & Bertazzi, L. (2024). Estimating optimal split delivery vehicle routing problem solution values. Computers & Operation Research, 168, 106714.
Lia, J., Qina, H., Baldaccib, R., & Zhuc, W. (2020). Branch-and-price-and-cut for the synchronized vehicle routingproblem with split delivery, proportional service time and multiple time windows. Transportation Research Part E: Logistics and Transportation Review, 140, 101955.
Mancini, S. (2016). A real-life Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet: Formulation and Adaptive Large Neighborhood Search based Matheuristic. Transportation Research Part C: Emerging Technologies, 70, 100–112.
Martins, S., Ostermeier, M., Amorim, P., Hübner, A., & Almada-Lobo, B. (2019). Product-oriented time window assignment for a multi-compartment vehicle routing problem. European Journal of Operational Research, 276(3), 893–909.
Mohammadi, M., Rahmanifar, G., Hajiaghaei-keshteli, M., Fusco, G., Colombaroni, C., & Sherafat, A. (2023). A dynamic approach for the multi-compartment vehicle routing problem in waste management. Renewable and Sustainable Energy Reviews, 184, 113526.
Moshref-Javadi, M., & Lee, S. (2016). The Customer-centric, multi-commodity vehicle routing problem with split delivery. Expert Systems With Applications Received, 56, 335–348.
Ngoo, C. M., Goh, S. L., Sze, S. N., Sabar, N. R., Hijazi, M. H. A., & Kendall, G. (2024). A survey of mat-heuristics for combinatorial optimisation problems: Variants, trends and opportunities. Applied Soft Computing, 164, 111947.
Ostermeier, M., Henke, T., Hübner, A., & Wäscher, G. (2021). Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions. European Journal of Operational Research, 292(3), 799–817.
Polat, O., & Topaloğlu, D. (2020). Collection of diferent types of milk with multi tank tankers under uncertainty: a real case study. Top, 30(1), 1–33.
Ropke, S., & Pisinger, D. (2006). An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, 40(4), 455–472.
Shaw, P. (1998). Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. International Confference on Principles and Practice of Constraint Programming, 417–431.Berlin, Heidelberg: Springer Berlin Heidelberg.
Toth, P., & Vigo, D. (2014). Vehicle routing problems: methods and applications (2nd ed.). Society for Industrial and Applied Mathematics.
Urli, T., & Kilby, P. (2017). Constraint-based fleet design optimisation for multi-compartment split-delivery rich vehicle routing. Principles and Practice of Constraint Programming: 23rd International Conference, CP 2017, Melbourne,VIC, Australia, August 28-September 1, 2017, Proceedings 23, 414–430.
Voigt, S. (2024). A review and ranking of operators in adaptive large neighborhood search for vehicle routing problems. European Journal of Operational Research.
Wang, J., Lian, Z., Liu, C., & Liu, K. (2023). Iterated clustering optimization of the split-delivery vehicle routing problem considering passenger walking distance. Transportation Research Interdisciplinary Perspectives, 17, 100751.
Wang, L., Kinable, J., & van Woensel, T. (2020). The fuel replenishment problem: A split-delivery multi-compartment vehicle routing problem with multiple trips. Computers & Operations Research, 118, 104904.
Zbib, H., & Laporte, G. (2020). The commodity-split multi-compartment capacitated arc routing problem. Computers and Operations Research, 122, 104994.
Zhang, Z., Che, Y., & Liang, Z. (2024). Split-demand multi trip vehicle routing problem with simultaneous pickup and delivery in airport baggage transit. European Journal of Operational Research, 312(3), 996–1010.