Eş zamanlı topla dağıt araç rotalama problemi için karınca koloni sistemi ile güçlendirilmiş değişken komşuluk arama algoritması

Abstract

Lojistik pazarı hızla büyüdüğü için, optimizasyon motoru olarak entegre edilen yazılım bileşenleri olan araç rotalama probleminin kullanımını harekete geçiren rotalama sistemleri optimizasyonu temel amaçtır. Rotalama optimizasyonunun önemli bir kilit faktörü, kaliteye karşı tepki zaman performansıdır. Daha güçlü çözümleme algoritmaları ile daha kısa zamanda daha etkili otomasyon süreçleri elde edilebilir. Bu tezin amacı, toplam kat edilen mesafenin minimize edilmesi ile birlikte araç kapasite kısıtlılığını gidermeyi amaçlayarak topla ve dağıt operasyonlarının eş zamanlı olarak kullanıldığı gerçek uygulamalarda ortaya çıkan temel Araç Rotalama Problemi’nin (ARP) popüler bir uzantısı olan Eş Zamanlı Topla Dağıt Araç Rotalama Problemi’ni (ETDARP) çözmektir. Problem NP-Zor olarak bilindiği için Karınca Koloni Sistemi (KKS) ile Değişken Komşuluk Araması’na (DKA) dayanan melez bir metasezgisel alogoritma çözümü geliştirilmiştir. DKA yoğun yerel arama sunan güçlü bir optimizasyon algoritmasıdır. Bununla birlikte, hafıza yapısı bulunmamaktadır. Bu zayıflık KKS’nin uzun süreli hafıza yapısını kullanılarak minimize edilebilir ve bu şekilde algoritmanın genel performansı artırılabilir. Önerilen algoritmada, yerel optimumdan ileri gitmek ve daha çok alan keşfetmek için, karınca yerine DKA kenarlardan feromon salgılarken, karıncalar bu feromon bilgisini kullanarak entegre algoritma için pertürbasyon mekanizması sağlar. Önerilen KKS ile güçlendirilmiş DKA algoritmasının performansı, ETDARP açık literatüründe kıyaslama amacıyla alınan kıyaslama test problemleri ile incelenmiştir. Kıyaslama veri setlerinde, daha kısa sürede sunulan daha iyi sonuçlar, iyi bir performans göstergesi olduğu için geliştirilen yaklaşımın hem çözüm kalitesi hem de CPU süresinde güçlü ve etkili olduğu sayısal sonuçlar ile kanıtlanmıştır.

Since the logistics market is growing rapidly, the optimization of routing systems is of primary concern that motivates the use of vehicle routing problem (VRP) solvers as software components integrated as an optimization engine. A critical success factor of routing optimization is quality vs. response time performance. Less time-consuming and more efficient automated processes can be achieved by employing stronger solution algorithms. This thesis aims to solve the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) which is a popular extension of the basic Vehicle Routing Problem arising in real world applications where pickup and delivery operations are simultaneously taken into account to satisfy the vehicle capacity constraint with the objective of total travelled distance minimization. Since the problem is known to be NP-hard, a hybrid metaheuristic algorithm based on an ant colony system (ACS) and a variable neighborhood search (VNS) is developed for its solution. VNS is a powerful optimization algorithm that provides intensive local search. However, it lacks a memory structure. This weakness can be minimized by utilizing long term memory structure of ACS and hence the overall performance of the algorithm can be boosted. In the proposed algorithm, instead of ants, VNS releases pheromones on the edges while ants provide a perturbation mechanism for the integrated algorithm using the pheromone information in order to explore search space further and jump from local optima. The performance of the proposed ACS empowered VNS algorithm is studied on well-known benchmarks test problems taken from the open literature of VRPSPD for comparison purposes. Numerical results confirm that the developed approach is robust and very efficient in terms of both solution quality and CPU time since better results provided in a shorter time on benchmark data sets is a good performance indicator.