| Abstract
|
:
|
Particle swarm optimization (PSO), an evolutionary algorithm, is known for its simplicity in coding, consistency in performance, and its local and global exploration capabilities. Discrete particle swarm optimization (DPSO), a modified version of PSO, can be used for solving decision problems with discrete solution space and has been applied for various combinatorial problems including the traveling salesman problem, vehicle routing, and scheduling. The orienteering problem (OP), a NP-hard problem, has several control points or nodes to be visited and each node has a score (or reward) tied to it. The starting and the ending nodes of the tour are distinct and are specified. The objective is to maximize the reward collected by visiting as many nodes as possible within the given time (or distance) constraint. The team orienteering problem (TOP), an extended version of the OP, allows for a team approach for maximizing the total team score. Each member of the team tries to visit as many nodes as possible such that the time (or distance) constraint is not violated. All members start and end at distinct and specified nodes. Once a node has been visited by a team member and awarded with a score, other team members visiting the same node will not earn any reward. Literature reveals several applications for the OP and the TOP such as vehicle routing, inventory routing and production scheduling applications. This research designs DPSO algorithms for the OP and the TOP. A novel constructive heuristic for the initial population using score/distance ( s/d ) ratio and cumulative density function ( s/d with CDF) has been applied in the DPSO algorithm for TOP. The algorithm designed for TOP is the first known DPSO algorithm implemented for the TOP. The two, three, and four team member scenarios have been studied for the TOP. Reduced variable neighborhood search (RVNS) and 2-opt are the local search tools used in the DPSO algorithms. RVNS employs insert and exchange neighborhoods in its search for a better solution. A creative swapping procedure is applied to switch between random method and center of gravity method in the RVNS local search heuristic. Furthermore, a new and effective particle update procedure has been designed and implemented to find the new position of the DPSO particles in each generation. Several design of experiments (DOE) and analysis of variance were used to fine-tune the DPSO parameters. The relative percentage error (RPE) and the average relative percentage error (ARPE) are the metrics used to measure the performance and robustness of the algorithms. RPE is the error between the best known solution and the best solution of all replications. ARPE is the average error of all replications. Four benchmark problem sets of size 21 to 33 nodes were used to evaluate the DPSO-OP algorithm. Seven benchmark problem sets of size ranging from 21 to 102 nodes were used to test the DPSO-TOP algorithm. The DPSO algorithms designed were compared with several metaheuristics including the TS, ant colony optimization and genetic algorithm. The overall average RPE of the designed DPSO-OP algorithm was zero which demonstrates that the DPSO algorithm found the best known solution for all the 67 benchmark problems for the OP. The grand ARPE of the DPSO-OP algorithm was 0.21%. For the TOP, the DPSO-TOP algorithm found the best known solution for 213 out of 353 benchmark problems. The overall average RPE was only 0.75% and the grand ARPE was 2.59 % for DPSO-TOP algorithm. It is evident that the DPSO algorithms developed for the OP and the TOP are competitive.
|