Retour

Séance MA8 - Tournées de véhicules I / Vehicle Routing Problem I

Jour lundi, le 7 mai 2007
Salle TAL Gestion globale d'actifs inc.
Président Gilbert Laporte

Présentations

10h30-
10h55
An Exact Algorithm for the Vehicle Routing Problem Based on the Set Partitioning Formulation with Additional Cuts
  Aristide Mingozzi, University of Bologna, Department of Mathematics, Via Sacchi 3, Cesena, Italy, 47023
Nicos Christofides, Imperial College, Centre for Quantitative Finance, Exhibition Road, London, UK, SW7 2PG
Roberto Baldacci, University of Bologna, DEIS, Via Venezia 52, Cesena, Italy, 47023

In this paper we present a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. We describe a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation of the CVRP. The second one combines Lagrangean relaxation and column/cut generation and the third attempts to close the duality gap left by the first two procedures using a classical column/cut generation technique. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between an upper bound and the lower bound achieved. The resulting problem is solved by an integer programming solver. Computational results over the main instances from the literature show the effectiveness of the proposed algorithm.


10h55-
11h20
The Vehicle Routing Problem with Multiple Trips
  Justin Goodson, The University of Iowa, Department of Management Sciences, S210 John Pappajohn Business Building, Iowa City, IA, USA, 52242-1000
Jeffrey Ohlmann, University of Iowa, Management Sciences, S210 Pappajohn Business Bldg, Iowa City, IA, USA, 52242-1000
Barrett W. Thomas, University of Iowa, Management Sciences, S210 Pappajohn Business Building, Iowa City, IA, USA, 52242-1000

We explore heuristics for the vehicle routing problem with multiple trips (VRPM). Unlike the classical vehicle routing problem, the VRPM permits vehicles to make multiple trips to and from a central depot within a given time duration. We begin by constructing routes via a petal heuristic. These routes are then combined to form a large number of linked routes. In contrast to previous research on the VRPM, which predominantly takes a bin-packing approach to route linking, we explicitly combine routes within the route duration limit. We then obtain a solution by solving a large scale set covering problem to select a subset of these routes. Finally, we present the results of this approach and compare them to those of other VRPM solution methodologies.


11h20-
11h45
Automatic Model Adjustment and the Scheduling of Vehicles in Evolving Environments
  Herbert Kopfer, University of Bremen, Chair of Logistics, Wilhelm-Herbst-Straße 5, Bremen, Germany, 28359
Jörn Schönberger, University of Bremen, Chair of Logistics, Wilhelm-Herbst-Straße 5, Bremen, Germany, 28359

The decision about the adequate fulfilment mode of consecutively arriving requests is a basic task of the operation transport planning. From the two modes self fulfilment (with own equipment) or subcontracting (deploying a service partner) the cheaper one is typically selected. However, in some unpredictable situations it is appropriate to deviate from this minimal cost strategy and to prefer the more expensive but more reliable mode of transport. In this contribution, we discuss general strategies to code such a strategy in an online optimization model. Furthermore, we propose generic models that adapt themselves to the current system state by modifying the search direction (objective) as well as the search space in order to consider not only cost criteria but reliability issues as well. The general applicability of such an approach is evaluated in comprehensive numerical results.


11h45-
12h10
Vehicle Routing Problem with Profits and Partial Coverage
  Gunes Erdogan, CRT et HEC Montréal
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

This study analyzes the problem of maximizing the profit collected by a traveling service facility that performs a tour. The facility collects the whole profit from the visited cities and partial profit from unvisited cities, which depends on the attractiveness of the visited cities and distance from the visited cities.


Retour