Branch-and-Price for the Team Orienteering Problem with Time Windows and Bivariate Time-Varying Profit

Motivated by multiple real-world applications, this study investigates the team orienteering problem with time windows and bivariate time-varying profit (TOPTW-BTP), where the profit collected at each node is modeled as a nonlinear function of both the arrival time and the service duration. We model the problem on a time-expanded network and introduce the concept of the bivariate-time (BT) arc, proving that dominated BT arcs can be systematically eliminated to reduce the solution space. To capture diverse real-world temporal profit patterns, we consider three types of arrival-time profit functions, monotonic (typically decreasing), concave, and others (e.g., bimodal), and discuss tailored modeling approaches for each case to avoid unnecessary arrival-time discretization. Especially for the concave case, we propose a novel route extension method that exploits the structural properties of concavity to mathematically formalize the extension as direct functional additions, thereby achieving a compact representation. This method is also applicable to related problems such as vehicle routing with time windows and convex node costs. A branch-and-price framework is developed to solve the TOPTW-BTP. Computational experiments show that the proposed algorithm efficiently solves instances with up to 100 nodes across all three types of arrival-time profit function, with the theoretical simplification in the concave case naturally leading to a more streamlined implementation than the state-of-the-art approach.

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 72371086, 72401081, and 72571079], the Zhejiang Provincial Philosophy and Social Science Planning Project [Grant 23SYS11ZD], and the Natural Science Foundation of Zhejiang Province [Grant LQN25G010003].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1516) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1516). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.