The tube challenge

Gilbert Laporte

doi:10.3138/infor.52.1.10

The tube challenge

Gilbert Laporte

HEC Montréal

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

Abstract

The Tube Challenge consists of visiting all stations of the London Underground in the least possible time. The competition started in 1959 and the current record was established in August 2013. This paper shows that under some simplifications, this problem and some of its variants can be cast as a Generalized Traveling Salesman Problem, as a Traveling Salesman Problem, as a Rural Postman Problem or as a Chinese Postman Problem defined on a directed graph.

Original language	English
Pages (from-to)	10-13
Number of pages	4
Journal	INFOR
Volume	52
Issue number	1
DOIs	https://doi.org/10.3138/infor.52.1.10
Publication status	Published - 1 Feb 2014

Keywords

Directed Chinese Postman Problem
Directed Generalized Traveling Salesman Problem
Directed Rural Postman Problem
Directed Traveling Salesman Problem
London Underground
Tube Challenge

ASJC Scopus subject areas

Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.3138/infor.52.1.10

Cite this

@article{4afd0d24a07546cdb82d8a92f5847538,

title = "The tube challenge",

abstract = "The Tube Challenge consists of visiting all stations of the London Underground in the least possible time. The competition started in 1959 and the current record was established in August 2013. This paper shows that under some simplifications, this problem and some of its variants can be cast as a Generalized Traveling Salesman Problem, as a Traveling Salesman Problem, as a Rural Postman Problem or as a Chinese Postman Problem defined on a directed graph.",

keywords = "Directed Chinese Postman Problem, Directed Generalized Traveling Salesman Problem, Directed Rural Postman Problem, Directed Traveling Salesman Problem, London Underground, Tube Challenge",

author = "Gilbert Laporte",

year = "2014",

month = feb,

day = "1",

doi = "10.3138/infor.52.1.10",

language = "English",

volume = "52",

pages = "10--13",

journal = "INFOR",

issn = "0315-5986",

publisher = "Taylor and Francis",

number = "1",

}

TY - JOUR

T1 - The tube challenge

AU - Laporte, Gilbert

PY - 2014/2/1

Y1 - 2014/2/1

N2 - The Tube Challenge consists of visiting all stations of the London Underground in the least possible time. The competition started in 1959 and the current record was established in August 2013. This paper shows that under some simplifications, this problem and some of its variants can be cast as a Generalized Traveling Salesman Problem, as a Traveling Salesman Problem, as a Rural Postman Problem or as a Chinese Postman Problem defined on a directed graph.

AB - The Tube Challenge consists of visiting all stations of the London Underground in the least possible time. The competition started in 1959 and the current record was established in August 2013. This paper shows that under some simplifications, this problem and some of its variants can be cast as a Generalized Traveling Salesman Problem, as a Traveling Salesman Problem, as a Rural Postman Problem or as a Chinese Postman Problem defined on a directed graph.

KW - Directed Chinese Postman Problem

KW - Directed Generalized Traveling Salesman Problem

KW - Directed Rural Postman Problem

KW - Directed Traveling Salesman Problem

KW - London Underground

KW - Tube Challenge

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

U2 - 10.3138/infor.52.1.10

DO - 10.3138/infor.52.1.10

M3 - Article

AN - SCOPUS:84928580469

SN - 0315-5986

VL - 52

SP - 10

EP - 13

JO - INFOR

JF - INFOR

IS - 1

ER -

The tube challenge

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this