|
|
|
Session TA10 - Tournées de véhicules III / Vehicle Routing III
Day |
Tuesday, May 10, 2005 |
Location |
TAL Gestion globale d'actifs inc. |
Chair |
Jean-François Cordeau |
Presentations
10h30 AM |
The Multi-Commodity Pickup-and-Delivery Travelling Salesman Problem |
|
Juan-José Salazar González, Universidad de La Laguna, DEIOC, Canary Islands, La Laguna, Tenerife, Spain, E-38271
Hipólito Dr. Hernández Pérez, University of La Laguna, DEIOC, La Laguna, Tenerife, Spain, E-38271
This talk concerns the problem of finding a Hamiltonian route for a capacitated vehicle serving a set of customers.
Each customer delivers and/or require known demands of some products. A product can have single or multiple sources and destinations. The routing costs are known, and the problem is to find the shortest route if one exists. We write a mathematical model for this problem and develop a branch-and-cut technique for the exact solution. We also show some preliminary computational results on small instances.
|
10h55 AM |
New Polyhedral Results for the Pickup and Delivery Problem |
|
Irina Dumitrescu, HEC Montréal, Chaire de recherche du Canada en distributique, Montreal, Canada
Jean-François Cordeau, HEC Montréal, CRT, GERAD et Chaire de recherche du Canada en distributique, 3000, ch. de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
Gilbert Laporte, HEC Montréal, GERAD, CRT et Chaire de recherche du Canada en distributique, 3000, ch. de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
Stefan Ropke, University of Copenhagen, Computer Science (DIKU), Universitetsparken 1, Copenhagen, Denmark, 2100
Given a vehicle and a set of customers who have some explicit pickup and delivery requests, the Pickup and Delivery Problem (PDP) consists of designing vehicle routes so that all customer requests are satisfied. Each request specifies a pickup and a delivery location. The vehicle must visit each pickup location before its corresponding delivery one. With this constraint, the PDP can be seen as a TSP with precedence constraints. We will review polyhedral results existent in the literature and propose new classes of valid inequalities. We will give conditions under which some classes of inequalities are facets for the PDP polytope. Preliminary numerical results for a branch-and-cut algorithm will be presented.
|
11h20 AM |
Solving Pickup and Delivery Problems with Time Windows Using Column Generation |
|
Stefan Ropke, University of Copenhagen, Computer Science (DIKU), Universitetsparken 1, Copenhagen, Denmark, 2100
Jean-François Cordeau, HEC Montréal, CRT, GERAD et Chaire de recherche du Canada en distributique, 3000, ch. de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
This talk presents an exact column generation algorithm for the pickup and delivery problem with time windows. Computational tests show that instances with up to 500 requests can be solved to optimality when time windows are tight. We also show how dial-a-ride problems can be solved using column generation
|
11h45 AM |
Metaheuristics for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading |
|
Francesco Carrabs, University di Salerno, Matematica ed Informatica, Via Ponte don Melillo, Fisciano, Salerno, Italy, 84081
Jean-François Cordeau, HEC Montréal, CRT, GERAD et Chaire de recherche du Canada en distributique, 3000, ch. de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
Gilbert Laporte, HEC Montréal, GERAD, CRT et Chaire de recherche du Canada en distributique, 3000, ch. de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
This paper addresses a variation of the traveling salesman problem with pickup and delivery in which loading and unloading operations have to be executed in a LIFO (Last-in-First-Out) order. We present tabu search and variable neighbourhood search metaheuristics based on three exchange operators specially adapted to this problem. We also evaluate the performance of the metaheuristics on instances from TSPLIB.
|
|