An asymptotic approximation of the traveling salesman problem with uniform non-overlapping time windows - CIS / I4S : Ingénierie des Systèmes de Soins et des Services de Santé Access content directly
Conference Papers Year : 2021

An asymptotic approximation of the traveling salesman problem with uniform non-overlapping time windows

Abstract

We develop a continuous asymptotic approximation of the traveling salesman problem with time windows in the Euclidean plane, constructing upon the well-known Beardwood-Halton-Hemmersley theorem. The time windows are taken to be a partition of a given time horizon. Computational experiments on random TSP with time windows instances show that the proposed asymptotic approximations of tour lengths and arrival times are close to the actual optimal values.
Fichier principal
Vignette du fichier
AsymTSP_TW.pdf (361.3 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03270043 , version 1 (24-06-2021)

Identifiers

Cite

Omar Rifki, Thierry Garaix, Christine Solnon. An asymptotic approximation of the traveling salesman problem with uniform non-overlapping time windows. CASE 2021 - IEEE 17th International Conference on Automation Science and Engineering, Aug 2021, Lyon, France. pp.1-6, ⟨10.1109/CASE49439.2021.9551615⟩. ⟨hal-03270043⟩
94 View
329 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More