Ağ ve araç rotalarının optimizasyonu için meta-sezgisel bir çözüm önerisi
A meta-heuristic algorithm approach for network and vehicle routing optimization
Yazar: DURSUN EKMEKCİ
Danışman: DR. ÖĞR. ÜYESİ FUAT ŞİMŞİR
Karabük Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2019
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Optimizasyon problemi = Optimization problem ; Optimizasyon teknikleri = Optimization techniques ; Yönlendirme = Routing

Özet:
Coğrafi bakımdan dağınık konumlardaki müşterilere, dağıtım/toplama hizmeti için bir ya da daha fazla depodan yola çıkacak araçların, en uygun rotalarının belirlenmesi problemi olarak ifade edilen araç rotalama problemi (ARP), uzun zamandır üzerinde değişik teknikler denenerek çözüm aranan ve optimizasyon açısından ilgi çeken problem çeşitlerinden biridir. Esnek bir araç rotalama sistemi; lojistik planların daha önceden hazırlanması, gerektiğinde yeni rotaların hızlı bir biçimde oluşturulabilmesi ve yüklerin; depolarda daha az süre tutulması gibi avantajları da beraberinde getirecektir. Klasik ARP yapısına farklı kıstaslar eklenerek, problemin değişik türleri oluşturulmuş ve daha kompleks hale dönüştürülmüştür. ARP türlerinin genelinde rota maliyeti mesafeyle ilişkilendirilir ve daha kısa mesafeli çözüm, daha başarılı çözüm olarak kabul edilir. En kısa mesafe hedefi, işletmelere maliyet ve zaman açısından önemli avantajlar sağlamaktayken, bu konuyu daha fazla araştırma yapılması için çekici kılmaktadır. Araç rotalama üzerine farklı yön ve alanlarda, çeşitli bakış açılarıyla oluşturulan problem türleri incelendiğinde, pratikteki uygulamaya en yakın olanının kapasite kısıtlı ve eş zamanlı dağıtım-toplamalı araç rotalama problemi (EDTARP) olduğu söylenebilir. EDTARP modelinde; bir ya da daha fazla depo merkezi, çok sayıda ziyaret edilecek müşteri düğüm ve tamamı depo merkezlerinde bulunan, sınırlı kapasiteli taşıma araçları yer alır. Problem senaryosunda, müşteri düğümlerden, miktarları ve dağıtım noktaları belirlenmiş olarak toplanan yükler, depo merkezlerinde biriktirilmiştir. Bu yükler, ilgili dağıtım noktalarına sevk edilecek ve aynı zamanda, uğranan düğümde, bir sonraki seferde dağıtılmak üzere hazırlanmış, miktarları belli yükler toplanacaktır. EDTARP'de amaç, eş kapasiteli taşıma araçlarının kapasiteleri aşılmadan, ziyaret edilen her bir düğümde dağıtım toplama faaliyetinin eş zamanlı olarak yürütülebilmesi ve bu araçların, toplamda minimum maliyetle depo merkezlerine dönecek biçimde rotalandırılmasıdır. Bu çalışmada, EDTARP için, Yapay Arı Koloni (YAK) algoritması kullanılarak bir çözüm önerisi sunulmuş ve uygulama, literatürde EDTARP için yaygın olarak kullanılan problem setleriyle test edilmiştir. Elde edilen sonuçlar, literatürde aynı test problemleri için belirlenen en düşük maliyetli rota çözümleriyle karşılaştırıldığında, az sayıdaki parametresine rağmen; önerilen yöntemin, literatürdeki en başarılı çözümlerin en çok %1.12'si kadar gerisinde kaldığı gözlemlenmiştir.

Abstract:
The vehicle routing problem (VRP), which is defined as the problem of determining the most appropriate routes of the vehicles that will depart from one or more depots to the customers in the geographically dispersed locations, is the solution that has been sought for a long time by trying different techniques and the problem of optimization is one of its varieties. A flexible vehicle routing system; preparation of logistics plans before, creation of new routes when necessary, it will bring advantages such as keeping loads in warehouses for less time. In most VRP types, route cost is associated with distance, and a shorter distance solution is considered a more successful solution. While the shortest distance goal provides significant advantages in terms of cost and time to businesses, this makes it attractive for further research. When examining the types of problems having different directions and areas devised from different points of view on vehicle routing, it can be said that the closest approach to practical application is the vehicle routing problem with simultaneous delivery and pickup (VRPSDP). In VRPSDP model; there are one or more depots, many customer nodes to visit, and limited capacity transport vehicles located at depots. In the problem scenario, the loads collected from the customer nodes with their designated amounts and delivery points are stored in depots. These loads will be shipped to the relevant delivery points and at the same time, certain loads will be collected in the line which is prepared to be distributed next time. The purpose in the VRPSDP model is that to ensure the delivery/pickup activity can be carried out simultaneously on each of the visited nodes without exceeding the capacities of the carrying vehicles, and that these vehicles are routed to return to depots at minimum cost in total. In this study, a solution proposal is presented for the VRPSDP using the Artificial Bee Colony (ABC) algorithm and the application is tested with the benchmark problem data sets commonly used for VRPSDP in the literature. When the results are compared with the least cost route solutions in the literature, it is observed that despite the few parameters, the proposed method can produce low-cost solutions, behind at most 1.12% of the most successful solutions in the literature.