Orienteering problem with time-windows and updating delay

DOI10.1016/J.TCS.2021.01.003MaRDI QIDQ2658039zbMATH OpenOpenAlexFDO

Authors Marc Demange, David Ellison, Bertrand Jouve

Publication date 18 March 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.00777

zbMATH Keywords

combinatorial optimisationcompetitive analysisonline orienteering problemonline scheduling

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Abstract: 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.

Recommendations

• Improved algorithms for orienteering and related problems
• The Orienteering Problem with Time Windows
• A dynamic and probabilistic orienteering problem
• Solving the orienteering problem with time windows via the pulse framework
• Approximation algorithms for time-dependent orienteering.

Cites work

• Algorithms for the on-line quota traveling salesman problem
• Algorithms for the on-line travelling salesman
• Encyclopedia of Distances
• How to whack moles
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• On-line algorithms for the dynamic traveling repair problem
• The orienteering problem
• The orienteering problem: a survey
• The selective travelling salesman problem

Cited in

(1)

• Solving the orienteering problem with time windows via the pulse framework

This page was built for publication: Orienteering problem with time-windows and updating delay

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2658039)