Market-Based Solution to the Allocation of Tasks to Agents Open Access Deposited

Downloadable Content

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

Tasks allocation is a fundamental problem in multiagent systems. We formulate the problem as a multiple traveling salesmen problem (MTSP), which is an extension to the well known traveling salesman problem (TSP), both considered to be NP-hard combinatorial optimization problems. We propose a solution in which agents interact in an economic market to win tasks situated in an environment. The agents strive to minimize required costs, defined as either the total distance traveled by all agents or the maximum distance traveled by any agent. Using a set of simple market operations, the agents come up with a solution for task allocation. In this work we examine the processing speed of the market-based solution (MBS), as well as the quality vs. optimal solutions achieved using enumeration for a 3 agents by 8 tasks scenario. We show that the MBS is both quick and close to optimal. We then show that the MBS can be scaled to more complicated problems, by comparing its results with results from genetic algorithm (GA) and clustering. We also show the robustness of the MBS to changes in the scenario, e.g. the addition and removal of tasks or agents.

Date Created
Journal Title
  • Procedia Computer Science
  • 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.1016/j.procs.2011.08.008

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


Permanent link to this page: