Abstract

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.

References

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.