Robust Team Orienteering Problem with Decreasing Profits

Qinxiao Yu (), Chun Cheng () and Ning Zhu ()
Additional contact information
Qinxiao Yu: Economics and Management College, Civil Aviation University of China, 300300 Tianjin, China
Chun Cheng: Institute of Supply Chain Analytics, Dongbei University of Finance and Economics, 116025 Dalian, China
Ning Zhu: Institute of Systems Engineering, College of Management and Economics, Tianjin University, 300072 Tianjin, China

INFORMS Journal on Computing, 2022, vol. 34, issue 6, 3215-3233

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.

Keywords: team orienteering; uncertain service time; robust optimization; branch-and-price; tabu search (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1240 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:6:p:3215-3233

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().