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 therefore proposes a decentralized approach with local auctions: carriers can bid on transportation orders offered by individual shippers or associate carriers. Thus, no central authority is involved. The main aim of this thesis is to investigate to what extent such an auction-based multi-agent system can be applied to dynamic large-scale collaborative vehicle routing problems.
First, we investigate the value of information sharing, that is, the quality of solutions that can be obtained when different types and amounts of carrier information are known. In a computational study, we vary whether carriers' routing plans or the positions of their vehicles are made available and also whether carriers share or hide information about their marginal costs for orders within each auction. The solutions generally improve in terms of service level, travel costs, and individual profits if more carrier information is available. Cost information is important to obtain high service levels, whereas position information is most useful if only a limited number of carriers is consulted for an order. In scenarios with a small fleet or urgent orders, limited information often suffices.
Next, we analyze the potential results of large-scale carrier cooperation. In a computational study based on a real-world data set consisting of over 12000 orders, we vary the number of carriers that collaborate. Reductions in travel costs of up to 77% can be obtained with 1000 cooperating carriers. Thus, whereas previous studies only report improvements of 20-30% for small collaborations, our local auction approach allows to solve large-scale problems and exceeds the reported cost reductions by a factor of three. Furthermore, small bundles of orders can be offered within our approach to benefit from interaction effects. Although the extra computational effort is limited, bundling can improve the results with up to 13% for 1000 cooperating carriers.
A third major contribution of this thesis is the investigation of the possible advantages of strategic behaviour. Instead of reporting (estimates of) their marginal costs, carriers might bid strategically and try to increase their individual profits at the cost of the others. We analyze that incurring small losses in an auction might be acceptable for carriers since they can be compensated either by a share of the cooperation gains or by future events. A computational study shows that it is highly dependent on the distribution of the cooperation gains whether strategic bidding pays off. Hence, cheating is possible but not straightforward. Strikingly, a second-price auction system does not help in preventing strategic behaviour: the possible benefits of cheating even increase.
Finally, we extend the developed auction-based multi-agent system such that it can be applied to problem variants where multiple pickup and delivery alternatives can be specified. By this, carriers have more flexibility in choosing the most efficient options. Furthermore, users may specify their preferences for the different options. The auction approach then assists in finding a balance between constructing efficient routes and meeting the user preferences as much as possible. A computational study shows that the approach outperforms centralized heuristics on large-scale instances of 2000 orders.
In short, the proposed multi-agent approach with local auctions can contribute to enabling and stimulating collaboration between many carriers in a dynamic world and thereby drastically reduce the overall number of driven kilometers -- implying less costs, less emissions, and less congestion. The approach is rather flexible in its assumptions on information availability, it can withstand strategic behaviour under some conditions, and can successfully be applied to practically relevant problems with specific user preferences. To fully exploit the benefits of cooperation in practice, some open challenges still must be addressed: incentives for carriers to participate must be carefully designed, among others through a fair distribution of obtained collaboration profits, stronger guarantees on truthful behaviour of collaborators, and high levels of autonomy for individual carriers.