Large-scale collaborative vehicle routing

Abstract

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.

Keywords: Collaborative vehicle routing; Combinatorial auctions; Multi-agent system; Platform-based transportation.

Fig. 1

Non-cooperative and cooperative solution for an instance of a collaborative pickup and delivery problem with 3 carriers and only initially assigned orders. In the non-cooperative case, each carrier serves its own orders. In the cooperative case, travel costs can be decreased by taking over orders of other carriers

Fig. 2

The standard MAS approach (a) has been extended in two ways (b): it is used for assignment and exchange of orders between carriers rather than for assignment to vehicles of a single carrier, and bundles are auctioned instead of single orders only

Fig. 3

Flowchart of the iterative auction procedure within the Multi-Agent System

Fig. 4

Decrease in travel costs for the cooperative scenarios (with and without bundling) compared to the non-cooperative scenario

Fig. 5

Profits for the platform and the collective of carriers on instance 1 as a percentage of the system’s revenue for different values of Winner Gain Share (WGS) and Contracted Gain Share (CGS). NC denotes the non-cooperative scenario

Fig. 6

Decrease in travel costs for the bundling scenario compared to the non-bundling scenario

Fig. 7

Routes for the non-cooperative scenario on instance 1 with 10 carriers, both for close assignment and no assignment. Examples of routes for the three main quartiles of length (in terms of number of stops) are highlighted in green, purple, and orange

Fig. 8

Average carrier profits if part of the carriers bid a fraction of their real (estimated) insertion costs

Fig. 9

Average shipper profits (a–c) and carrier profits (d–f) if part of the shippers and carriers mention lower reservation prices than their true ones

Fig. 10

Average number of rejected orders if part of the shippers and carriers mention lower reservation prices than their true ones