×

The joint network vehicle routing game with optional customers. (English) Zbl 1511.90083

Summary: We consider logistic collaborations where multiple carriers collaborate by consolidating demands, combining delivery routes, and serving new customers. Logistic collaborations are known to provide numerous benefits such as an increase in profit as well as a reduction in emissions for all parties involved. One of the challenges associated with collaborations is the allocation of the additional profits. To this end, we model the corresponding profit allocation problem as a collaborative game. Here, the profit obtained by any subset of the collaborating carriers depends on the new customers served by the remaining carriers. Specifically, we try to determine an allocation in the core based on both the best-case profit and the worst-case profit that each subset of carriers can attain. To achieve this, we propose a heuristic row generation algorithm. We verify the performance of this algorithm on instances derived from benchmark instances of the capacitated vehicle routing problem. We show that our heuristic algorithm scales well with respect to the number of carriers considered and provides allocations similar to those obtained by enumerating all best-case and worst-case profits of each coalition.

MSC:

90B06 Transportation, logistics and supply chain management
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
91A12 Cooperative games

Software:

CVRPSP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Augerat, P., Approche Polyédrale Du Problème de Tournées de Véhicules (1995), Institut National Polytechnique de Grenoble, France
[2] Baldacci, R.; Mingozzi, A.; Roberti, R., New route relaxation and pricing strategies for the vehicle routing problem, Oper. Res., 59, 5, 1269-1283 (2011) · Zbl 1233.90059
[3] Ballot, E.; Fontane, F., Reducing transportation CO2 emissions through pooling of supply networks: perspectives from a case study in french retail chains, Prod. Plann. Control, 21, 6, 640-650 (2010)
[4] Costa, L.; Contardo, C.; Desaulniers, G., Exact branch-price-and-cut algorithms for vehicle routing, Transp. Sci., 53, 4, 946-985 (2019)
[5] Dai, B.; Chen, H., Proportional egalitarian core solution for profit allocation games with an application to collaborative transportation planning, Eur. J. Indust. Eng., 9, 1, 53 (2015)
[6] Drechsel, J.; Kimms, A., Computing core allocations in cooperative games with an application to cooperative procurement, Int. J. Prod. Econ., 128, 1, 310-321 (2010) · Zbl 1209.91028
[7] Engevall, S.; Göthe-Lundgren, M.; Värbrand, P., The traveling salesman game: An application of cost allocation in a gas and oil company, Ann. Oper. Res., 82, 453-472 (1998) · Zbl 0910.90272
[8] Engevall, S.; Göthe-Lundgren, M.; Värbrand, P., The heterogeneous vehicle-routing game, Transp. Sci., 38, 1, 71-85 (2004)
[9] Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C., An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems, Networks, 44, 3, 216-229 (2004) · Zbl 1056.90014
[10] Fishburn, P.; Pollak, H. O., Fixed-route cost allocation, Amer. Math. Monthly, 90, 6, 366-378 (1983) · Zbl 0515.90056
[11] Gansterer, M.; Hartl, R. F., Request evaluation strategies for carriers in auction-based collaborations, OR Spectrum, 38, 1, 3-23 (2016) · Zbl 1336.90015
[12] Gansterer, M.; Hartl, R. F., Collaborative vehicle routing: A survey, European J. Oper. Res., 268, 1, 1-12 (2018) · Zbl 1403.90110
[13] Göthe-Lundgren, M.; Jörnsten, K.; Värbrand, P., On the nucleolus of the basic vehicle routing game, Math. Program., 72, 1, 83-100 (1996) · Zbl 0851.90031
[14] Guajardo, M.; Rönnqvist, M., A review on cost allocation methods in collaborative transportation, Int. Trans. Oper. Res., 23, 3, 371-392 (2015) · Zbl 1338.90050
[15] Irnich, S.; Desaulniers, G., Shortest path problems with resource constraints, (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column Generation (2005), Springer US: Springer US Boston, MA), 33-65 · Zbl 1130.90315
[16] Krajewska, M. A.; Kopfer, H., Collaborating freight forwarding enterprises, OR Spectrum, 28, 3, 301-317 (2006) · Zbl 1130.90309
[17] Krajewska, M.; Kopfer, H.; Laporte, G.; Ropke, S.; Zaccour, G., Horizontal cooperation among freight carriers: request allocation and profit sharing, J. Oper. Res. Soc., 59, 11, 1483-1491 (2008) · Zbl 1168.90348
[18] Kuyzu, G., Lane covering with partner bounds in collaborative truckload transportation procurement, Comput. Oper. Res., 77, 32-43 (2017), https://www.sciencedirect.com/science/article/pii/S0305054816301824 · Zbl 1391.90069
[19] Laporte, G.; Nobert, Y.; Desrochers, M., Optimal routing under capacity and distance restrictions, Oper. Res., 33, 5, 1050-1073 (1985) · Zbl 0575.90039
[20] Lenstra, J.; Kan, A. H.G. R., Complexity of vehicle routing and scheduling problems, Networks, 11, 2, 221-227 (1981)
[21] Liu, R.; Jiang, Z.; Fung, R. Y.; Chen, F.; Liu, X., Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration, Comput. Oper. Res., 37, 5, 950-959 (2010), https://www.sciencedirect.com/science/article/pii/S0305054809001968 · Zbl 1177.90040
[22] Lysgaard, J.; Letchford, A. N.; Eglese, R. W., A new branch-and-cut algorithm for the capacitated vehicle routing problem, Math. Program., 100, 2, 423-445 (2004) · Zbl 1073.90068
[23] Martinelli, R.; Pecin, D.; Poggi, M., Efficient elementary and restricted non-elementary route pricing, European J. Oper. Res., 239, 1, 102-111 (2014) · Zbl 1339.90061
[24] Özener, O.Ö.; Ergun, Ö.; Savelsbergh, M., Lane-exchange mechanisms for truckload carrier collaboration, Transp. Sci., 45, 1, 1-17 (2011)
[25] Pecin, D.; Pessoa, A.; Poggi, M.; Uchoa, E., Improved branch-cut-and-price for capacitated vehicle routing, Math. Program. Comput., 9, 1, 61-100 (2016) · Zbl 1368.90111
[26] Pecin, D.; Pessoa, A.; Poggi, M.; Uchoa, E.; Santos, H., Limited memory rank-1 cuts for vehicle routing problems, Oper. Res. Lett., 45, 3, 206-209 (2017) · Zbl 1409.90231
[27] Pérez-Bernabeu, E.; Juan, A. A.; Faulin, J.; Barrios, B. B., Horizontal cooperation in road transportation: a case illustrating savings in distances and greenhouse gas emissions, Int. Trans. Oper. Res., 22, 3, 585-606 (2014) · Zbl 1317.90054
[28] Righini, G.; Salani, M., New dynamic programming algorithms for the resource constrained elementary shortest path problem, Networks, 51, 3, 155-170 (2008) · Zbl 1144.90514
[29] Soysal, M.; Bloemhof-Ruwaard, J. M.; Haijema, R.; van der Vorst, J. G., Modeling a green inventory routing problem for perishable products with horizontal collaboration, Comput. Oper. Res., 89, 168-182 (2018), https://www.sciencedirect.com/science/article/pii/S030505481630020X · Zbl 1391.90028
[30] van Zon, M.; Spliet, R.; van den Heuvel, W., The joint network vehicle routing game, Transp. Sci., 55, 1, 179-195 (2021)
[31] Wang, X.; Kopfer, H., Collaborative transportation planning of less-than-truckload freight, OR Spectrum, 36, 2, 357-380 (2014) · Zbl 1290.90051
[32] Zakharov, V.; Shchegryaev, A. N., Stable cooperation in dynamic vehicle routing problems, Autom. Remote Control, 76, 5, 935-943 (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.