Routing a Heterogeneous Fleet of Vehicles

Routing a Heterogeneous Fleet of Vehicles

Roberto Baldacci, Maria Battarra, and Daniele Vigo

DEIS, University of Bologna

via Venezia 52, 47023 Cesena, Italy

{rbaldacci, mbattarra, dvigo}@deis.unibo.it

Summary. In the well-known Vehicle Routing Problem (VRP) a set of identical

vehicles, based at a central depot, is to be optimally routed to supply customers

with known demands subject to vehicle capacity constraints.

An important variant of the VRP arises when a fleet of vehicles characterized

by different capacities and costs is available for distribution activities. The problem

is known as the Mixed Fleet VRP or as the Heterogeneous Fleet VRP.

This chapter gives an overview of approaches from the literature to solve heterogeneous

VRPs. In particular, we classify the different variants described in the

literature and, as no exact algorithm has been presented for any variants of heterogeneous

VRP, we review the lower bounds and the heuristic algorithms proposed.

Computational results, comparing the performance of the different heuristic algorithms

on benchmark instances, are also discussed.

Key words: Heterogeneous vehicle routing problem.

1 Introduction

The Vehicle Routing Problem (VRP) is one of the most studied combinatorial

optimization problems and is concerned with the optimal design of routes

to be used by a fleet of vehicles to serve a set of customers. Since it was

first proposed by Dantzig and Ramser [15], hundreds of papers have been

devoted to the exact and approximate solution of the many variants of this

problem, such as the Capacitated VRP (CVRP), in which a homogeneous

fleet of vehicles is available and the only constraint is the vehicle capacity,

or the VRP with Time Windows (VRPTW), where customers may be served

within a specified time interval and the schedule of the vehicle trips needs to

be determined.

More recently, greater attention has been devoted to more complex variants

of the VRP, sometimes named ¡°rich¡± VRPs, that are closer to the practical

distribution problems that the VRP models. In particular, these variants

are characterized by multiple depots, multiple trips to be performed by the

B. Golden et al. (eds.), The Vehicle Routing Problem,

doi: 10.1007/978-0-387-77778-8 1, c Springer Science+Business Media, LLC 2008

4 Baldacci, Batarra, and Vigo

vehicles, multiple vehicle types or other operational issues such as loading

constraints. Trying to systematize such a huge literature is a challenging and

useful activity that has attracted considerable efforts in the scientific community.

Among the various surveys on the VRP are the book by Toth and Vigo

[55] and the more recent update by Cordeau et al. [14]. Specific surveys of

rich VRPs may be found in Br¡§aysy et al. [6].

This chapter considers an important variant of the VRP, in which a fleet

of vehicles characterized by different capacities and costs, is available for the

distribution activities. The problem is known as the Mixed Fleet VRP or as

the Heterogeneous Fleet VRP and was first considered in a structured way in

Golden et al. [30].

We examine the basic problem including capacity constraints only, which

has received greater attention in the literature, as well as the more recently

studied variants including time window constraints. Moreover, we briefly review

a related variant known as the Site-Dependent VRP (SDVRP), where

there are compatibility relations between customers and vehicle types. Additional

case studies and applications related to the solution of Heterogeneous

VRPs can be found in Semet and Taillard [48], Rochat and Semet [45],

Brand.ao and Mercer [5], Prins [43], Wu et al. [57] and Tavakkoli-Moghaddam

et al. [53]. In addition, Engevall et al. [19] use a game-theoretic approach to

model the problem of allocating the cost of the heterogeneous fleet to the

customers.

This chapter is organized as follows. The next section introduces the notation

used throughout the chapter and describes the variants of heterogeneous

VRPs with capacity constraints studied in the literature. Section 3 presents

the main integer programming formulations and discusses lower bounding approaches.

Section 4 reviews heuristics and metaheuristics and reports on their

performances. Finally, the last section offers conclusions and suggestions for

future research.

2 Notation and Problem Variants

A directed graph G = (V,A) is given, where V = {0, 1, . . ., n} is the set of

n + 1 nodes and A is the set of arcs. Node 0 represents the depot, while the

remaining node set V  = V \{0} corresponds to the n customers.

Each customer i ¡ô V  requires a supply of qi units from the depot

...