Carriers can remarkably reduce transportation costs and emissions when they collaborate, for example through a platform. Such gains, however, have only been investigated for relatively small problem instances with low numbers of carriers. We develop auction-based methods for large-scale dynamic collaborative pickup and delivery problems, combining techniques of multi-agent systems and combinatorial auctions. We evaluate our approach in terms of both solution quality and possibilities of strategic behaviour using a real-world data set of over 12,000 orders. Hence, this study is (to the best of our knowledge) the first to assess the benefits of large-scale carrier cooperation and to propose an approach for it. First, we use iterative single-order auctions to investigate possible collaboration gains for increasing numbers of carriers. Our results show that travel costs can be reduced by up to 77% when 1000 carriers collaborate, largely increasing the gains that were previously observed in smaller-scale collaboration. We also ensure that individual rationality is guaranteed in each auction. Next, we compare this approach of multiple local auctions with an established central combinatorial auction mechanism and observe that the proposed approach performs better on large-scale instances. Furthermore, to improve solution quality, we integrate the two approaches by allowing small bundle auctions in the multi-agent system. We analyze the circumstances under which bundling is beneficial in a large-scale decentralized system and demonstrate that travel cost gains of up to 13% can be obtained for 1000 carriers. Finally, we investigate whether the system is vulnerable to cheating: we show that misrepresentation of true values by individual participants sometimes can benefit them at the cost of the collective. Although such strategic behaviour is not straightforward, we also discuss different means to prevent it.

@en

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.

@en

Collaboration in transportation is important to reduce costs and emissions, but carriers may have incentives to bid strategically in decentralized auction systems. We investigate what the effect of the auction strategy is on the possible cheating benefits in a dynamic context, such that we can recommend a method with lower chances for carriers to cheat. We consider both a first-price auction system and a second-price auction scheme. Contrary to what was expected, a second-price auction scheme gives more room for successful strategic behaviour, while it also results in more rejected orders. A first-price auction scheme might be useful in practice if the profit shares that are allocated to the winner of an auction are selected carefully.

@en

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.@en

Cooperation is important in order to find efficient vehicle routing solutions for the growing transportation market. Increasingly, platforms emerge as facilitators for this kind of collaborative transportation. However, individual actors connected to a platform might refuse to share (parts of) their information due to reasons of competition. Though the need for realistic information sharing models is widely acknowledged by transportation researchers and practitioners, the precise value of such information is mostly unknown. We investigate the quality of solutions that can be obtained when different types and levels of carrier data are available. We consider an auction-based Multi-Agent System to solve large-scale, dynamic pickup and delivery problems, and vary whether carriers’ positions or route plans are available, and whether carriers are fully cooperative or more competitive in placing their bids by sharing or hiding their marginal costs. In total, we evaluate 9 different information sharing policies. The availability of vehicle position and route plan information turns out to be important for decreasing total route costs, and sharing marginal costs has a positive impact on service level. We provide detailed insights into trade-offs of carriers’ confidentiality concerns and a range of system performance objectives (service level, travel costs, and carrier profits) under different circumstances (various numbers of auctions, penalties for rejected orders, emission or congestion fees, and different problem characteristics). Based on these results, platform providers can stimulate sharing of certain information to improve the total system efficiency.

@en

While collaborative vehicle routing has a significant potential to reduce transportation costs and emissions, current approaches are limited in terms of applicability, unrealistic assumptions, and low scalability. Centralized planning generally assumes full information and full control, which is often unacceptable for individual carriers. Combinatorial auctions with one central auctioneer overcome this problem and provide good results, but are limited to small static problems. Multi-agent approaches have been proposed for large dynamic problems, but do not directly take the advantages of bundling into account. We propose an approach where participants can individually outsource orders, while a platform can suggest bundles of the offered requests to improve solutions. We consider bundles of size 2 and 3 and show that travel costs can be decreased with 1.7% compared to the scenario with only single order auctions. Moreover, experiments on data from a Dutch transportation platform company show that large-scale collaboration through a platform results in system-wide savings of up to 79% for 1000 carriers.

@en

The transportation market requires collaboration to improve efficiency and reduce emissions. Individual carriers, however, might be hesitant to share their private information on a transportation platform. Although a few articles have investigated the value of information sharing, they assume identical behaviour of all carriers. In practice, nonetheless, some carriers are open to share more information than others. We consider such a hybrid information sharing setting and investigate the value of information sharing dependent on what other carriers are willing to share. We propose a Multi-Agent System in which carriers and customers interact and vary carriers’ willingness to share information about vehicle locations and marginal costs. The results show that sharing full route plans is always beneficial for individual carriers, independent of what position information other carriers share. However, to increase the total profit in scenarios with limited interaction, at least 50% of the carriers need to share full plans instead of only current positions. Furthermore, about 60% of the carriers need to be stimulated to share full cost information for solutions with maximal service level, although it might be unprofitable for themselves.@en

To provide more routing flexibility and improve service in delivery processes, we extend the Pickup and Delivery Problem with multiple time-location combinations for service. Furthermore, we introduce preference possibilities for each option, and aim for finding solutions that balance minimizing total travel costs and customer or operator dissatisfaction. We compare an Adaptive Large Neighborhood Search metaheuristic with solving the problem exactly. Simulation experiments indicate that a multiple-location scenario is highly beneficial compared to the corresponding single-location scenario and that the metaheuristic always finds the optimum if this could be computed by the exact solver.@en