DECOMPOSITION STRATEGIES FOR SOLVING CROWDSOURCED-DELIVERY MATCHING PROBLEMS

DOI Web Site 1 Citations 7 References
  • WATANABE Taiki
    東北大学 大学院情報科学研究科人間社会情報科学専攻
  • AKAMATSU Takashi
    東北大学 大学院情報科学研究科人間社会情報科学専攻

Bibliographic Information

Other Title
  • クラウド・ソーシング配送システムにおける効率的マッチング・アルゴリズム

Abstract

<p> Crowdsourced delivery (CSD) is a last mile delivery system in which drivers of private cars scheduling trips make deliveries by taking detours during the trips. While the CSD system reduces delivery cost, it is required to solve the unsolvable large-scale optimization problem of matching a large number of drivers with a large number of delivery tasks. To address this problem, we propose an efficient algorithm for the matching problem of CSD. In the proposed algorithm, this matching problem is decomposed into a hierarchical problem consisting of a master problem and multiple sub-problems. Further, a virtual network that can express matching as a traffic assignment to the path is constructed, and the master problem is reformulated into a traffic assignment problem on that network, to reduce the scale of the master problem. Then, the problem is drastically reduced by transforming it from an expression that uses path variables to an expression that uses only link variables. Numerical experiments have shown that the proposed algorithm reduces the computational cost optimizing calculations in the order of several digits and enables large-scale CSD matching.</p>

Journal

Citations (1)*help

See more

References(7)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top