A Market-based Solution to the Multiple Traveling Salesmen Problem Open Access Deposited

Downloadable Content

Download PDF
Download Adobe Acrobat Reader
Date Uploaded: 02/13/2017
Date Modified: 04/05/2017

This paper describes a market-based solution to the problem of assigning mobile agents to tasks. The problem is formulated as the multiple depots, multiple traveling salesmen problem (MTSP), where agents and tasks operate in a market to achieve near-optimal solutions. We consider both the classical MTSP, in which the sum of all tour lengths is minimized, and the Min-Max MTSP, in which the longest tour is minimized. We compare the market-based solution with direct enumeration in small scenarios, and show that the results are nearly optimal. For the classical MTSP, we compare our results to linear programming, and show that the results are within 1 % of the best cost found by linear programming in more than 90 % of the runs, with a significant reduction in runtime. For the Min-Max case, we compare our method with Carlsson's algorithm and show an improvement of 5 % to 40 % in cost, albeit at an increase in runtime. Finally, we demonstrate the ability of the market-based solution to deal with changes in the scenario, e.g., agents leaving and entering the market. We show that the market paradigm is ideal for dealing with these changes during runtime, without the need to restart the algorithm, and that the solution reacts to the new scenarios in a quick and near-optimal way.

Date Created
Journal Title
  • Journal of Intelligent & Robotic Systems
  • This work was part of a pilot "mediated-deposit model" where library staff found potential works, later submitted for faculty review

Digital Object Identifier (DOI)

Identifier: 10.1007/s10846-012-9805-3

This DOI link is the best way for others to cite your work.


Permanent link to this page: