title   
  

Ant colony optimization and its application to the vehicle routing problem with pickups and deliveries

Çatay, Bülent (2009) Ant colony optimization and its application to the vehicle routing problem with pickups and deliveries. In: Chiong, Raymond and Dhakal, Sandeep, (eds.) Natural Intelligence for Scheduling, Planning and Packing Problems. Studies in Computational Intelligence, 250. Springer-Verlag, Germany, pp. 219-244. ISBN 978-3-642-04038-2

This is the latest version of this item.

[img]
Preview
PDF (This is a RoMEO green publisher -- author can archive post-print (ie final draft post-refereeing)) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
858Kb

Official URL: http://dx.doi.org/10.1007/978-3-642-04039-9_9

Abstract

Ant Colony Optimization (ACO) is a population-based metaheuristic that can be used to find approximate solutions to difficult optimization problems. It was first introduced for solving the Traveling Salesperson Problem. Since then many implementations of ACO have been proposed for a variety of combinatorial optimization. In this chapter, ACO is applied to the Vehicle Routing Problem with Pickup and Delivery (VRPPD). VRPPD determines a set of vehicle routes originating and ending at a single depot and visiting all customers exactly once. The vehicles are not only required to deliver goods but also to pick up some goods from the customers. The objective is to minimize the total distance traversed. The chapter first provides an overview of ACO approach and presents several implementations to various combinatorial optimization problems. Next, VRPPD is described and the related literature is reviewed, Then, an ACO approach for VRPPD is discussed. The approach proposes a new visibility function which attempts to capture the “delivery” and “pickup” nature of the problem. The performance of the approach is tested using well-known benchmark problems from the literature.

Item Type:Book Section / Chapter
Subjects:UNSPECIFIED
ID Code:13212
Deposited By:Bülent Çatay
Deposited On:03 Dec 2009 09:55
Last Modified:08 Feb 2010 10:05

Available Versions of this Item

Repository Staff Only: item control page