Abstract | ||
---|---|---|
The Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) is a Stochastic Vehicle Routing Problem considering time dependencies. Even the evaluation of the objective function is considered to be a computationally demanding task. So far there is no evaluation method known that guarantees a polynomial runtime, but on the other hand there are also no hardness results regarding the PTSPD objective function. In our work we show that the evaluation of the objective function of the PTSPD, even for Euclidean instances, is #P-hard. In fact, we even show that computing the probabilities, with which deadlines are violated is #P-hard. Based on this result we additionally show that the decision variant of the Euclidean PTSPD, the optimization variant of the Euclidean PTSPD and delta evaluation in reasonable local search neighborhoods is #P-hard. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-32147-4_35 | ISCO |
Keywords | Field | DocType |
delta evaluation,evaluation method,optimization variant,salesman problem,hardness result,euclidean ptspd,stochastic vehicle routing problem,objective function,ptspd objective function,decision variant,euclidean instance | Probabilistic traveling salesman problem,Mathematical optimization,Vehicle routing problem,Polynomial,Local search (optimization),Euclidean geometry,Mathematics,Computational complexity theory | Conference |
Citations | PageRank | References |
6 | 0.52 | 16 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dennis Weyland | 1 | 108 | 8.43 |
Roberto Montemanni | 2 | 643 | 44.25 |
Luca Maria Gambardella | 3 | 7926 | 726.40 |