Title: Solving the team orienteering problem with time windows and mandatory visits using a constraint programming approach

Authors: Emre Kirac; Ridvan Gedik; Furkan Oztanriseven

Addresses: Luter School of Business, Christopher Newport University, One Avenue of the Arts, Newport News, VA 23606, USA ' Amazon.Com, Inc., 410 Terry Ave N, Seattle 98109, WA, USA ' Le Moyne College, 1419 Salt Springs Road, Syracuse, NY 13214, USA

Abstract: This paper presents a constraint programming (CP) approach for solving the team orienteering problem with time windows and mandatory visits (TOPTW-MV), which has many real-world implementations, such as tourist tour planning, routing technicians, and disaster relief routing. In the TOPTW-MV, a set of locations is given; some locations must be visited, while others are optional. For each location, the profit, service time, and service time window information are known. A fleet of homogeneous vehicles is available for visiting locations and collecting the profits. The objective in solving this problem is to create a set of vehicle routes that begin and end at a depot, visit mandatory locations exactly once and optional locations at most once, while observing other restrictions such as time windows and sequence-based travel times. The CP-based approach finds 99 of the best-known solutions and explores 64 new best-known solutions for the benchmark instances.

Keywords: team orienteering problem; TOP; time windows; mandatory visits; vehicle routing; constraint programming.

DOI: 10.1504/IJOR.2023.128542

International Journal of Operational Research, 2023 Vol.46 No.1, pp.20 - 42

Received: 31 Dec 2019
Accepted: 20 Feb 2020
Published online: 26 Jan 2023 *