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 well-known 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.

Deriving Convergence of Vehicle Routing Problems using a Fictitious Play approach

NOCERA, SILVIO
2007

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 well-known 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11578/586
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact