Orienteering problem with time-windows and updating delay

Bertrand Jouve (1) , Marc Demange , David Ellison

1 LISST - Laboratoire Interdisciplinaire Solidarités, Sociétés, Territoires

The Orienteering Problem with Time Window and Delay (OPTiWinD) is a variant of the online orienteering problem. A series of requests appear in various locations while a vehicle moves within the territory to serve them. Each request has a time window during which it can be served and a weight which describes its importance. There is also a minimum delay T between successive requests. The objective is to find a path for the vehicles that maximises the sum of the weights of the requests served. We further assume that the length of each time window is equal to the diameter of the territory. We study the optimal performance and competitive ratio for the set of instances with n requests. We obtain complete resolution for T at least half of the diameter, small values of T or small values of n, as well as partial results in the remaining cases.

Mots clés: Online orienteering problem; Online scheduling; Competitive analysis; Combinatorial optimisation

Domaines: Mathématique discrète [cs.DM]

Bertrand Jouve, Marc Demange, David Ellison. Orienteering problem with time-windows and updating delay. Theoretical Computer Science, 2021, 863, pp.1-18. ⟨10.1016/j.tcs.2021.01.003⟩. ⟨hal-03507666⟩