A selective-discrete particle swarm optimization algorithm for solving a class of orienteering problems

• Main Authors: GUNAWAN, Aldy, YU, Vincent F., REDI, Perwira, JEWPANYA, Parida, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2017
• Subjects: Orienteering Problem; Optimization; algorithms; Artificial Intelligence and Robotics; Computer Sciences; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/3892; https://ink.library.smu.edu.sg/context/sis_research/article/4894/viewcontent/MISTA_2017_paper_51.pdf
• Institution: Singapore Management University

This study addresses a class of NP-hard problem called the Orienteering Problem (OP), which belongs to a well-known class of vehicle routing problems. In the OP, a set of nodes that associated with a location and a score is given. The time required to travel between each pair of nodes is known in advance. The total travel time is limited by a predetermined time budget. The objective is to select a subset of nodes to be visited that maximizes the total collected score within a path. The Team OP (TOP) is an extension of OP that incorporates multiple paths. Another widely studied OP extension is the Team OP with Time Windows (TOPTW) that adds the time windows constraint. We introduce a discrete version of Particle Swarm Optimization (PSO), namely Selective-Discrete PSO (S-DPSO) to solve TOP and TOPTW. S-DPSO has a different movement compared with other DPSO algorithms reported in the literature. S-DPSO considers four different movement schemes: (a) following its own position, (b) moving towards its personal best position, (c) moving towards the global best position, and (d) moving towards the combination of three above-mentioned schemes. The best movement scheme is selected in order to determine the next position of the particle. The S-DPSO algorithm is tested on the benchmark instances. The experiment results show that S-DPSO performs well in solving benchmark instances. S-DPSO is promising and comparable to the state-of-the-art algorithms.