Information Technology Reference
In-Depth Information
A GRASP for a Multi-depot Multi-commodity
Pickup and Delivery Problem with Time
Windows and Heterogeneous Fleet
in the Bottled Beverage Industry
Roger Z. Rıos-Mercado
1
,J.Fabian Lopez-Perez
2
,
and Andres Castrillon-Escobar
1
1
Universidad Autonoma de Nuevo Leon (UANL), Graduate Program in Systems
Engineering, AP 111-F, Cd. Universitaria, San Nicolas de los Garza, NL 66450,
Mexico
{
roger,andres
}
@yalma.fime.uanl.mx
2
Universidad Autonoma de Nuevo Leon (UANL), Graduate Program in
Management Science, CEDEEM, San Nicolas de los Garza, NL 66450, Mexico
jesus.lopezpz@uanl.edu.mx
Abstract.
A pickup and delivery vehicle routing problem from a real-
world bottled-beverage distribution company is addressed. The problem
consists of deciding how to load every trailer, how to configure the ve-
hicles in terms of the trailers, and how to route the vehicles, so as to
minimize routing and fixed costs. The problem includes several features
such as time windows on both customers and vehicles, multiple depots,
multiple product delivery, split delivery, heterogeneous fleet, and dock
capacity, to name a few. To solve this problem a GRASP-based heuristic
is proposed. Problem decomposition, vehicle composition and route con-
struction mechanisms, and local search procedures for different types of
neighborhoods are developed. The heuristic is empirically assessed over
a wide set of instances. Empirical results show that the proposed method
obtains solutions of better quality than those reported by the company.
Keywords:
Vehicle routing, Pickup and delivery, Multi-commodity,
Heterogeneous fleet, Metaheuristics, GRASP.
1 Introduction
The problem addressed in this paper comes from a bottled beverage distribution
company located in the city of Monterrey, Mexico. This company needs to dis-
tribute its products across several distribution centers. The distribution centers
can also in turn request to withdraw products or relocate products to other cen-
ters. Due to its specific features, this problem is classified as a vehicle routing
problem with pickup and delivery (PDP) with multiple depots.
The problem consists of transporting products among plants and distribution
centers in a network. In each plant, there is a determined number of vehicles that
