A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case. Issue 1 (2nd January 2018)

• Record Type: Journal Article
• Authors: Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John
• Is Part Of: International journal of geographical information science. Volume 32:Issue 1(2018)
• Page Start: 169
• Page End: 190
• Publication Date: 2018-01-02
• Subjects: Arc routing -- rural postman problem -- tabu search -- police patrol; Geography -- Data processing -- Periodicals; Information storage and retrieval systems -- Periodicals; Géomatique -- Périodiques; Systèmes d'information -- Périodiques; 910.285
• DOI: 10.1080/13658816.2017.1380201
• Languages: English
• ISSNs: 1365-8816

Abstract

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.