This article is cited in 2 papers

Multi-period cooperative vehicle routing games

Alexander Shchegryaev, Victor V. Zakharov

St. Petersburg State University, Faculty of Applied Mathematics and Control Processes, Universitetsky Prospect 35, St. Petersburg, Peterhof, 198504, Russia

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.

Language: English