Multi-period Cooperative Vehicle Routing Games

Authors

  • Alexander Shchegryaev Saint Petersburg State University
  • Victor V. Zakharov Saint Petersburg State University

Abstract

In the paper we treat the problem of minimizing and sharing joint transportation cost in multi-agent vehicle routing problem (VRP) on large-scale networks. A new approach for calculation subadditive characteristic function in multi-period TU-cooperative vehicle routing game (CVRG) has been developed. The main result of this paper is the method of constructing the characteristic function of cooperative routing game of freight carriers, which guarantees its subadditive property. A new algorithm is proposed for solving this problem, which is called direct coalition induction algorithm (DCIA). Cost sharing method proposed in the paper allows to obtain sharing distribution procedure which provides strong dynamic stability of cooperative agreement based on the concept of Sub-Core and time consistency of any cost allocation from Sub-Core in multi-period CVRG.

Keywords:

VRP, vehicle routing problem, vehicle routing games, heuristics, multi-period cooperative games, dynamic stability, time consistency

Downloads

Download data is not yet available.

References

Agarwal, R., Ö. Ergun, L. Houghtalen and O. O. Ozener (2009). Collaboration in Cargo Transportation. In Optimization and Logistics Challenges in the Enterprise. Springer Optimization and Its Applications, 30, 373–409.

Baldacci, R., A. Mingozzi and R. Roberti (2012). Recent exact algorithms for solvingthe vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218, 1–6.

Ergun, Ö., G. Kuyzu and M.W. P. Savelsbergh (2007). Shipper collaboration. Computers & Operations Research, 34, 1551–1560.

Kallehauge B. (2008). Formulations and exact algorithms for the vehicle routing problem with time windows. Computers & Operations Research, 35, 2307–2330.

Krajewska M. A., H. Kopfer, G. Laporte, S. Ropke and G. Zaccour (2009). Horizontal cooperation among freight carriers: request allocation and profit sharing. Journal of the Operational Research Society, 59, 1483–1491.

Petrosyan, L. A. and N. A. Zenkevich (2009). Principles of dynamic stability, Mat. Teor. Igr Pril.„ 1:1, 106–123 (in Russian).

Ropke S. and D. Pisinger (2006). An adaptive large neighbourhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40, 455–472.

Zakharov, V., O-Hun Kwon (1999). Selectors of the core and consistency properties. Game Theory and Applications, 4, 237–250.

Zakharov V., M. Dementieva (2004). Multistage cooperative games and problem of time–consistency. International Game Theory Review 6, 1, 1–14.

Downloads

Published

2022-08-09

How to Cite

Shchegryaev, A., & V. Zakharov, V. (2022). Multi-period Cooperative Vehicle Routing Games. Contributions to Game Theory and Management, 7. Retrieved from https://gametheory.spbu.ru/article/view/13622

Issue

Vol. 7 (2014)

Section

Articles

License

Articles of "Contributions to Game Theory and Management" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.