UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case

Chen, H; Cheng, T; Shawe-Taylor, J; (2017) A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case. International Journal of Geographical Information Science 10.1080/13658816.2017.1380201. (In press). Green open access

[thumbnail of A Balanced Route Design for Min Max Multiple Depot Rural Postman Problem MMMDRPP a police patrolling case.pdf]
Preview
Text
A Balanced Route Design for Min Max Multiple Depot Rural Postman Problem MMMDRPP a police patrolling case.pdf - Published Version

Download (2MB) | Preview

Abstract

Providing distributed services on road networks is an essential concern for many applications, such as mail delivery, logistics and police patrolling. Designing effective and balanced routes for these applications is challenging, especially when involving multiple postmen from distinct depots. In this research, we formulate this routing problem as a Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP). To solve this routing problem, we develop an efficient tabu-search-based algorithm and propose three novel lower bounds to evaluate the routes. To demonstrate its practical usefulness, we show how to formulate the route design for police patrolling in London as an MMMDRPP and generate balanced routes using the proposed algorithm. Furthermore, the algorithm is tested on multiple adapted benchmark problems. The results demonstrate the efficiency of the algorithm in generating balanced routes.

Type: Article
Title: A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case
Open access status: An open access version is available from UCL Discovery
DOI: 10.1080/13658816.2017.1380201
Publisher version: https://doi.org/10.1080/13658816.2017.1380201
Language: English
Additional information: This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/ by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Keywords: Arc routing, rural postman problem, tabu search, police patrol
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Civil, Environ and Geomatic Eng
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of the Built Environment
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of the Built Environment > Centre for Advanced Spatial Analysis
URI: https://discovery.ucl.ac.uk/id/eprint/10026011
Downloads since deposit
179Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item