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.

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 .

To mitigate traffic oscillations that usually sustainably propagate upstream, this paper proposes a jam-absorption driving (JAD) strategy in the framework of Newell's car-following theory. The basic idea of the JAD strategy is to guide a vehicle to move slowly before being captured by an oscillation and terminate the slow movement when the vehicle would start to leave the jam if no such slow movement was implemented. To practically implement the idea, a two-step method is proposed to estimate the time-space ending point of the strategy, and a proper vehicle is selected to implement the JAD strategy based on a given expected absorbing speed and current traffic conditions. To test the JAD strategy, two simulated traffic scenarios are constructed based on a realistic data-driven car-following model. The first scenario, which only reproduces one oscillation, directly shows the effectiveness of the JAD idea in preventing wave propagation and capacity drop. The second scenario, which contains a series of traffic oscillations induced by the rubbernecking behavior, validates the proposed JAD strategy in more complicated and realistic conditions. It is indicated that the JAD strategy is able to absorb traffic oscillations; thus, the side effects incurred by the oscillations could be subsequently mitigated. The significance of this paper is to provide us a new idea to mitigate traffic oscillations, i.e., the JAD strategy.

In transportation networks, traditional fixed sensors are used to monitor the operation of transportation systems. However, fixed sensors cannot move once they are installed. In this paper, the motion ability of traffic sensors is introduced to improve the performance of transportation network surveillance. A mobile traffic sensor routing problem is proposed, modeled as a novel vehicle routing problem. A measure of traffic information acquisition benefits is developed and used to gauge the surveillance performance. To solve this mobile-sensor routing problem, a hybrid two-stage heuristic algorithm is designed, which is based on particle swarm optimization and ant colony optimization. Numerical experiments are conducted. The results show that the mobile traffic sensor has a better network surveillance performance than the fixed sensor in most experimental cases.