Project CEMAPRE internal
| Title | Development of an algorithm for vehicle routing problem with backhauls and soft time windows |
| 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 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. |