Yıldırım, Mahir Umman and Çatay, Bülent (2009) An ant colony algorithm for timedependent vehicle routing problem with time windows. In: Annual International Conference of the German Operations Research Society, 2008, Augsburg, Germany
This is the latest version of this item.
PDF (This is a RoMEO green publisher  author can archive postprint (ie final draft postrefereeing))
ant_colony.pdf
Download (276kB)
ant_colony.pdf
Download (276kB)
Official URL: http://dx.doi.org/10.1007/9783642001420_55
Abstract
In this paper, we address the Vehicle Routing Problem with Time Windows, both timeindependent and dependent cases. In the timeindependent case, our objective is to minimize the total distance. To solve this problem, we propose an Ant Colony Optimization algorithm. Then we implement the algorithm to solve the timedependent case where the objective is to minimize the total tour time. The time dependency is embedded in this model by using a deterministic travel speed function which is a step function of the time of the day. An experimental evaluation of the proposed approach is performed on the wellknown benchmark problems Optimizing a distribution network has been and remains an important challenge both in the literature and in reallife applications and the routing of a eet of vehicles is the most widely addressed problem in a distribution network. 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. 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 time is either penalized (soft time windows) or strictly forbidden (hard time windows). The interested reader is referred to [1] for more details on VRPTW. In the Stochastic Vehicle Routing Problem, the customer demands and/or the travel times between the customers may vary. Although stochastic travel times and demand distributions have been frequently used in the literature, timevarying travel speeds and timedependent VRPTW (TDVRPTW) have seldom been addressed. In the literature, time dependency is taken into consideration in two ways: stochastic travel times and deterministic travel times. First introduced by [2], stochastic travel times are mainly examined by [4] and [3]. [5] proposeda deterministic travel time based model in which the important nonpassing property is introduced. [6] and [7] also use deterministic travel times in a setting where the day is divided into time intervals.
Item Type:  Papers in Conference Proceedings 

Subjects:  T Technology > T Technology (General) 
Divisions:  Faculty of Engineering and Natural Sciences 
Depositing User:  Bülent Çatay 
Date Deposited:  10 Nov 2009 14:45 
Last Modified:  26 Apr 2022 08:52 
URI:  https://research.sabanciuniv.edu/id/eprint/12609 
Available Versions of this Item

An ant colony algorithm for timedependent vehicle routing problem with
time windows. (deposited 24 Oct 2008 10:50)
 An ant colony algorithm for timedependent vehicle routing problem with time windows. (deposited 10 Nov 2009 14:45) [Currently Displayed]