Integrating exclusion constraints into the traveling salesman Problem: An application to Formula 1 calendar design

© 2026 by the Author(s). This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution -Noncommercial 4.0 International License (CC-by the license) ( https://creativecommons.org/licenses/by-nc/4.0/ )

Download PDF

XML

Cite

Abstract

The paper presents an integer programming model for the Traveling Salesman Problem, extended with exclusion criteria that take into account for circumstances affecting the order of visits. The model is illustrated through a well-known real-world example: the optimization of the Formula 1 race calendar. For the 24 venues of the 2026 season, the optimal route of the reference model with 11 exclusion constraints has a length of 64,135 km, only about 1.7% longer than the unconstrained shortest tour (63,078 km) and about 39% shorter than the official sequence (105,571 km). In addition, the study analyzes how an increasing number of inserted exclusion restrictions affects computational requirements and runtime, which grows approximately linearly with the number of exclusions: from 1-2 min with 5 exclusions to over 10 min with 35-40 exclusions.

Keywords

Traveling salesman problem

Integer programing

Mixed-integer linear programming

Funding

None.

Conflict of interest

The author declares that there are no conflicts of interest related to the publication of this article.

References

Kucukoglu I, Gunduz T, Balkancioglu F, Topal EC, Sayim O. Application of precedence constrained travelling salesman problem model for tool path optimization in CNC milling machines. Int J Optim Control Theor Appl. 2019;9(3):59-68. https://doi.org/10.11121/ijocta.01.2019.00662
Asih HM, Leuveano RAC, Rahman A, Faishal M. Traveling salesman problem with prioritization for perishable products in Yogyakarta, Indonesia. J Adv Manuf Technol. 2022;16(3).
Miller CE, Tucker AW, Zemlin RA. Integer programming formulation of traveling salesman problems. J ACM. 1960;7(4):326-329. https://doi.org/10.1145/321043.321046
Bellmore M, Nemhauser GL. The traveling salesman problem: a survey. Oper Res. 1968;16(3):538-558. https://doi.org/10.1287/opre.16.3.538
Balas E, Toth P. Branch and Bound Methods for the Traveling Salesman Problem. John Wiley & Sons; 1983.
Rego C, Gamboa D, Glover F, Osterman C. Traveling salesman problem heuristics: leading methods, implementations and latest advances. Eur J Oper Res. 2011;211(3):427-441. https://doi.org/10.1016/j.ejor.2010.09.010
Shi Y, Zhang Y. The neural network methods for solving traveling salesman problem. Procedia Comput Sci. 2022;199:681-686. https://doi.org/10.1016/j.procs.2022.01.084
Sui J, Ding S, Huang X, et al. A survey on deep learning-based algorithms for the traveling salesman problem. Front Comput Sci. 2024;19(6). https://doi.org/10.1007/s11704-024-40490-y
Bai R, Chen X, Chen ZL, et al. Analytics and machine learning in vehicle routing research. Int J Prod Res. 2021;61(1):4-30. https://doi.org/10.1080/00207543.2021.2013566
Dumas Y, Desrosiers J, Gelinas E, Solomon MM. An optimal algorithm for the traveling salesman problem with time windows. Oper Res. 1995;43(2):367-371. https://doi.org/10.1287/opre.43.2.367
Ascheuer N, Fischetti M, Grötschel M. A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks. 2000;36(2):69-79. https://doi.org/10.1002/1097-0037(200009)36:2<69::aid-net1>3.0.co;2-q
Ascheuer N, Jünger M, Reinelt G. A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Comput Optim Appl. 2000;17(1):61-84. https://doi.org/10.1023/a:1008779125567
Vincenty T, Warren FE. A note on the reduction of measured distances to the ellipsoid. Surv Rev. 1975;23(175):40-42. https://doi.org/10.1179/sre.1975.23.175.40
Karney CFF. Algorithms for geodesics. J Geod. 2012;87(1):43-55. https://doi.org/10.1007/s00190-012-0578-z
Lindboe C. Geopy (Version 2.4.1) [Computer software]. 2024. Accessed January 8, 2026. https://geopy.readthedocs.io/en/stable/#module-geopy.distance
Mao X, Meng Z, Comer B, Decker T. Greenhouse Gas Emissions and Air Pollution from Global Shipping, 2016–2023. International Council on Clean Transportation; 2025. Accessed January 8, 2026. https://theicct.org/wp-content/uploads/2025/04/ID-332-%E2%80%93-Global-shipping_report_final.pdf
DeWeerdt T, Dargusch P, Hill G. A case study of how DHL practices carbon management. Adv Environ Eng Res. 2022;3(1):1-19. https://doi.org/10.21926/aeer.2201010
Balas E. Disjunctive programming. In: Annals of Discrete Mathematics. Elsevier; 1979:3-51. https://doi.org/10.1016/s0167-5060(08)70342-x
Williams HP. Model Building in Mathematical Programming. John Wiley & Sons; 2013.
Gurobi Optimization, LLC. Gurobi Optimizer (Version 11.0.0) [Computer software]. 2024. Accessed January 8, 2026. https://www.gurobi.com
Folium Contributors. Folium (Version 0.17.0) [Computer software]. 2024. Accessed January 8, 2026. https://python-visualization.github.io/folium/
Formula 1. Formula 1 reveals calendar for 2026 season. Formula 1. Accessed January 8, 2026. https://www.formula1.com/en/latest/article/formula-1-reveals-calendar-for-2026-season.YctbMZWqBvrgyddrnauo8
Wolsey LA. Integer Programming. Vol 42. New York: Wiley; 1998.

Previous article in this issue

Next article in this issue

Journal of Autonomous Systems Modelling and Computation, Published by AccScience Publishing