Heterojen Araç Filolu Eş Zamanlı Dağıtım-Toplamalı Araç Rotalama Problemi İçin Bir Karar Destek Sistemi

Year 2011, Volume: 3 Issue: 1, 11 - 18, 15.01.2011

Suna Çetin Emre Özkütük Cevriye Gencer

Abstract

In this study a new heuristic algorithm is developed for the heterogeneous fleet vehicle routing problem with simultaneous delivery and pickup (heterogeneous fleet VRPSPD). A decision support system (DSS), which is based on this algorithm, is composed. The decision support system determines the vehicle fleet composition and the routes, which are originated at a central depot and serve a set of customers with known pick up and delivery demand with minimum cost. Visual basic 6.0 is used to code the interface of DSS and C++ programming language is used to code the computation algorithm. Since there are not benchmarking problems in the literature, the algorithm is tested using the real data of a transportation firm and the results derived are compared to the current situation by distance and total cost.

Keywords

Vehicle routing problem (VRP), VRP with pick up and delivery, VRP with simultaneous pick up and delivery, Heterogeneous VRP, Decision support system, Heuristic algorithm

Heterojen Araç Filolu Eş Zamanlı Dağıtım-Toplamalı Araç Rotalama Problemi İçin Bir Karar Destek Sistemi

Abstract

Bu çalışmada heterojen araç filolu eş zamanlı dağıtım toplamalı araç rotalama problemlerinin çözümü için yeni bir sezgisel algoritma önerilmiş ve önerilen algoritmaya dayalı bir karar destek sistemi (KDS) oluşturulmuştur. Karar destek sistemi, tek bir depodan çeşitli noktalarda bulunan müşterilerin dağıtım ve toplama taleplerini minimum maliyetle yapabilecek uygun araç filosu karışımını ve bu araçların hangi güzergâhları kullanacağını gösteren rotaları belirlemekte ve karar vericiye sunmaktadır. Hazırlanan KDS’nin ara yüzleri Visual Basic 6.0 programlama diliyle, hesaplama algoritması ise C++ programlama diliyle kodlanmıştır. Literatürde karşılaştırma yapacak test problemlerinin olmaması sebebiyle algoritma, taşıma faaliyeti gösteren bir şirketin verileri alınarak denenmiş ve mevcut durumla mesafe ve maliyet açısından karşılaştırılmıştır.

Keywords

Araç rotalama problemleri (ARP), dağıtım toplamalı ARP, Eş zamanlı dağıtım toplamalı ARP, heteerojen filolu ARP, Karar destek sistemi, Sezgisel algoritma

References

• [1] Min, H., 1989, “The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Points”, Transportation Research- A, 23A(5), 377-386. [2] Dethloff, J., 2001, “Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simultaneous Delivery and Pick-Up”’, OR Spektrum, 23, 79-96. [3] Nagy, G.; Salhi, S., 2003, “ Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries”, European Journal of Operational Research, 162, 126-141. [4] Montane, F.A.T.; Galvao, R.D., 2006, “A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick-Up and Delivery Service”, Computers and Operations Research, 33, 595–619. [5] Chen, P.; Huang, H.; Dong, X., 2007, An ant colony system based heuristic algorithm for the vehicle routing problem with simultaneous delivery and pickup, ICIEA 2007: 2007 Second IEEE Conference on Industrial Electronics and Applications, 136-141. [6] Zachariadis, E.E., Tarantilis, C.D. And Kiranoudis, C. T. “Hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service”, Expert System with Applications, 36: 1070-1081 (2009a). [7] Zachariadis, E. E., Tarantilis, C. D. And Kiranoudis, C. T., “An adaptive memory methodology optimization for the vehicle routing problem with simultaneous pick-ups and deliveries”, European Journal of Opera-tional Research, 202(2): 401-411 (2009b). [8] Subramanian, A., Drummond, L.M.A., Bentes C., Ochi, L.S. And Farias, R., “ A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery”, Computers&operation Research, 37: 1899-1911 (2009). [9] Gajpal Y, Abad P., “An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup”, Computers & Operations Research, 36(12): 3215–3223 (2009). [10] Ai, T., Kachitvichyanukul, V., “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery”, Computers & Operations Research, 36: 1693-1702 (2009). [11]Golden, B.; Assad, A.; Levy,L.; Gheysens, F., 1984, “The Fleet Size And Mix Vehicle Routing Problem”, Computers and Operations Research, 11, 49–66. [12] Choi, E.; Tcha, D.W., 2007, “A Column Generation Approach to the Heterogeneous Fleet Vehicle Routing Problem”, Computers and Operations Research, 34, 2080–2095. [13] Gheysens, F.; Golden, B.; Assad, A., 1984, “A Comparison of Techniques for Solving the Fleet Size and Mix Vehicle Routing Problem”, OR Spektrum, 6, 207–216. [14] Gheysens, F.; Golden, B.; Assad, A., 1986, “A New Heuristic for Determining Fleet Size and Composition”, Mathematical Programming Study, 26, 233–236. [15] Salhi, S., Rand, G.K., 1993, “Incorporating Vehicle Routing into the Vehicle Fleet Composition Problem”, European Journal of Operational Research, 66, 313–360. [16] Osman, I.; Salhi, S., 1996, Local search strategies for the vehicle fleet mix problem, in: V.J. , Modern Heuristic Search Methods, Wiley, 131–153. [17] 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. [18] Taillard, E.D., 1999, “Heuristic Column Generation Method for the Heterogeneous Fleet VRP”, Recherche-Operationnelle 33, 1–14. [19] Taillard, E.D., 1996, “A Heuristic Column Generation Method for the Heterogeneous Fleet VRP”, Publication CRT, 3,1-13 [20] Yaşa, Ö., 2006, Ulaştırma Komutanlığı Ring Seferlerinin Eş Zamanlı Dağıtım Toplama Karar Destek Sistemi, (Yayımlanmamış Yüksek Lisans Tezi), Ankara, Kara Harp Okulu Savunma Bilimleri Enstitüsü.