This study focuses on a distribution problem involving incompatible products which cannot be stored in a compartment of a vehicle. To satisfy different types of customer demand at minimum logistics cost, the products are stored in different compartments of fleet vehicles, which requires the problem to be modeled as a multiple-compartment vehicle routing problem (MCVRP). While there is an extensive literature on the vehicle routing problem (VRP) and its numerous variants, there are fewer research papers on the MCVRP. Firstly, a novel taxonomic framework for the VRP literature is proposed in this study. Secondly, new mathematical models are proposed for the basic MCVRP, together with its multiple-trip and split-delivery extensions, for obtaining exact solutions for small-size instances. Finally, heuristic algorithms are developed for larger instances of the three problem variants. To test the performance of our heuristics against optimum solutions for larger instances, a lower bounding scheme is also proposed. The results of the computational experiments are reported, indicating validity and a promising performance of an approach.
Dantzig GB, Ramser JH. The Truck Dispatching Problem. Management Science. 1959;6(1):80-91.
Lenstra J, Rinnooy KA. Complexity Of Vehicle Routing And Scheduling Problems. Networks. 1981;11(2):221-227.
Reisman A. Management Science Knowledge: It’s Creation Generalization And Consolidation. Westport CT: Quorum Books Publishing Company; 1992.
Bodin L, Golden B. Classification in Vehicle Routing and Scheduling. Networks. 1981;11(2):97–108.
Desrochers M, Lenstra JK, Savelsbergh MWP. A Classification Scheme For Vehicle Routing And Scheduling Problems. European Journal of Operational Research. 1990;46(3):322–332.
Laporte G, Osman IH. Routing Problems: A bibliography. Annals of Operations Research. 1995;61(1):227-262.
Eksioglu B, Vural AV, Reisman A. The Vehicle Routing Problem: A taxonomic review Computers & Industrial Engineering. 2009;57(4):1472–1483.
Bin S, Fu Z. An Improved Genetic Algorithm For Vehicle Routing Problem With Soft Time Windows. Systems Engineering. 2003;21(6):12–15.
Chang TS, Wan YW, Tsang W. A Stochastic Dynamic Traveling Salesman Problem With Hard Time Windows. OOI European Journal of Operational Research. 2009;198(3):748–759.
Rais A, Alvelos F, Carvalho MS. New Mixed Integer-Programming Model For The Pickup And Delivery Problem With Transshipment. European Journal of Operational Research. 2014;235(3):530–539.
Goetschalckx M, Blecha CJ. The Vehicle Routing Problem With Backhauls. European Journal of Operational Research. 1989;42(1):39-51.
Oesterle J, Bauernhansl T. Exact Method for the Vehicle Routing Problem with Mixed Linehaul and Backhaul Customers, Heterogeneous Fleet, time Window and Manufacturing Capacity. Procedia CIRP. 2016;41:573-578.
Dror M, Trudeau P. Split Delivery Routing. Naval Research Logistics. 1990;37(3):383- 402.
Salhi S. The Integration Of Routing Into The Location-Allocation And Vehicle Composition Problems. [PhD thesis]. University of Lancaster; 1987.
Lahyani R, Coelho CL, Khemakhem M, Laporte G, Semet F. A Multi-Compartment Vehicle Routing Problem Arising in the Collection of Olive Oil in Tunisia. Omega. 2015;51:1-10.
Kuo Y, Wang CC, Chuang PY. Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds. Computers & Industrial Engineering, 2009;57(4):1385-1392.
Çetin S, Gencer C. Heterojen Araç Filolu Zaman Pencereli Eş Zamanlı Dağıtım-Toplamalı Araç Rotalama Problemleri: Matematiksel Model. International Journal of Research and Development. 2011;3(1):19-27.
Yakıcı E, Karasakal O. A min–max vehicle routing problem with split delivery and heterogeneous demand. Optimization Letters. 2013;7(7):1611–1625.
Bullnheimer B, Hartl RF, Strauss C. Applying the Ant System to the Vehicle Routing Problem. In: Voss S, Martello S, Osman IH, Roucairol C, editors. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization: Springer/Kluwer, 1997; p. 285-296.
Lee T, Ueng J. A Study Of Vehicle Routing Problems With Load-Balancing. International Journal of Physical Distribution & Logistics Management 1999;29(10):646-658.
Corberan A, Fernandez E, Laguna M, Marti R. Heuristic Solutions To The Problem of Routing School Buses With Multiple Objectives. Journal of the Operational Research Society. 2002;53(4):427–435.
Han H, Cueto EP. Waste collection vehicle routing problem: literature review. Promet-Traffic and Transportation. 2015;27(4):345-358.
Cordeau JF, Laporte G. A Tabu Search Algorithm For The Site Dependent Vehicle Routing Problem With Time Windows. INFOR. 2001;39(3):292–298.
Letchford AN, Eglese RW. The Rural Postman Problem With Deadline Classes. European Journal of Operational Research. 1998;105(3):390-400.
Derigs U, Gottlieb J, Kalkoff J, Piesche M, Rothlauf F. Vogel, U., 2011, Vehicle Routing With Compartments: Applications, Modelling And Heuristics. OR Spectrum. 2011;33(4):885-914.
Rabbani M, Farrokhi-asl H, Rafiei H. A hybrid genetic algorithm for waste collection problem by heterogeneous fleet of vehicles with multiple separated compartments. Journal of Intelligent & Fuzzy Systems. 2016;30(3):1817-1830.
Archetti C,Jabali.OM, Speranza G. Multi-period Vehicle Routing Problem with Due dates. Computers and Operations Research. 2015;61:122-134.
Kendall DG. Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain. The Annals of Mathematical Statistics. 1953;24(3):338-354.
Van der Bruggen L, Gruson R, Salomon M. Reconsidering the Distribution Structure Of Gasoline Products For A Large Oil Company. European Journal Operational Research. 1995;81(3):460-473.
Avella P, Boccia M, Sforza A. Solving a Fuel Delivery Problem by Heuristic and Exact Approaches. European Journal of Operational Research. 2004;152(1):170-179.
Suprayogi, Komara S, Yamato H. A Local Search Technique for Solving a Delivery Problem of Fuel Products. Proceedings of the 2nd International Conference on Operations and Supply Chain Management; 2007 May 18-20; Bangkok, Thailand.
El Fallahi A, Prins C, Wolfler C. A Memetic Algorithm And A Tabu Search For The Multi-Compartment Vehicle Routing Problem. Computers & Operations Research. 2008;35(5):1725-1741.
Mendoza, JE, Castaniera B, Guéreta C, Medagliab AL, Velascob N. A Memetic Algorithm For The Multi-Compartment Vehicle Routing Problem With Stochastic Demands. Computers & Operations Research. 2010;37(11):1886-1898.
Surjandari I, Rachman A, Dianawati F, Wibowo RP. Petrol Delivery Assignment with Multi-Product, Multi-Depot, Split Deliveries and Time Windows. International Journal of Modeling and Optimization. 2011;1(5):375-379.
Benantar A, Oufi R. Optimization of Vehicle Routes: An Application to Logistic and Transportation of the Fuel Distribution. Paper presented at: 9th International Conference on Modeling, Optimization & SIMulation; 2012 June 8; Bordeaux, France.
Asawarungsaengkul K, Rattanamanee T, Wuttipornpun, T. A Multi-Size Compartment Vehicle Routing Problem for Multi-Product Distribution: Models and Solution Procedures, International Journal of Artificial Intelligence. 2013;11(A13):237-256.
Coelho LC, Laporte G. Classification, models and exact algorithms for multicompartment delivery problems. Operations Research. 2015;242(3):854-864.
Abdulkader MMS, Gajpal Y, ElMekkawy TY. Hybridized ant colony algorithm for the multi compartment vehicle routing problem. Applied Soft Computing. 2015;37:196-203.
Koch H, Henke T, Wascher G. A Genetic Algorithm for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes. University of Magdeburg. Working Paper 04/2016.
Alinaghian M, Shokouhi N. Multi-Depot Multi-Compartment Vehicle Routing Problem, Solved By A Hybrid Adaptive Large Neighborhood Search. Omega, In Press, Accepted Manuscript. 2017.
“Author”, 2015.
Mladenović N, Hansen P. Variable neighborhood search. Computers & Operations Research. 1997;24(11):1097-1100.
Guest Editor: Eleonora Papadimitriou, PhD
Editors: Dario Babić, PhD; Marko Matulin, PhD; Marko Ševrović, PhD.
The mission of our journal is to provide high quality communication of research results, which is crucial for the effectiveness of scientific research, the promotion of scientific information, new ideas, and original research in the field of traffic and transportation engineering.
1848-4069
0353-5320
Proud publisher
Accelerating Discoveries in Traffic Science |
2024 © Promet - Traffic&Transportation journal
