Version 5 (modified by apolidur, 8 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. |