|
|
|
Session MB10 - Tournées de véhicules II / Vehicle routing II
Day |
Monday, May 09, 2005 |
Location |
TAL Gestion globale d'actifs inc. |
Chair |
Adam Letchford |
Presentations
03h30 PM |
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.
|
03h55 PM |
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.
|
04h20 PM |
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.
|
|