For example, delivery companies need to work out how to pick up packages from multiple depots and deliver them to customers who may be dispersed over a large geographical area. A well-designed route can improve the efficiency of this process and substantially reduce the cost of the distributed service. Therefore, routing problems have long been an essential area of operations research, and are receiving increasing attention in both research and applications.
Routing problems become more complicated when multiple vehicles from different depots are involved, where the balance of workloads and route lengths should be considered. In the case of policing, police patrol officers belong to different stations, and should cooperate to cover a set of important crime hotspots in the region. The patrol routes should be balanced in order to target crime and promote public confidence through visibility, whilst preventing work overload.
At UCL, we are researching how to design balanced routes for police patrol, in order to improve the efficiency of policing. This involves formulating the problem on the road network, and then solving the problem with intelligent computational algorithms. You can read about the latest progress of this research in our paper ‘Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a Police Patrolling Case’– International Journal of Geographical Information Science (October 2017).
This research solves the route design problem where multiple vehicles from different depots cooperate to cover a set of locations on the road network. An efficient algorithm has been developed to determine balanced routes for vehicles, based on their depots. The method is applied to police patrol routing.
Authors
Tao Cheng, Huanfa Chen, John Shawe-Taylor
