A multi-depot vehicle routing problem with time windows for daily planned maintenance and repair service planning

Year 2023, Volume: 29 Issue: 8, 913 - 919, 31.12.2023

Elif Toru Görkem Yılmaz

Abstract

A compressor manufacturer producing in Kocaeli/Dilovası region makes vehicle routing and employee planning daily to fulfill the maintenance and repair requests of the Marmara region and its surroundings the next day. The service types and times are agreed upon with the customer before service planning. The vehicles and their respective operators for a given planning day are known, with the service personnel's starting and ending points being the residences. All the planned services must be satisfied in the time windows customers give. We approach the issue as a multi-depot vehicle routing problem with time windows (MDVRPTW) and construct a mixed-integer linear programming framework. The solution is deemed adequate in resolving the company's service planning predicament. To tackle large instances, we formulate a clustering algorithm that yields a proficient solution in a concise duration.

Keywords

Multi depot, Vehicle routing problem, Time window

Günlük planlanmış bakım ve onarım servis planlaması için zaman pencereli bir çok depolu araç rotalama problemi

Abstract

Kocaeli/Dilovası bölgesinde üretim yapan bir kompresör üreticisi, Marmara bölgesi ve çevresinin ertesi günkü bakım ve onarım talebini karşılamak için günlük olarak araç rotalama ve personel planlaması yapmaktadır. Servis planlamasından önce servis türleri ve süreleri müşteri ile kararlaştırılır. Servis personelinin başlangıç ve bitiş noktaları ikametgah adresleri olmak üzere, belirli bir planlama günü için araçlar ve ilgili operatörleri bilinmektedir. Tüm talepler, müşteriler tarafından verilen zaman pencerelerinde karşılanır. Problem, Zaman Pencereli Çok Depolu Araç Rotalama problemi (MDVRPTW) olarak ele alınmaktadır ve bir karma tamsayılı doğrusal programlama modeli geliştirilmiştir. Matematiksel model çözümü şirketin problemini çözmeye yeterlidir. Büyük örnekleri çözmek için, kısa sürede yeterli bir çözüm sağlayan bir kümeleme algoritması geliştirilmiştir.

Keywords

Çoklu depo, Araç rotalama problemi, Zaman penceresi

References

• [1] Lenstra JK, Kan AR. “Complexity of vehicle routing and scheduling problems”. Networks, 11(2), 221-227, 1981.
• [2] Zhen L, Ma C, Wang K, Xiao L, Zhang W. “Multi-Depot multi-trip vehicle routing problem with time windows and release dates". Transportation Research Part E: Logistics and Transportation Review, 135, 10-18, 2020.
• [3] Bae H, Moon I. “Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles". Applied Mathematical Modelling, 40(13-14), 6536-6549, 2016.
• [4] Li J, Li Y, Pardalos PM. “Multi-depot vehicle routing problem with time windows under shared depot resources". Journal of Combinatorial Optimization, 31, 515-532. 2016.
• [5] Sim I, Kim T, Cha J, Lee H. “A design and analysis of scheduling for the dual of appliances delivery and installation services”. Journal of the Korean Society of Supply Chain Management, 11, 41-53, 2011.
• [6] Kim K, Sun J, Lee S. "A hierarchical approach to vehicle routing and scheduling with sequential services using the genetic algorithm". International Journal of Industrial Engineering, 20(1-2), 99-113, 2013.
• [7] Salhi S, Wassan N, Hajarat M. “The fleet size and mix vehicle routing problem with backhauls: Formulation and set partitioning-based heuristics". Transportation Research Part E: Logistics and Transportation Review, 56, 22-35, 2013.
• [8] Reyes D, Erera AL, Savelsbergh MW. “Complexity of routing problems with release dates and deadlines". European Journal of Operational Research, 266(1), 29-34, 2018.
• [9] Molina JC, Salmeron JL, Eguia I, Racero J. “The heterogeneous vehicle routing problem with time windows and a limited number of resources". Engineering Applications of Artificial Intelligence, 94, 1-15, 2020.
• [10] Crevier B, Cordeau JF, Laporte G. “The multi-depot vehicle routing problem with inter-depot routes". European Journal of Operational Research, 176(2), 756-773, 2007.