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 the following: 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. |