Decentralized task allocation using magnet: An empirical evaluation in the logistics domain

Mark Hoogendoorn, Maria L. Gini, Catholijn M. Jonker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper presents a decentralized task allocation method that can handle allocation of tasks with time and precedence constraints in a multi-agent setting where not all information needed for a centralized approach is shared. In our MAGNET-based approach agents distribute tasks via first-price reverse combinatorial auctions, where the auctioneer is whatever agent has tasks to be allocated. The choice of MAGNET is based on its uniqueness to handle auctions for allocation of tasks which include time windows and precedence constraints. Empirical evaluations based on real data obtained from a logistics company show that the system performs well. The costs of the allocations obtained by our approach are on average within 5% from the optimal allocation. The computation time is linear in the number of tasks, while computing the optimal allocation is an NP-hard problem.

Original languageEnglish (US)
Title of host publicationICEC 2007
Subtitle of host publicationProceedings of the Ninth International Conference on Electronic Commerce
Pages319-328
Number of pages10
DOIs
StatePublished - Dec 14 2007
EventProceedings of the ninth international conference - Minneapolis, MN, United States
Duration: Aug 19 2007Aug 22 2007

Publication series

NameACM International Conference Proceeding Series
Volume258

Other

OtherProceedings of the ninth international conference
CountryUnited States
CityMinneapolis, MN
Period8/19/078/22/07

Keywords

  • Automated auctions
  • Logistics
  • Multi-agent contracting

Fingerprint Dive into the research topics of 'Decentralized task allocation using magnet: An empirical evaluation in the logistics domain'. Together they form a unique fingerprint.

Cite this