Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
12-2017
Abstract
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.
Keywords
Orienteering Problem, Optimization, algorithms
Discipline
Artificial Intelligence and Robotics | Computer Sciences | Operations Research, Systems Engineering and Industrial Engineering
Research Areas
Intelligent Systems and Optimization
Publication
MISTA 2017: Proceedings of the 8th Multidisciplinary International Conference on Scheduling: Theory and Applications: Kuala Lumpur, December 5-8
First Page
229
Last Page
243
Publisher
MISTA
City or Country
Kuala Lumpur
Citation
GUNAWAN, Aldy; YU, Vincent F.; REDI, Perwira; JEWPANYA, Parida; and LAU, Hoong Chuin.
A selective-discrete particle swarm optimization algorithm for solving a class of orienteering problems. (2017). MISTA 2017: Proceedings of the 8th Multidisciplinary International Conference on Scheduling: Theory and Applications: Kuala Lumpur, December 5-8. 229-243.
Available at: https://ink.library.smu.edu.sg/sis_research/3892
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Included in
Artificial Intelligence and Robotics Commons, Operations Research, Systems Engineering and Industrial Engineering Commons