Comparison of non-split and split delivery strategies for the heterogeneous vehicle routing problem

Bu çalışma merkezi İzmir’de bulunan bir market zincirinin taze gıda dağıtımını incelemektedir. Problem, literatürde hiçbir yöntemin en iyi çözüm sağladığı ispat edilmemiş, heterojen filolu araç rotalama problemi olarak kurgulanmıştır. Önerilen çözüm algoritması ana problemi alt probleme ayrıştırıp, her alt probleme gerekli araçları atamaktadır. Daha sonra, alt problemler tamsayı programlama ile çözülmektedir. Aynı zamanda, birleşik teslimat ve ayrışık teslimat stratejileri bu yöntem içinde test edilmiştir. Sonuçlar firmanın şu anki dağıtım performansı ile karşılaştırılmıştır. Önerilen algoritma her iki strateji ile de mevcut performanstan daha iyi sonuçlar elde etmiştir.

Heterojen filosu araç rotalama problemi için bütünleşik ve bölünmüş dağıtım stratejilerinin karşılaştırılması

This paper considers fresh goods distribution of a retail chain store in Izmir. The problem is formulated as a vehicle routing problem with a heterogeneous fleet. Although there are exact algorithms available in the literature, to the best of our knowledge, none of them is able to solve large scale instances optimally. The proposed algorithm decomposes the main problem into subproblems and simultaneously allocates vehicles to a number of NP-complete subproblems. Then integer programming is employed to solve subproblems. Also, non-split and split delivery strategies are tested for the distribution. Solutions of both strategies are compared with the current performance of the firm. Results indicated considerable improvement in the performance.

PDF

___

1. Archetti, C., Savelsbergh, M.W.P., Speranza, M.G., In pres. To split or not to split: That is the question. Transportation Research Part E.
2. Burchett, D., Campion, E., (2002). Mix fleet vehicle routing problem – An application of tabu search in the grocery delivery industry. Management Science Honors Project.
3. Chen, H.K., Hsueh, C.F., Chang, M.S., (2006). The realtime time-dependent vehicle routing problem. Transportation Research Part E 42, 383-408.
4. Choi, E., Tcha, D.W., (2007). A column generation approach to the heterogeneous fleet vehicle routing problem. Computers & Operations Research 34(7), 2080-2095.
5. Desrochers, M., Verhoog, T.W., (1991). A new Heuristic for the Fleet Size and Mix Vehicle Routing Problem. Computers & Operations Research 18, 263-274.
6. Dinçerler, A., Güven, N.E., Tanrıkulu, M.M., Temel, M., Yitmen, M., Yaman, H., (2004). Bilkent Üniversitesi Personel Taşıma Sistemi İçin Etkin ve Ekonomik Çözüm. Endüstri Mühendisliği Dergisi 15(2), 2-14.
7. Dror, M., Laporte, G., Trudeau, P., (1994). Vehicle Routing With Split Deliveries. Discrete Applied Mathematics 50, 239-254.
8. Du, T., Wang, F.k., Lu, P.y., in Press. A Real-time Vehicledispatching System for Consolidating Milk Runs. Transportation Research Part E.
9. Faulin, J., (2003). Applying Mixalg Procedure in a Routing Problem to Optimize Food Product Delivery. Omega 31, 387-395.
10. Frizzell, P.W., Giffin, J.w., (1995). The Split Delivery Vehicle Scheduling Problem With Time Windows and Grid Network Distances. Computers & Operations Research 22, 655-667.
11. Gendreau, M., Laporte, G., Musaraganyi, C, Taillard E.D., (1999). A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem. Computers & Operations Research 26, 1153-1173.
12. Golden, B.L., Assad, A.A., Levy, L., Gheysens, F., (1984). the Fleet Size and Mix Vehicle Routing Problem. Computers & Operations Research 11, 49-66.
13. Ho, S.C., Haugland, D., (2004). A Tabu Search Heuristic for the Vehicle Routing Problem With Time Windows And Split Deliveries. Computers & Operations Research 31, 1947-1964.
14. Ilog S.A., 2003. Ilog Opl Studio 3.7 Language Manual, France.
15. Laporte, G., Semet, F., (2002). Classical Heuristics for the Capacitated VRP. In: Toth, P.,Vigo, D. (Eds.), The Vehicle Routing Problem, Siam, Philadelphia, USA, PP. 109-128.
16. Lee, C.G., Epelman, M., White, C.C., Bozer, Y.A., (2002). A Shortest Path Approach to the Multiple-Vehicle Routing Problem With Split Pick-ups. 17th International Symposium on Mathematical Programming.
17. Li, F., Golden, B., Wasil, E., (2007). A Record-to-record Travel Algorithm for Solving the Heterogeneous Fleet Vehicle Routing Problem. Computers & Operations Research 34(9), 2734-2742.
18. Lima, C.M.R.R., Goldbarg, M.C., Goldbarg, E.F.G., (2004). A Memetic Algorithm for the Heterogeneous Fleet Vehicle Routing Problem. Electronic Notes in Discrete Mathematics 18, 171-176.
19. Liu, F.H., Shen, S.Y., (1999). A Method for Vehicle Routing Problem With Multiple Vehicle Types and Time Windows. Proceedings of National Science Council Roc 23, 526-536.
20. Moghaddam, R.T., Safaei, N., Gholipour, Y., (2006). A Hybrid Simulated Annealing for Capacitated Vehicle Routing Problems With Independent Route Length. Applied Mathematics And Computation 176(2), 445-454.
21. Moghaddam, R.T., Safaei, N., Kah, M.M.O., Rabbani, M., (2007). A New Capacitated Vehicle Routing Problem With Split Service for Minimizing Fleet Cost By Simulated Annealing. Journal Of The Franklin Institute 344, 406-425.
22. Ochi, L.S., Vianna, D.S., Drummond, L.M.A., Victor, A.O., (1998). A Parallel Evolutionary Algorithm for the Vehicle Routing Problem With Heterogeneous Fleet. Future Generation Computer Systems 14, 285-292.
23. Salhi, S., Sari, M., (1997). A Multi Level Composite Heuristic for the Multi Depot Vehicle Fleet Mix Problem. European Journal of Operations Research 103, 95-112.
24. Tarantilis, C.D., Kiranoudis, C.T., (2001). A Meta-heuristic Algorithm for the Efficient Distribution of Perishable Foods. Journal of Food Engineering 50, 1-9.
25. Ulusoy, G., (1985). The Fleet Size and Mix Problem for Capacitated Arc Routing. European Journal of Operational Research 22, 329-337.
26. Taillard, E.D., (1999). A Heuristic Column Generation Method For The Heterogeneous Fleet Vrp. Rairo 33, 1-4.

ISSN: 1300-3410
Yayın Aralığı: Yılda 3 Sayı
Başlangıç: 1989
Yayıncı: TMMOB MAKİNA MÜHENDİSLERİ ODASI

Arşiv

Sayıdaki Diğer Makaleler

Comparison of non-split and split delivery strategies for the heterogeneous vehicle routing problem

Mızrak Pınar ÖZFIRAT, İrem ÖZKARAHAN

Hazırlık zamanı kaynaklı üretim kayıplarını enazlayan çok amaçlı bir çizelgeleme algoritması

Tuğba SARAÇ, Müjgan SAĞIR