SANSERO: Tourenplanung im Sicherheitsbereich

Im Rahmen des Projektes wird ein neuartiges, multikriterielles Tourenplanungsproblem betrachtet bei dem verschiedene Bedarfspunkte in periodischen Abständen bedient werden. Die Ziele bestehen darin, möglichst kosteneffiziente und zugleich möglichst heterogene Touren zu erzeugen. Letztere werden dadurch definiert dass es vermieden werden soll, dass gleiche Knoten/Kantensequenzen wiederholthintereinanderbesucht werden;dass bestimmte Knoten/Kanten immer in den gleichen periodischen Abständen besucht werden bzw. dass ein Knoten oder eine Kante immer zur selben Tageszeit besucht wird. Die Definition und Entwicklung von Evaluierungskonzepten für heterogene Touren wird im Rahmen des Projektes erfolgen. Die dargestelltenAnforderungenwerdenspeziell imSicherheitsbereich gestellt. Beispielsweisemüssen verschiedeneGebäude/RäumeinperiodischenAbständen kontrolliert werden, wobei die Kontrollzeitpunkte und routen immer unterschiedlich sein müssen, um das Risiko eines Zwischenfalls zu senken. Gleichzeitig soll die zurückgelegte Strecke minimiert werden, um eine möglichst kostengünstige Lösung zu erhalten. Generell bietenprivate Sicherheitsunternehmeneine Reihe anDienstleistungenan(zB Personenschutz, Transport von Bargeld/Personen, Bewachung von Gebäuden). All diese Aufgaben können als Leistungen die eine Routing-Komponente enthalten bzw. Leistungen die keine Routing-Komponente enthalten klassifiziert werden. Wir unterscheiden drei Gruppen (i) der Sicherheitsmann bewegt sich, die Objekte/Personen die gesichert werden sind fix, (ii) sowohl der Sicherheitsmann als auch die Objekte/Personen die gesichert werden bewegen sich, (iii) weder der Sicherheitsmann noch die Objekte/Personen bewegen sich. In diesem Projekt konzentrieren wir uns auf Probleme mit einer Routing Komponente und klassifizieren diese als Security Routing Probleme. Um das Problem zu lösen wird ein innovativer Hybridansatz basierend auf Set Covering / Set Partitioning und Variable Neighborhood Search entwickelt (zunächst für das mehrperiodische Einzielproblem). Dieser Ansatz wird dann mit Path Relinking verknüpft um die Lösung von Mehrzielproblemen zu ermöglichen. Zudem wird der hybride genetische Algorithmus, welcher von Vidal et al. entwickelt wurde erweitert (und mit dem NSGA-II/III Ansatz kombiniert), um die Ergebnisse unseres Ansatzes vergleichen zu können. Zudem ist geplant, das Problem um weitere reale Bedingungen erweitern, wie bspw. Berücksichtigung von zusätzlichem Mitarbeiterbedarf durch unvorhergesehene Ereignisse oder Planungsprobleme mit Synchronisationsnebenbedingungen für den Fall, dass an bestimmten Bedarfspunkten mehr als einen Mitarbeiter benötigt wird.

Im Rahmen des Projektes wird ein neuartiges, multikriterielles Tourenplanungsproblem betrachtet bei dem verschiedene Bedarfspunkte in periodischen Abständen bedient werden. Die Ziele bestehen darin, möglichst kosteneffiziente und zugleich möglichst heterogene Touren zu erzeugen. Letztere werden dadurch definiert dass es vermieden werden soll, dass gleiche Knoten/Kantensequenzen wiederholt hintereinander besucht werden; dass bestimmte Knoten/Kanten immer in den gleichen periodischen Abständen besucht werden bzw. dass ein Knoten oder eine Kante immer zur selben Tageszeit besucht wird. Die dargestellten Anforderungen werden speziell im Sicherheitsbereich gestellt. Beispielsweise müssen verschiedene Gebäude/Räume in periodischen Abständen kontrolliert werden, wobei die Kontrollzeitpunkte und -routen immer unterschiedlich sein müssen, um das Risiko eines Zwischenfalls zu senken. Gleichzeitig soll die zurückgelegte Strecke minimiert werden, um eine möglichst kostengünstige Lösung zu erhalten. Generell bieten private Sicherheitsunternehmen eine Reihe an Dienstleistungen an (zB Personenschutz, Transport von Bargeld/Personen, Bewachung von Gebäuden). All diese Aufgaben können als Leistungen die eine Routing-Komponente enthalten bzw. Leistungen die keine Routing-Komponente enthalten klassifiziert werden. Wir unterscheiden drei Gruppen (i) der Sicherheitsmann bewegt sich, die Objekte/Personen die gesichert werden sind fix, (ii) sowohl der Sicherheitsmann als auch die Objekte/Personen die gesichert werden bewegen sich, (iii) weder der Sicherheitsmann noch die Objekte/Personen bewegen sich. In diesem Projekt konzentrieren wir uns auf Probleme mit einer Routing Komponente und klassifizieren diese als "Security Routing" Probleme. Um diese Probleme zu lösen wird ein innovativer metaheuristischer Lösungsansatz basierend auf Adaptive Large Neighborhood Search entwickelt - für das mehrperiodische Einzielproblem. Dieser Ansatz wird dann mit epsilon-constraint, box-splitting, multi-directional local search zu einem Mehrziellösungsasatz erweitert. In der Modellierung werden neben der klassischen simple Graph Modellierung auch multi Graph Ansätze erprobt. Durch die neuen Lösungsmethoden insbesondere mit der multi Graph Erweiterung konnten neue gute Lösungen generiert werden.