STRONG EQUILIBRIA IN THE VEHICLE ROUTING GAME

Nikolay Zenkevich () and Andrey Zyatchin ()
Additional contact information
Andrey Zyatchin: Center for International Logistics and Supply Chain Management, DB & RZD, Graduate School of Management, St. Petersburg University, Russia;

International Game Theory Review (IGTR), 2014, vol. 16, issue 04, 1-13

Abstract: This paper introduces an extension of the vehicle routing problem by including several distributors in competition. Each customer is characterized by demand and a wholesale price. Under this scenario a solution may have unserviced customers and elementary routes with no customer visits. The problem is described as a vehicle routing game (VRG) with coordinated strategies. We provide a computable procedure to calculate a strong equilibrium (SE) in the VRG that is stable against deviations from any coalition. Following this procedure, we solve iteratively optimization subproblems for a single distributor, reducing the set of unserviced customers at each iteration. We prove that strong equilibria of one type exist for a VRG, and we provide conditions for another type to exist. We also introduce a semi-cooperative SE that helps reduce a set of strong equilibria in the VRG. Our methodology is suited for parallel computing, and could be efficiently applied to routing vehicles with a few compartments. It also calculates a numerical example for a three person VRG with six cars and twelve customers.

Keywords: Game theory; combinatorial optimization; graph theory; networks; vehicle routing problem; 91A06; 91A43; 05C57 (search for similar items in EconPapers)
JEL-codes: B4 C0 C6 C7 D5 D7 M2 (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219198914500133
Access to full text is restricted to subscribers

Related works:
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:wsi:igtrxx:v:16:y:2014:i:04:n:s0219198914500133

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219198914500133

Access Statistics for this article

International Game Theory Review (IGTR) is currently edited by David W K Yeung

More articles in International Game Theory Review (IGTR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().