The Joint Network Vehicle Routing Game

Mathijs van Zon (), Remy Spliet () and Wilco van den Heuvel
Additional contact information
Mathijs van Zon: Econometric Institute, Erasmus School of Economics, Erasmus University Rotterdam, 3000 DR Rotterdam, Netherlands
Remy Spliet: Econometric Institute, Erasmus School of Economics, Erasmus University Rotterdam, 3000 DR Rotterdam, Netherlands

Transportation Science, 2021, vol. 55, issue 1, 179-195

Abstract: Collaborative transportation can significantly reduce transportation costs as well as greenhouse gas emissions. However, allocating the cost to the collaborating companies remains difficult. We consider the cost-allocation problem, which arises when companies, each with multiple delivery locations, collaborate by consolidating demand and combining delivery routes. We model the corresponding cost-allocation problem as a cooperative game: the joint network vehicle routing game (JNVRG). We propose a row generation algorithm to either determine a core allocation for the JNVRG or show that no such allocation exists. In this approach, we encounter a row generation subproblem, which we model as a new variant of a vehicle routing problem with profits. Moreover, we propose two main acceleration strategies for the row generation algorithm. First, we generate rows by relaxing the row generation subproblem, exploiting the tight linear programming (LP) bounds for our formulation of the row generation subproblem. Secondly, we propose to also solve the row generation subproblem heuristically and to only solve it to optimality when the heuristic fails. We demonstrate the effectiveness of the proposed row generation algorithm and the acceleration strategies by means of numerical experiments for both the JNVRG as well as the traditional vehicle routing game, which is a special case of the JNVRG. We create instances based on benchmark instances of the capacitated vehicle routing problem from the literature. We are able to either determine a core allocation or show that no core allocation exists, for instances ranging from 5 companies with a total of 79 delivery locations to 53 companies with a total of 53 delivery locations.

Keywords: collaborative transportation; cooperative game theory; vehicle routing; row generation; vehicle routing with profits; branch-and-cut-and-price (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/trsc.2020.1008 (application/pdf)

Related works:
Working Paper: The Joint Network Vehicle Routing Game (2019)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:55:y:2021:i:1:p:179-195

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().