On the computational complexity of the Probabilistic Traveling Salesman Problem with Deadlines

The Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) is a stochastic vehicle routing problem considering time dependencies in terms of deadlines. The evaluation of the PTSPD objective function is believed to be a computationally demanding task and all efforts to find a polynomial time approach have failed so far. On the other hand, no hardness results regarding the evaluation of the PTSPD objective function are known. We fill this gap and show that the evaluation of the PTSPD objective function is indeed a computationally demanding task: even for Euclidean instances this task is #P-hard. We then derive additional hardness results for different computational tasks related to the PTSPD. Among other results, we show that the decision variant and the optimization variant of the PTSPD are both #P-hard. Following this, we focus on polynomial time approximations of the PTSPD objective function. We prove the existence of an FPRAS under certain conditions and examine the approximation guarantees obtained by the existing approaches. Finally, we give a strong inapproximability result regarding the objective function of a slightly more general problem, the Dependent PTSPD.