The Multi-Path Traveling Salesman Problem with Dependent Random Cost Oscillations

Reducing air pollution is nowadays one of the main goals of several institutions and go- vernments of industrial countries. Developing methods able to schedule companies logistic operations and public services in a efficient way is coherent with such objective as it would imply less production of pollutants. Several logistic problems can be assimilated to the traveling salesman problem (TSP). Nevertheless, in real applications the stochastic envi- ronment deeply influences the performance of the solution. In [1] it has been proven that it is important to consider the stochastic nature of the distribution network in order to obtain affordable solutions. Nevertheless, since the complexity of the stochastic problem grows very fast, deterministic approximations have been developed. All these approxima- tions assume that cost oscillations are independent and identically distributed. In this paper, we relax such hypothesis by assuming that cost oscillations are still identically distributed but just asymptotically independent. This assumption addresses the traffic congestion effects. In particular, we consider the multi-path traveling salesman problem with dependent random cost oscillations (mpTSPdo), where the cost oscillations are sto- chastic with unknown distribution and between any pair of locations there are usually several alternative paths. We propose a method to find a deterministic approximation solution of the mpTSPdo and we evaluate its quality and efficiency.