SEMINAR
| Title |
An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem
[PDF announcement] |
| Speakers | ARCHETTI, Claudia (University of Brescia, Italie) |
| Date | Tuesday, November 13, 2007 |
| Time | 10h45 AM |
| Place | Salle 6516, Pavillon André-Aisenstadt Campus de l'Université de Montréal 2920, chemin de la Tour |
|
Abstract In vehicle routing problems (VRPs) a set of customers needs to be served and a fleet of capacitated vehicles is available to do so. The objective is the minimization of costs, which usually means minimizing the total distance traveled. In most VRPs it is assumed that the demand of a customer is less than or equal to the capacity of a vehicle and that each customer has to be served by exactly one vehicle, i.e., there is a single-visit assumption. While it is obvious that when a customer’s demand exceeds the vehicle capacity it is necessary to visit that customer more than once, it requires only a little more thought to see that even when all customer demands are less than or equal to the vehicle capacity, it may be beneficial to use more than one vehicle to serve a customer. In the split delivery vehicle routing problem (SDVRP) the single-visit assumption is relaxed and each customer may be served by more than one vehicle. We present a solution approach for the SDVRP that integrates heuristic search with optimization by using an integer program to explore promising parts of the search space identified by a tabu search heuristic. Computational results show that the method is able to improve the solution of the tabu search in all but one instance of a large test set. Pour plus d'information, veuillez contacter Alain Hertz (alain.hertz@gerad.ca). |
|
| Organizer | Pierre Hansen (pierre.hansen@gerad.ca) |
