Branch-and-Price Algorithm for the Team Orienteering Problem with Time-Dependent Rewards

Das Team Orienteering Problem mit zeitabhängigen Belohnungen (Team Orienteering Problem with Time-Dependent Rewards (TOPwTDR)) ist eine Erweiterung des klassischen Team Orienteering Problems, bei der der kundenbezogene Gewinn als eine Zeitfunktion dargestellt wird, z.B. linear fallende Funktion, exponentiell wachsende Funktion etc. Das Ziel des TOPwTDRs besteht darin, den Gesamtgewinn zu maximieren, so dass jeder Kunde innerhalb einer vorgeschriebenen Frist höchstens einmal besucht wird. Das TOPwTDR wurde bisher in der Literatur unter der Annahme von sinkenden Gewinnen betrachtet. Die Dantzig-Wolfe-Zerlegung wird angewendet und das TOPwTDR wird durch einen Branch-and-Price-Algorithmus exakt gelöst. Zur Lösung des Pricing-Problems wird ein modifizierter Labelling-Algorithmus vorgeschlagen, der in der ersten Stufe für die Spaltenfindung Heuristiken verwendet, um das reduzierte Masterproblem einzugeben. Da die Dominanzregeln aufgrund der zeitabhängigen Gewinne sehr schwach sind, werden Schranken der reduzierten Kosten benutzt, um den Suchraum des Pricing-Problems deutlich zu reduzieren. Zwei Schranken werden implementiert, und zur weiteren Beschleunigung des Algorithmus werden spezielle Verfahren eingesetzt. Die Methode verwendet ein Branching Scheme, das mit dem vorgeschlagenen Spaltenerzeugungsverfahren kompatibel ist. Für die Durchführung der Berechnungsexperimente werden die klassischen TOP-Instanzen aus der Fachliteratur verwendet, die je nach Problemart leicht modifiziert werden. Die Ergebnisse zeugen von der Wirksamkeit der Methode.