The multi-vehicle covering tour problem: building routes for urban patrolling
In this paper we study a particular aspect of the urban community policing: routine patrol route planning. We seek routes that guarantee visibility, as this has a sizable impact on the community perceived safety, allowing quick emergency responses and providing surveillance of selected sites (e.g., hospitals, schools). The planning is restricted to the availability of vehicles and strives to achieve balanced routes. We study an adaptation of the model for the multi-vehicle covering tour problem, in which a set of locations must be visited, whereas another subset must be close enough to the planned routes. It constitutes an NP-complete integer programming problem. Suboptimal solutions are obtained with several heuristics, some adapted from the literature and others developed by us. We solve some adapted instances from TSPLIB and an instance with real data, the former being compared with results from literature, and latter being compared with empirical data.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Exact algorithms and heuristics for capacitated covering salesman problems
This paper introduces the Capacitated Covering Salesman Problem (CCSP), approaching the notion of service by coverage in capacitated vehicle routing problems. In CCSP, locations where vehicles can transit are provided, s…
Dynamic Bi-Objective Routing of Multiple Vehicles
In practice, e.g. in delivery and service scenarios, Vehicle-Routing-Problems (VRPs) often imply repeated decision making on dynamic customer requests. As in classical VRPs, tours have to be planned short while the numbe…
Decision MakingSequential Decision MakingBuildMapper: A Fully Learnable Framework for Vectorized Building Contour Extraction
Deep learning based methods have significantly boosted the study of automatic building extraction from remote sensing images. However, delineating vectorized and regular building contours like a human does remains very c…
PolyBuild: An End-to-End Method for Polygonal Building Contour Extraction from High-Resolution Remote Sensing Images
Extracting building polygon contours from high-resolution remote sensing images is a fundamental task for various mapping applications. However, the presence of varying imaging conditions and complex building structures,…
Object DetectionMulti-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach
Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics distribution systems. Over the past decade, numerous methods for MVRPSTW have been proposed, but most are …
Computational EfficiencyDecoderMulti-agent Reinforcement Learningreinforcement-learning+2