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 http://orcid.org/0000-0001-7693-3980
  • Levent Kandiller Yasar University, Department of Industrial Engineering
DOI: https://doi.org/10.7307/ptt.v31i1.2670
Keywords: multiple compartment vehicle routing problem, incompatible products, split delivery, multiple trips, mathematical model, heuristic algorithms

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.

Author Biographiesaaa replica rolex repwatches replica rolex watches for men replica iwc watch

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.

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.

Published
2019-02-22
How to Cite
1.
Tasar B, Türsel Eliiyi D, Kandiller L. Vehicle Routing with Compartments Under Product Incompatibility Constraints. Promet [Internet]. 2019Feb.22 [cited 2024Apr.25];31(1):25-6. Available from: http://traffic.fpz.hr/index.php/PROMTT/article/view/2670
Issue
Vol 31 No 1 (2019)
Section
Articles

Copyright (c) 2019 Bahar Tasar, Deniz Türsel Eliiyi, Levent Kandiller

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).