Seminar 4th February 2010 4 p.m. Room 3041, Building 2, Highfield Campus, University of Southampton
The Split Delivery Vehicle Routing Problem
Professor Grazia Speranza
University of Brescia, Italy
- Categories
- Optimisation
- Submitter
- Nicki Lewin
CORMSIS Seminar
In the vehicle routing problem (VRP) the objective is to find a minimum cost set of routes serving all customers where the demand of each customer is not greater than the vehicle capacity and where each customer is visited exactly once. In the split delivery vehicle routing problem (SDVRP) the restriction that each customer is visited once is relaxed. Moreover, the demand of each customer can be greater than the capacity of the vehicles. The SDVRP is NP-hard, even under restricted conditions on the costs, when all vehicles have a capacity greater than two, while it is solvable in polynomial time when the vehicles have a maximum capacity of two. To better understand the relations between the VRP and the SDVRP the complexity of the two problems on specific structures on the underlying graph will be discussed. It turns out that on these structures the SDVRP is never harder than the VRP.
The cost saving that can be obtained by allowing split deliveries can be up to 50% of the cost of the optimal solution of the VRP. The variant of the VRP in which the demand of a customer may be greater than the vehicle capacity, but where each customer has to be visited a minimum number of times, will also be considered. The cost saving that can be obtained by allowing more than the minimum number of required visits can be again up to 50%. Simple heuristics that serve the customers with demands greater than the vehicle capacity by full load out-and-back trips until the demands become less than the vehicle capacity may generate solutions that cost in the worst-case twice the cost of the optimal solution. Finally, the state of the art of exact and heuristic algorithms will be presented.
Tea/coffee will be available before the start of the seminar.