Probabilistic routing problems in the plane

Probabilistic routing problems are generalized versions of deterministic routing problems with explicit inclusion of probabilistic elements in the problem definitions. Based on the probabilistic traveling salesman problem (PTSP) and its generalizations (the m-PTSP, the Capacitated PTSP, and the Capacitated m-PTSP), the main objective of this paper is to give a rigorous treatment of the analysis of these problems in the plane. More specifically the paper presents general finite-size bounds and limit theorems for the different objective functions. It also describes some examples of worst-case and probabilistic analysis of heuristics for these problems and the paper finally indicates some open problems of general interest.