A revised ant colony system approach to vehicle routing problems

Abstract

ÖZET Araç Rotalama Problemlerinin zaman kısıtı, değişik özellikli araçlar, eşzamanlı dağıtım ve toplama gibi çok çeşitli uzantıları vardır. Bütün problemdeki amaç ise tüm kısıtlan sağlayan kat edilen toplam mesafeyi, kullanılan araç sayısını vs. azaltan optimal rotalar oluşturmaktır. Bu çalışmada çeşitli Araç Rotalama Problemlerinin çözümü için kullanılabilecek karınca kolonisi optimizasyonuna dayanan bir sezgisel yaklaşım önerilmiştir. Modeldeki amaç fonksiyonu, araçlar tarafından kat edilen toplam mesafenin en küçüklenmesidir. Önerilen yaklaşım Zaman Kısıtlı Araç Rotalama Problemine ve Eş Zamanlı Dağıtım ve Toplamalı Araç Rotalama Problemine uygulanmıştır. Tüm araçlar aynı özelliklere sahiptir ve araçların kapasiteleri göz önünde bulundurulmaktadır. Önerilen sezgisel yöntem dört aşamadan oluşmaktadır, ilk olarak hesaplama zamanım azaltmak için aday listeleri oluşturulur. İkinci olarak olurlu bir çözüm bulunur ve bu çözüm kullanılarak her bir yol üzerindeki başlangıç feromen seviyeleri hesaplanır. Daha sonra Dorigo (1997) tarafından önerilen yönteme dayanılarak rotalar oluşturulur. Rotaların oluşturulması sırasında uygunluk hesaplanırken müşteriler arasındaki uzaklık, müşterilerin depoya olan uzaklıkları ve zaman kısıtı göz önünde bulundurulur. Feromen seviyeleri ise hem yerel hemde global feromen yenileme yöntemleri ile değiştirilir. Son olarak oluşturulan rotalar 2-opt algoritmasi kullanılarak iyileştirilir. Algoritma, zaman kısıtlı araç rotalama problemi için Solomon'un 1987 yılında oluşturduğu kıyaslama problemi örnekleri ile, eş zamanlı dağıtım ve toplamalı araç rotalama problemi için ise Min' in 1989 yılında ve Dethloff un 2001 yılında oluşturduğu kıyaslama problemi örnekleri ile test edilmiştir. Algoritma, problemlerin literatürde bilinen en iyi sonuçlan ile karşılaştırldığında iyi sonuçlar vermektedir.

ABSTRACT Vehicle routing problems have various extensions such as time windows, multiple vehicles, backhauls, simultaneous delivery and pick-up, etc. The objectives of all these problems are to design optimal routes minimizing total distance traveled, minimizing number of vehicles, etc that satisfy corresponding constraints. In this study, an ant colony optimization based heuristic that can be used to solve various vehicle routing problems is proposed. The objective function minimizes the total distance traveled by all vehicles. The heuristic is applied to vehicle routing problem with time windows and vehicle routing with simultaneous delivery and pick up. Vehicles are identical and capacities of the vehicles are finite. The time window constraints in the first problem are assumed to be strict. The proposed heuristic consists of four steps. First, a candidate list is formed for each customer in order to reduce computational time. Second, a feasible solution is found, and initial pheromone trails on each arc is calculated using it. Then, routes are constructed based on Dorigo et al. (1996). While visibility is calculated during route construction process, the distance between two customers, customers' distance to the depot and the time window associated with the customer to whom the ant is considered to move are considered. Pheromone trails are modified by both local and global pheromone update. Finally, constructed routes are improved using 2-opt algorithm. The algorithm has been tested on the benchmark problem instances of Solomon (1987) for vehicle routing problem with time windows, and benchmark problem instances of Min (1989) and Dethloff (2001) for vehicle routing with simultaneous delivery and pick-up. The algorithm is proven to give good results when compared to the best known results in the literature.