The undirected m-Capacitated Peripatetic Salesman Problem |
| |
| Authors: | É ric Duchenne,Gilbert Laporte,Fré dé ric Semet |
| |
| Affiliation: | 1. LAMIH-DIM, Université de Valenciennes et du Hainaut-Cambrésis, Le Mont Houy, 59313 Valenciennes Cedex 9, France;2. CIRRELT and Canada Research Chair in Distribution Management, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montreal, Canada H3T 2A7;3. LAGIS, École Centrale de Lille, Cité Scientifique, BP 48, 59651 Villeneuve d’Ascq, France |
| |
| Abstract: | In the m-Capacitated Peripatetic Salesman Problem (m-CPSP) the aim is to determine m Hamiltonian cycles of minimal total cost on a graph, such that all the edges are traversed less than the value of their capacity. This article introduces three formulations for the m-CPSP. Two branch-and-cut algorithms and one branch-and-price algorithm are developed. Tests performed on randomly generated and on TSPLIB Euclidean instances indicate that the branch-and-price algorithm can solve instances with more than twice the size of what is achievable with the branch-and-cut algorithms. |
| |
| Keywords: | Peripatetic Salesman Problem Traveling Salesman Problem Capacity Branch-and-cut Branch-and-price |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
