Research projects

Project CEMAPRE internal

TitleDevelopment of an algorithm for vehicle routing problem with backhauls and soft time windows
ParticipantsJosé Brandão (Principal Investigator)
SummaryThe 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 that belong to
the route assigned to it in a given sequence and, after visiting the last customer, returns to the
depot. The main constraints are the following: each customer must be visited exactly once by one of
the vehicles and his requirements should be completely fulfilled; the capacity of the vehicle cannot
be exceeded and the total time travelled by a vehicle must not pass a given threshold. This is what
is called basic VRP. The vehicle routing problem with backhauls and soft time windows (VRPBSTW) is
an extension of the basic VRP, which contains the following additional characteristics:
i) There two distinct sets of customers: those that receive goods from the depot, who are called
linehauls, and those that send goods to the depot, named backhauls. In each route the linehauls have
to be served before the backhauls.
ii) 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.
There are many real situations that can be modelled as a VRPBSTW. An example is the distribution of
drinks, where the delivery of full bottles is followed by the collection of empty ones at the end of
the route.
The VRPBSTW is a NP-hard problem as well as the VRP. However, the additional constraints existing in
the VRPBSTW make it much more difficult to solve, especially due to the time windows. So far as I
know, there is no published paper for VRPBSTW and even for VRPBTW, i.e., the same problem with hard
time windows, the number of papers is rather scarce. Therefore, these are good reasons for
developing algorithms for the VRPBSTW.