A novel encoding scheme based evolutionary approach for the bi-objective grid patrol routing problem with multiple vehicles

Authors

1 Department of Industrial Management, National Formosa University Huwei, Yunlin 632, TAIWAN

2 Department of Business Administration, National ChiaYi University Chia-Yi 600, TAIWAN

3 School of Information Science, University of Pittsburgh Pittsburgh, PA 15260, USA

4 Department of Security Technology and Management, WuFeng University Ming-Hsiung, Chia-Yi 621, TAIWAN

Abstract

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.

Keywords

Scientia Iranica
Volume 22, Issue 4 - Serial Number 4
Transactions on Mechanical Engineering (B)
August 2015
Pages 1576-1585

Files

Share

How to cite

Statistics