Back to Search
Start Over
Robust Team Orienteering Problem with Decreasing Profits.
- Source :
-
INFORMS Journal on Computing . Nov/Dec2022, Vol. 34 Issue 6, p3215-3233. 19p. - Publication Year :
- 2022
-
Abstract
- 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]
- Subjects :
- *ORIENTEERING
*ORIENTEERS
*DYNAMIC programming
*TIME perspective
*CONSUMERS
Subjects
Details
- Language :
- English
- ISSN :
- 10919856
- Volume :
- 34
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- INFORMS Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 160929566
- Full Text :
- https://doi.org/10.1287/ijoc.2022.1240