Titre :

The undirected m-Capacitated Peripatetic Salesman Problem

Auteur(s) :

Duchenne, Éric [Auteur]
Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201 [LAMIH]
Laporte, Gilbert [Auteur]
Laboratoire CIRRELT Université Laval Quebec [CIRRELT]
Semet, Frédéric [Auteur]
LAGIS-OSL

Titre de la revue :

European Journal of Operational Research

Pagination :

637-643

Éditeur :

Elsevier

Date de publication :

2012-01-01

ISSN :

0377-2217

Mot(s)-clé(s) en anglais :

Peripatetic Salesman Problem
Traveling Salesman Problem
Capacity
Branch-and-cut
Branch-and-price

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL