Solving Large-Scale Dynamic Collaborative Vehicle Routing Problems: An Auction-Based Multi-Agent Approach

The freight transportation sector is one of the major contributors to air pollution. An important way to reduce emissions consists of collective route planning. Although unloaded trips and inefficient routes could not always be prevented by individual carriers, more efficient operations could often be obtained if multiple carriers collaborate by exchanging part of their shipments. The resulting vehicle mileage reductions not only lower the costs for the cooperating carriers, but also reduce emissions and decrease the level of congestion. Achieving a successful collaboration between carriers, however, is a difficult problem. On top of the NP-hardness of the vehicle routing problem, the collaborative variants suffer from different carriers each having their individual policies, objectives, and preferences. Whereas information is generally assumed to be available in fleet management problems for individual carriers, this is problematic in collaborative cases: carriers might be hesitant to share confidential information with each other or with a platform that coordinates the cooperation. Furthermore, carriers might be more interested in increasing their own profits than in reducing the overall costs. Hence, they might try to exploit a cooperative approach. This thesis explores how the above problems can be approached in the context of dynamic large-scale collaborative pickup and delivery problems. Earlier, centralized collaboration approaches have been proposed, but these are only applicable to problems of limited size: computation times increase with the number of orders, and hence, quick adaptations in a dynamic world will be hindered. Furthermore, information is assumed to be always available in centralized approaches, and carriers need to give up their autonomy. To avoid the last two problems, decentralized approaches with central auctions have been used, but these still suffer from scalability issues due to the role of a central auctioneer. This thesis ther
Transport Engineering and Logistics