Project CEMAPRE internal
|Title||Development of metaheuristics for two variants of the vehicle routing problem.|
|Participants||José Brandão (Principal Investigator)|
|Summary||The vehicle routing problem (VRP) consists of defining a set of routes that should be travelled by a|
set of vehicles in order to serve a given number of customers, with known demand and geographical
location, at a minimum cost. Each vehicle departs from the depot visits the customers of the route
assigned to it and, after visiting the last customer, returns to the depot. The main constraints are
the following: each customer must be visited exactly once; the capacity of the vehicle cannot be
exceeded and the total time travelled by a vehicle must not pass a given threshold. The current
project aims at studying two variants of the VRP, which contain some additional constraints that
make them more realistic: the vehicle routing problem with backhauls and soft time windows (VRPBSTW)
and the multi-depot open vehicle routing problem (MDOVRP). Their main additional characteristics are
1 - The VRPBSTW contains two distinct sets of customers: those that receive goods from the depot
(linehauls) and those that send goods to the depot (backhauls). In each route the linehauls have to
be served before the backhauls. To each customer is associated an interval of time (time window),
during which each one should be served. If the time window can be violated it is called soft, but
this violation implies an additional cost.
2 - In the MDOVRP there are several depots and each customer can be served from any of them. This
VRP is called open because the vehicle does not return to the depot after visiting the last customer
of the route. This happens in practice when the vehicles are hired.
In terms of computational complexity, both the VRPBSTW and MDOVRP are NP-hard. So far as I know,
there is no published paper for the VRPBSTW and there are very few for the MDOVRP.