Retour

Séance WA8 - Tournées de véhicules V / Vehicle Routing Problem V

Jour mercredi, le 9 mai 2007
Salle TAL Gestion globale d'actifs inc.
Président Stefan Ropke

Présentations

10h30-
10h55
A Branch-and-Cut Algorithm for the Undirected Capacitated Arc Routing Problem
  Gianpaolo Ghiani, Universita di Lecce, Ingegneria, Strada per Arnesano, Lecce, Italy, 73100
Demetrio Laganà, Università della Calabria, Italy
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
Roberto Musmanno, Universita della Calabria, Elettronica, Informatica e Sistemistica, Rende, CS, Italy, 87036

The Capacitated Arc Routing Problem (CARP) consists of determining a set of least cost capacitated vehicle routes servicing a set of arcs. The undirected CARP is formulated as a pure binary linear integer problem. Valid inequalities are generated and the problem is solved by branch-and-cut. All the benchmark instances proposed by DeArmon and Benavent et al. can be solved without any branching, for the first time ever.


10h55-
11h20
Branch-Cut-and-Price for the Capacitated Vehicle Routing Problem with Two-Dimensional Loading Constraints
  Stefan Ropke, HEC Montréal, CRT, Chaire de recherche du Canada en distributique, Université de Montréal, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7
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
Manuel Iori, University of Modena and Reggio Emilia, DISMI, Viale Amendola 2, Reggio Emilia, Italy, 42100
Daniele Vigo, Università di Bologna, DEIS, Via Risorgimento 2, Bologna, Italy, 40100

We describe a branch-and-cut-and-price algorithm for the vehicle routing problem with two-dimensional loading constraints. This problem extends the classical vehicle routing problem by considering that items demanded by the customer must be packed into the space available in the vehicle serving the customer, together with other items delivered by the vehicle.


11h20-
11h45
Pattern-Based Dynamic Guided Cooperative Search for the Vehicle Routing Problem with Time Windows
  Teodor Gabriel Crainic, Université du Québec à Montréal et CRT, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7
Alexandre Le Bouthillier, Université de Montréal, CRT, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7
Peter Kropf, Université de Montréal, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7

A guided cooperative-search mechanism identifies promising patterns in previously identified solutions and the global search while controlling the diversification and intensification phases. The mechanism is based on the solution warehouse strategy, in which several search processes cooperate by asynchronously exchanging information on the best solutions identified. Each of the independent processes implements a different search, a metaheuristic such as evolutionary algorithm, a tabu search, a random search or a post-optimization procedure. Patterns of elements in promising and unpromising solutions are identified and used to guide the search. We propose an enhancement to the cooperative search with a dynamic guidance mechanism to orient the search by controlling automatically the diversification and intensification phases. The variation in entropy of the solution warehouse is used as a metric to control these phases and to prevent premature convergence. No attempt has been made to calibrate the individual search methods, the parallel cooperative method or the dynamic guidance mechanism. The results obtained on a set of selected test problems of the vehicle routing problem with time windows shows that the dynamically guided cooperative search performs better than other cooperatives methods. It identifies solutions of comparable quality to those obtained by the best methods in the literature and finds one new best result. Keywords : parallel cooperative search, dynamic guidance, entropy, vehicle routing with time windows


11h45-
12h10
On Flow Based Formulations for Capacitated Arc-Routing Problems
  Maria Cândida Mourão, Universidade Técnica de Lisboa, Inst Superior de Economia e Gestão / Centro IO, Rua do Quelhas, 6, Lisboa, PORTUGAL, 1200-781
Leonor S. Pinto, Universidade Técnica de Lisboa, Instituto Superior de Economia e Gestão / CEMAPRE, Rua do Quelhas, 6, Lisboa, Portugal, 1200-781
Luis Gouveia, Universidade de Lisboa, DEIO-CIO Faculdade de Ciências, Cidade Universitaria Bloco C6 Piso 4, Campo Grande, Lisboa, Portugal, 1749-016

The Capacitated Arc Routing Problem (CARP) is a well known NP-hard problem. In this talk we discuss the use of several flow based formulations for an extended mixed CARP. These formulations are evaluated over a set of benchmark problems.


Retour