首页    期刊浏览 2024年11月07日 星期四
登录注册

文章基本信息

  • 标题:A Study of Proxies for Shapley Allocations of Transport Costs
  • 本地全文:下载
  • 作者:Haris Aziz ; Casey Cahan ; Charles Gretton
  • 期刊名称:Journal of Artificial Intelligence Research
  • 印刷版ISSN:1076-9757
  • 出版年度:2016
  • 卷号:56
  • 页码:573-611
  • 出版社:American Association of Artificial
  • 摘要: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 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.
国家哲学社会科学文献中心版权所有