五種不同粒子群最佳化算法求解車輛途程問題之比較研究

A Comparative Study of Five Different Particle Swarm optimization Algorithms in Solving Vehicle Routing Problems

李政鋼、黃柏維、陳彥亦
C. K. Lee, B. W. Huang and Y. Y. Chen

正修科技大學 工業工程與管理系


摘要

本研究旨在比較五種不同的粒子群最佳化算法,包括: 基本粒子群算法(PSO)、帶壓縮因子的粒子群算法(YSPSO)、線性遞減權重粒子群算法(LinWPSO)、自適應權重粒子群算法(SAPSO)與隨機權重粒子群算法(RandWPSO),在求解車輛途程問題(Vehicle Routing Problem, VRP)上是否有優劣之分。粒子群最佳化算法所解的VRP問題是引用自NEO網站上的15題測試問題。算法的求解能力定義為算法能求到的最短距離與真正的最短距離之平均誤差百分比。研究結果顯示帶壓縮因子的粒子群算法(YSPSO)在求解車輛途程問題上具有最好的表現,基本粒子群算法(PSO)、線性遞減權重粒子群算法(LinWPSO)與自適應權重粒子群算法(SAPSO)的表現中等且相近,而隨機權重粒子群算法(RandWPSO)則表現最差。

關鍵字:車輛途程問題、粒子群最佳化算法。

ABSTRACT

The purpose of this study is to compare five different Particle Swarm Optimization (PSO) algorithms that are used to solve Vehicle Routing Problems (VRP). The problems solved by the algorithms are the 15 VRP test problems downloaded from NEO website. The algorithm's ability is defined as the average difference between the shortest distance solved by the algorithm and the true shortest distance of the problem. The performance of YSPSO is the best. The performances of PSO, LinWPSO, and SAPSO are moderate and alike. The performance of RandWPSO is the worst.

Keywords: Vehicle Routing Problem; Particle Swarm Optimization Algorithm