Large-scale collaborative vehicle routing

Johan Los, Frederik Schulte, Margaretha Gansterer, Richard F. Hartl, Matthijs T. J. Spaan, Rudy R. Negenborn

Veröffentlichungen: Beitrag in FachzeitschriftArtikelPeer Reviewed


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.
FachzeitschriftAnnals of Operations Research
Frühes Online-Datum8 Apr. 2022
PublikationsstatusElektronische Veröffentlichung vor Drucklegung - 8 Apr. 2022

ÖFOS 2012

  • 502017 Logistik