The bi-objective heuristic approach for solving the multiple time window and multiple use vehicle routing problem

Öz

In today’s competitive environment, minimizing production waste has become critical for firms to ensure their sustainability. A considerable portion of this waste arises from unnecessary production downtimes. This study investigates the downtimes experienced by a company operating in the medical sector that manufactures laboratory consumables. The analysis indicates that these downtimes predominantly occur during the supply of raw materials and semi-finished products to workstations. A “water spider” system for material delivery to workstations is proposed to address this problem. The routing problem of the water spider is defined as a Time-Window Vehicle Routing Problem (TWVRP). A mathematical model was developed to minimize the total travel and tardiness times within the constraints of workstation time windows. A bi-objective genetic algorithm is proposed for solving the problem, and both objective functions are aggregated using the weighted-sum scalarization method. Parameter calibration was performed using both experimental design and the irace method, with the results favouring the parameter values obtained through experimental design. In addition to the weighted-sum method, conic and Chebyshev scalarization approaches were also employed. The findings confirm that the model is feasible and demonstrate that the proposed water spider system can reduce downtimes and enhance utilization within the production process.

Anahtar Kelimeler

• Vehicle routing
• multiple use
• multiple time-window
• mixed integer linear programming
• water spider

Çoklu zaman pencereli ve çok kullanımlı araç rotalama probleminin çözümü için iki amaçlı sezgisel yaklaşım

Öz

Rekabetin hızla arttığı günümüzde, firmaların üretimdeki israfları minimize etmesi en önemli faktörlerden biridir. Bu israfların büyük bir kısmını da üretim sürecindeki gereksiz duruşlar oluşturmaktadır. Bu çalışmada, medikal sektörde faaliyet gösteren ve laboratuvar sarf malzemeleri üreten bir firmanın duruşları incelenmiştir. Duruşların, istasyonlara hammadde ve yarı mamul tedariği sırasında meydana geldiği saptanmıştır. Bu durumu önlemek amacıyla, istasyonlara malzeme tedarik edecek bir su örümceği yapısı önerilmiştir. Bu yapının rota probleminin zaman pencereli araç rotalama problemi (ZPARP) olduğu belirlenmiştir. Su örümceği için toplam seyahat süresi ve gecikme süresini enküçüklemeyi hedefleyen bir matematiksel model geliştirilmiştir. Çözüm için iki amaçlı genetik algoritma önerilmiş ve ağırlıklı-toplam yöntemi ile amaçlar birleştirilmiştir. Parametre kalibrasyonu deney tasarımı ve irace yöntemi ile yapılmış, deney tasarımının daha başarılı olduğu görülmüştür. Ağırlıklı-toplam yöntemine ek olarak, konik ve Chebyshev skalerleştirme yöntemleri de uygulanmıştır. Sonuçlar, modelin uygulanabilir olduğunu ve duruşları azaltarak kullanılabilirliği artırabileceğini göstermektedir.

Anahtar Kelimeler

• Araç rotalama
• çoklu kullanım
• çoklu zaman penceresi
• karma tamsayılı doğrusal programlama
• su örümceği

Kaynakça

1. 1. Koç Ç., Karaoğlan İ., A mathematical model for the multi-use vehicle routing problem with time windows, Gazi Univ. J. Sci. Eng., 27 (3), 569-576, 2012.
2. 2. Cai Y., Cheng M., Zhou Y., Liu P., Guo J.M., A hybrid evolutionary multitask algorithm for the multiobjective vehicle routing problem with time windows, Inf. Sci., 612, 168-187, 2022.
3. 3. Expósito A., Brito J., Moreno J.A., Expósito-Izquierdo C., Quality of service objectives for vehicle routing problem with time windows, Appl. Soft Comput., 84, 105–127, 2019.
4. 4. Su X., Xu G., Huang N., Qin H., A branch-and-price-and-cut for the manpower allocation and vehicle routing problem with staff qualifications and time windows, Adv. Eng. Inform., 57, 102-143, 2023.
5. 5. Sipahioğlu A., Altın İ., A mathematical model for in-plant milk-run routing, Pamukkale Univ. Müh. Bilim Derg., 25 (9), 1050-1055, 2019.
6. 6. Klenk E., Galka S., Günthner W.A., Operating strategies for in-plant milk-run system, IFAC-Pap. Online, 48 (3), 1882-1887, 2015.
7. 7. Cömert S.E., Yazgan H.R., Sertvuran İ., Şengül H., A new approach for solution of vehicle routing problem with hard time window: An application in a supermarket chain, Sādhanā, 42, 2067–2080, 2017.
8. 8. Angel-Bello F., Martinez-Salazar I., Alvarez A., Minimizing waiting times in a route design problem with multiple use of a single vehicle, Electron. Notes Discrete Math., 41, 269-276, 2013.

9. 9. Rivera J.C., Afsar H.M., Prins C., Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem, Eur. J. Oper. Res., 249, 93-104, 2016.
10. 10. Altundaş S., Tütüncü G., Eren S.Z., Routing and payload planning of multi-base, heterogeneous fleet unmanned aerial vehicles to time-windowed missions, Journal of the Faculty of Engineering and Architecture of Gazi University., 40 (3), 501–520, 2025.
11. 11. Kurtay, K. G., Dağıstanlı, H. A., Altundaş, A., Simultaneous Pick Up-Delivery Vehicle Routing Sustainability Model for Ammunition Recycling. In The International Symposium for Production Research (pp. 349-369). Cham: Springer Nature Switzerland, 2024.
12. 12. Dağıstanlı H.A., Çok ürünlü çok depolu araç rotalama problemi: askeri ilaç fabrikası örneği. J. Polytechnic, 27(3), 1017–1027, 2024.
13. 13. Kumari M., De P.K., Chaudhuri K., Narang P., Utilizing a hybrid metaheuristic algorithm to solve capacitated vehicle routing problem, Results Control Optim., 13, 100-122, 2023.
14. 14. Wu H., Gao Y., An ant colony optimization based on local search for the vehicle routing problem with simultaneous pickup–delivery and time window, Appl. Soft Comput., 139, 1-16, 2023.
15. 15. Wang Y., Wei Y., Wang X., Wang Z., Wang H., A clustering-based extended genetic algorithm for the multidepot vehicle routing problem with time windows and three-dimensional loading constraints, Appl. Soft Comput., 133, 109-122, 2023.
16. 16. Yesodha R., Amudha T., A bio-inspired approach: Firefly algorithm for multi-depot vehicle routing problem with time windows, Comput. Commun., 190, 48-56, 2022.
17. 17. Ke-Wei J., San-Yang L., Xiao-Jun S., A hybrid algorithm for time-dependent vehicle routing problem with soft time windows and stochastic factors, Eng. Appl. Artif. Intell., 109, 104-126, 2022.
18. 18. Eydi A., Ghasemi-Nezhad S.A., A bi-objective vehicle routing problem with time windows and multiple demands, Ain Shams Eng. J., 12, 2617-2630, 2021.
19. 19. Alvarez A., Munari P., An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen, Comput. Oper. Res., 83, 1-12, 2017.
20. 20. Zhang D., Cai S., Ye F., Si Y.W., Nguyen T.T., A hybrid algorithm for a vehicle routing problem with realistic constraints, Inf. Sci., 394, 167-182, 2017.
21. 21. Kumar S.N., Panneerselvam R., Development of an efficient genetic algorithm for the time dependent vehicle routing problem with time windows, Am. J. Oper. Res., 7, 1-25, 2017.
22. 22. Victoria J.F., Afsar H.M., Prins C., Column generation based heuristic for the vehicle routing problem with time-dependent demand, IFAC-Pap. Online, 49 (12), 526-531, 2016.
23. 23. Anggodo Y.P., Ariyani A.K., Ardi M.K., Mahmudy W.F., Optimization of multi-trip vehicle routing problem with time windows using genetic algorithm, J. Environ. Eng. Sustain. Technol., 3 (2), 92-97, 2016.
24. 24. Kırcı P., An optimization algorithm for a capacitated vehicle routing problem with time windows, Sādhanā, 41 (5), 519–529, 2016.
25. 25. Nalepa J., Blocho M., Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows, Soft Comput., 20, 2309–2327, 2015.
26. 26. Wang Z., Li Y., Hu X., A heuristic approach and a tabu search for the heterogeneous multi-type fleet vehicle routing problem with time windows and an incompatible loading constraint, Comput. Ind. Eng., 89, 162-176, 2015.
27. 27. Yan S., Chu J.C., Hsiao F.Y., & Huang H.J. (2015). A planning model and solution algorithm for multi-trip split-delivery vehicle routing and scheduling problems with time windows, Comput. Ind. Eng., 87, 383-393.
28. 28. Küçükoğlu İ., Öztürk N., An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows, Comput. Ind. Eng., 86, 60-68, 2015.
29. 29. Melián-Batista B., De Santiago A., Angel-Bello F., Alvarez A., A bi-objective vehicle routing problem with time windows: A real case in Tenerife, Appl. Soft Comput., 17, 140–152, 2014.
30. 30. Kumar V.S., Thansekhar M.R., Saravanan R., Amali S.M.J., Solving multi-objective vehicle routing problem with time windows by FAGA, Procedia Eng., 97, 2176-2185, 2014.
31. 31. Yükselen C., OEE nedir? Nasıl uygulanır ve hesaplanır? https://www.yalindanisman.com/oee-nedir/, Yayın tarihi 7 Nisan, 2024. Erişim tarihi 10 Mayıs, 2024.
32. 32. Yalçın A., Deliktaş D. Genetic algorithm based on weighted goal programming for doctor rostering problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 39 (4), 2567-2586, 2024.
33. 33. Miettinen, K., Nonlinear multiobjective optimization, volume 12, Springer Science & Business Media, 2012.
34. 34. Gasimov, R. N., Characterization of the Benson proper efficiency and scalarization in nonconvex vector optimization. In Multiple Criteria Decision Making in the New Millennium: Proceedings of the Fifteenth International Conference on Multiple Criteria Decision Making (MCDM) Ankara, Turkey, July 10–14, 2000 (pp. 189-198). Berlin, Heidelberg: Springer Berlin Heidelberg, 2001.
35. 35. Dagistanli, H. A., Üstün, Ö., An integrated multi-criteria decision making and multi-choice conic goal programming approach for customer evaluation and manager assignment. Decision Analytics Journal, 8, 100270, 2023.
36. 36. Deli̇ktaş, D., Ustun, O., Demirtas, E. A., Arapoglu, R. A., Multi-choice conic goal programming model-based network data envelopment analysis. RAIRO-Operations Research, 58 (4), 3391-3416, 2024.
37. 37. Steuer, R. E., Choo, E. U., An interactive weighted Tchebycheff procedure for multiple objective programming. Mathematical programming, 26 (3), 326-344, 1983.
38. 38. Rodríguez-Escoto, J. N., Nucamendi-Guillén, S., Olivares-Benitez, E., Trade-off optimization of a location-routing problem involving open routes and flexible fleet: a case study in Guadalajara, Mexico. TOP, 1-37, 2025.
39. 39. Deliktaş D., Özcan E., Ustun O., Torkul O., Evolutionary algorithms for multi-objective flexible job shop cell scheduling, Appl. Soft Comput., 113, 107-120, 2021.
40. 40. Lee K.M., Yamakawa T., Lee K.-M., A genetic algorithm for general machine scheduling problems, 2nd Int. Conf. on Knowledge-Based Intelligent Electronic Systems, Adelaide-Australia, 725-893, 21-23 Nisan, 1998.
41. 41. Deng Q., Gong G., Gong X., Zhang L., Liu W., Ren Q., A bee evolutionary guiding nondominated sorting genetic algorithm II for multiobjective flexible job‐shop scheduling, Comput. Intell. Neurosci., 2017 (1), 1-6, 2017.
42. 42. Marler R.T., Arora J.S., Function-transformation methods for multi-objective optimization, Eng. Optim., 37 (6), 551-570, 2005.
43. 43. Deliktaş D., Ustun O., Multi-objective genetic algorithm based on the fuzzy MULTIMOORA method for solving the cardinality constrained portfolio optimization, Appl. Intell., 53 (12), 14717–14743, 2023.
44. 44. Kim J., Kim S.K., A CHIM-based interactive Tchebycheff procedure for multiple objective decision making, Comput. Oper. Res., 33 (6), 1557–1574., 2006.