The Joint Network Vehicle Routing Game

Mathijs van Zon, Remy Spliet and Wilco van den Heuvel

No EI2019-03, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

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 determine a core allocation for the JNVRG. 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 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 and solve instances based on benchmark instances of the capacitated vehicle routing problem from the literature, 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)
Pages: 22
Date: 2019-01-01
New Economics Papers: this item is included in nep-gth and nep-ure
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/115273/EI2019-03.pdf (application/pdf)

Related works:
Journal Article: The Joint Network Vehicle Routing Game (2021)
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:ems:eureir:115273

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).