Solving the Multiple Traveling Salesperson Problem on Regular Grids in Linear Time

Philipp Hungerländer (), Anna Jellen (), Stefan Jessenitschnig (), Lisa Knoblinger (), Manuel Lackenbucher () and Kerstin Maier ()
Additional contact information
Philipp Hungerländer: University of Klagenfurt
Anna Jellen: University of Klagenfurt
Stefan Jessenitschnig: University of Klagenfurt
Lisa Knoblinger: University of Klagenfurt
Manuel Lackenbucher: University of Klagenfurt
Kerstin Maier: University of Klagenfurt

A chapter in Operations Research Proceedings 2019, 2020, pp 215-221 from Springer

Abstract: Abstract In this work we analyze the multiple Traveling Salesperson Problem (mTSP) on regular grids. While the general mTSP is known to be NP-hard, the special structure of regular grids can be exploited to explicitly determine optimal solutions in linear time. Our research is motivated by several real-world applications, for example delivering goods with swarms of unmanned aerial vehicles (UAV) or search and rescue operations. In order to obtain regular grid structures, we divide large search areas in several equal-sized squares, where we choose the square size as large as the sensor range of a UAV. First, we use an Integer Linear Program (ILP) to formally describe our considered mTSP variant on regular grids that aims to minimize the total tour length of all salespersons, which corresponds to minimizing the average search time for a missing person. With the help of combinatorial counting arguments and the establishment of explicit construction schemes, we are able to determine optimal mTSP solutions for specific grid sizes with two salespersons, where the depot is located in one of the four corners.

Keywords: Combinatorial optimization; Mixed-integer programming; Routing (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-030-48439-2_26

Ordering information: This item can be ordered from
http://www.springer.com/9783030484392

DOI: 10.1007/978-3-030-48439-2_26

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().