Probabilistic Traveling Salesman Problem
Description
The Probabilistic Traveling Salesman Problem (PTSP) models situations in a delivery context where a set of customers have to be visited on a regular basis (e.g. daily), but all customers do not always require a visit (they have \probabilities" of being visited). In general, every day only a subset of customers requires a visit, and this subset is only known the same day as the required deliveries so re-optimizing vehicle routes from scratch every day is unfeasible. In this situation, the delivery man would follow a standard route skipping the customers that do not require a visit on that day. Therefore, the goal is to find a standard route of least expected length.
Based on the way the solutions are evaluated, we can distinguish between an analytical PTSP and am estimated PTSP. Currently, only the second one is fully functional in HeuristicLab.
Problem Parameters:
| Parameter | Description |
|---|---|
| BestKnownQuality | The quality of the best known solution of this PTSP instance. |
| BestKnownSolution | The best known solution of this PTSP instance. |
| Coordinates | The x- and y-Coordinates of the cities. |
| DistanceMatrix | The matrix which contains the distances between the cities. |
| Evaluator | The operator which should be used to evaluate PTSP solutions. |
| ProbablityMatrix | The matrix which contains the probabilities of the cities. |
| Realizations | The list which contains the realizations of the Monte Carlo sampling. |
| RealizationsSize | The integer which represents the number of realizations to use. |
| SolutionCreator | RandomPermutationCreator: The operator which should be used to create new TSP solutions. |
| UseDistanceMatrix | True if a distance matrix should be calculated and used for evaluation, otherwise false. |
