A novel encoding scheme based evolutionary approach for the bi-objective grid patrol routing problem with multiple vehicles
نویسندگان
1 College of Information and Communication Engineering, Sungkyunkwan University 300 Cheoncheon-dong, Jangan-gu, Suwon-si, Gyeonggi-do 440-746, Korea
2 Department of Information and Electronics Engineering, Mokpo National University 1666 Cheonggye-myeon, Muan-gun, Jeollanam-do 534-729, Korea
3 School of Electrical Engineering and Computer Science, Oregon State University Corvallis, Oregon, 97331, USA
4 College of Information and Communication Engineering, Sungkyunkwan University 300 Cheoncheon-dong, Jangan-gu, Suwon-si, Gyeonggi-do 440-746, Korea
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.
