SANSERO: Safe and Secure Routing

Main aim of the project is to model and solve a novel multi-objective route planning problem that occurs especially in the area of security services. Typically, private security companies offer a range of services that seek to protect objects and individuals (e.g., personal protection, transportation of cash/individuals, mobile guarding, custody of buildings). Such security services can be classified as tasks that contain a routing component, and those without any such routing component. We distinguish three groups of related security tasks, in which (i) the security guard moves, but the objects/persons to be secured are fixed; (ii) both the guards and the objects/persons to be secured move; and (iii) neither the guard nor the objects/persons move. In this project, we seek to focus on problems that contain a routing component, which constitute security routing problems. In real-world applications, security guards must visit certain control points various times during a planning horizon (e.g., visit different factory premises multiple times through the night at irregular time intervals). When planning the routes, the distance traveled should be minimized to generate a cost-efficient solution. In addition, it should be hard to predict the times that the security personnel are located at a certain node or traverse specific edges, to reduce the risk of an attack. Therefore the problem at hand is a multi-objective problem with the main aims of minimizing the distance traveled and maximizing the amount of heterogeneous routes which can be achieved by mainly avoiding visits of the same nodes and/or traversing the same edges (i) in repetitive sequences; (ii) at periodic intervals; or (iii) always at the same time in the planning horizon. The definition and development of evaluation mechanisms is part of the work that will be conducted within the project. To solve the problem, we develop an innovative hybrid solution approach combining set covering / set partitioning with variable neighborhood search for the single objective problem (with multiple periods). Next a two-phase method, based on our hybrid method and path relinking will be developed to solve multi-objective problems with multiple periods. We will also adapt the hybrid genetic algorithm with adaptive diversity management developed by Vidal et al. (and combine this method with the NSGA-II/III) to compare the results achieved by this method to those achieved with our hybrid VNS (and its combination with path relinking). If time permits, we will extend the problem to consider real-world conditions, including (i) strategies to tackle additional personnel requirements in case of unforeseen events and (ii) the integration of synchronization strategies for control points that require the visit of two or more service guards at the same point in time.

Main aim of the project is to model and solve a novel multi-objective route planning problem that occurs especially in the area of security services. Typically, private security companies offer a range of services that seek to protect objects and individuals (e.g., personal protection, transportation of cash/individuals, mobile guarding, custody of buildings). Such security services can be classified as tasks that contain a routing component, and those without any such routing component. We distinguish three groups of related security tasks, in which (i) the security guard moves, but the objects/persons to be secured are fixed; (ii) both the guards and the objects/persons to be secured move; and (iii) neither the guard nor the objects/persons move. In this project, we seek to focus on problems that contain a routing component, which constitute security routing problems. In real-world applications, security guards must visit certain control points various times during a planning horizon (e.g., visit different factory premises multiple times through the night at irregular time intervals). When planning the routes, the distance traveled should be minimized to generate a cost-efficient solution. In addition, it should be hard to predict the times that the security personnel are located at a certain node or traverse specific edges, to reduce the risk of an attack. Therefore the problem at hand is a multi-objective problem with the main aims of minimizing the distance traveled and maximizing the amount of heterogeneous routes which can be achieved by mainly avoiding visits of the same nodes and/or traversing the same edges (i) in repetitive sequences; (ii) at periodic intervals; or (iii) always at the same time in the planning horizon. To solve the problem, we develop an innovative metaheuristic search technique based on adaptive large neighborhood search for the single objective problem (with multiple periods). For the multi-objective extension the adaptive large neighborhood search method is integrated into an epsilon constraint framework, a box-splitting framework and a multi directional local search. In the problem formulation simple graph models and also multi graph models were tested. With the new techniques especially with the multi graph extension new promising results for safe and secure routing problems could be generated.