Multi objetivo ant colony system

A MULTIOBJECTIVE ANT COLONY SYSTEM FOR VEHICLE ROUTING PROBLEM WITH TIME WINDOWS
Benjamín Barán and Matilde Schaerer Centro Nacional de Computación, Universidad Nacional de Asunción San Lorenzo, P.O. Box 1439 Paraguay bbaran@cnc.una.py, schma@rieder.net.py

ABSTRACT
This paper proposes a variation of the Multiple Ant Colony System for Vehicle Routing Problem with Time Windows (MACS-VRPTW)algorithm, which is based on an Ant Colony System approach, using two ant colonies to minimize first the number of vehicles and then the total traveled distance. As an improvement, the present work proposes to use a modified version specialized for a multiobjective context, using just one colony to get a set of Pareto optimal solutions considering three objectives at the same time, the number ofvehicles, the total traveling time and the total delivery time. Experimental results validate the new approach with very good results when compared to the original MACS-VRPTW.

The spatial problem of routing vehicles has been extensively studied in the literature. Several approaches have been published dealing with it, using parallel implementations [3], hybrid strategies coupling local searchmethod to evolutionary algorithm [4], neuronal network [5, 6], a heuristic that uses pheromone information [7], and works that deal with this problem using evolutionary calculation to optimize the demand for each vehicle besides the optimization of the vehicle number and the total traveling time [8]. More recently, the time window constraint has been considered and many approaches have been presentedto solve the VRPTW: parallel algorithms with a polynomial number of processor [9], genetic algorithm [10, 11, 12, 13], and parallel simulated annealing [14, 15]. In this context, MACS-VRPTW [16] was developed as an evolutionary proposal based on Ant Colony System (ACS), and more generally, on Ant Colony Optimization (ACO), with the aim of optimizing two objective functions, as summarized in section3. In fact, ACO is a metaheuristic approach that imitates ants’ behavior, where ants cooperate in their search for food by depositing chemical traces (pheromones). In a computational implementation, ants that found good solutions deposit pheromones in their paths. That way, ants of the following generations may decide with good probability to follow a good trace with greater quantity ofpheromones. This paper is concerned with solution construction for the VRPTW using ACS. The approach presented may be considered an extension of the MACS-VRPTW algorithm for a truly multiobjective context. The novelty of the presented approach consists in incorporating the Pareto optimal concept in such a way that the final solution is not a single optimum but a whole set of Pareto optimal solutions whereall objectives are equally considered, i.e., a set of solutions where no solution can be improved in any objective without damaging other objectives [17]. The rest of this work is organized as follows: section 2 formalizes the problem, section 3 introduces the MACSVRPTW while its improved version is presented in
97

KEY WORDS
Multiobjective optimization, Ant Colony Optimization, VehicleRouting Problem with Time Windows, Pareto Optimal Set.

1. INTRODUCTION
The Vehicle Routing Problem with Time Windows (VRPTW) [1] is an extension of the Vehicle Routing Problem (VRP) [2], in which the aim is to find a set of minimum-cost vehicle routes, that originates and terminates at a central depot, for a fleet of vehicles that serve a given set of customers with known demand. Each customer isserved exactly once and all the customers must be assigned to vehicles without exceeding vehicle capacities. VRPTW added to these issues the complexity of allowable delivery times, or time windows. With the time windows, the total routing and scheduling cost include not only the total travel distance and time costs, but also the cost of waiting time incurred when a vehicle arrives too early at a...