Large-scale collaborative vehicle routing
Open Access
- 8 April 2022
- journal article
- research article
- Published by Springer Nature in Annals of Operations Research
- Vol. 350 (1) , 201-233
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
Funding Information
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek (14894)
This publication has 33 references indexed in Scilit:
- Price-setting based combinatorial auction approach for carrier collaboration with pickup and delivery requestsOperational Research, 2014
- Collaborative Logistics from the Perspective of Road Transportation CompaniesTransport Reviews, 2013
- Collaborative transportation planning of less-than-truckload freightOR Spectrum, 2013
- Interaction between intelligent agent strategies for real-time transportation planningCentral European Journal of Operations Research, 2011
- A multi-agent and auction-based framework and approach for carrier collaborationLogistics Research, 2011
- Solutions to the request reassignment problem in collaborative carrier networksTransportation Research Part E: Logistics and Transportation Review, 2010
- Can agents measure up? A comparative study of an agent-based and on-line optimization approach for a drayage problem with uncertaintyTransportation Research Part C: Emerging Technologies, 2010
- An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time WindowsTransportation Science, 2006
- Efficient Insertion Heuristics for Vehicle Routing and Scheduling ProblemsTransportation Science, 2004
- Competitive Performance Assessment of Dynamic Vehicle Routing Technologies Using Sequential AuctionsTransportation Research Record: Journal of the Transportation Research Board, 2004