Team Orienteering with Time-Varying Profit

Qinxiao Yu (), Yossiri Adulyasak (), Louis-Martin Rousseau (), Ning Zhu () and Shoufeng Ma ()
Additional contact information
Qinxiao Yu: College of Management and Economics, Tianjin University, Tianjin 300072, China; Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, QC H3C 3A7, Canada; Interuniversity Research Center on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal, QC H3C 3A7, Canada
Yossiri Adulyasak: HEC Montréal and GERAD, Montréal, QC H3T 2A7, Canada
Louis-Martin Rousseau: Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, QC H3C 3A7, Canada; Interuniversity Research Center on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal, QC H3C 3A7, Canada
Ning Zhu: College of Management and Economics, Tianjin University, Tianjin 300072, China
Shoufeng Ma: College of Management and Economics, Tianjin University, Tianjin 300072, China

INFORMS Journal on Computing, 2022, vol. 34, issue 1, 262-280

Abstract: 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.

Keywords: team orienteering; routing and scheduling; mixed integer nonconvex programming; Benders branch-and-cut; hybrid heuristic (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1026 (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:1:p:262-280

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 ().