Vrp Multiobjetivo

Available online at www.sciencedirect.com

European Journal of Operational Research 189 (2008) 293–309 www.elsevier.com/locate/ejor

Invited Review

Multi-objective vehicle routing problems
Nicolas Jozefowiez
a

a,b

´ ´ , Frederic Semet

b,*

, El-Ghazali Talbi

a

´ Laboratoire d’Informatique Fondamentale de Lille, Universite des Sciences et Technologies de Lille, Villeneuved’Ascq, France b ´ Laboratoire d’Automatique, de Mecanique et d’Informatique industrielles et Humaines, ´ ´ Universite de Valenciennes et du Hainaut-Cambresis, Valenciennes, France Received 31 March 2006; accepted 31 May 2007 Available online 15 June 2007

Abstract Routing problems, such as the traveling salesman problem and the vehicle routing problem, are widely studied both because of theirclassic academic appeal and their numerous real-life applications. Similarly, the field of multi-objective optimization is attracting more and more attention, notably because it offers new opportunities for defining problems. This article surveys the existing research related to multi-objective optimization in routing problems. It examines routing problems in terms of their definitions, theirobjectives, and the multi-objective algorithms proposed for solving them. Ó 2007 Elsevier B.V. All rights reserved.
Keywords: Combinatorial optimization; Routing; Multi-objective programming

1. Introduction This article provides an overview of the research into routing problems with several objectives. By routing problems, we mean any problem that involves of generating a tour, or a collection oftours, on a network, or a subset of a network, given a set of constraints and the need to optimize one or several fixed objective(s). Together, routing problems form a highly-studied family of problems that includes the well-known traveling salesman problem. Although such problems are frequently used to model real cases, they are often set up with the single objective of minimizing the cost of thesolution, despite the fact that the majority of the probCorresponding author. Tel.: +33 0 3 27 51 19 55. E-mail address: frederic.semet@univ-valenciennes.fr (F. Semet).
*

lems encountered in industry, particularly in logistics, are multi-objective in nature. In real-life, for instance, there may be several costs associated with a single tour. Moreover, the objectives may not always be limited tocost. In fact, numerous other aspects, such as balancing of workloads (time, distance . . .), can be taken into account simply by adding new objectives. A routing problem can be defined in terms of the following components: the network, the demand(s), the fleet, the cost(s), and the objective(s). • The network can be symmetrical, asymmetrical or mixed. It is represented as a graph on which the nodesstand for towns, customers and/or depots, while arcs stand for real links (e.g., roads, pipelines) or symbolic connections. On valuated graphs, a value generally represents the cost of traversing an arc. Time windows associated with

0377-2217/$ - see front matter Ó 2007 Elsevier B.V. All rights reserved. doi:10.1016/j.ejor.2007.05.055

294

N. Jozefowiez et al. / European Journal ofOperational Research 189 (2008) 293–309

•

•

•

•

nodes or arcs may also be defined in some problems. The demands can be fixed or stochastic, can be associated with both nodes and arcs, and can be given for one or several product(s). Generally, demands appear in distribution problems, in which a certain amount of a given product must be delivered to certain nodes (i.e., customers) or musttravel along a certain arc (i.e., delivery route). Demands are also a part of pick-up and delivery problems, in which demanded goods must first be picked up at a specific location and then be delivered elsewhere. The fleet generates constraints that affect the tours. A fleet can be heterogeneous or homogeneous. It can be composed of a single vehicle or several vehicles, whose use may, or may not, be...