Home
Poster (PDF)
 
Attendees
Conference program
Registration
Location
Hotel information
Links
 
 
Previous editions
2004
2003
2002


    

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.