The Multiple Traveling Salesperson Problem on Regular Grids
Philipp Hungerländer (philipp.hungerlaenderaau.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
Entry Submitted: 08/17/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|