A Novel Particle Swarm Optimization for Multi-Objective Vehicle Routing Problem

doi:10.7652/xjtuxb201609016

您当前的位置：

首页 >

文章列表页 >

A Novel Particle Swarm Optimization for Multi-Objective Vehicle Routing Problem

更新时间：2025-07-09

- A Novel Particle Swarm Optimization for Multi-Objective Vehicle Routing Problem
- Vol. 50, Issue 9, Pages: 97-104(2016)
- 作者机构：
  
  吉林大学计算机科学与技术学院,长春,130012
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201609016
  CLC： TP273
- Online First：10 September 2016，
  
  Published：2016
- 稿件说明：
移动端阅览
A Novel Particle Swarm Optimization for Multi-Objective Vehicle Routing Problem[J]. 2016, 50(9): 97-104.
DOI：

A Novel Particle Swarm Optimization for Multi-Objective Vehicle Routing Problem[J]. 2016, 50(9): 97-104. DOI： 10.7652/xjtuxb201609016.

摘要

针对粒子群算法(PSO)及其变种在约束多目标等复杂问题优化过程中所遇到的易陷入局部最优和收敛性问题

提出了一种基于动态学习和突变因子的粒子群算法(DSPSO)。首先

通过分析粒子群群体的学习机制

采用动态的学习策略

使粒子自适应动态调整认知成分和社会成分在迭代更新中的权重

以引导自身向最优解的方向探索

有效改善了群体的收敛速度; 其次

通过引入阶梯突变因子的概念

使粒子在陷入局部最优时进行试探跳跃

阶梯突变赋予粒子突破更新步长限制的能力

使粒子在当前位置速度矢量方向上的二维空间邻域内进行试探寻优

当发现更优解时则跳出当前局部最优; 最后

通过在BenchMark基准函数测试集中典型函数上的实验

证明了DSPSO的求解精度和收敛速度均优于对比算法。在多目标车辆路径问题实例优化中

解的可接受率和成功率分别为0.91和0.66

远优于对比算法中最优解的0.16和0.11

体现了所提改进算法在车辆路径问题中的优越性。

Abstract

Considering the problems that particle swarm optimization(PSO)algorithm and its variants are easily to fall into local optimal solutions and convergence in the optimization process of complex constrained multi-objective problem

a novel PSO based on dynamic learning strategy and mutation factor(DSPSO)is proposed. First

through analyzing the learning mechanism of particle swarm

DSPSO introduces the dynamic learning strategy

enabling particles to adaptively adjust the weights of cognitive component and social component in the iteration renewal process and guide themselves to explore in the optimal direction

hence effectively accelerating the convergence rate. Second

by introducing the ladder mutation factor

when the particles are trapped in a local optimum

they are enabled to break the limit of update-step size to make tentative jumps in the two-dimensional spatial neighborhood of the velocity vector direction. When a better solution is found

the optimal solution would be updated. Finally

experiments are conducted on the typical functions of BenchMark

and the results show that the accuracy and convergence rate of DSPSO are better than the contrast algorithms. In the multi-objective vehicle routing problem optimization

the acceptable and success rates of the DSPSO solutions are 0.91 and 0.66

respectively

far outperform the results of 0.16 and 0.11 by comparison algorithm

reflecting the superiority of DSPSO in the multi-objective vehicle routing problem.

关键词

Keywords

references

YUSUF I, BABA M S, IKSAN N. Applied genetic algorithm for solving rich VRP [J]. Applied Artificial Intelligence, 2014, 28(10): 957-991.

ZHANG Changsheng, YIN Hao, ZHANG Bin. A novel ant colony optimization algorithm for large scale QoS-based service selection problem [J]. Discrete Dynamics in Nature and Society, 2013(6): 1104-1116.

KENNEDY J, EBERHART R C. Particle swarm optimization [M]. Berlin, Germany: Springer, 2010: 760-766.

CHATTERJEE S, SARKAR S, HORE S, et al. Particle swarm optimization trained neural network for structural failure prediction of multistoried RC buildings[M/OL]∥Neural Computing Applications. [2015-12-12]. http: ∥link. springer. com/article/10.1007/s00521-016-2190-2.

许榕, 周东, 蒋士正, 等. 自适应粒子群神经网络交通流预测模型 [J]. 西安交通大学学报, 2015, 49(10): 103-108.

XU Rong, ZHOU Dong, JIANG Shizheng, et al. A traffic forecasting model using adaptive particle swarm optimization trained neural network [J]. Journal of Xi'an Jiaotong University, 2015, 49(10): 103-108.

KENNEDY J, EBERHART R C. A discrete binary version of the particle swarm algorithm [C]∥IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ, USA: IEEE, 1997: 4104-4108.

PARSOPOULOS K E, VRAHATIS M N. Recent approaches to global optimization problems through particle swarm optimization [J]. Natural Computing, 2002, 1(2): 235-306.

WANG Zutong, GUO Jiansheng, ZHENG Mingfa, et al. Uncertain multiobjective traveling salesman problem [J]. European Journal of Operational Research, 2015, 241(2): 478-489.

LI Ning, ZOU Tong, SUN Debao. Particle swarm optimization for vehicle routing problem [J]. Journal of Systems Engineering, 2005, 19(6): 596-600.

DUAN Peibo, ZHANG Changsheng, ZHANG Bin. A local stability supported parallel distributed constraint optimization algorithm[J/OL]. The Scientific World Journal. [2015-12-10]. http: ∥www. hindawi. com/journals/tswj/2014/734975/abs/.

YIN Hao, ZHANG Changsheng, ZHANG Bin, et al. A hybrid multi-objective discrete particle swarm optimization algorithm for a SLA-aware service composition problem [J]. Mathematical Problems in Engineering, 2014, 89(1): 112-121.

SHI Yuhui, EBERHART R C. Empirical study of particle swarm optimization [C]∥Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 1999: 1945-1950

TAN Guanzheng, BAO Kun, RIMIRU R. A composite particle swarm algorithm for global optimization of multimodal functions [J]. Journal of Central South University, 2014, 21(5): 1871-1880.

LI Jun, SUN Qirui, ZHOU Mengchu, et al. A new multiple traveling salesman problem and its genetic algorithm-based solution [C]∥The 2013 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ, USA: IEEE, 2013: 627-632.

TANG Yaoping, YU Hong, WANG Wenmu, et al. Application of TSP model based multi-objective in Yongzhou city's tourist routes [J]. Journal of Central South University of Forestry Technology, 2011(10): 154-157.

SHI Yuhui, EBERHART R C. A modified particle swarm optimizer [C]∥The IEEE International Conference on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 1998: 69-73.

CLERC M. The swarm and the queen: towards a deterministic and adaptive particle swarm optimization [C]∥Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 1999: 1951-1957.

LI Zhuangkuo, MA Yannan, LIU Liang. Particle swarm optimization based on the average optimal information for vehicle routing problem [C]∥The 6th International Symposium on Computational Intelligence and Design. Piscataway, NJ, USA: IEEE, 2013: 51-54.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Optimal Scheduling of Island Integrated Energy System Using Improved Multi-Objective Particle Swarm Optimization Algorithm

Multi-Objective White Shark Optimizer for Edge-Side Industrial Microservice Deployment

Multi-Objective Optimization of Flow and Heat Transfer in Matrix Cooling Channels with Tapered Holes

Multi-Objective Assembly Performance Oriented Optimization of Vertical Cable Pretension in Large Deployable Mesh Antenna

Research on Optimal Scheduling of Island Integrated Energy System Using Improved Multi-Objective Particle Swarm Optimization Algorithm

Related Author

DAI Hongwei

HU Qingyi

SUN Jing

WANG Jinlong

YANG Yu

LI Xiaobin

GOU Kunyao

YIN Chao

Related Institution

School of Data Science，Qingdao University of Science and Technology

School of Computer Engineering，Jiangsu Ocean University

Green Intelligent Manufacturing Research Institute, Chongqing University

School of Mechanical Engineering, Xi'an Jiaotong University

Key Laboratory of Modern Design and Rotor-Bearing System (Ministry of Education),School of Mechanical Engineering ,Xi’an Jiaotong University

⁰