Skip navigation
Skip navigation

A Study of Proxies for Shapley Allocations of Transport Costs

Aziz, Haris; Cahan, Casey; Gretton, Charles; Kilby, Philip; Mattei, Nicholas; Walsh, Toby

Description

We survey existing rules of thumb, propose novel methods, and comprehensively evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle transport setting. Cost to serve analysis has applications both strategically and operationally in transportation settings. The problem is formally modeled as the traveling salesperson game (TSG), a cooperative transferable utility game in which agents correspond to locations in a traveling salesperson...[Show more]

dc.contributor.authorAziz, Haris
dc.contributor.authorCahan, Casey
dc.contributor.authorGretton, Charles
dc.contributor.authorKilby, Philip
dc.contributor.authorMattei, Nicholas
dc.contributor.authorWalsh, Toby
dc.date.accessioned2018-11-29T22:54:39Z
dc.date.available2018-11-29T22:54:39Z
dc.identifier.issn1076-9757
dc.identifier.urihttp://hdl.handle.net/1885/152870
dc.description.abstractWe survey existing rules of thumb, propose novel methods, and comprehensively evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle transport setting. Cost to serve analysis has applications both strategically and operationally in transportation settings. The problem is formally modeled as the traveling salesperson game (TSG), a cooperative transferable utility game in which agents correspond to locations in a traveling salesperson problem (TSP). The total cost to serve all locations in the TSP is the length of an optimal tour. An allocation divides the total cost among individual locations, thus providing the cost to serve each of them. As one of the most important normative division schemes in cooperative games, the Shapley value gives a principled and fair allocation for a broad variety of games including the TSG. We consider a number of direct and sampling-based procedures for calculating the Shapley value, and prove that approximating the Shapley value of the TSG within a constant factor is NP-hard. Treating the Shapley value as an ideal baseline allocation, we survey six proxies for it that are each relatively easy to compute. Some of these proxies are rules of thumb and some are procedures international delivery companies use(d) as cost allocation methods. We perform an experimental evaluation using synthetic Euclidean games as well as games derived from real-world tours calculated for scenarios involving fast-moving goods; where deliveries are made on a road network every day. We explore several computationally tractable allocation techniques that are good proxies for the Shapley value in problem instances of a size and complexity that is commercially relevant.
dc.format.mimetypeapplication/pdf
dc.publisherMorgan Kauffman Publishers
dc.sourceJournal of Artificial Intelligence Research
dc.titleA Study of Proxies for Shapley Allocations of Transport Costs
dc.typeJournal article
local.description.notesImported from ARIES
local.identifier.citationvolume56
dc.date.issued2016
local.identifier.absfor080101 - Adaptive Agents and Intelligent Robotics
local.identifier.ariespublicationu5357342xPUB45
local.type.statusPublished Version
local.contributor.affiliationAziz, Haris, NICTA
local.contributor.affiliationCahan, Casey, University of Auckland
local.contributor.affiliationGretton, Charles, College of Engineering and Computer Science, ANU
local.contributor.affiliationKilby, Philip, College of Engineering and Computer Science, ANU
local.contributor.affiliationMattei, Nicholas, NICTA
local.contributor.affiliationWalsh, Toby, National ICT Australia
local.identifier.doi10.1613/jair.5021
local.identifier.absseo970108 - Expanding Knowledge in the Information and Computing Sciences
local.identifier.absseo890299 - Computer Software and Services not elsewhere classified
local.identifier.absseo880105 - Road Freight
dc.date.updated2018-11-29T08:01:27Z
local.identifier.thomsonID000396194700001
dcterms.accessRightsOpen Access
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Aziz_A_Study_of_Proxies_for_Shapley_2016.pdf971.08 kBAdobe PDFThumbnail


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator