IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v55y2021i1p179-195.html
   My bibliography  Save this article

The Joint Network Vehicle Routing Game

Author

Listed:
  • 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)

  • Wilco van den Heuvel

    (Econometric Institute, Erasmus School of Economics, Erasmus University Rotterdam, 3000 DR Rotterdam, Netherlands)

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.

Suggested Citation

  • Mathijs van Zon & Remy Spliet & Wilco van den Heuvel, 2021. "The Joint Network Vehicle Routing Game," Transportation Science, INFORMS, vol. 55(1), pages 179-195, 1-2.
    • Handle: RePEc:inm:ortrsc:v:55:y:2021:i:1:p:179-195
    DOI: 10.1287/trsc.2020.1008
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2020.1008
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2020.1008?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Arin Aguirre, Francisco Javier, 2003. "Egalitarian distributions in coalitional models: The Lorenz criterion," IKERLANAK 6503, Universidad del País Vasco - Departamento de Fundamentos del Análisis Económico I.
    2. Lloyd S. Shapley, 1967. "On balanced sets and cores," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 14(4), pages 453-460.
    3. Martinelli, Rafael & Pecin, Diego & Poggi, Marcus, 2014. "Efficient elementary and restricted non-elementary route pricing," European Journal of Operational Research, Elsevier, vol. 239(1), pages 102-111.
    4. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    5. M A Krajewska & H Kopfer & G Laporte & S Ropke & G Zaccour, 2008. "Horizontal cooperation among freight carriers: request allocation and profit sharing," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(11), pages 1483-1491, November.
    6. Frisk, M. & Göthe-Lundgren, M. & Jörnsten, K. & Rönnqvist, M., 2010. "Cost allocation in collaborative forest transportation," European Journal of Operational Research, Elsevier, vol. 205(2), pages 448-458, September.
    7. Stefan Engevall & Maud Göthe-Lundgren & Peter Värbrand, 1998. "The traveling salesman game: An application ofcost allocation in a gas and oil company," Annals of Operations Research, Springer, vol. 82(0), pages 203-218, August.
    8. SCHMEIDLER, David, 1969. "The nucleolus of a characteristic function game," LIDAM Reprints CORE 44, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    10. Potters, J.A.M. & Curiel, I. & Tijs, S.H., 1992. "Traveling salesman games," Other publications TiSEM 0dd4cf3d-25fa-4179-80f6-6, Tilburg University, School of Economics and Management.
    11. Mads Jepsen & Bjørn Petersen & Simon Spoorendonk & David Pisinger, 2008. "Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows," Operations Research, INFORMS, vol. 56(2), pages 497-511, April.
    12. Joen Dahlberg & Stefan Engevall & Maud Göthe-Lundgren, 2018. "Consolidation in Urban Freight Transportation — Cost Allocation Models," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(04), pages 1-23, August.
    13. N Lehoux & S D'Amours & Y Frein & A Langevin & B Penz, 2011. "Collaboration for a two-echelon supply chain in the pulp and paper industry: the use of incentives to increase profit," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(4), pages 581-592, April.
    14. Bo Dai & Haoxun Chen, 2015. "Proportional egalitarian core solution for profit allocation games with an application to collaborative transportation planning," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 9(1), pages 53-76.
    15. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    16. Drechsel, J. & Kimms, A., 2010. "Computing core allocations in cooperative games with an application to cooperative procurement," International Journal of Production Economics, Elsevier, vol. 128(1), pages 310-321, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Schlicher, L. & Dietzenbacher, Bas & Musegaas, Marieke, 2023. "Stable streaming platforms: a cooperative game approach," Research Memorandum 001, Maastricht University, Graduate School of Business and Economics (GSBE).
    2. Chen, Shukai & Wang, Hua & Meng, Qiang, 2023. "Cost allocation of cooperative autonomous truck platooning: Efficiency and stability analysis," Transportation Research Part B: Methodological, Elsevier, vol. 173(C), pages 119-141.
    3. van Zon, M. & Spliet, R. & van den Heuvel, W., 2021. "The effect of algorithm capabilities on cooperative games," Econometric Institute Research Papers EI2021-02, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    4. Soriano, Adria & Gansterer, Margaretha & Hartl, Richard F., 2023. "The multi-depot vehicle routing problem with profit fairness," International Journal of Production Economics, Elsevier, vol. 255(C).
    5. Soriano, Adria & Gansterer, Margaretha & Hartl, Richard F., 2022. "Reprint of: The multi-depot vehicle routing problem with profit fairness," International Journal of Production Economics, Elsevier, vol. 250(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. van Zon, M. & Spliet, R. & van den Heuvel, W., 2021. "The effect of algorithm capabilities on cooperative games," Econometric Institute Research Papers EI2021-02, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    2. Kimms, A. & Kozeletskyi, I., 2016. "Core-based cost allocation in the cooperative traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 248(3), pages 910-916.
    3. Diego Pecin & Claudio Contardo & Guy Desaulniers & Eduardo Uchoa, 2017. "New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 489-502, August.
    4. Kellner, Florian & Schneiderbauer, Miriam, 2019. "Further insights into the allocation of greenhouse gas emissions to shipments in road freight transportation: The pollution routing game," European Journal of Operational Research, Elsevier, vol. 278(1), pages 296-313.
    5. Naber, S.K. & de Ree, D.A. & Spliet, R. & van den Heuvel, W., 2015. "Allocating CO2 emission to customers on a distribution route," Omega, Elsevier, vol. 54(C), pages 191-199.
    6. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    7. Christian Tilk & Ann-Kathrin Rothenbächer & Timo Gschwind & Stefan Irnich, 2016. "Asymmetry Helps: Dynamic Half-Way Points for Solving Shortest Path Problems with Resource Constraints Faster," Working Papers 1615, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    8. Said Dabia & David Lai & Daniele Vigo, 2019. "An Exact Algorithm for a Rich Vehicle Routing Problem with Private Fleet and Common Carrier," Transportation Science, INFORMS, vol. 53(4), pages 986-1000, July.
    9. Bhusiri, Narath & Qureshi, Ali Gul & Taniguchi, Eiichi, 2014. "The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 1-22.
    10. Tilk, Christian & Rothenbächer, Ann-Kathrin & Gschwind, Timo & Irnich, Stefan, 2017. "Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster," European Journal of Operational Research, Elsevier, vol. 261(2), pages 530-539.
    11. Florian Kellner, 2022. "Generating greenhouse gas cutting incentives when allocating carbon dioxide emissions to shipments in road freight transportation," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 833-874, September.
    12. Lozano, S. & Moreno, P. & Adenso-Díaz, B. & Algaba, E., 2013. "Cooperative game theory approach to allocating benefits of horizontal cooperation," European Journal of Operational Research, Elsevier, vol. 229(2), pages 444-452.
    13. Ciancio, Claudio & Laganá, Demetrio & Vocaturo, Francesca, 2018. "Branch-price-and-cut for the Mixed Capacitated General Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 267(1), pages 187-199.
    14. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.
    15. Line Blander Reinhardt & Mads Kehlet Jepsen & David Pisinger, 2016. "The Edge Set Cost of the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 50(2), pages 694-707, May.
    16. Zhenzhen Zhang & Zhixing Luo & Hu Qin & Andrew Lim, 2019. "Exact Algorithms for the Vehicle Routing Problem with Time Windows and Combinatorial Auction," Transportation Science, INFORMS, vol. 53(2), pages 427-441, March.
    17. Yin, Yunqiang & Yang, Yongjian & Yu, Yugang & Wang, Dujuan & Cheng, T.C.E., 2023. "Robust vehicle routing with drones under uncertain demands and truck travel times in humanitarian logistics," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    18. Nikolaus Furian & Michael O’Sullivan & Cameron Walker & Eranda Çela, 2021. "A machine learning-based branch and price algorithm for a sampled vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 693-732, September.
    19. Said Dabia & Emrah Demir & Tom Van Woensel, 2017. "An Exact Approach for a Variant of the Pollution-Routing Problem," Transportation Science, INFORMS, vol. 51(2), pages 607-628, May.
    20. Yiming Liu & Yang Yu & Yu Zhang & Roberto Baldacci & Jiafu Tang & Xinggang Luo & Wei Sun, 2023. "Branch-Cut-and-Price for the Time-Dependent Green Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 14-30, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:55:y:2021:i:1:p:179-195. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.