The undirected m-Capacitated Peripatetic Salesman Problem

Éric Duchenne; Gilbert Laporte; Frédéric Semet

doi:10.1016/j.ejor.2012.07.022

The undirected m-Capacitated Peripatetic Salesman Problem

Éric Duchenne, Gilbert Laporte, Frédéric Semet

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

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.

Original language	English
Pages (from-to)	637-643
Number of pages	7
Journal	European Journal of Operational Research
Volume	223
Issue number	3
DOIs	https://doi.org/10.1016/j.ejor.2012.07.022
Publication status	Published - 16 Dec 2012

Keywords

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

ASJC Scopus subject areas

Computer Science(all)
Modelling and Simulation
Management Science and Operations Research
Information Systems and Management

Access to Document

10.1016/j.ejor.2012.07.022

Link to publication in Scopus

Fingerprint Dive into the research topics of 'The undirected m-Capacitated Peripatetic Salesman Problem'. Together they form a unique fingerprint.

Cite this

@article{7bca9f4b424740a0b823f9214fd57a77,

title = "The undirected m-Capacitated Peripatetic Salesman Problem",

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 = "Branch-and-cut, Branch-and-price, Capacity, Peripatetic Salesman Problem, Traveling Salesman Problem",

author = "{\'E}ric Duchenne and Gilbert Laporte and Fr{\'e}d{\'e}ric Semet",

year = "2012",

month = dec,

day = "16",

doi = "10.1016/j.ejor.2012.07.022",

language = "English",

volume = "223",

pages = "637--643",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - The undirected m-Capacitated Peripatetic Salesman Problem

AU - Duchenne, Éric

AU - Laporte, Gilbert

AU - Semet, Frédéric

PY - 2012/12/16

Y1 - 2012/12/16

N2 - 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.

AB - 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.

KW - Branch-and-cut

KW - Branch-and-price

KW - Capacity

KW - Peripatetic Salesman Problem

KW - Traveling Salesman Problem

UR - http://www.scopus.com/inward/record.url?scp=84866427925&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2012.07.022

DO - 10.1016/j.ejor.2012.07.022

M3 - Article

AN - SCOPUS:84866427925

VL - 223

SP - 637

EP - 643

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -