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.The Team Orienteering Problem with Time-Dependent Rewards (TOPwTDR) is an extension of the classical Team Orienteering Problem, where the profit associated with each customer is a function of time, e.g. linear decreasing, exponentially increasing, etc. The objective of the TOPwTDR is to maximise the total collected profit by finding vehicle routes, which visit each customer at most once within a prescribed time limit. The TOPwTDR has been considered previously in the literature under the assumption of decreasing profits. The Dantzig-Wolfe decomposition is applied and the TOPwTDR is solved exactly with a Branch-and-Price algorithm. For tackling the Pricing problem a modified labelling algorithm is proposed, which on the first stage uses heuristics to find columns to enter the reduced master problem. As the dominance rules are very weak due to time-dependency of the profits, reduced costs bounding is used to reduce significantly the search space of the Pricing problem. Two of such bounds are implemented, and for further speeding up the algorithm a set of accelerating techniques are employed. The methodology is completed with a branching scheme compatible with the proposed Column Generation procedure. Computational experiments are conducted on the classical TOP instances found in the literature, slightly modified according to the nature of the problem. The results demonstrate the effectiveness of the method