Probabilistic Traveling Salesman Problem: Mathematical Model and Heuristic Approach

Optimisation in transport logistics plays a central role in the efficient management of supply chains, as it helps to reduce costs, improve productivity and maximize customer satisfaction. It is essentially a decision-making tool for companies and individuals. In this context, this work focuses on tour optimization, presented as the Traveling Salesman Problem (TSP). First, a detailed presentation of the TSP is provided, followed by a generation constraint strategy for solving the problem. Next, the stochastic version, known as the Probabilistic Traveling Salesman Problem (PTSP), is examined, where customer locations are random variables. This problem is relevant to many delivery companies where a subset of customers requires delivery every day, while others may not order or can cancel at the last minute, necessitating re-optimization to find an optimal TSP tour for each day. A new mathematical formulation of the PTSP is proposed, based on the Dantzig, Fulkerson, Johnson formulation of the classical TSP. This formulation is efficient for solving complex problems. The objective of this work is to prove that the presented formulation of the probabilistic problem is better than the one in the literature, as well as numerical results obtained by exact solution for a series of small instances.