Secure and efficient routing on nodes, edges, and arcs on simple- and multi-graphs

Georg Erwin Adrian Fröhlich, Karl Franz Dörner, Margaretha Gansterer

Many security companies offer patrolling services, where guards have to inspect facilities or streets on a regular basis. Patrolling routes should be cost efficient, while the inspection patterns should not be predictable for of-fenders. Also cash-in-transit services result in routing problems, where cost minimization and route inconsistency have to be traded-off. We introduce this setting as multi-objective periodic node, edge, arc routing problem with the objectives being minimizing the costs and minimizing the route consistency. It is mathematically formulated and transformed into an asymmetric capacitated vehicle routing problem, once with a simple-graph and once with a multi-graph. In order to solve the problem, we propose to embed an adaptive large neighborhood search procedure into multi-objective solution frameworks. We implement three frameworks, namely multi-directional local search (MDLS), ε-constraint heuristic (ECH), and ε-box splitting heuristic (EBSH). The methods were tested on artificial as well as on real-world in-stances. In an extensive computational study, we show that EBSH and ECH seem to be the superior methods. Furthermore, the results indicate that considering more than one shortest paths between nodes, can significantly increases solution quality.

Department of Business Decisions and Analytics, Research Platform Data Science @ Uni Vienna, Department of Accounting, Innovation and Strategy
Networks (New York): an international journal
Publication date
Peer reviewed
Austrian Fields of Science 2012
502052 Business administration
Portal url