Accueil
Affiche (PDF)
 
Participants
Programme
Inscription
Site
Hébergement
Liens
 
 
Éditions précédentes
2004
2003
2002


    

Séance MB10 - Tournées de véhicules II / Vehicle routing II

Jour lundi, le 09 mai 2005
Salle TAL Gestion globale d'actifs inc.
Président Adam Letchford

Présentations

15h30 The Undirected m-Peripatetic Salesman Problem: Polyhedral Results and New Algorithms
  Éric Duchenne, Université de Valenciennes, LAMIH-ROI, Le Mont Houy, 59313 Valenciennes, Cedex 9, France
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
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 new valid inequalities, polyhedral results and an improved 2-index branch-and-cut algorithm for the m-PSP. Tests performed on randomly generated and TSPLIB Euclidean instances indicate that this algorithm can solve instances with more than double size of what was previously achievable.


15h55 Solving the Precedence Constrained Asymmetric Traveling Salesman Problem with an Extended Formulation
  Pierre Pesneau, Universidade de Lisboa, Ciências, Cidade Universitaria Bloco C6 Piso 4, Campo Grande, Lisboa, Portugal, 1749-016
Luis Gouveia, Universidade de Lisboa, DEIO-CIO Faculdade de Ciências, Cidade Universitaria Bloco C6 Piso 4, Campo Grande, Lisboa, Portugal, 1749-016

We present formulations for the Precedence Constrained Assymetric Travelling Salesman (PCATS) problem obtained by relating formulations of the ATS problem with formulations of the so-called linear ordering problem. We introduce several exponential sized sets of cut-like inequalities to link formulation of these two problems. From a practical point of view, we discuss polynomial routines to separate these inequalities and give preliminary results evaluating the strength of our formulations.


16h20 Fast Separation for the Planar TSP
  Nick Pearson, Lancaster University, United Kingdom
Adam Letchford, Lancaster University, Management Science, Lancaster, U.K., LA1 4YX

It is well known that the TSP remains NP-hard even when the underlying graph is planar. However, there are indications that the planar TSP is in some sense 'easier' than the TSP on general graphs: i) a sub-exponential time exact algorithmis known for the planar TSP (Deinecko et al.), whereas for the general TSP none is known; ii) a polynomial-time approximation scheme (PTAS) is known for the planar TSP (Arora et al.), whereas none exists for the general TSP unless P=NP; iii) there exists an efficient separation algorithm for the so-called 'domino-parity' inequalities, which only works when the point to be separated induces a planar graph (Letchford). In this talk, we continue to examine the separation question. We show that the separation problem for the subtour elimination, 2-matching and simple domino-parity constraints can be solved much more quickly in the planar case than in the case of general graphs. We also present a small number of graphs for which the subtour elimination and domino-parity inequalities are insufficient to describe the (graphical) TSP polyhedron, and conjecture that these are the excluded minors for this property.