Search

This paper studies a robust variant of the team orienteering problem with decreasing profits, 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 routes for the vehicles 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 two-index robust formulation for the problem, which is defined using constraints based on dynamic programming recursive equations and can be directly solved by a general-purpose optimization solver. We also present a route-based formulation for the problem, which is solved by a tailored branch-and-price (B&P) algorithm. To tackle large-size instances efficiently, we further implement a tabu search (TS) algorithm. Numerical tests show that our B&P algorithm can solve most instances with 100 customers to optimality within 30 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 with the solutions generated by the deterministic model. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72201267, 72101049, 72122015, 71971154] and the Fundamental Research Funds for the Central Universities, Civil Aviation University of China [Grant 3122022093]. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.1240. [ABSTRACT FROM AUTHOR]

This paper studies the team orienteering problem, where the arrival time and service time affect the collection of profits. Such interactions result in a nonconcave profit function. This problem integrates the aspect of time scheduling into the routing decision, which can be applied in humanitarian search and rescue operations where the survival rate declines rapidly. Rescue teams are needed to help trapped people in multiple affected sites, whereas the number of people who could be saved depends as well on how long a rescue team spends at each site. Efficient allocation and scheduling of rescue teams is critical to ensure a high survival rate. To solve the problem, we formulate a mixed-integer nonconcave programming model and propose a Benders branch-and-cut algorithm, along with valid inequalities for tightening the upper bound. To solve it more effectively, we introduce a hybrid heuristic that integrates a modified coordinate search (MCS) into an iterated local search. Computational results show that valid inequalities significantly reduce the optimality gap, and the proposed exact method is capable of solving instances where the mixed-integer nonlinear programming solver SCIP fails in finding an optimal solution. In addition, the proposed MCS algorithm is highly efficient compared with other benchmark approaches, whereas the hybrid heuristic is proven to be effective in finding high-quality solutions within short computing times. We also demonstrate the performance of the heuristic with the MCS using instances with up to 100 customers. Summary of Contribution: Motivated by search and rescue (SAR) operations, we consider a generalization of the well-known team orienteering problem (TOP) to incorporate a nonlinear time-varying profit function in conjunction with routing and scheduling decisions. This paper expands the envelope of operations research and computing in several ways. To address the scalability issue of this highly complex combinatorial problem in an exact manner, we propose a Benders branch-and-cut (BBC) algorithm, which allows us to efficiently deal with the nonconcave component. This BBC algorithm is computationally enhanced through valid inequalities used to strengthen the bounds of the BBC. In addition, we propose a highly efficient hybrid heuristic that integrates a modified coordinate search into an iterated local search. It can quickly produce high-quality solutions to this complex problem. The performance of our solution algorithms is demonstrated through a series of computational experiments. [ABSTRACT FROM AUTHOR]