带时间窗车辆路径问题的粒子群算法

文章编

F D =>C >E ;=>F G

收稿日期$!"",&"#&,"

资助项目$航天技术创新基金项目.

作者简介$李宁*%m (!n+-男*汉+-湖北京山人-博士研究生-主要研究方向$系统工程8人工智能8演化计算8人工生命/孙德宝*%m #%n+-男*汉+-

湖北云梦人-教授-博士生导师-研究方向$人工智能8信号处理等o 引言

车辆路径问题*3A I >?@A 4F J =>G K0K 和4;C N A <于%m p m 年首次提出的-它是指对一系列发货点*或收货点+-组成适当的行车路径-使车辆有序地通过它们-在满足一定约束条件的情况下-达到一定的目标*诸如路程最短8费用最小-耗费时间尽量少等+q %r

-属于完全Q 0问题-在运筹8计算机8物流8管理等学科均有重要意义7

带时间窗的车辆路径问题*3A I >?@A 4F J =>G K0=I5>C A 6>G M F B N -34056+是在340问题上加了客户要求访问的时间窗口7由于在现实生活中许多问题都可以归结为34056问题来处理*如邮政投递8火车及公共汽车的调度等+-其处理的好坏将直接影响到企业的服务质量-所以对它的研究越来越受到人们的重视7先后出现了一般启发式算法和神经网络8遗传算法8禁忌搜索和模拟退火等智能化启

发式算法-也取得了一些较好的效果q %r 7

粒子群算法*012-0;<=>?@A 1B ;C >E ;=>F G +q !r

是最近出现的一种模拟鸟群飞行的仿生算法-有着个体数目少8计算简单8鲁棒性好等优点-在各类多维连续空间优化问题上均取得非常好的效果q ,r

7

本文将012应用于车辆路径问题求解中-

取得了很好的效果s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s 7

!有时间窗车辆路径问题的描述及数学模型

有时间窗车辆路径问题一般描述为"有一个中心仓库#拥有车$辆#容量分别为%&

’&()#*#+#$,-现有.个发货点运输任务需要完成#以)#*#+#.表示/第0个发货点的货运量为10’0()#*#+#.,#’234’1,05234’%0,,#完成发货点0任务需要的时间’装贷或卸货,表示为60

#且任务0且必须在时间窗口7860#.609完成#其中860为任务0的允许最早开始时间#.60为任务0的允许最迟开始时间/如果车辆到达发货点0的时间早于860#则车辆需在0处等待-如果车辆到达时间晚于.60

#任务0将被延迟进行/求满足货运要求的运行费用最少的车辆行驶线路/此问题称之为带时间窗的车辆优化调度问题/它又可分为两类"

),硬时间窗:;<硬时间窗:;<指每项任务必须在要求的时间范围内完成#出这个时间范围#则得到的解为不可行解=

*,软时间窗:;<软时间窗:;<指如果某项任务不能在要求的时间范围内完成#则给予一定的惩罚"若车辆在860之前到达点0#则车辆在此等待#增加了时间成本-若车辆在.60之后到达点0

#则服务被延迟#须支付一定的罚金成本/本文采用文献7)9提出的数学模型#将中心仓库编号为>#发货点编号为)#*#+#.#任务及中心仓库均以点0’0(>#)#+#.

,来表示/定义变量如下"?&0(

)发货点0

的任务由在&完成>@

否则

A 0B &(

)车&从点行驶到点B

>@

否则

C 0B 表示为从点0到B 的运输成本#它的含义可以是距离

D 费用D 时间等/

E 0

表示车辆到达任务点0的时间#F 8表示在860之前到达任务点0等待的单位时间成本#F .表示在.60之后到达任务点0的单位时间所得到的罚金成本-若车辆在860之前到达点0#则增加机会成本F 8G’E 0H 860,#若车辆在.60

之后到达点0#则增加罚金成本F .G’.60H E 0

,/则可得到车辆优化调度数学模型如下"

2I JK (

L 0

L B

L &

C 0B A

0B &

M F 8L N

0()

234’860H E 0#>,M F .L N

0()

234’E 0H .60

#>,’),O P Q P L 0

10?&05%&R&

’*,L &

?&0()

0()#*#+#.

’S ,L 0

A

0B &

(?&B B (>#)#+#.-R&’T ,L B

A

0B &

(?&00

(>#)#+#.-R&’U ,V (’A 0B &

,W X ’Y ,A 0B &(>

或)0#B (>#)#+#.-R&’Z ,

?&0(>

或[

\

])0(>#)#+#.-R&’^,当’),中F 8(F ._‘时#

以上模型为硬时间窗:;<问题/该模型要求每个发货点都得到车辆的配送服务#并限制每个发货点的需求仅能由某一车辆来完成-同时保证每条路径上的各发货点的总需求量不超过此条路径配送车的容量/优化问题也就是在满足以上约束条件下#使总成本a 最小/这个模型通用性很强#经过参数的不同设定#可以将其转换为其他组合优化问题的数学模型/若式’),中860(>#.60

_‘#则:;

)

S )第T 期

带时间窗车辆路径问题的粒子群算法

!粒子群算法"#$%&’()*+,$%-./&’-’0$&’12

3粒子群算法由4566578和9:5;<=;>在?@@A 年提出B 该算法模拟鸟集群飞行觅食的行为B 通过鸟之间的集体协作使群体达到最优目的C

在D E F 系统中B 每个备选解被称为一个G 粒子H "D =;>I J K 53B 多个粒子共存L 合作寻优"近似鸟群寻找食物3B 每个粒子根据它自身的G 经验H 和相邻粒子群的最佳G 经验H 在问题空间中向更好的位置G 飞行H B 搜索最优解C

D E F 算法数学表示如下"E

3M N O

P 设搜索空间为Q 维B 总粒子数为R S 第T 个粒子位置表示为向量U T V"W T ?B W T X BYB W T Q 3Z 第T 个粒子G 飞行H 历史中的过去最优位置"即该位置对应解最优3为[T V"\T ?B \T X BYB \T Q 3

B 其中第]个粒子的过去最优位置[]为所有[T "T V?BX B YB R 3中的最优Z 第T 个粒子的位置变化率"速度3为向量^T V "_T ?B _T X

B YB _T Q 3S 每个粒子的位置按如下公式进行变化"G 飞行H 3P _T ‘"a b ?3V c d _T ‘"a 3b e ?d ;=67"3d M \T ‘"a 3f W T ‘"a 3O b e X d ;=67"3d M \]‘"a 3f W T ‘"a 3O "@3W T ‘"a b ?3V W T ‘"a 3b _T ‘

"a b ?3?g T g R Z ?g ‘g Q "?h 3其中B e ?B e X 为正常数B 称为加速因子Z ;=67"3为M h B ?O 之间的随机数Z c 称惯性因子B c 较大适于对解空间进行大范围探查"5i j K k ;=>I k 63B c 较小适于进行小范围开挖"5i j K k I >=>I k 63S 第‘"?g ‘g Q 3维的位置变化范围为M f U lm U ‘BU lm U ‘O B 速度变化范围为M f ^lm U ‘B^lm U ‘O B

迭代中若位置和速度超过边界范围则取边界值S n=o ;I J 5p K 5;J 对上述参数进行了分析B 给出了D E F 算法收敛的参数条件M q O

S

粒子群初始位置和速度随机产生B 然后按公式"@3L "?h 3

进行迭代B 直至找到满意的解C 目前B 常用的粒子群算法将全体粒子群"r K k :=K 3分成若干个有部分粒子重叠的相邻子群B 每个粒子根据子群"s k J =K 3内历史最优[t 调整位置B 即公式"@3中[]‘换为[t ‘S D E F 算法可用伪代码表示如下P 随机初始化粒子群中的每个粒子"D =;>I J K 5

3Z u k

v k ;每个粒子"

5=J I J K 53按式"?3

计算适应度Z w x

粒子当前适应度优于该粒子历史最优适应度y <56记历史最优适应度值和位置"[T

3为该粒子当前适应度和位置"U T 3Z 967

选择当前粒子群"或相邻子群3中适应度最优的粒子Z

w x

当前粒子群"或相邻子群3中最优适应度优于群内历史最优适应度y <56记粒子群"或相邻子群3历史最优适应度和最优位置[]"k ;[t 3

为当前群内最优适应度和最优粒子的位置Z v k ;每个粒子

按式"@3计算粒子飞行速度^T Z 按式"?h 3

更新粒子位置U T Z 967

z

近几年的研究和实践表明B D E F 在多维空间多峰问题寻优L

动态目标寻优方面有着速度快L 解质量高L 鲁棒性好等优点M N O

C

{车辆路径问题的粒子群算法

{|}构造粒子表达方式

如何找到一个合适的表达方法B 使粒子与解对应B 是实现算法的关键问题之一S 借鉴文献M A O 的思路B 本文中构造一个X ~维的空间对应有~个发货点任务的!"D 问题B

每个发货点任务对应两维P 完成该任务车X

N ?系统工程理论与实践

X h h q 年q 月

辆的编号!"该任务在!车行驶路径中的次序#$为表达和计算方便"将每个粒子对应的%&维向量’分成两

个&维向量(’)*

表示各任务对应的车辆编号+和’#*表示各任务在对应的车辆路径中的执行次序+$例如"设,-.问题中发货点任务数为/

"车辆数为0"若某粒子的位置向量’为(发货点任务号(1%0234/

’)(1%%%%00

’#

(1201%%1则该粒子对应解路径为(

车1(56165车%(56263606%65车0(56/6465

粒子速度向量7与之对应表示为7)和7#

$该表示方法的最大优点是使每个发货点都得到车辆的配送服务"并限制每个发货点的需求仅能由某一车辆来完成"使解的可行化过程计算大大减少$虽然该表示方法的维数较高"但由于.89算法在多维寻

优问题有着非常好的特性:4;

"

维数的增加并未增加计算的复杂性"这一点在实验结果中可以看到$<=>算法实现过程

前面所述.89算法为连续空间算法"而,-.问题为整数规划问题"因此在算法实现过程中要作相应修改?具体实现步骤如下(

步骤@初始化粒子群?

A 粒子群划分成若干个两两相互重叠的相邻子群B

C 每个粒子位置向量’)的每一维随机取1

D

E *车辆数+之间的整数"’#的每一维随机取1

D &*

发货点任务数+之间的实数B F

每个速度向量7)的每一维随机取G*E G1+D*E G1+*车辆数+之间的整数"7#的每一维随机取G*&G1+D*&

G1+之间的实数B H 用评价函数I J K L

评价所有粒子B M 将初始评价值作为个体历史最优解N O "并寻找各子群内的最优解N P 和总群体内最优解N Q

$步骤>重复执行以下步骤"直到满足终止条件或达到最大迭代次数$

A 对每一个粒子"按式*R +计算7)S 7#

B 按照式*R +计算’)S ’#"其中’)向上取整B 当7S ’超过其范围时按边界取值$

C 用评价函数T )U P

评价所有粒子B F 若某个粒子的当前评价值优于其历史最优评价值"

则记当前评价值为该历史最优评价值"同时将当前位置向量记为该粒子历史最优位置N O

B H 寻找当前各相邻子群内最优和总群体内最优解"若优于历史最优解则更新N P S N Q

$对于子群内有多个体同为最优值的情况"则随机取其中一个为子群内当前最优解$其中"评价函数T V )U P

完成以下任务(1+根据公式*1+计算该粒子所代表路径方案的行驶成本W "

在计算中发货点任务的执行次序要根据对应’#值的大小顺序"由小到大执行$

%+将’#按执行顺序进行重新整数序规范$例如"

某粒子初始化和迭代一次后结果如下(’)(1

%

%

%

%

’#(30=%4=%1=%%=35=32=%

则评价后重新规范的’#是(1021%1%

X 实验结果及分析

为便于比较结果"用YK Z [K \4=1编写了,-.]^问题的粒子群算法和遗传算法*_‘+程序?并在同一.21=/_S %34Y -‘Y S ^a b %555操作系统的计算机上运行?其中"_‘采用了文:

1;中的染色体编码方式0

01第2期

带时间窗车辆路径问题的粒子群算法

和相关参数!"#$采用满足文献%

&’中约束条件的参数(实验)采用了文%*’中无时间窗+,"的例子-问题为一个有.个发货点任务的车辆路径问题-各任务点的坐标及货运量见表*(

表*各发货点坐标及货运量

序号/*01&23.坐标4*5-2&6

400-3/6425-3764.*-.*6451-&3647*-15640&-&064*5-&/6货运量489

6/:57

/:*&

/:05

/:11

/:0*

/:&*

/:2.

/表示中心仓库-设车辆容量皆为;<*:/-由1辆车完成所有任务=4最优路径距离为0*.:5*6

>?参数@群体规模A <&/!交叉概率B C

粒子数A <&/!分为0个子群-子群规模为00-子群间重叠的粒子数为0个4子群规模的*E */6!F

<*:&7&&2!最大代数0//=两种方法各运行2/次-结果如表0所示=表1则给出"#$每次达到最优路径的代数=

表0实验*>?G "#$方法结果对比

方法

达到最优路径次数

未达最优路径次数

达到最优路径平均代数达到最优路径的平均时间4H

6>?10*521:710:1"#$

2/

/

05:13

1:/&

表1实验*"#$方法达到最优路径的代数

.010*..*.*1.&**705**11*&0*01**.*500&*125130/*/15

23212

7

0*2.3023.1/22707

0*3157&1*&5*071.7

实验结果表明-"#$方法对该问题的搜索成功率为*//I-远远高于>?方法的3&I-而且达到最优路径的速度比>?方法提高近*/倍左右(说明在该问题上使用"#$方法的效果远远优于>?方法(这一结果与文献%2’中>?和"#$在并行处理器任务调度分配问题中的比较结果非常近似(

实验J 采用文%*’中+,"K L 的例子-该问题有5项货物运输任务4编号为*-0-M-56-各任务货运量89G 卸货时间工及每项任务时间窗%N O 9-P O 9

’由表&给出=这些任务由中心仓库/发出的1辆容量为5吨的车辆完成-中心仓库与各任务点间及各任务点之间的距离由表2给出-车速2/-单位运输成本为*-超出时间窗的单位惩罚为@Q N <2/-Q P <2

/=表&各发货点坐标及货运量

任务序号*01&23.5货运量4896

0*:2&:21*:2&0:21O 9

*0*100:21/:5%N O 9-P O 9

’%*-&’

%&-3’

%*-0’

%&-.’

%1-2:2’

%0-2’

%2-5’

%*:2-&’

已知最少行驶成本路径为@车*@/R3R&R/

车0@/R1R*R0R /车1@/R5R 2R.R/

总行驶成本S <7*/=对>?和"#$各运行2/次-两种算法参数与例*相同-结果对比如表3所示(实验结果表明-"#$对该问题的搜索成功率为&3I-远高于>?的0&I(同时-在平均行驶成本和平均搜索成功时间方面-"#$也明显优于>?(说明在该问题上"#$方法也优于>?方法(

为验证实验结果是否具备一般性-随机产生多个+,"K L 问题-使用不同群体数和不同参数的>?

&

1*系统工程理论与实践

0//&年&月

和!"#算法进行实验$

所取得结果近似%根据多次试验得到以下经验规律&’(当发货点任务数的增加$必须适当增加粒子数来避免收敛于局部最优%对于发货点任务数的相同的不同)*!+,问题$

使之达到较高搜索成功率-搜索到最优路径的几率(的最少粒子数也有所不同%一般而言$对无时间窗)*!$当粒子数为任务数的./0倍左右时$搜索成功率一般能达到123以上4而对有时间窗)*!

$粒子数则要为粒子数的’2倍左右4表5任务点与中心仓库及各任务点间距离

距离2

’

6

7

8

5

.

9

2282.29512622’22’.202’822.582’225295’’2’226.2.5295’22’2295959579582952’22521212’52812’22’22’222’229595’22562252’2252’222921295.’229595129592292’229’.2’’295129512922’220

02’2295’52’2295’22’222

表.实验6:;

搜索成功率

平均行驶成本

平均成功搜索时间

:;683117&.’0&8’=!"#

8.3

182&5

0&57

6(使用不同的相邻子群数对搜索成功率和达到最优行驶成本路径的平均代数有影响$采用6/8个子群数的效果最佳4

7(子群之间重叠粒子个数对搜索成功率和达到最小行驶成本路径的平均代数也有一定影响$采用子群规模的’>’2/’>62左右效果最好4

8(当粒子数大于任务数的5/.倍之后$

粒子数的增加对于达到最优解的搜索时间<52次试验结果平均行驶成本并无很大影响$即此时粒子数与寻优结果的相关性不大%

文献?.@在对典型连续非线性多维函数使用!"#方法寻优的经验研究中$发现粒子数与寻优结果的相关性并不大4通过自适应修改惯量A 的方法$可以克服在非常复杂空间寻优时收敛于局部最优解的问题%但

)*!+,属于整数规划问题$

实验中采用自适应修改惯量A 的方法$并未能解决收敛于局部最优解的问题%B 结论

分析!"#方法$可以看出它与:;等其他演化算法的最大不同在于%

’(迭代运算中只涉及到初等运算$

且运算量非常少46(每个粒子能直接获取群体历史经验和个体历史经验$比在其他方法中使用精英集-C D E F E =G (

的方法更有效4

7(整个粒子群被划分为几个的子群$

且子群之间有一定重叠$从而使收敛于局部最优解的几率大大减少%正因为如此$本文将!"#应用于带时间窗车辆路径问题求解中$取得了很好的效果$有着运算速度快<鲁棒性好<解的质量与个体数目相关性小<所获得的解质量高等诸多优点%

参考文献H

?’@李军$郭耀煌&物流配送车辆优化调度理论与方法?I @

&北京H 中国物资出版社$622’&?6@J C K K C L MN $O P C Q R S Q F *T &!S Q F E U D C=V S Q G W X F E G E Y S F E W K ?;@&!Q W UZ O O O Z K F C Q K S F E W K S D T W K [C Q C K U CW K\C ]Q S D \C F ^

V W Q _=$Z )?T @&!E =U S F S V S M $\N H Z O O O"C Q ‘E U C T C K F C Q

$’115&’186a’180&?7@O P C Q R S Q F *T $"R E b &!S Q F E U D C =V S Q G W X F E G E Y S F E W K H L C ‘C D W X G C K F =$S X X D E U S F E W K =S K LQ C =W ]Q U C =?;@&!Q W U T W K c Q C ==W K

O ‘W D ]F E W K S Q MT W G X ]F S F E W K 622’?T @&!E =U S F S V S M $\N H Z O O O!Q C ==$622’&0’a0.&?8@IS ]Q E U CT D C Q U $N S G C =J C K K C L M &+R CX S Q F E U D C=V S Q G ^C d X D W =E W K $=F S P E D E F M $S K LU W K ‘C Q c C K U CE KSG ]D F E L E G C K =E W K S D

U W G X D C d=X S U C ?N @&Z O O O+Q S K =S U F E W KW KO ‘W D ]F E W K S Q MT W G X ]F S F E W K

$6226$.-’(H50a97&?5@;M C L"S D G C K $Z G F E S Y ;R G S L $"S P S R;D a IS L S K E &!S Q F E U D C =V S Q G W X F E G E Y S F E W K[W Q F S =_S ==E c K G C K F X Q W P D C G ?N @&IE ^

U Q W X Q W U C ==W Q =S K LIE U Q W =M =F C G =

$6226$6.H7.7a79’&?.@"R E b $O P C Q R S Q F *T &O G X E Q E U S D =F ]L M W [X S Q F E U D C =V S Q G W X F E G E Y S F E W K ?;@&!Q W U C C L E K c =W [F R C ’111T W K c Q C ==W KO ‘W ^

D ]F

E W K S Q MT W G X ]

F S F E W K ?T @&!E =U S F S V S M $\N H Z O O O"C Q ‘E U C T C K F C Q

$’111&’185a’152&5

7’第8期

带时间窗车辆路径问题的粒子群算法

带时间窗车辆路径问题的粒子群算法

作者：李宁， 邹彤， 孙德宝

作者单位：李宁(华中科技大学控制科学与工程系,湖北,武汉,430074;武汉理工大学计算机科学与技术学院,湖北,武汉,430070)， 邹彤,孙德宝(华中科技大学控制科学与工程系,湖北,武汉

,430074)

刊名：

系统工程理论与实践

英文刊名：SYSTEMS ENGINEERING—THEORY & PRACTICE

年，卷(期)：2004，24(4)

被引用次数：68次

参考文献(6条)

1.李军.郭耀煌物流配送车辆优化调度理论与方法 2001

2.Kennedy J.Eberhart R C Particle swarm optimization 1995

3.Eberhart R C.Shi Y Particle swarm optimization: developments,applications and resources 2001

4.Maurice Clerc.James Kennedy The particle swarm-explosion, stability, and convergence in a multidimensional complex space 2002(01)

5.Ayed Salmen.Imtiaz Ahmad.Sabah Al-Madani Particle swarm optimization for task assignment problem 2002

6.Shi Y.Eberhart R C Empirical study of particle swarm optimization 1999

相似文献(10条)

1.期刊论文叶伟.YE Wei带时间窗车辆路径问题的混合量子粒子群算法-物流科技2009,32(6)

针对带时间窗的车辆路径问题,采用混合量子粒子群算法对该问题进行了求解,该算法将量子粒子群算法与模拟退火算法相结合,充分发挥量子粒子群算法全局寻优能力强以及模拟退火算法局部寻优能力强的特点,从而能有效地避免早熟.仿真结果表明,该算法不仅收敛速度快,而且还具有较高的求解质量.

2.学位论文吴斌车辆路径问题的粒子群算法研究与应用2007

物流被称为“第三利润源泉”，越来越受到人们的关注，日益成为国民经济的基础产业。运输是物流中的重要环节，占物流成本的60％以上。车辆路径问题主要研究物流配送中车辆线路优化以降低运输成本。该问题是运筹学和组合优化领域中的著名NP问题，在航班调度、列车编组等众多领域都有应用。由于NP问题求解的复杂性，目前车辆路径问题的求解方法主要使用各种智能优化算法。本文主要研究了以下四种模型的车辆路径问题：有能力约束的车辆路径问题，开放式车辆路径问题，基于客户满意度的开放式车辆路径问题，开放式动态网络车辆路径问题。研究了粒子群及其改进算法对上述模型的求解。具体的研究内容如下：

(1)首先介绍了本论文的研究背景及意义，给出了车辆路径问题的定义，分析了车辆路径问题的组成要素。然后在对国内外大量文献总结提炼的基础上，从车辆路径问题的模型和求解算法两方面，深入分析了车辆路径问题的国内外研究现状。

(2)系统研究了基于粒子群算法的有能力约束车辆路径问题(CapacityVehicle Routing Problem，CVRP)。提出了整数编码、实数编码两种求解CVRP的方法。在整数编码中，以交换数为基础，对粒子的速度重新定义，并对速度的加、减等操作进行了定义，提出了“换位减”算子作为整数编码的速度计算方法：针对整数编码算法存在的问题，提出了一种实数编码方法求解CVRP，用实数的整数部分表示客户所在的车辆，小数部分表示在该车辆中配送的次序，融合遗传算法的思想，引入交叉算子以增加种群的多样性，详细讨论了粒子群算法的各个参数对算法结果的影响。为了与其他智能优化算法比较，研究了遗传算法、人工鱼群算法在CVRP中的应用。将双种群遗传算法用于CVRP的求解；提出了人工鱼群算法在CVRP中的应用，针对车辆路径问题的特点，定义了鱼群的距离、领域等概念，提出了人工鱼根据自身在鱼群中的排序，自适应选择移动算子的策略。

(3)通过引入虚拟配送中心的概念，建立了开放式车辆路径问题的三下标数学模型。提出了开放式车辆路径问题的粒子群求解方法，将最邻近插入、最远插入、2-Opt、3-Opt 等启发式算法作为再优化过程引入粒子群算法，通过这些启发式算法调整线路内和线路间的客户来改进解，从理论上分析了这些算法的计算复杂度。通过实验分析，找出合适的启发式算子，并和其他的算法进行了比较。

(4)以客户满意度为首要优化目标，建立了基于客户满意度的开放式车辆路径问题的数学模型，使用梯形模糊数表示客户满意度。综合考虑距离、等待时间、客户的满意度等因素，定义了广义的距离和节约费用的概念，提出了改进的最邻近法和最廉价插入法，将这两个算法作为初始化和改进算子结合粒子群算法进行优化求解。分析了算法的复杂度，对算法的各个参数进行了讨论，通过实验仿真对这几种方法进行了分析比较。

(5)动态网络车辆路径问题目前研究的热点和难点问题，将动态网络与开放式两个因素结合起来研究车辆路径问题还未见报道。本文针建立了开放式动态网络车辆路径问题的数学模型，提出了一种连续时间依赖函数模型。提出了自适应惯性权重调整的粒子群算法，定义了粒子的“位置比”概念，充分利用粒子的已有知识，动态的调整惯性权重。在算法中，引入公告板策略，根据粒子适应度的高低分类更新粒子状态，对于优秀粒子使用一种新的状态更新公式，以使其跳出局部极值点。对于适应度低的粒子，通过统计其在公告板中出现的频率，用新的粒子替换以保持种群的多样性。通过实验讨论了算法的参数设置，对几种惯性权重方案进行了分析比较，实验结果证明了算法的有效性。

(6)在上述理论工作的基础上，针对第三方物流在国内的迅速发展，而相应的车辆调度软件功能不够完善，开发了智能车辆调度系统。该系统包括智能车辆调度、承运单的管理、电子地图的显示等功能。该系统可以处理有时间窗、有能力约束等多种情况的车辆调度问题，提供遗传算法、粒子群算法等多种优化算法供用户使用。系统在杭州某物流公司应用，取得了良好的效果。

最后，对全文研究工作进行了总结，展望了车辆路径问题的模型和算法研究的前景。

3.学位论文张丽艳粒子群算法在车辆路径问题中的应用2006

车辆路径问题是供应链研究的一项重要内容，是运筹学中的NP难题。粒子群优化算法是一种利用群智能技术的进化算法，种群内社会信息的共享使粒子群算法拥有很好的进化优势，粒子通过跟踪个体极值（单个粒子所经历的最优解）和全局极值（整个种群经历的最优解）来进行寻优，具有很高的搜索效率；模拟退火算法模拟金属冷却过程，使用概率来避免陷入局部最优。本课题将粒子群优化算法与模拟退火算法结合，提出了一种求解车辆路径问题的混合粒子群算法。通过实例计算及与遗传算法的比较，得出结论：应用混合粒子群算法可以快速地求得带时间窗车辆路径问题

的优化解，是一种求解离散组合优化问题的有效方法。

本课题将VRP分解为两个子问题：（1）任务分配问题，即把所有发货点任务分配给可供选择的车辆；（2）路径优化问题，也就是旅行商问题，对每辆车所走的路径进行优化，以达到整体路径最短。应用粒子群算法进行任务分配后，用模拟退化算法进行路径优化，两次优化运算独立，根据其并行性，本课题设计了并行混合粒子群算法并用MPI实现了消息通讯。

4.期刊论文吴勇.叶春明.马慧民.夏梦雨.WU Yong.YE Chun-ming.MA Hui-min.XIA Meng-yu基于并行粒子群

算法的带时间窗车辆路径问题-计算机工程与应用2007,43(14)

提出求解带时间窗车辆路径问题的多群并行的粒子群算法.为了提高算法的收敛速度,在每个粒子群中嵌入了记忆功能.针对基本粒子群算法在求解有时间窗车辆路径问题时初始解的单一性导致局部收敛的问题,对两个种群采用了两种不同的初始化方法,并在进化过程中,两个种群相互用记忆粒子替换对方种群中的较差粒子.最后将该算法的运行结果与其他算法进行比较,表明该算法的有效性.

5.学位论文罗先国粒子群算法及其在车辆路径问题中的应用研究2006

本文针对基本粒子群算法易陷入局部极小点、搜索精度不高等缺点，利用遗传算法的原理，在粒子群算法中引入了选择、杂交和变异算子，结合局部版粒子群算法的思想，提出了一种基于遗传机制的改进粒子群算法。用基准函数对改进的粒子群算法进行了测试，取得了很好的效果，具有很好的通用性。

将粒子群算法应用于车辆路径问题的求解。设计了一种实数编码方案，用粒子的位置表示车辆路径，建立了解决车辆路径问题的粒子群算法。建立了车辆路径问题的数学模型，应用改进的粒子群算法求解非满载车辆路径问题和带时间窗的车辆路径问题，取得了很好的仿真结果。与车辆路径问题的遗传算法相比，改进的粒子群算法提高了最优路径搜索的成功率，能更有效地求解车辆路径问题。

6.期刊论文张丽艳.庞小红.夏蔚军.吴智铭.梁硕.ZHANG Li-yan.PANG Xiao-hong.XIA Wei-jun.WU Zhi-ming.

LIANG Shuo带时间窗车辆路径问题的混合粒子群算法-上海交通大学学报2006,40(11)

将粒子群优化算法与模拟退火算法结合,提出了一种求解车辆路径问题的混合粒子群算法.实例计算及与遗传算法比较的结果表明:应用混合粒子群算法可以快速地求得带时间窗车辆路径问题的优化解;该算法是一种求解离散组合优化问题的有效方法.

7.期刊论文魏明.靳文舟求解车辆路径问题的离散粒子群算法-计算机科学2010,37(4)

考虑车辆行驶时间和顾客服务时间的不确定性,建立了以车辆配送总费用最小为目标的机会约束规划模型,将其进行清晰化处理,使之转化为一类确定性数学模型,并构造了求解该问题的一种离散粒子群算法.算法重新定义了粒子的运动方程及其相关离散量运算法则,并设计了排斥算子来维持群体的多样性.与标准遗传算法和粒子群算法比较,该算法能够有效避免算法陷入局部最优,取得了满意的结果.

8.期刊论文张念志.吴耀华.ZHANG Nian-zhi.WU Yao-hua基于车辆路径问题的带近邻因子的粒子群算法-计算

机工程与应用2008,44(32)

提出了一种改进的粒子群算法.该算法通过引入近邻因子,增强了当前粒子的学习功能,克服了基本粒子群算法易陷于局部最优的缺陷,提高了算法进化的收敛精度.将该算法用于解决车辆路径问题,实验结果表明具有较好的性能和很好的应用价值.

9.学位论文陈利基于混合粒子群算法的物流配送车辆路径问题的研究2007

配送是物流系统中很重要的一个环节。在物流的各项成本中，配送成本占了相当高的比例。车辆路径问题是配送系统中的核心问题，也是研究热点之一。路径安排合理能有效提高运输效率、降低服务成本。本文以物流配送为背景，对物流配送车辆路径问题和带时间窗的车辆路径问题采用基于爬山算法的混合粒子群算法进行了深入的研究。

粒子群算法是一种基于群智能方法的演化计算技术，具有深刻的智能背景，广泛应用于科学研究和工程问题。针对粒子群算法早熟收敛和局部搜索能力不足的缺陷，本文引入局部搜索能力强的爬山算法对其进行优化，提出了基于爬山算法的混合粒子群算法。设计了两种混合粒子群算法

，对每代群体中的全局极值引入爬山操作构成混合PSO方案一，对每个粒子进行爬山操作构成混合：PSO方案二。混合粒子群算法在局部搜索能力和收敛速度上较标准PSO都有很大的改进。混合PSO方案一局部搜索能力大于标准PSO，混合PSO方案二局部搜索能力大于混合PSO方案一。混合PSO方案二的收敛速度最快，混合PSO方案一次之，标准PSO的收敛速度最慢。

本文在查阅大量中外文献的基础上，结合物流配送的特点，建立了物流配送车辆路径问题的数学模型。采用标准PSO算法、混合PSO方案一和混合PSO方案二3种方法求解了物流配送车辆路径问题和带时间窗的车辆路径问题。仿真试验表明，本文提出的混合PSO方案一和混合PSO方案二性能均优于标准PSO。混合PSO方案二的性能最优，具有很强的收敛能力，能够有效地求解物流配送车辆路径问题。该方法对物流配送企业优化配送路径、降低配送成本和提高物流经营管理水平，最终增加企业的竞争能力具有重要的参考价值。

10.期刊论文郗建国.郝会霞基于捕食搜索策略的粒子群算法在车辆路径问题中的应用-硅谷2009,""(7)

通过对捕食搜索策略限制的调节,来实现粒子群算法搜索空间的增大或减小,从而达到探索能力和开发能力的平衡,使粒子群算法求得更好的最优解,并用C++语言编程实现并将其应用于实例,证明该算法的有效性和可行性.

引证文献(68条)

1.马炫.彭破.刘庆求解带时间窗车辆路径问题的改进粒子群算法[期刊论文]-计算机工程与应用 2009(27)

2.黄泽汉.谭跃进.邓宏钟基于蚁群优化的物流网络多约束路径规划[期刊论文]-系统工程 2009(6)

3.何建佳.徐福缘.牟欣SDN的一个供需流:物流系统的整合优化分析[期刊论文]-工业技术经济 2009(2)

4.陈永刚.牛丹梅.范庆辉粒子群算法在组合优化问题上的研究与发展[期刊论文]-电脑与电信 2008(12)

5.靳志宏.解玉真.李阳.韩骏集装箱支线运输船舶调度优化问题[期刊论文]-中国航海 2008(4)

6.江玮皤.何建民.吴容基于粒子群优化的有反向物流的车辆路径问题[期刊论文]-系统管理学报 2008(4)

7.张兰.雷秀娟几种改进PSO算法在带时间窗车辆路径问题中的比较与分析[期刊论文]-计算机工程与科学2008(12)

8.蔡延光.魏明一种新型自适应混沌粒子群算法在联盟运输调度问题中的研究[期刊论文]-系统工程 2008(8)

9.沈林成.霍霄华.牛轶峰离散粒子群优化算法研究现状综述[期刊论文]-系统工程与电子技术 2008(10)

10.王雅琳.王宁.阳春华.桂卫华求解任务分配问题的一种离散微粒群算法[期刊论文]-中南大学学报（自然科学版） 2008(3)

11.龙汀.潘若愚蚁群算法求解带时间窗的配送路径问题[期刊论文]-合肥工业大学学报（自然科学版）

2008(7)

12.杨鸣亮.李蓓智.周亚勤蚁群算法和遗传算法融合及其在有时间窗的车辆路径问题中的应用[期刊论文]-工业控制计算机 2008(6)

13.张志霞.邵必林基于改进蚁群算法的运输调度规划[期刊论文]-公路交通科技 2008(4)

14.席阳.李铁克基于粒子群算法求解区间值板坯设计优化问题[期刊论文]-计算机工程与应用 2008(3)

15.陈文兰.戴树贵车辆路径安排问题算法研究综述[期刊论文]-滁州学院学报 2007(3)

16.李昊.罗霞.姚琛浮动车数据在车辆路径问题中的应用[期刊论文]-西南交通大学学报 2007(6)

17.钟一文.蔡荣英求解二次分配问题的离散粒子群优化算法[期刊论文]-自动化学报 2007(8)

18.姚韵.朱金福.柏明国航班过站地面服务的优化调度算法[期刊论文]-信息与控制 2007(4)

19.马楠.张立宁基于粗糙集——粒子群神经网络的建设项目安全预测研究[期刊论文]-中国安全科学学报2007(4)

20.丰伟.李雪芹基于粒子群算法的多目标车辆调度模型求解[期刊论文]-系统工程 2007(4)

21.贾顺平.尹相勇基于VRPTW模型与合理化判断的货物配送流程研究[期刊论文]-物流技术 2007(3)

22.王芳.丁海利.高成修改进的粒子群优化算法在随机需求车辆路径问题中的应用[期刊论文]-武汉大学学报（理学版） 2007(1)

23.张旭梅.邱晗光基于k-中心点法的改进粒子群算法在旅行商问题中的应用[期刊论文]-计算机集成制造系统 2007(1)

24.肖辉.严勇.萧蕴诗.吴启迪上海世博园区路径智能优化及流量控制策略[期刊论文]-计算机工程与应用2007(19)

25.蔡荣英.李丽珊.林晓宇.钟一文求解旅行商问题的自学习粒子群优化算法[期刊论文]-计算机工程与设计2007(2)

26.钟一文.宁正元.蔡荣英.詹仕华一种改进的离散粒子群优化算法[期刊论文]-小型微型计算机系统

2006(10)

27.钟一文.宁正元.蔡荣英.詹仕华一种改进的离散粒子群优化算法[期刊论文]-小型微型计算机系统

2006(10)

28.李继玲.卢才武.李金成基于蚁群算法的有时间窗车辆调度问题的研究[期刊论文]-信息技术 2006(5)

29.钟一文.杨建刚.宁正元求解TSP问题的离散粒子群优化算法[期刊论文]-系统工程理论与实践 2006(6)

30.姚韵.朱金福.柏明国一类有动态时间窗的并行多机启发式调度算法[期刊论文]-系统工程 2006(1)

31.董媛媛.陶绪林.周晶带回程的车辆运输路径优化及定价模型[期刊论文]-现代交通技术 2006(4)

32.李军军.王锡淮.黄有方.肖健梅基于混合微粒群优化算法的配送中心选址问题求解[期刊论文]-物流科技2006(8)

33.王海星.王德占.申金升蚁群算法解决有时间窗的车辆优化调度问题研究[期刊论文]-物流技术 2006(11)

34.刘振峰.陈燕基于时间Petri网的供应链网络关键路径分析[期刊论文]-数学的实践与认识 2006(11)

35.张丽艳.庞小红.夏蔚军.吴智铭.梁硕带时间窗车辆路径问题的混合粒子群算法[期刊论文]-上海交通大学

学报 2006(11)

36.钟一文.杨建刚独立任务分配问题的离散粒子群优化算法[期刊论文]-模式识别与人工智能 2006(3)

37.刘娜.雷秀娟免疫PSO算法求解多库房带时间窗VRP[期刊论文]-计算机工程与应用 2010(5)

38.康琦.汪镭.吴启迪半导体生产线工序参数的逻辑时序微粒群优化策略[期刊论文]-控制与决策 2006(9)

39.王德东.陈术山.郑丕谔不确定车辆数的有时间窗车辆选径问题的混合算法[期刊论文]-计算机应用

2006(2)

40.刘志雄.王少梅基于粒子群算法的并行多机调度问题研究[期刊论文]-计算机集成制造系统 2006(2)

41.陈群.晏克非.成峰基于粒子群优化算法的动态停车路径诱导技术[期刊论文]-计算机工程与应用 2006(15)

42.唐勇.刘峰涛新型遗传模拟退火算法求解带VRPTW问题[期刊论文]-计算机工程与应用 2006(7)

43.李永先.胡祥培.熊英物流配送系统中车辆路径问题仿真优化及其进展[期刊论文]-管理科学 2006(4)

44.林献坤.李爱平.陈炳森混合粒子群算法在混流装配线优化调度中的应用[期刊论文]-工业工程与管理2006(1)

45.石玉峰战时不确定性运输路径优化研究[学位论文]博士 2006

46.刘芹基于信息平台的车辆调度研究与仿真[学位论文]硕士 2006

47.王俊伟粒子群优化算法的改进及应用[学位论文]博士 2006

48.秦绪伟物流系统集成规划模型及优化算法研究[学位论文]博士 2006

49.闫滨大坝安全监控及评价的智能神经网络模型研究[学位论文]博士 2006

50.熊英有时间窗的车辆路径问题仿真模型研究[学位论文]硕士 2006

51.奚玮君粒子群优化算法的研究与应用[学位论文]硕士 2006

52.熊建秋水科学信息分析计算新方法及其应用[学位论文]博士 2006

53.谭皓.王金岩.何亦征.沈春林一种基于子群杂交机制的粒子群算法求解旅行商问题[期刊论文]-系统工程2005(4)

54.李宁.付国江.库少平.陈明俊粒子群优化算法的发展与展望[期刊论文]-武汉理工大学学报（信息与管理工程版） 2005(2)

55.AC-PSO算法在无人机任务规划中的应用[期刊论文]-南京航空航天大学学报（英文版） 2005(3)

56.康琦.汪镭.吴启迪群体智能与人工生命[期刊论文]-模式识别与人工智能 2005(6)

57.吴建生.秦发金基于MATLAB的粒子群优化算法程序设计[期刊论文]-柳州师专学报 2005(4)

58.周柏松随机行驶时间车辆调度问题研究[学位论文]硕士 2005

59.李继玲蚁群算法在物流运输车辆优化调度中的应用研究[学位论文]硕士 2005

60.尚志强基于粗糙集-神经网络的建筑工程成本预测方法研究[学位论文]硕士 2005

61.黄娟港口物流中心配送方法研究[学位论文]硕士 2005

62.田明俊智能反演算法及其应用研究[学位论文]博士 2005

63.赵传信混合粒子群算法应用研究[学位论文]硕士 2005

64.史志俊粒子群优化算法及其在结构动力修改中的应用研究[学位论文]硕士 2005

65.矫志宁微粒群算法及其应用研究[学位论文]硕士 2005

66.康琦微粒群优化算法的研究与应用[学位论文]硕士 2005

67.胡志杰基于GIS的配送路径规划方法研究[学位论文]硕士 2005

68.彭扬.陈子侠.吴承键定位-运输路线安排问题的改进离散粒子群优化算法[期刊论文]-智能系统学报

2010(1)

本文链接：https://www.wendangku.net/doc/9514656889.html,/Periodical_xtgcllysj200404020.aspx

授权使用：杭州电子科技大学(hzdzkj)，授权号：47878a98-8a3b-4650-bf66-9dd200fba181

下载时间：2010年8月14日