Last-mile Collaboration: A Decentralized Mechanism with Bounded Performance Guarantees and Implementation Strategies


The last-mile urban freight market is characterised by soaring fragmentation, fierce competition and a super-low profit margin. These conditions make it difficult for operators to succeed commercially and provide level-of-service guarantees. At the same time, uncoordinated vehicle trips result in additional traffic that further exacerbates urban congestion and emissions. Despite increasing pressure from local authorities and regulators, there has been a notable lack of success in resolving these issues. Common barriers to progress include the lack of commercially meaningful incentives for operators alongside a reluctance to share information that is deemed commercially sensitive. Previous research in decentralised collaboration has focused on combinatorial auctions, while large-scale applications are still limited. In this work, we propose an Iterative, Decentralized, and Auction-based Mechanism (IDAM) for the last-mile urban freight collaboration. It is individually rational, budge balanced, non-decreasing and theoretically convergent. Its performance is bounded by quantifying the Price of Anarchy and the Price of Stability of corresponding resource-sharing games. From an optimistic view, IDAM could be as efficient as centralized planning. Conservatively, the worst performance depends on the fleet capacity and order spatial distribution. These bounds provide a reference for the potential benefits of collaboration and shed light on our model’s suitability. To tackle the computational complexities, implementation strategies are incorporated for accelerating large-scale applications. The IDAM is validated on several instances and against a benchmark model based on the combinatorial auction. A case study of the Inner London Area, which involves 50 companies and 1000 orders, showed that our model can achieve up to 76% cost savings.

Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023)