wiki:Documentation/Reference/ProbabilisticTravelingSalesmanProblem

Version 5 (modified by apolidur, 4 years ago) (diff)

--

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 a estimated PTSP. Currently, one 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.

HeuristicLab Results

References