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.

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	TSPRoundedEuclideanPathEvaluator: 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.

HeuristicLab Results

References