A MTZ Formulation-Based Formulation of the Traveling Salesman Problem under Uncertainty
Received: 3 February 2026 | Revised: 20 March 2026, 1 April 2026, and 4 April 2026 | Accepted: 5 April 2026 | Online: 6 June 2026
Corresponding author: Soufia Benhida
Abstract
The Traveling Salesman Problem (TSP) plays a key role in transport logistics, particularly in route optimization and cost reduction. In transportation and distribution, it is significant to minimize vehicle travel distance while meeting delivery deadlines. The TSP determines the shortest route that passes through multiple destinations before returning to the starting point, thereby reducing fuel consumption and travel time. This problem is the basic model for all transportation problems, and its concept is well known in operations research. This article addresses its stochastic version. The classic TSP is considered, but with a more specific case: the customers on the tour are random variables. These customers are associated with a probability pi, and the tour must be adapted to ignore absent customers. The proposed formulation is based on the original PTSP2 model. To determine the effectiveness of the proposed formulation, a comparative analysis was conducted with an existing model in the literature based on the Miller–Tucker–Zemlin (MTZ) formulation. The comparison was conducted primarily of the Continuous Relaxation Quality (QRC%) bounds determined by the two models. The two formulations were then solved via an exact solution based on a Branch-and-Cut algorithm with a constraint generation strategy that permits constraint violations to be added gradually as the optimization occurred. The models were tested with a series of test instances to evaluate their performance. The findings indicate that the proposed formulation generates substantially tighter continuous relaxation bounds. Specifically, the QRC of the proposed model has increased by over 50% compared with that of the currently existing MTZ-based model reported in the literature. Secondly, the introduced model is more computationally effective in several cases. These findings prove that the proposed formulation is effective in addressing the problem in question.
Keywords:
probabilistic traveling salesman problem, constraint generation strategy, MTZ formulation, customers, continuous relaxation quality, stochastic model, two-stage formulation, computing time, classical TSPReferences
D. Fouskakis and D. Draper, "Comparing Stochastic Optimization Methods for Variable Selection in Binary Outcome Prediction, With Application to Health Policy," Journal of the American Statistical Association, vol. 103, no. 484, pp. 1367–1381, Dec. 2008.
M.-H. Lin, J.-F. Tsai, and C.-S. Yu, "A Review of Deterministic Optimization Methods in Engineering and Management," Mathematical Problems in Engineering, vol. 2012, no. 1, 2012, Art. no. 756023.
J. C. Spall, "Stochastic Optimization," in Handbook of Computational Statistics: Concepts and Methods, J. E. Gentle, W. K. Härdle, and Y. Mori, Eds. Berlin, Heidelberg: Springer, 2012, pp. 173–201.
L. A. Hannah, "Stochastic optimization," International Encyclopedia of the Social & Behavioral Sciences, vol. 2, pp. 473–481, 2015.
P. Adasme, R. Andrade, J. Leung, and A. Lisser, "A Two-stage Stochastic Programming Approach for the Traveling Salesman Problem," presented at the International Conference on Operations Research and Enterprise Systems, Feb. 2016, vol. 2, pp. 163–169.
P. Jaillert, "Probabilistic Traveling Salesman Problems," M.S. Thesis, Massachusetts Institute of Technology, USA, 1985.
L. Zhou, Y. Ju, and S. Moura, "Learning-Guided Local Search for Asymmetric Traveling Salesman Problem," presented at the 2nd AI for Math Workshop @ ICML 2025, July 2025, [Online]. Available: https://openreview.net/forum?id=PlEn4KjSTN¬eId=PlEn4KjSTN.
C. E. Miller, A. W. Tucker, and R. A. Zemlin, "Integer Programming Formulation of Traveling Salesman Problems," J. ACM, vol. 7, no. 4, pp. 326–329, July 1960.
E. dos S. Teixeira and S. A. de Araujo, "Formulations for the Traveling Salesman Problem with D-Relaxed Priority Rule." Social Science Research Network, Rochester, NY, Aug. 14, 2022.
T. Bektaş and L. Gouveia, "Requiem for the Miller–Tucker–Zemlin subtour elimination constraints?," European Journal of Operational Research, vol. 236, no. 3, pp. 820–832, Aug. 2014.
M. Velednitsky, "Short Combinatorial Proof that the DFJ Polytope is contained in the MTZ Polytope for the Asymmetric Traveling Salesman Problem," Operations Research Letters, vol. 45, no. 4, pp. 323–324, July 2017.
G. Dantzig, R. Fulkerson, and S. Johnson, "Solution of a Large-Scale Traveling-Salesman Problem," Journal of the Operations Research Society of America, vol. 2, no. 4, pp. 393–410, Nov. 1954.
P. L. J. Wissink, "The Traveling Salesman Problem with Stochastic and Correlated Customers," Transportation Science, vol. 57, no. 5, pp. 1321–1339, Sept. 2023.
Ф. Ель Асрі, К. Таяні, Х. Фахурі, F. El Asri, C. Tajani, and H. Fakhouri, "A combined ant colony optimization with Levy flight mechanism for the probabilistic traveling salesman problem with deadlines," Feb. 2024.
M. Blanchard, A. Jacquillat, and P. Jaillet, "Probabilistic Bounds on the k-Traveling Salesman Problem and the Traveling Repairman Problem," Mathematics of Operations Research, vol. 49, no. 2, pp. 1169–1191, May 2024.
R. Salman, F. Ekstedt, and P. Damaschke, "Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem," Operations Research Letters, vol. 48, no. 2, pp. 163–166, Mar. 2020.
T. Q. T. Vo, M. Baiou, and V. H. Nguyen, "A branch-and-cut algorithm for the balanced traveling salesman problem," Journal of Combinatorial Optimization, vol. 47, no. 2, Jan. 2024, Art. no. 4.
R. Tadei, G. Perboli, and F. Perfetti, "The multi-path Traveling Salesman Problem with stochastic travel costs," EURO Journal on Transportation and Logistics, vol. 6, no. 1, pp. 3–23, Mar. 2017.
S. Rosenow, "A heuristic for the probabilistic traveling salesman problem," in Operations Research Proceedings 1996, 1997, pp. 117–122.
G. Campuzano, C. Obreque, and M. M. Aguayo, "Accelerating the Miller–Tucker–Zemlin model for the asymmetric traveling salesman problem," Expert Systems with Applications, vol. 148, June 2020, Art. no. 113229.
É. D. Taillard, "A linearithmic heuristic for the travelling salesman problem," European Journal of Operational Research, vol. 297, no. 2, pp. 442–450, Mar. 2022.
G. Angulo and D. Moran, "On parametric formulations for the Asymmetric Traveling Salesman Problem." arXiv, Nov. 21, 2024.
M. Lopez-Ibanez and T. Stutzle, "The Automatic Design of Multiobjective Ant Colony Optimization Algorithms," IEEE Transactions on Evolutionary Computation, vol. 16, no. 6, pp. 861–875, Sept. 2012.
R. Gan, Q. Guo, H. Chang, and Y. Yi, "Improved ant colony optimization algorithm for the traveling salesman problems," Journal of Systems Engineering and Electronics, vol. 21, no. 2, pp. 329–333, Apr. 2010.
T.-L. Jin, Q.-J. Jiang, and Z.-K. Shao, "Particle Swarm Optimization-Based Algorithms for Traveling Salesman Problem," in 2025 Joint International Conference on Automation-Intelligence-Safety (ICAIS) & International Symposium on Autonomous Systems (ISAS), Feb. 2025, pp. 1–5.
C. Blum and A. Roli, "Metaheuristics in combinatorial optimization: Overview and conceptual comparison," ACM Comput. Surv., vol. 35, no. 3, pp. 268–308, June 2003.
H. Jafarzadeh, N. Moradinasab, and M. Elyasi, "An Enhanced Genetic Algorithm for the Generalized Traveling Salesman Problem," Engineering, Technology & Applied Science Research, vol. 7, no. 6, pp. 2260–2265, Dec. 2017.
M. Abdul-Niby, M. Alameen, A. Salhieh, and A. Radhi, "Improved Genetic and Simulating Annealing Algorithms to Solve the Traveling Salesman Problem Using Constraint Programming," Engineering, Technology & Applied Science Research, vol. 6, no. 2, pp. 927–930, Apr. 2016.
Downloads
How to Cite
License
Copyright (c) 2026 Soufia Benhida, Imane Beqqali Hassani, Nabil Lamii, Khalid Oqaidi
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
