Optimization Online


The Multiple Traveling Salesperson Problem on Regular Grids

Philipp Hungerländer (philipp.hungerlaender***at***aau.at)
Anna Jellen (anna.jellen***at***aau.at)
Stefan Jessenitschnig (stefanje***at***edu.aau.at)
Lisa Knoblinger (lisakn***at***edu.aau.at)
Manuel Lackenbucher (malackenbuch***at***edu.aau.at)
Kerstin Maier (kerstin.maier***at***aau.at)

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 grids can be exploited to explicitly determine optimal solutions, i.e., the problem can be solved in linear time. We suggest a Mixed-Integer Linear Programming (MILP) formulation for the mTSP on regular grids where we minimize two different objective functions. The first one models the sum of the tour lengths of all salespersons and the second one considers the maximal tour length of a single salesperson. With the help of these MILPs and combinatorial counting arguments, we establish lower bounds, explicit construction schemes and hence optimal mTSP solutions for specific grid sizes, depot positions and two salespersons.

Keywords: Multiple Traveling Salesperson Problem, Mixed-Integer Linear Programming, Grid.

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: TR-AAUK-M-O-18-08-17, Alpen-Adria Universität Klagenfurt, Mathematics, Optimization Group, August 2018

Download: [PDF]

Entry Submitted: 08/17/2018
Entry Accepted: 08/19/2018
Entry Last Modified: 09/10/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society