Selective discrete particle swarm optimization for the team orienteering problem with time windows and partial scores

• Main Authors: YU, Vincent F., REDI, Perwira A. A. N., JEWPANYA, Parida, GUNAWAN, Aldy
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Team orienteering problem; Time window; Partial score; Discrete particle swarm optimization; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/4469; https://ink.library.smu.edu.sg/context/sis_research/article/5472/viewcontent/Selective_discrete_particle_swarm_optimization_for_the_team_orienteering_problem_with_time_windows_and_partial_scores.pdf
• Institution: Singapore Management University

This paper introduces the Team Orienteering Problem with Time Windows and Partial Scores (TOPTW-PS),which is an extension of the Team Orienteering Problem with Time Windows (TOPTW). In the context of theTOPTW-PS, each node is associated with a set of scores with respect to a set of attributes. The objective ofTOPTW-PS is to find a set of routes that maximizes the total score collected from a subset of attributes whenvisiting the nodes subject to the time budget and the time window at each visited node. We develop a mathematical model and propose a discrete version of the Particle Swarm Optimization (PSO), namely, the SelectiveDiscrete PSO (S-DPSO), to solve TOPTW-PS. The proposed S-DPSO uses four different movement schemes tomove a particle from its current position. The best movement scheme is selected to determine the next position ofthe particle. To evaluate the performance of the proposed S-DPSO algorithm, we first test S-DPSO on two variants of Orienteering Problem, namely, Team Orienteering Problem (TOP) and TOPTW. Experimental resultsshow that S-DPSO performs well in solving benchmark instances of TOP and TOPTW. In general, S-DPSO iscomparable to the state-of-the-art algorithms for these problems. We also apply the S-DPSO to solve 168 newlygenerated TOPTW-PS instances and conclude that the proposed S-DPSO can produce high-quality TOPTW-PSsolutions.