An ant colony algorithm for the time-independent and time-dependent vehicle routing problem with time windows

Abstract

Araç Rotalama Problemi (ARP), tüm müşteriler yalnızca bir kez ziyaret edilecek ve tek bir rotaya atanan müşterilerin toplam talepleri araç kapasitesini aşmayacak şekilde depodan başlayan ve depoda sonlanan rotaların belirlenmesi problemidir. Amaç, toplamda katedilen mesafenin enküçüklenmesidir. Bir diğer örtülü amaç ise en az sayıda aracın kullanılmasıdır. ARP'nin bir uzantısı olan Zaman Kısıtlı ARP (ZKARP), her bir müşteriye gidilebilecek zaman için en erken ve en geç sınırların tanıtıldığı problemdir. Bu sınırlar dışındaki varış zamanları ya cezalandırılmakta (gevşek zaman kısıtı) ya da tamamıyla yasaklanmaktadır (sıkı zaman kısıtı). Zaman-Bağımlı ARP'nde ise yolculuk zamanları, farklı yol tipleri yanında zaman aralıklarındaki farklı trafik koşullarına bağlı olarak değişkenlik göstermektedir. Bu tezde, hem zaman-bağımlı hem de zaman-bağımsız sıkı zaman kısıtlı ARP ele alınmaktadır. Çözüm yöntemi olarak karınca kolonisi algoritması kullanılmaktadır. Önerilen yaklaşımın performansı literatürdeki problemler üzerinde test edilmektedir.

The Vehicle Routing Problem (VRP) determines a set of vehicle routes originating and terminating at a single depot such that all customers are visited exactly once and the total demand of the customers assigned to each route does not violate the capacity of the vehicle. The objective is to minimize the total distance traveled by all vehicles. An implicit primary objective is to use the least number of vehicles The Vehicle Routing Problem with Time Windows (VRPTW) is a variant of VRP in which lower and upper limits are imposed to the delivery time of each customer. The arrival at a customer outside the specified delivery times is either penalized (soft time windows) or strictly forbidden (hard time windows). In the time-dependent VRP, the travel times between the customers vary due to different traffic conditions in time intervals throughout the scheduling horizon beside different road types. In this thesis, both the time-independent and -dependent VRP with hard time windows are addressed. We tackle these problems using an Ant Colony Optimization approach. The performance of the proposed algorithm is tested on the well-known benchmark instances from the literature.