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.
We apply Dantzig-Wolfe decomposition and solve exactly the TOPwTDR with a Branch-and-Price algorithm. For solving the pricing problem we propose a modified labelling algorithm, which on the first stage uses heuristics to find columns to enter the reduced master problem. As dominance rules are very weak due to time-dependency of the profits, we employ reduced costs bounding to reduce significantly the search space of the pricing problem. Two of such bounds are implemented, and we further speed up the algorithm by using a set of accelerating techniques. We complete the methodology 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 effectiveness of the method and show a positive impact of the proposed accelerating techniques.
| Subject : | : | Abstracts |
| Topics | : | Column Generation |
| Topics | : | Exact Methods |
| PDF version | : |  PDF version |
