Project CEMAPRE internal
|Title||Development of an algorithm for the open vehicle routing problem with time windows.|
|Participants||José Brandão (Principal Investigator)|
|Summary||Given a set of customers geographically spread and an unlimited set of identical vehicles, the|
vehicle routing problem (VRP) consists of defining a set of routes that should be travelled by the
vehicles in order to serve the customers at a minimum cost. Each vehicle departs from de 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. Therefore, solving the VRP implies to assign the customers to the vehicles
and to define the order of visiting the customers, such as the constraints are respected and the
total cost is minimized. This is what is called basic VRP. The open vehicle routing problem with
time windows (OVRPTW) is an extension of the basic VRP that assumes that each vehicle does not
return to the depot after visiting the last customer of the route and that each customer must be
served during a given interval of time called time window. This is what happens in many real
The OVRPTW is an NP-hard problem as well as the VRP, but the former is much more complex to solve.
If the time windows are tight, even finding a non trivial feasible solution is an NP-hard problem.
This is the reason why it is important to develop algorithms capable of finding high quality
solutions in reasonable time. Contrary to what happens with the VRP and OVRP, for which a very large
amount of solution methods have been published, for the OVRPTW only very few algorithms are
available. This enhances the importance and the relevance of this project that aims at producing an
algorithm that is able to solve large instances efficiently and providing solutions of high quality.