Robust Team Orienteering Problem with Decreasing Profits

This paper studies a robust variant of the team orienteering problem with decreasing profits (TOP-DP), where a fleet of vehicles are dispatched to serve customers with decreasing profits in a limited time horizon. The service times at customers are assumed to be uncertain, which are characterized by a budgeted uncertainty set. Our goal is to determine the set of customers to be served and the vehicle routes such that the collected profit is maximized; meanwhile, all the planned routes remain feasible for any realization of service times within the uncertainty set. We propose a tractable robust formulation for the problem, which utilizes dynamic programming recursive equations to calculate the worst-case arrival times at customers along a given route. To solve the robust model, we develop a branch-and-price (B&P) algorithm for exact solutions and a tabu search (TS) algorithm for approximation solutions. Numerical tests show that our B&P algorithm can solve most instances with 100 customers to optimality within 25 minutes and that the TS algorithm can find high-quality solutions within a few seconds. Moreover, we find that in most cases the robust solutions can significantly reduce the probability of deadline violations in simulation tests with only a slight compromise of profit, compared to the solutions generated by the deterministic model.

Article

Download

View Robust Team Orienteering Problem with Decreasing Profits