An Auction-Based Multi-Agent System for the Pickup and Delivery Problem with Autonomous Vehicles and Alternative Locations

The trends of autonomous transportation and mobility on demand in line with large numbers of requests increasingly call for decentralized vehicle routing optimization. Multi-agent systems (MASs) allow to model fully autonomous decentralized decision making, but are rarely considered in current decision support approaches. We propose a multi-agent approach in which autonomous vehicles are modeled as independent decision makers that locally interact with auctioneers for transportation orders. The developed MAS finds solutions for a realistic routing problem in which multiple pickup and delivery alternatives are possible per order. Although information sharing is significantly restricted, the MAS results in better solutions than a centralized Adaptive Large Neighborhood Search with full information sharing on large problem instances where computation time is limited.