A novel encoding scheme based evolutionary approach for the bi-objective grid patrol routing problem with multiple vehicles
نویسندگان
1 School of Planning, Architecture and Civil Engineering, Queen's University Belfast, United Kingdom
2 Department of Civil and Environmental Engineering, The University of Auckland, New Zealand
3 School of Planning, Architecture and Civil Engineering, Queen's University Belfast, United Kingdom
4 Faculty of Civil Engineering, Universiti Teknologi Malaysia, 81310 Johor Bahru, Johor, Malaysia
5 Faculty of Civil Engineering, Universiti Teknologi Malaysia, 81310 Johor Bahru, Johor, Malaysia
doi
چکیده
In this paper, we investigate the bi-objective grid patrol routing problem (BGPRP) in which multiple patrol vehicles have to cooperatively patrol several nodes for a given specific time during a certain planning horizon in a grid map. The BGPRP is an NP-hard problem and an extended application of periodic vehicle routing problem (PVRP). However, unlike PVRP, in addition to minimizing the total routing distance, the considered BGPRP also aims to maximize the routing coverage of lanes. The BGPRP involves both the combination and permutation of nodes simultaneously. In this paper, an efficient encoding scheme is developed to tackle both the combination and the permutation of nodes simultaneously, and then we apply an immune based evolutionary approach for solving the BGPRP with the objective of minimizing total routing distance. Finally, an integer programming approach is utilized to maximize the routing coverage of lanes. Numerical results of multiple patrol vehicles in a grid map show the performance of the approach.
