Retour

Séance TA8 - Tournées de véhicules II / Vehicle Routing Problem II

Jour mardi, le 8 mai 2007
Salle TAL Gestion globale d'actifs inc.
Président Guy Desaulniers

Présentations

10h30-
10h55
A New 2-Variables Formulation for the Undirected m-Peripatetic Salesman Problem
  Éric Duchenne, Université de Valenciennes, LAMIH-ROI, Le Mont Houy, 59313 Valenciennes, Cedex 9, France
Gilbert Laporte, GERAD, HEC Montréal et CRT, Chaire de recherche du Canada en distributique, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
Frédéric Semet, Université de Valenciennes, LAMIH-ROI, Le Mont Houy, 59313 Valenciennes, Cedex 9, France

In the m-Peripatetic Salesman Problem (m-PSP) the aim is to determine m edge disjoint Hamiltonian cycles of minimum total cost on a graph. This presentation introduces a new formulation with two types of variables: the classical edge variables and new edge-edge variables. A branch-and-cut algorithm for the m-PSP according to this formulation and some numerical results on randomly generated and TSPLIB Euclidean instances are presented.


10h55-
11h20
Vehicle Routing Problem with Cross Docking
  Min Wen, Technical University of Denmark, Informatics and Mathematical Modelling, Richard Petersens Plads DTU - Building 305 room 212, Lyngby, Copenhagen, Denmark, 2800
Jesper Larsen, Technical University of Denmark, Informatics and Mathematical Modelling, Build 321, Kgs. Lyngby, Denmark, DK 2800
Jean-François Cordeau, GERAD, HEC Montréal et CRT, Chaire de recherche du Canada en distributique, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
Gilbert Laporte, GERAD, HEC Montréal et CRT, Chaire de recherche du Canada en distributique, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
Jens Clausen, Technical University of Denmark, Informatics and Mathematical Modelling, Richard Petersens Plads DTU - Building 305 room 218, Lyngby, Copenhagen, Denmark, 2800

Over the past decade, cross docking has emerged as a material handling technology in transportation. As a variation of the well-known Vehicle Routing Problem (VRP), the Vehicle Routing Problem with Cross-Docking (VRPCD) becomes a realistic problem in the logistic planning of the supply chain management. This paper addresses the VRPCD, where a set of homogenous vehicles are used to transport goods from the suppliers to the corresponding customers via a cross dock. The goods can be consolidated at the cross dock but cannot be stored during the night as the cross dock does not have the inventory-holding function. The objective of VRPCD is to minimize the total travelling distance while the time windows for each supplier/customer and the time horizon for the whole transportation operation are respected. In this paper, a Mixed Integer Programming formulation for the VRPCD is proposed. A tabu search heuristic based on Cordeau et al. (2001) is embedded in an adaptive memory procedure for solving the problem. The proposed algorithm is implemented and tested on the data provided by Transvision involving up to 200-pair nodes. The preliminary results show that, this algorithm can solve the problem within reasonable computational time.


11h20-
11h45
A Large Neighborhood Search Algorithm for the Vehicle Routing Problem with Time Windows
  Éric Prescott-Gagnon, GERAD et École Polytechnique de Montréal, Mathématiques et génie industriel, Montréal, Québec, Canada, H3C 3A7
Guy Desaulniers, GERAD et École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Louis-Martin Rousseau, Université de Montréal, CRT, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7

Given a fleet of vehicles assigned to a single depot, the vehicle routing problem with time windows (VRPTW) consists of determining a set of feasible vehicle routes to deliver goods to a set of customers while minimizing, first, the number of vehicles used and, second, total mileage. A large number of heuristic approaches for the VRPTW have been proposed in the literature, but none have taken advantage of the power of branch-and-price which is the leading methodology for the exact solution of the VRPTW. In this paper, we present a large neighborhood search algorithm that relies on a heuristic branch-and-price method for neighborhood exploration. To ensure diversification during the search, this approach uses different procedures for defining the neighborhood to explore at each iteration. Computational results on the Solomon's and Homberger's benchmark instances will be reported.


Retour