A MTZ Formulation-Based Formulation of the Traveling Salesman Problem under Uncertainty
Engineering, Technology & Applied Science Research · 06.06.2026 · 16 (3) · 36762-36768
DOI: 10.48084/etasr.17944 ↗Kurz gefasst
Fachartikel in der Zeitschrift Engineering, Technology & Applied Science Research, online erschienen am 06.06.2026. Verfasst von Soufia Benhida und 3 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Benhida, S., Hassani, I. B., Lamii, N., & Oqaidi, K. (2026). A MTZ Formulation-Based Formulation of the Traveling Salesman Problem under Uncertainty. Engineering, Technology & Applied Science Research, 16(3), 36762-36768. https://doi.org/10.48084/etasr.17944
Vancouver
Benhida S, Hassani IB, Lamii N, Oqaidi K. A MTZ Formulation-Based Formulation of the Traveling Salesman Problem under Uncertainty. Engineering, Technology & Applied Science Research. 2026;16(3):36762-36768. doi:10.48084/etasr.17944
BibTeX
@article{Benhida2026,
author = {Benhida, Soufia and Hassani, Imane Beqqali and Lamii, Nabil and Oqaidi, Khalid},
title = {A MTZ Formulation-Based Formulation of the Traveling Salesman Problem under Uncertainty},
journal = {Engineering, Technology & Applied Science Research},
year = {2026},
volume = {16},
number = {3},
pages = {36762--36768},
doi = {10.48084/etasr.17944}
}
EUVIMED