Publication Type

Journal Article

Version

submittedVersion

Publication Date

12-2019

Abstract

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.

Keywords

Team orienteering problem, Time window, Partial score, Discrete particle swarm optimization

Discipline

Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

Computers and Industrial Engineering

Volume

138

First Page

1

Last Page

13

ISSN

0360-8352

Identifier

10.1016/j.cie.2019.106084

Publisher

Elsevier

Additional URL

https://doi-org/10.1016/j.cie.2019.106084

Download

Share

COinS