朱婷婷,单小红

(桂林电子科技大学　商学院,广西　桂林　541004)

车辆调度问题的全局
—局部最优信息比粒子群算法研究

朱婷婷,单小红

(桂林电子科技大学商学院,广西桂林541004)

[摘要]文章提出了一种新的改进标准粒子群算法即全局—局部最优信息比粒子群算法。该算法与标准粒子群算法和全局—局部最优最小值粒子群优化算法作了比较,仿真实验结果表明,该算法在收敛速度、解的质量和鲁棒性上都表现出了较优的性能,是求解车辆调度问题的一种较好方法。

[关键词]车辆调度问题；粒子群算法；全局—局部最优信息比；数学模型

[DOI]10.13939/j.cnki.zgsc.2016.10.145

1引言

近年来,研究者们先后将一般启发式算法和智能化启发式算法用于车辆调度问题,取得了一些较好的效果。[1]粒子群算法(ParticleSwarmOptimization,PSO)是一种模拟鸟群飞行的仿生算法,有着个体数目少、计算简单、鲁棒性好等优点。[2]

2车辆调度问题(VRP)的描述及数学模型

VRP描述为：有一个配送中心0,配送车辆K辆和货运点个N,每辆车的载重量为qi,各个送货点的需求量为gi,且maxqi≤maxgi,把货物配送到N个送货点,使车辆调度问题的目标函数达到最小。

定义变量如下：

(1)

(2)

cij是配送点之间的距离,则VRP的数学模型表示为：

(3)

(4)

(5)

(6)

(7)

xijk=0或1， i, j=1, 2, …, N; k=1, 2, …, K

(8)

yik=0或1， i, j=1, 2, …, N; k=1, 2, …, K

(9)

X=(xijk)∈S

(10)

式(3)为目标函数：车辆行驶的总路径最小；式(4)：每条线路上配送点需求量之和不超过最大载重量；式(5)：每个配送点仅被访问一次；式(6)(7)：每个送货点的需求量只能由一辆车完成；式(8)(9)：变量取值范围；式(10)：支路消去约束。该问题在约束条件下,使所有车辆的总路径最小。……