Visiting a network of services with time constraints

Visiting a network of services with time constraints

0.00 Avg rating0 Votes
Article ID: iaor20042082
Country: United Kingdom
Volume: 30
Issue: 8
Start Page Number: 1187
End Page Number: 1217
Publication Date: Jul 2003
Journal: Computers and Operations Research
Authors:
Keywords: heuristics
Abstract:

A set of facilities is connected by a transportation network, where the weight of each arc corresponds to its travel time. Each facility is capable of providing a specific service during prespecified set of time windows. A visiting path of length k visits exactly k different facilities, respecting the time window of each facility within a given time limit Tmax. This paper examines the specific problem of finding the maximum number of feasible paths that visit k facilities. For this optimisation problem, which is shown to be NP-hard, a heuristic approach is presented to solve real size problems. We discuss in detail our computational experience on City of Rome's network and we present some computational results obtained applying our algorithm on randomised graph instances.

Reviews

Required fields are marked *. Your email address will not be published.