基于遗传算法的物流配送路径优化研究.docx

该【基于遗传算法的物流配送路径优化研究 】是由【zhangkuan1439】上传分享，文档一共【12】页，该文档可以免费在线阅读，需要了解更多关于【基于遗传算法的物流配送路径优化研究 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1
2
用单亲遗传算法求解配送车辆调度问题的研究
郎茂祥
(北京交通通大学交通运输输学院,北北京11000444)
摘要::论文建立立了物流配配送车辆调调度问题的的数学模型型,并针对对传统遗传传算法对复复杂问题搜搜索效率低低,易陷入入“早熟收敛敛”的缺点,构构建了求解解物流配送送车辆调度度问题的单单亲遗传算算法,并进进行了实验验计算。计计算结果表表明,用单单亲遗传算算法求解物物流配送车车辆调度问问题,可以以取得比传传统遗传算算法更优的的结果。
关关键词:物物流配送;;车辆调度度问题;单单亲遗传算算法;遗传传算法
StudyyonthePartthenoo-GenneticcAlggoritthmfforPPhysiicalDisttribuutionnVehhicleeSchhedullingProbblem
LLANGMao--xianng,HUUSi--ji
(SchoooloofTrraffiicanndTrranspportaationn,NorrtherrnJiiaotoongUUniveersitty,Beeijinng10000444,Chiina)
Abstrract::“ImmaatureeConnverggencee”,thhisppaperresttabliisheddapparthheno--geneeticalgoorithhmfforssolviingpphysiicaldisttribuutionnvehhicleeschhedullingprobblemandmadeesommeexxperiimenttalccompuutatiions..Theecommputaationnalrresulltshhadddemonnstraatedthatttheeparrthenno-geenetiicallgoriithmhadhighherooptimmizinngeffficiiencyyanddquaalityythaantrradittionaalgeenetiicallgoriithminssolviingpphysiicaldisttribuutionnvehhicleeschhedullingprobblem..
Keywoords::physsicalldisstribbutioon;vvehicclesscheddulinngprrobleem;pertthenoo-genneticcalggoritthm;geneeticalgoorithhm
1引言言
随随着市场经经济的发展展和物流专专业化水平平的提高,物物流配送业业得到了迅迅速发展。
1
3
在在物流配送送业务中,配配送车辆调调度问题的的涉及面较较广,对企企业提高服服务质量、降降低物流成成本的影响响也较大。在在现实生产产和生活中中,邮政投投递问题、公公共汽车调调度问题、电电力调度问问题、管道道铺设问题题、计算机机网络拓扑扑设计问题题等都可以以抽象为物物流配送车车辆调度问问题。因此此,研究物物流配送车车辆调度问问题具有重重要的理论论和现实意意义。
物流配送车车辆调度问问题作为一一个NP难难题,随着着客户数量量的增加,可可选的车辆辆路径方案案数量将以以指数速度度急剧增长长。因此,用用启发式算算法求解该该问题就成成为人们研研究的一个个重要方向向。求解物物流配送车车辆调度问问题的方法法很多,常常用的有旅旅行商法、动动态规划法法[1]、节节约法[22]、扫描描法[3]]、分区配配送算法[[4]、方方案评价法法[5]等。
遗传算法的的出现为求求解物流配配送车辆调调度问题提提供了新的的工具。BBerthhold、MMalmbborg、OOchi、姜姜大立、李李大卫、李李军、谢秉秉磊、张涛涛等人都曾曾利用遗传传算法求解解物流配送送车辆调度度问题[66-15]],并取得得了一些研研究成果。作作者也尝试试采用新的的编码方法法和遗传算算子构造了了求解物流流配送车辆辆调度问题题的遗传算算法,并对对文献[99]中的例例题进行了了实验计算算,计算结结果表明,虽虽然利用传传统遗传算算法能够方方便地求得得问题的近近似最优解解,但也暴暴露出其存存在对复杂杂问题搜索索效率低,易易陷入“早熟收敛敛”[16]的缺点点。为了提提高优化效效率和质量量,作者构构造了求解解物流配送送车辆调度度问题的单单亲遗传算算法,通过过实验计算算,取得比比传统遗传传算法更好好的计算结结果。
2物流流配送车辆辆调度问题题的数学模模型
物物流配送车车辆调度问问题可以描描述为:从从某物流中中心用多台台配送车辆辆向多个客客户送货,每每个客户的的位置和货货物需求量量一定,每每台配送车车辆的载重重量一定,其其一次配送送的最大行行驶距离一一定,要求求合理安排排车辆配送送路线,使使目标函数数得到优化化,并满足足以下条件件:(1)每每条配送路路径上各客客户的需求求量之和不不超过配送送车辆的载载重量;(22)每条配配送路径的的长度不超超过配送车车辆一次配配送的最大大行驶距离离;(3)每每个客户的的需求必须须满足,且且只能由一一台配送车车辆送货。
设设物流中心心有K台配配送车辆,每每台车辆的的载重量为为Qk(k=11,2,····,KK),其一一次配送的的最大行驶驶距离为DDk,需要向向L个客户户送货,每每个客户的的货物需求求量为qi(i=11,2,····,LL),客户户i到j的运距为为dij,物流流中心到各各客户的距距离为d0j(i、j=1,2,···,L),再设设nk为第k台台车辆配送送的客户数数(nk=0表
1
4
示示未使用第第k台车辆),用用集合Rk表示第k条路径,其其中的元素素rki表示客户户rki在路径径k中的顺序序为i(不包括括物流中心心),令rrk0=0表示物物流中心,若若以配送总总里程最短短为目标函函数,则可可建立如下下物流配送送车辆调度度问题的数数学模型::
(11)
..(2)
(3)
(44)
(5)
(66)
(7)
(8)
上述模型中中,(1)式式为目标函函数;(22)式保证证每条路径径上各客户户的货物需需求量之和和不超过配配送车辆的的载重量;;(3)式式保证每条条配送路径径的长度不不超过配送送车辆一次次配送的最最大行驶距距离;(44)式表明明每条路径径上的客户户数不超过过总客户数数;(5)式式表明每个个客户都得得到配送服服务;(66)式表示示每条路径径的客户的的组成;(
1
4
77)式限制制每个客户户仅能由一一台配送车车辆送货;;(8)式式表示当第第k辆车服服务的客户户数≥1时,说说明该台车车参加了配配送,则取取signn(nk)=1,当当第k辆车车服务的客客户数<1时,表表示未使用用该台车辆辆,因此取取signn(nk)=0。
3物流流配送车辆辆调度问题题的单亲遗遗传算法

单单亲遗传算算法[17]是对传统统遗传算法法的一种改改进,它不不使用传统统遗传算法法中常用的的交叉算子子,对某个个个体的遗遗传操作只只在该条染染色体上进进行,即只只通过单个个个体繁殖殖后代。对对于采用自自然数编码码的个体,单单亲遗传算算法常用的的遗传操作作算子有::基因换位位算子、基基因倒位算算子和基因因移位算子子等,使用用这些算子子可完全实实现PMXX、CX、OOX等传统统交叉算子子[18]的功能。由由于单亲遗遗传算法不不使用交叉叉算子,即即使群体中中的个体完完全相同,也也不影响遗遗传迭代的的进行,从从而摆脱了了对群体多多样性的要要求,能克克服“早熟收敛敛”问题。
使用单亲遗遗传算法求求解问题,也也需要从任任一初始群群体出发,通通过选择、染染色体重组组等遗传操操作,使群群体一代一一代地进化化到搜索空空间中越来来越好的区区域。单亲亲遗传算法法包括编码码、初始群群体生成、适适应性评估估、选择和和染色体重重组5个基基本要素。

(11)编码方方法的确定定。根据物物流配送车车辆调度问问题的特点点,作者采采用了简单单直观的自自然数编码码方法,用用0表示配配送中心,用用1、2、···、L表示各需求点。由于在配送中心有K台车辆,则最多存在K条配送路径,为了在编码中反映车辆配送的路径,作者巧妙地采用了增加K-1个虚拟配送中心的方法,分别用L+1、L+2、···、L+K-1表示。这样,1、2、···、L+K-1这L+K-1个互不重复的自然数的随机排列就构成一个个体,并对应一种配送路径方案。例如,对于一个有7个需求点,用3台车辆完成配送任务的问题,则可用1、2、···、9(8、9也表示配送中心)这9个自然数的随机排列,表示物流配送路径方案,如个体129638547表示的的配送方案为:路径1:0-1-2-9(0),路径2:9(0)-6-3-8(0),路径3:8(0)-5-4-7-0,需3台车辆配送。
(22)初始群群体的确定定。随机产产生一种11~L+KK-1这LL+K-11个互不重重复的自然然数的排列列,即形成成一个个体体。设群体体规模为NN,则通过过随机产生生N个这样样的个体,
1
5
即即形成初始始群体。
(33)适应度度评估。对对于某个个个体所对应应的配送路路径方案,要要判定其优优劣,一是是要看其是是否满足配配送的约束束条件;二二是要计算算其目标函函数值(即即各条配送送路径的长长度之和)。本本文根据配配送路径选选择问题的的特点所确确定的编码码方法,隐隐含能够满满足每个需需求点都得得到配送服服务及每个个需求点仅仅由一台车车辆配送的的约束条件件,但不能能保证满足足每条路径径上各需求求点需求量量之和不超超过汽车载载重量及每每条配送路路线的长度度不超过汽汽车一次配配送的最大大行驶距离离的约束条条件。为此此,对每个个个体所对对应的配送送方案,要要对各条路路径逐一进进行判断,看看其是否满满足上述两两个约束条条件,若不不满足,则则将该条路路径定为不不可行路径径,最后计计算其目标标函数值。对对于某个个个体j,设设其对应的的配送路径径方案的不不可行路径径数为Mjj(Mj=0表示该该个体是一一个可行解解),其目目标函数值值为Zj,则该个个体的适应应度Fj,可用下下式表示::
Fjj=1/(ZZj+Mj×Pw)(9)
式中,Pww为对每条条不可行路路径的惩罚罚权重(该该权重可根根据目标函函数的取值值范围取一一个相对较较大的正数数)。
(44)选择操操作。将每每代群体中中的N个个个体按适应应度由大到到小排列,排排在第一位位的个体性性能最优,将将它复制一一个直接进进入下一代代,并排在在第一位。下下一代群体体的另N--1个个体体需要根据据前代群体体的N个个个体的适应应度,采用用赌轮选择择法产生。具具体地说,就就是首先计计算上代群群体中所有有个体适应应度的总和和(ΣFj),再计计算每个个个体的适应应度所占的的比例(FFj/ΣFj),以此此作为其被被选择的概概率。这样样选择方法法既可保证证最优个体体生存至下下一代,又又能保证适适应度较大大的个体以以较大的机机会进入下下一代。
(55)染色体体重组。对对通过选择择操作产生生的新群体体,除排在在第一位的的最优个体体外,另NN-1个个个体要运用用单亲遗传传算子进行行染色体重重组。本文文选用多点点基因换位位算子实现现染色体重重组,现举举例说明其其操作过程程:①根据预先先确定的最最大基因换换位次数(NNc),取取随机数kk(1≤k≤Nc)。本本例中设NNc=4,kk=2。②②在染色体体上随机选选取k对基基因,并交交换其位置置。本例中中设原染色色体为A==47855639221,随机机产生的第第一对交换换基因位为为2和5,则则基因换位位后染色体体变为A’’=46885739921;随随机产生的的第二对交交换基因位位为3和88,再次实实施基因换换位后染色色体变为
1
7
AA”=46225739981。③③判断实施施多点基因因换位后,个个体的适应应值是否增增加,若增增加,则用用换位后的的个体取代代原个体,进进入下一代代,否则原原个体直接接进入下一一代。本例例中设A”的适应值值大于A的的适应值,则则A”进入下一一代。
(66)终止准准则。采用用进化指定定代数的终终止准则。
4实验验计算与结结果分析
作者用C语语言分别编编制了物流流配送车辆辆调度问题题的传统遗遗传算法程程序和单亲亲遗传算法法程序,并并对文献[[9]中某某配送中心心使用2台台车辆对88个需求点点送货的问问题进行了了实验计算算(计算时时在原问题题的基础上上增加了车车辆一次配配送的最大大行驶距离离为40kkm的约束束条件)。实实验中采用用了以下参参数:群体体规模为220,进化化代数为550,,单单亲遗传算算法的最大大基因换位位次数取44。将两种种算法的计计算机程序序分别随机机运行100次,得到到的计算结结果(即配配送路径总总长度)见见表1。
表1物物流配送车车辆调度问问题的传统统遗传算法法和单亲遗遗传算法计计算结果的的比较
计算次序
1
2
3
4
5
6
7
8
9
10
传统遗传算算法的计算算结果Z/km
72
72

70

70

75

69
单亲遗传算算法的计算算结果Z/kkm
69

70
70

69

72
69

从表1可以以看出,传传统遗传算算法和单亲亲遗传算法法的10次次计算结果果均优于节节约法的结结果79..5km,而而且单亲遗遗传算法得得到的结果果更优,110次计算算中,,还还有3次得得到了问题题的次优解解69kmm,而传统统遗传算法法仅1次得得到了最优优解,1次次得到了次次优解。这这充分说明明,单亲遗遗传算法可可以克服传传统遗传算算法的“早熟收敛敛”问题,具具有良好的的搜索效率率和寻优性性能。
另外,作者者还对文献献[19]]中一个某某配送中心心使用3台台车辆向110个需求求点送货的的实例进行行了实验计计算,计算算显示了同同样的效果果,用单亲亲遗传算法法能够方便便地求得问问题的两个个最优解,其其配送路径径总长度都都是80kkm,其中中一个解与与文献[119]中
1
7
节节约法的计计算结果相相同。由于于该问题的的约束条件件比较强,利利用传统遗遗传算法求求解,有时时甚至不能能得到可行行解。
5结论论
(1)本文文在建立物物流配送车车辆调度问问题的数学学模型的基基础上,针针对传统遗遗传算法对对复杂问题题搜索效率率低,易陷陷入“早熟收敛敛”的缺点,构构造了求解解物流配送送选择问题题的单亲遗遗传算法。实实验计算结结果表明,单单亲遗传算算法可以克克服传统遗遗传算法的的上述缺点点,从而取取得比传统统遗传算法法更优的结结果,充分分显示了其其良好的寻寻优性能。
(2)本文文构造单亲亲遗传算法法的思路,以以及在算法法中巧妙设设计的个体体编码方法法、个体适适应值计算算方法及选选择、多点点基因换位位等遗传算算子,对解解决类似的的组合优化化问题有一一定的参考考价值。
[参考文献献]
[1]蔡蔡希贤,[M]..武汉::华中工学学院出版社社,19885.
[2]..Scheeduliingoofveehicllesffromaceentraaldeepottoaanummberofddelivverypoinnts[JJ].,11964,..
[3]..anddMilllerLR...AAHeuuristticAAlgorrithmmforrtheeVehhicleeDisspatcchProbblem[[J]..,11974,222.
[4]罗罗上远,徐徐天亮,[JJ].物物流技术,22000,,pp22-225.
[5]刘刘朝晖,范范荣华,[[M].北京:中中国物资出出版社,11997年年1月.
[6]::AGGenetticAApprooach[[J].EuroopeannJouurnallofOperratioonalReseearchh,19995,,p6445-6661.
[7]MMalmbborg,,[JJ].EEuroppeanJourrnalofOOperaationnalRReseaarch,,19966,,,,p1221-1334.
[8]OOchi,,LuizzS...Viaanna,,ParralleelEvvoluttionaaryAAlgorrithmmforrTheeVehhicleeRouutinggProoblemmwitthHeeteroogeneeousFleeet[J]].FuutureeGe
1
8
nnerattionCompputerrSysstemss,19998,,N0..5-6,,p2855-2922.
[9]姜姜大立,[J]].系统统工程理论论与实践,11999..1.
[10]李大卫,王王莉,[JJ].系系统工程理理论与实践践,19999年第88期.
[11]李军,[[M].北京:中中国物资出出版社,22001..
[12]李军,谢谢秉磊,[J]].系统统工程理论论方法应用用,20000,.
[13]谢秉磊,李李军,[[J].中国学术术期刊,11999,,No..8,p11068——10699.
[14]谢秉磊,李李军,[[J].系统工程程学报,22000,..
[15]张涛,王王梦光,[[J].系统工程程学报,22000,,.
[16]陈国良,王王煦法,庄庄镇泉,[M]..北京::人民邮电电出版社,11996..
[17]李茂军,[JJ].自自动化学报报,..
[18](美美).演化程程序——遗传算算法和数据据编码的结结合[M]].北京::科学出版版社,20000.
[19]日通综合合研究所(日日).物物流手册[[M].北京:中国物资资出版社,,19886.