Deriving Convergence of Vehicle Routing Problems using a Fictitious Play Approach

Abstract

Vehicle Routing Problem (VRP) has been the subject of many studies during the last few years. Many different kinds of algorithms were developed for its solution, as reviewed in Cordeau et al. (2004).

This paper defines VRP as a fictitious play to give mathematical support to the effectiveness of some of the most known solution strategies and techniques. It will be proved that reaching a solution of given requirements is possible in the trivial case (i.e., if the algorithm starts with a solution having the same order of precision), or if the distance between the starting and the final solution can be reduced slightly fast.

After having defined VRP as a fictitious play (paragraph 1), this paper states the wellknown theorem of Monderer and Shapley for fictitious plays (paragraph 2). The structure of some of the most recent algorithms for the solution of VRP is then re-examined in the light of this theorem, used as a convergence criterion (paragraph 3). Some conclusions and possibilities of further development are briefly drawn in the final paragraph 4.

Keywords:

• Vehicle Routing Problem
• Fictitious Play
• Convergence
• Heuristic
• Transportation