Information Technology Reference
In-Depth Information
can be used to do the routing. In addition, a decision has to be made so as to haul
one or two trailers into a vehicle. This decision has two main effects. As it turns
out, both the cost and time of traveling between two given points depend on
whether the vehicle is single or double. A single vehicle travels faster and costs
less than a double vehicle. However, a double vehicle has more capacity and
can carry a larger amount of product between points. There are time windows
requirements in both distribution centers and vehicles. The later is due to the
fact that a daily maintenance for each vehicle must be performed at specific
times. The orders can be split into several deliveries and vehicles can also visit
several times a distribution center if necessary. The planning horizon is daily. In
addition, there is a dock capacity in each distribution center that must be met.
Each vehicle must return to its original depot by the end of the day.
Each trailer has two compartments: one on the top and one on the bottom. For
each trailer, the capacity of both top and bottom is known, but not necessarily
equal for every trailer. Moreover, some trailers may have a fixed shelf (or division
between the top and bottom compartments) which would become an important
issue when loading the products. There are many different products handled by
the company; however, by and large they can be divided into two main types of
products: returnable (type R) and non-returnable (type N). This distinction is
important because type R products are heavier. As a direct consequence of this,
the following loading rules must be met: (i) if the trailer has a shelf, any product,
regardless its type, can be placed in any part of the trailer compartments; (ii) if
the trailer does not have a shelf, it is strictly forbidden to place a type R product
on top of a type N product due to the weight difference between products. It is
assumed that when a product of type R is delivered to a customer a matching
amount of empty type R bottles is picked up. The goal is to find the best route
configuration that minimizes the total cost associated with the product routing
and vehicle usage. In doing so, decisions so as to what type of vehicle is to be
used and how each trailer must be loaded must be made simultaneously.
Although the field of vehicle routing, particularly the class of PDPs, has been
widely studied (e.g. [3, 6, 8-10]), to the best of our knowledge there is no other
work in the literature addressing a PDP with all the features mentioned previ-
ously simultaneously present, namely, multiple depots, heterogeneous vehicles,
time windows at nodes and vehicles, split deliveries, multiple products, vehicles
with compartments, dock capacity. For recent extensive surveys on PDPs the
reader is referred to the work of Berbeglia et al. [1], Drexl [4], and Parragh
et al. [7].
In this paper, we introduce a mixed-integer linear programming (MILP) model
for this problem. Given its inherent computational complexity, we propose a
metaheuristic framework that combines decomposition, greedy randomized con-
struction, and local search components. The effectiveness of the heuristic is em-
pirically assessed. It was found that the proposed method found better routings
and truck configurations than those reported by the company, resulting in im-
portant cost reductions.
