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 situations. 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. |