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

Autor(en)
Georg Erwin Adrian Fröhlich, Karl Franz Dörner, Margaretha Gansterer
Abstrakt

Many security companies offer patrolling services, such that guards inspect facilities or streets on a regular basis. Patrolling routes should be cost efficient, but the inspection patterns should not be predictable for offenders. We introduce this setting as a multi-objective periodic mixed capacitated general routing problem with objectives being cost minimization and route inconsistency maximization. The problem is transformed into an asymmetric capacitated vehicle routing problem, on both a simple-graph and a multi-graph; and three multi-objective frameworks using adaptive large neighborhood search are implemented to solve it. As tests with both artificial and real-world instances show that some frameworks perform better for some indicators, a hybrid search procedure, combining two of them, is developed and benchmarked against the individual solution methods. Generally, results indicate that considering more than one shortest path between nodes, can significantly increase solution quality for smaller instances, but is quickly becoming a detriment for larger instances.

Organisation(en)
Institut für Business Decisions and Analytics, Forschungsverbund Data Science
Externe Organisation(en)
Alpen-Adria-Universität Klagenfurt
Journal
Networks (New York): an international journal
Band
76
Seiten
431-450
Anzahl der Seiten
20
ISSN
0028-3045
DOI
https://doi.org/10.1002/net.21993
Publikationsdatum
2019
Peer-reviewed
Ja
ÖFOS 2012
502052 Betriebswirtschaftslehre
Schlagwörter
ASJC Scopus Sachgebiete
Information systems, Computer Networks and Communications
Link zum Portal
https://ucris.univie.ac.at/portal/de/publications/secure-and-efficient-routing-on-nodes-edges-and-arcs-of-simplegraphs-and-of-multigraphs(299d42ed-921e-49c9-9fa1-2243d51627a7).html