MACS-VRPTW:

A Multiple Ant Colony Optimization System for

Vehicle Routing Problems with Time Windows (VRPTW)


IDSIA
Istituto Dalle Molle di Studi sull'Intelligenza Artificiale
Galleria 2, CH-6928 Manno-Lugano
Phone: +41 91 - 6108660
Fax: +41 91 - 6108661
email:
luca@idsia.ch


Luca Maria Gambardella

COURSE on Vehicle Routing Problems: 28-29 November 2000, Technische Universiteit Eindhoven, MetaHeuristics Network


The Problem

The most elementary version of the vehicle routing problem is the capacitated vehicle routing problem (CVRP). The CVRP is described as follows: n customers must be served from a unique depot. Each customer asks for a quantity qi of goods (i = 1,..., n) and a vehicle of capacity Q is available to deliver goods. Since the vehicle capacity is limited, the vehicle has to periodically return to the depot for reloading. In the CVRP, it is not possible to split customer delivery. Therefore, a CVRP solution is a collection of tours where each customer is visited only once and the total tour demand is at most Q.

From a graph theoretical point of view the CVRP may be stated as follows: Let G = (C,L) be a complete graph with node set C = (co, c1, c2,..., cn) and arc set L = (ci, cj): ci, cj Î C, i j. In this graph model, co is the depot and the other nodes are the customers to be served. Each node is associated with a fixed quantity qi of goods to be delivered (a quantity qo = 0 is associated to the depot co). To each arc (ci, cj) is associated a value tij representing the travel time between ci and cj. The goal is to find a set of tours of minimum total travel time. Each tour starts from and terminates at the depot co, each node ci (i = 1,..., n) must be visited exactly once, and the quantity of goods to be delivered on a route should never exceed the vehicle capacity Q.

An important extension of the CVRP is the vehicle routing problem with time windows (VRPTW). In addition to the mentioned CVRP features, this problem includes, for the depot and for each customer ci (i = 0,..., n) a time window [bi, ei] during which the customer has to be served (with b0 the earliest start time and e0 the latest return time of each vehicle to the depot). The tours are performed by a fleet of v identical vehicles. The additional constraints are that the service beginning time at each node ci (i = 1,..., n) must be greater than or equal to bi, the beginning of the time window, and the arrival time at each node ci must be lower than or equal to ei, the end of the time window. In case the arrival time is less than bi, the vehicle has to wait till the beginning of the time window before starting servicing the customer. In the literature the fleet size v is often a variable and a very common objective is to minimize v. Usually, two different solutions with the same number of vehicles are ranked by alternative objectives such as the total traveling time or total delivery time (including waiting and service times).

MACS-VRPTW: A Multiple Ant Colony System for vehicle routing problems with time windows

MACS-VRPTW is an Ant Colony System Optimization based approach useful to solve vehicle routing problems with time windows. MACS-VRPTW is organized with a hierarchy of artificial ant colonies designed to successively optimize a multiple objective function: the first colony minimizes the number of vehicles while the second colony minimizes the traveled distances. Cooperation between colonies is performed by exchanging information through pheromone updating. We show that MACS-VRPTW is competitive with the best known existing methods both in terms of solution quality and computation time. Moreover, MACS-VRPTW improves some of the best solutions known for a number of problem instances in the literature.

Numerical results

Solomon problems

Gambardella L.M., Taillard E., Agazzi G., MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows , In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization. McGraw-Hill, 1999 (Also available as, Tech. Rep. IDSIA-06-99 , IDSIA, Lugano, Switzerland)