article

Free access

Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem

Authors:

Mandell Bellmore,

Saman HongAuthors Info & Claims

Journal of the ACM (JACM), Volume 21, Issue 3

Pages 500 - 504

https://doi.org/10.1145/321832.321847

Published: 01 July 1974 Publication History

PDF eReader

Abstract

It is shown that the multisalesmen problem can be solved by solving the standard traveling salesman problem on an expanded graph. The expanded graph has m — 1 more nodes than the original graph where m is the number of salesmen available at the base.

References

[1]

BELLMORE, i., AND 1NTEMHAUSER, G.L. The traveling salesman problem: a survey. Oper. Res. 16 (1968), 538-558.

Google Scholar

[2]

HELD, i., AND KARP, R.M. The traveling salesman problem and minimum spanning tree; Part II. Math. Programming 1 (1971), 6-25.

Google Scholar

[3]

HoNo, S. Linear programming approach for the traveling salesman problem. Ph.D. Diss., The Johns Hopkins University, 1972.

Google Scholar

[4]

MILLER, C. E., TUCKER, A. W., AND ZEMLIN, R. A. Integer programming formulation and traveling salesman problem. J. A UM 7 (1960), 326-329.

Crossref

Google Scholar

Cited By

View all

Kang SLee H(2024)Probabilistic Multi-Robot Task Scheduling for the Antarctic Environments with CrevassesSymmetry10.3390/sym1609122916:9(1229)Online publication date: 19-Sep-2024
https://doi.org/10.3390/sym16091229
Gauthier JIrnich S(2024)Inter-depot moves and dynamic-radius search for multi-depot vehicle routing problemsDiscrete Applied Mathematics10.1016/j.dam.2023.12.004346:C(131-153)Online publication date: 31-Mar-2024
https://dl.acm.org/doi/10.1016/j.dam.2023.12.004
Kim SLee H(2023)Multi-Robot Task Scheduling with Ant Colony Optimization in Antarctic EnvironmentsSensors10.3390/s2302075123:2(751)Online publication date: 9-Jan-2023
https://doi.org/10.3390/s23020751
Show More Cited By

Index Terms

Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

Solving the Railway Traveling Salesman Problem via a Transformation into the Classical Traveling Salesman Problem
HIS '08: Proceedings of the 2008 8th International Conference on Hybrid Intelligent Systems

The Railway Traveling Salesman Problem (RTSP) is a practical extension of the classical traveling salesman problem considering a railway network and train schedules. We are given a salesman who has to visita number of cities to carry out some business. ...
Halin graphs and the travelling salesman problem

A Halin graphH=TźC is obtained by embedding a treeT having no nodes of degree 2 in the plane, and then adding a cycleC to join the leaves ofT in such a way that the resulting graph is planar. These graphs are edge minimal 3-connected, hamiltonian, and ...
Traveling salesman problem under categorization

We introduce two new classes of traveling salesman problems (TSP1 and TSP2) which subsume the classical traveling salesman problem and the bottleneck traveling salesman problem. It is shown that these problems are strongly NP-complete on Halin graphs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 21, Issue 3

July 1974

173 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321832

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1974

Published in JACM Volume 21, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

93
Total Citations
View Citations
1,336
Total Downloads

Downloads (Last 12 months)137
Downloads (Last 6 weeks)18

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kang SLee H(2024)Probabilistic Multi-Robot Task Scheduling for the Antarctic Environments with CrevassesSymmetry10.3390/sym1609122916:9(1229)Online publication date: 19-Sep-2024
https://doi.org/10.3390/sym16091229
Gauthier JIrnich S(2024)Inter-depot moves and dynamic-radius search for multi-depot vehicle routing problemsDiscrete Applied Mathematics10.1016/j.dam.2023.12.004346:C(131-153)Online publication date: 31-Mar-2024
https://dl.acm.org/doi/10.1016/j.dam.2023.12.004
Kim SLee H(2023)Multi-Robot Task Scheduling with Ant Colony Optimization in Antarctic EnvironmentsSensors10.3390/s2302075123:2(751)Online publication date: 9-Jan-2023
https://doi.org/10.3390/s23020751
Cornejo-Acosta JGarcía-Díaz JPérez-Sansalvador JSegura C(2023)Compact Integer Programs for Depot-Free Multiple Traveling Salesperson ProblemsMathematics10.3390/math1113301411:13(3014)Online publication date: 6-Jul-2023
https://doi.org/10.3390/math11133014
Alyassi RKhonji MKarapetyan AChau SElbassioni KTseng C(2023)Autonomous Recharging and Flight Mission Planning for Battery-Operated Autonomous DronesIEEE Transactions on Automation Science and Engineering10.1109/TASE.2022.317556520:2(1034-1046)Online publication date: Apr-2023
https://doi.org/10.1109/TASE.2022.3175565
Ling ZZhou YZhang Y(2023)Solving multiple travelling salesman problem through deep convolutional neural networkIET Cyber-Systems and Robotics10.1049/csy2.120845:1Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1049/csy2.12084
Weber AFiege FKnoll A(2022)Vehicle mission guidance by symbolic optimal control2022 European Control Conference (ECC)10.23919/ECC55457.2022.9838238(1243-1249)Online publication date: 12-Jul-2022
https://doi.org/10.23919/ECC55457.2022.9838238
Belyaev MBorovikhin PVetoshkin AKaravaev DRasskazov I(2022)Guidance of the Scientific Equipment of the International Space Station to Objects under StudyCosmic Research10.1134/S001095252201001460:1(58-66)Online publication date: 11-Feb-2022
https://doi.org/10.1134/S0010952522010014
Wang JMeng M(2022)Real-Time Decision Making and Path Planning for Robotic Autonomous Luggage Trolley Collection at AirportsIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2020.304898452:4(2174-2183)Online publication date: Apr-2022
https://doi.org/10.1109/TSMC.2020.3048984
Weber AKnoll A(2021)On the Solution of the Travelling Salesman Problem for Nonlinear Salesman Dynamics using Symbolic Optimal Control2021 European Control Conference (ECC)10.23919/ECC54610.2021.9655131(1995-2001)Online publication date: 29-Jun-2021
https://doi.org/10.23919/ECC54610.2021.9655131
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Solving the Railway Traveling Salesman Problem via a Transformation into the Classical Traveling Salesman Problem

Halin graphs and the travelling salesman problem

Traveling salesman problem under categorization

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations