陕西理工学院毕业论文
完成一次配送后,各路径上的信息素根据（3. 2）式更新. ?ij?t?n??(1??)??ij(t)???ij (3. 2)
???k?1mkij ??ij? (3. 3)
其中m是快递员人数;ρ(0 < ρ <1)表示信息素挥发的快慢;△τij表示t时刻所有快
k
递员在（i,j） 上信息素的增量.△τij表示蚂蚁k在（i,j） 上的信息素量.如果快递员k
kk
没有经过（i,j）,则△τij的值为零.△τij表示为：
?Q当第ｋ个快递员经过ｉｊ时?k ??ij＝?Lk (3. 4)
?0当不经过时?其中,Q 为正常数,Lk 表示第k个快递员在本次配送中所走过路径的长度.
k定义?ij?1/dij.快递员k（k＝１,２,?,m）在运动过程中,pij表示在t时刻快递员k由位置i转移到位置j的概率：
????ij?ij?t?????kpij＝???is?is?t?s?allowdk???0j?allowedk (3. 5)
其他用蚁群算法解决TSP问题是一个递推过程,当t?0时,设定每条路径上的信息量初值
?ij(0)?C,每位快递员根据公式(3. 5)决定的概率从客户i到客户j.?ij(t)表示曾经有多少快递员经过路径(i,j);?ij说明较近的客户点有更大的可能性被选中.?,?用来控制两者对快递员选择的影响力程度.经过一次访问后,根据公式(3. 3),(3. 4),(3. 5)计算更新每条路径的信息量?ij(t).将所有的tabu,2,?,m)复原,最后求出本次访问的最短路径k(k?1minLk.这个过程不断重复,直到所有的快递员都选择同样的路径,或者循环次数达到预先设定的最高次数NCmax.
解决快递配送中n个客户点的TSP问题算法设计如下：
⑴初始化:设定t?0,循环计数器NC?0,对每条路径设定初始信息量?ij(0)?C,??ij?0将m个快递员选择n个客户点（为了使问题简化,设定m?n.）
⑵设定tabu集合的索引s?1,对k从１到m,把第k个快递员放在起始位置,对应的设定集合tabuk?s?.
⑶重复下面的步骤,直到集合tabu满为止（这一步将重复n?1次）: 设定s?s?1;
对k从1到m,根据公式(3. 5)确定的概率,选择下一步移动的目标客户j｛在时间t时,第k个快递员所在的位置是i?tabuk(s?1)};
将第k个快递员访问客户j; 把j加入到集合tabuk(s)中. ⑷对k从１到m：
将第k个快递员从tabuk(n)移动到tabuk(1);
计算第ｋ个快递员所走过的路程和Lk,并更新最小路径minLk;
k对每条路径(i,j)： ??ij???ij???ij (3. 6)
⑸对每条路径(i,j)根据?ij(t?n)????ij(t)???ij计算?ij?t?n?;
第5页 共8页
陕西理工学院毕业论文
设定t?t?n;
设定NC?NC?1;
对每条路径(i,j),设定??ij?0. ⑹如果NC?NCmax, 则清空所有的集合tabu, 转到第二步;
否则,得出最短的路径.
在这儿我们用的是ant?cycle算法,这种算法,每当结束一次访问后,根据公式(3.4)计k算??ij.
4 实验案例
以快递公司的快递配送路线为例,用蚁群算法进行计算,来验证蚁群算法的可行性. 公司有20台配送车辆,货车油耗为25L∕百公里,货车行驶速度为50km∕h,需要向9个客户送货,货车的最大承重为5t.快递中心的坐标为（450,350）,9个周边配送点的坐标及货物需求量见表1.
表4-1 实例数据 客户编号 1 2 3 4 5 6 7 8 9 横坐标x∕km 100 250 300 550 450 720 400 600 200 纵坐标y∕km 200 560 400 300 500 450 100 250 270 货物需求量q∕t 2 3 1 3 1 2 4 2 3
此快递公司在使用蚁群算法模型优化配送路径,路径见图4.1.
图4.1 配送路径
配送路径为线路一：（450,350）→（450,500）→（250,560）→（300,400）→（200,270）
第6页 共8页
陕西理工学院毕业论文
→（100,200）→（450,350）,即：0→5→2→3→9→1→0;线路二：（450,350）→（400,100）→（600,250）→（720,450）→（550,300）→（450,350）,即：0→7→8→6→4→0.
在此种配送方案下,配送路径的总长度T为13.42km.其中线路一的配送长度为T1=7.34km,线路二的配送长度为T2=6.08km.
因此,应用蚁群算法来求解快递配送问题,可以快速而有效的求得快递配送的最佳路径.
5 结束语
本文利用蚁群算法对快递公司的配送优化问题进行求解,详细分析计算结果,数据表明优化后的配送时间和路线长度都缩短,节约配送费用;证明此算法在一定的约束条件下,找到了一条满足约束条件的优化路径,避免了实际工作中司机最优路径盲目性,可以为快递公司配送环节提供参考.
通过快递配送路径优化问题的特点,提出了一种基于蚁群算法的优化路径算法.通过改进客户点选择策略,增强蚁群算法的正反馈作用,从而提高了算法的收敛速度和全局搜索能力.实验结果表明,蚁群算法可以快速有效地求得优化快递配送路径的最优解或近似最优解.本文的研究工作,对蚁群算法及快递配送路径优化问题的研究有一定参考价值.
参考文献
[1] 许星.物流配送路径优化问题的研究[D].浙江大学, 2006年. [2] 李士勇.蚁群算法及其应用[M].哈尔滨工业大学出版社,2004. [3] 左洪浩.蚁群优化算法及其应用研究[D].中国科学技术大学, 2006.
[4] 马军建,董增川,王春霞. 蚁群算法研究进展[J]. 河海大学学报：自然科学版, 2005. [5] 曾云.基于改进蚁群算法的物流配送路径优化研究[D]. 北京物资学院,2012. [6] 谢宏,蚁群算法解决TSP问题的研究[J]. 农业网络信息,2007.
[7] 李军,郭耀煌.物流配送车辆优化调度理论与方法[M]. 北京：中国物资出版社, 2001. [8] 郭平,鄢文晋. 基于TSP问题的蚁群算法综述[J]. 计算机科学 ,2007.
[9] DORIGO M,GAMBARDELLA L M.Ant Colonies for the Traveling Salesman Problem[J].BioSystems.1997. [10] DORIGO M,BIRATTARI M,STUTZLE T.Ant Conlony Optimiization[J].Computational Intelligence Magazine,2006,1(4):28-39.
第7页 共8页
陕西理工学院毕业论文
A Research of Algorithm
Design About Optimal Path of Express
Lu Bin
(Grade11,Class1, Major in mathematics education,Institute of mathematics and computer
sciences, Shaanxi University of Technology,Hanzhong 723000,Shaanxi)
Tutor:He Bintao
Abstract: Researching a problem of path optimization of express delivery , is one of the key aspects of
modern express distribution services, which needs a quick and effective solution to improve the quality of logistics services. The article uses the ant colony algorithm to solve the problem of path optimization of delivery through constructing express mathematical model for this problem,and improves update approaches of the pheromone and strategic decision for customers in order to improve the search speed and overall capacity of searching for the optimal path. Results show that the ant colony algorithm can find the optimal solution about express distribution in the shortest time,which is the express delivery path.
Key words: Express; distribution Path; OptimizationAntcolony; optimization; algorithm,Selection; strategiesPheromone.
第8页 共8页
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库一种快递最佳路径算法设计研究(2)在线全文阅读。
相关推荐：