Orienteering problem with time-windows and updating delay

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 d...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2021-04, Vol.863, p.1-18
Main Authors: Demange, Marc, Ellison, David, Jouve, Bertrand
Format: Article
Language:English
Subjects:
Combinatorial optimisation
Competitive analysis
Computer Science
Discrete Mathematics
Online orienteering problem
Online scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2021.01.003