Vehicle Routing with Compartments Under Product Incompatibility Constraints

  • Bahar Tasar Yasar University, Department of Industrial Engineering
  • Deniz Türsel Eliiyi Izmir Bakircay University, Department of Industrial Engineering
  • Levent Kandiller Yasar University, Department of Industrial Engineering
Keywords: multiple compartment vehicle routing problem, incompatible products, split delivery, multiple trips, mathematical model, heuristic algorithms


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.

Author Biographies

Bahar Tasar, Yasar University, Department of Industrial Engineering
Bahar Taşar received her B.S. and M.S. degrees in Industrial Engineering from Yasar University in years 2013 and 2016, respectively. She worked as a research assistant at the Department of Industrial Engineering of Yasar University. After she received her M.S., she started to work at DYO Paint Company as a purchasing representative. Her research interests include vehicle routing and scheduling.
Deniz Türsel Eliiyi, Izmir Bakircay University, Department of Industrial Engineering
Deniz Türsel Eliiyi is a professor at the Department of Industrial Engineering of Izmir Bakircay University in Izmir, Turkey. She has previously worked at Middle East Technical University, Dokuz Eylül University, Izmir University of Economics and Yasar University at various academic positions. Her research interests include mathematical modeling and optimization, scheduling and vehicle routing, container port operations management, and scheduling of IoT devices. She has several academic studies on these topics, as well as research and industrial projects.
Levent Kandiller, Yasar University, Department of Industrial Engineering
Levent Kandiller is a professor of Industrial Engineering and Vice Rector at Yasar University in İzmir, Turkey. He has worked as an visiting professor at Rutgers University, as an assistant professor and associate professor at the Department of Industrial Engineering of M.E.T.U., as a professor at the Department of Industrial Engineering and Dean of Faculty of Engineering of Çankaya University. Before he was Vice Rector in Yasar University, he was Dean of Faculty of Engineering. His research interests are combinatorial optimization, cellular manufacturing, assembly line balancing, combat modelling.


[1] Dantzig GB, Ramser JH. The Truck Dispatching Problem. Management Science. 1959;6(1): 80-91.
[2] Lenstra J, Rinnooy KA. Complexity of Vehicle Routing and Scheduling Problems. Networks. 1981;11(2): 221-227.
[3] Reisman A. Management Science Knowledge: It’s Creation Generalization and Consolidation. Westport CT: Quorum Books Publishing Company; 1992.
[4] Bodin L, Golden B. Classification in Vehicle Routing and Scheduling. Networks. 1981;11(2): 97-108.
[5] 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.
[6] Laporte G, Osman IH. Routing Problems: A bibliography. Annals of Operations Research. 1995;61(1): 227-262.
[7] Eksioglu B, Vural AV, Reisman A. The Vehicle Routing Problem: A taxonomic review. Computers & Industrial Engineering. 2009;57(4): 1472-1483.
[8] Bin S, Fu Z. An Improved Genetic Algorithm for Vehicle Routing Problem with Soft Time Windows. Systems Engineering. 2003;21(6): 12-15.
[9] 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.
[10] 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.
[11] Goetschalckx M, Blecha CJ. The Vehicle Routing Problem with Backhauls. European Journal of Operational Research. 1989;42(1): 39-51.
[12] 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.
[13] Dror M, Trudeau P. Split Delivery Routing. Naval Research Logistics. 1990;37(3): 383- 402.
[14] Salhi S. The Integration of Routing into the Location-Allocation and Vehicle Composition Problems. [PhD thesis]. University of Lancaster; 1987.
[15] 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.
[16] 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.
[17] Ç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.
[18] Yakıcı E, Karasakal O. A min–max vehicle routing problem with split delivery and heterogeneous demand. Optimization Letters. 2013;7(7): 1611-1625.
[19] 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.
[20] 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.
[21] 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.
[22] Han H, Cueto EP. Waste collection vehicle routing problem: literature review. Promet – Traffic & Transportation. 2015;27(4): 345-358.
[23] Cordeau JF, Laporte G. A Tabu Search Algorithm for the Site Dependent Vehicle Routing Problem with Time Windows. INFOR. 2001;39(3): 292-298.
[24] Letchford AN, Eglese RW. The Rural Postman Problem With Deadline Classes. European Journal of Operational Research. 1998;105(3): 390-400.
[25] Derigs U, Gottlieb J, Kalkoff J, Piesche M, Rothlauf F, Vogel U. Vehicle Routing with Compartments: Applications, Modelling and Heuristics. OR Spectrum. 2011;33(4): 885-914.
[26] 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.
[27] Archetti C, Jabali OM, Speranza G. Multi-period Vehicle Routing Problem with Due dates. Computers and Operations Research. 2015;61: 122-134.
[28] 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.
[29] 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.
[30] 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.
[31] 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.
[32] 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.
[33] 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.
[34] 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.
[35] 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.
[36] 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.
[37] Coelho LC, Laporte G. Classification, models and exact algorithms for multicompartment delivery problems. Operations Research. 2015;242(3): 854-864.
[38] Abdulkader MMS, Gajpal Y, ElMekkawy TY. Hybridized ant colony algorithm for the multi compartment vehicle routing problem. Applied Soft Computing. 2015;37: 196-203.
[39] 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 No. 04/2016, 2016.
[40] Alinaghian M, Shokouhi N. Multi-Depot Multi-Compartment Vehicle Routing Problem, Solved by a Hybrid Adaptive Large Neighborhood Search. Omega. 2018;76: 85-99.
[41] Kandiller L, Eliiyi DT, Taşar B. A Multi-compartment Vehicle Routing Problem for Livestock Feed Distribution. In: Dörner K, Ljubic I, Pflug G, Tragler G. (eds) Operations Research Proceedings 2015, 1-4 September 2015, University of Vienna, Austria; 2017. p. 149-155. Available from: doi:10.1007/978-3-319-42902-1_20
[42] Mladenović N, Hansen P. Variable neighbourhood search. Computers & Operations Research. 1997;24(11): 1097-1100.
[43] Clarke G, Wright J. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research. 1964;12(4): 568-581.
[44] Ho W, Ji P. Component scheduling for chip shooter machines: A hybrid genetic algorithm approach. Computers & Operations Research. 2003;30(14): 2175-2189.
[45] Glover F, Lagua M. Tabu search. MA: Kluwer Academic Publishers; 1997.
How to Cite
Tasar B, Türsel Eliiyi D, Kandiller L. Vehicle Routing with Compartments Under Product Incompatibility Constraints. Promet - Traffic & Transportation [Internet]. 22Feb.2019 [cited 26Mar.2019];31(1):25-6. Available from: