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).
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-pp.ucl.ac.uk/id/eprint/10026011 |
Archive Staff Only
 |
View Item |
