题目一种快递最佳路径算法设计研究学生姓名卢斌学号 1109014022 所在学院数学与计算机科学学院专业班级数学教育1101班指导教师和斌涛完成地点陕西理工学院2015年06月 10日一种快递最佳路径算法设计研究卢斌(陕西理工学院,数学与计算机科学学院学院,数教11级,陕西汉中723000)指导教师: 和斌涛[摘要] 研究快递配送路径优化问题,是现代快递配送服务的关键环节之一,需要有一个快捷而有效的求解算法,来提高快递的服务质量.本文通过构建快递配送路径优化的数学模型,运用蚁群算法来解决快递配送路径优化的问题,同时,通过改进客户点的选择策略,来提高算法的搜索效率和全局寻优能力.结果表示,蚁群算法能够在最短的时间内找到快递配送的最优化解,是解决快递配送路径优化的有效算法.[关键词] 快递配送;路径优化;蚁群算法;选择策略;信息素1引言1.1 背景介绍快递配送是企业出产进程中的关键之一,也是现代快递体系研究范畴中的重要内容之一.快递配送是由客户订货的要求和时间规定,在快递配送中心按时完成分货、配货,并将装配完成的货物用汽车往返运送的方式及时投递客户的小范围、近距离、小批量、多品种、为多客户服务的运输.在快递配送的办理上,需要有可行计划来寻觅一组使得费用最小的最佳路径,能将货物配送到每一位客户的手中,即所谓快递路径最优化题目.快递配送路径的公道与否,对降低配送本钱、加快配送速率、进步服务质量及增添整体经济效益影响庞大.因此,必需采纳科学合理的方法来确定快递配送路线,这是配送过程中一项非常重要的事情之一.快递配送路径最优化问题是一类组合优化问题,其计算的研究过程十分复杂.随着市场经济的繁荣,快递配送业已取得了快速发展,越来越多的当代企业感受到快递配送在其企业出产与销售中的重要性.企业规模逐步扩展,营业越来越多,配送网点的数目自然而然的增多了起来,因此,快递配送中的路径选择的好与否对物流的配送效率、服务质量及配送费用都会有直接影响[1].1.2 最佳路径问题的研究方向和特点快递配送中的配送路径选择问题是一个典型的困难问题,其与铁路运输、水道航路、公交调剂选择十分相似,对于快递配送路径问题,很多学者举行了深入的研究,讨论出很多种求解方式,如系统仿真法、精确解法和人机互动法等.这些方法是提供了解决问题的思维想法,但事实上它们都各自存在不足.在系统仿真法中,现实中的快递景象逻辑化不能为仿真程序的可行性获得有效的保证;在精确解法中,会因为题目量大而求解耗时,效果低;在人机互动法中,办理者必须具备快递配送专业知识,因此主观性比较强,针对配送路径选择具有随意性.是以这些不足限定了这些方法的利用.启发式算法是指按照办理题目过去经验采用归纳推理和分析,从而来解决问题,目标是在可接受的价格下得出待解决问题的满意解,既节省了求解时间,又满足了解决问题的现实要求.因此,由于启发式算法的实现简单、效力高等优点引起了优化钻研范畴的高度重视,并在近年来取得了飞速的成长.蚁群算法是一种新的种群启发式算法,其通过模拟自然界蚁群从巢穴到食物源的最短路径的寻找食物的过程来求解一些难题,它具有正反馈、并行计算、较强的鲁棒性,是基于总体优化的方法,在很多领域有着广泛的应用.蚁群算法原型本身就是一个寻找最短路径的模型,因此,它在路径优化方面都占据上风,应用蚁群算法对快递配送路径最优化进行求解,实验结果表明通过蚁群算法可以快速的找到一条最优的快递配送路径[2].2 蚁群算法概念2.1蚁群算法的提出蚁群算法(),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法.它由于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为.蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.蚁群算法之所以能引起相关领域研究者的关注,是因为这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来.其中,寻优的快速性是通过正反馈式的信息传递和积累来保证的.而算法的早熟性收敛又可以通过其分布式计算特征加以避免,同时,具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答.这种优越的问题分布式求解模式经过相关领域研究者的关注和努力,已经在最初的算法模型基础上得到了很大的改进和拓展.研究蚁群算法的改进方法以及其发展和应用的趋势,为蚁群算法在更多领域有更多的应用价值来说是十分必要的[3].2.2 蚁群算法原理2.2.1蚁群算法的概念原型各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物.当一只找到食物以后,它会向环境释放一种挥发性分泌物(称为信息素,该物质随着时间的推移会逐渐挥发消失,信息素浓度的大小表征路径的远近)来实现的,吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物.有些蚂蚁并没有像其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果另开辟的道路比原来的其他道路更短,那么,渐渐地,更多的蚂蚁被吸引到这条较短的路上来.最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复着.2.2.2 蚁群算法的原理蚁群算法是一种“自然”算法,它是由于受自然界生物的行为,对自然界蚂蚁的寻求方式进行模拟而得出的一种算法.蚂蚁在运动过程中,能够在它所经过的路径上留下一种信息素（）的物质进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并且以此来指引自己的运动方向,因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大.在时间规定范围内,短路径会被很多的后来蚂蚁选择,因此,积累的信息量越来越多,在后面过程中被其他的蚂蚁选择的希望就越大.这个过程会一直延续到全部的蚂蚁都沿着最短的那条路径走为止.最终整个蚁群会找出最优路径.如下图就显示了这样一个模拟的过程[4].（a）（b）（c）在（图a）中,有一群蚂蚁,假如A是蚁巢是食物源（反之亦然）.这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶.假如在A和E之间突然出现了一个障碍物（图b）,那么,在B 点（或D点）的蚂蚁将要做出决策,到底是向左行驶还是向右行驶？由于一开始路上没有前面蚂蚁留下的信息素（）,蚂蚁朝着两个方向行进的概率是相等的.但是当有蚂蚁走过时,它将会在它行进的路上释放出信息素,并且这种信息素会议一定的速率散发掉.信息素是蚂蚁之间交流的工具之一.它后面的蚂蚁通过路上信息素的浓度,做出决策,往左还是往右.很明显,沿着短边的的路径上信息素将会越来越浓（图c）,从而吸引了越来越多的蚂蚁沿着这条路径行驶.2.3蚁群算法的特点2.3.1 人工蚁群的特点基于以上蚁群寻找食物时的最优路径选择问题,可以构造人工蚁群,来解决最优化问题,如问题.人工蚁群中把具有简单功能的工作单元看作蚂蚁.它们的相似之处在于都是优先选择信息素浓度大的路径.较短路径的信息素浓度高,所以能够最终被所有蚂蚁选择,也是最终的优化结果.它们的区别在于人工蚁群有一定的记忆能力,能够记忆已经访问过的节点.同时,人工蚁群再选择一条路径的时候是按一定算法规律有意识地寻找最优路径,并不是盲目的.例如在问题中,可以预先知道当前城市到下一个目的地的距离.以问题为例：(1)人工蚂蚁具有一定的记忆能力,为保证不会重复走相同的路径,它可以记住走过的路径,然而现实的蚂蚁没有记忆能力.(2)人工蚂蚁不仅依据信息素确定了要走的路径,而且引入了与问题相关的启发信息,比如相邻边的长度,这个构造的启发信息对下一步的搜索具有一定作用.(3)人工蚂蚁是在一个离散的时间环境下,而现实中的蚂蚁是在一个连续的环境状态下.因此,人工蚂蚁会根据问题的需要相对灵活加入相应的规则,来更加有效的解决实际问题[2].2.3.2 蚁群算法的框架：根据蚁群算法的原理得到,蚁群算法的框架主要由三个部分组成：（1）蚁群的活动;（2）信息素的挥发;（3）信息素的增强.3 快递配送路径优化问题的数学模型3.1 问题描述快递配送路径优化一般可以描述为：设某快递公司有N 个货物需求点和M 个配送中心,处于在不同地理位置的客户,在满足必要的约束前提下,从M 个中心出发,合理地选择行车路线一次访问N 个客户,最后回到配送中心,同时要使配送费用最小.3.2 快递配送中路径优化问题的假设及条件本文的路径优化问题是针对单车快递路径优化模型进行假设,即从一个快递中心出发,在每一个客户的地理位置和订单货物已知的情况下,按照配送车辆的里程限制,合理安排行车线路,使车辆有序地经过它们,在满足必要的约束前提下,如交货时间、发送量、行驶里程限定、车辆容量限定、时间限制等,到达一定的目标使总费用最小,如路程最短、费用最少、时间最少,使得目标函数达到最优（本文的最优要求为最短路径）.为了建立数学模型,做了以下假设：（1）快递中心和要访问的所有客户的位置已知且固定;（2）客户所分布的位置在配送区域,每个需求点只由一辆车服务一次,每辆车只能服务一条路线;（3）客户与快递中心及客户需求点之间距离已知;（4）车辆一律由配送中心出发,任务完成后回到快递中心;（5）快递车辆配送过程中无装货,只有卸货的情况;（6）最终的目标是寻找一条快递配送路径使得配送费用最小.3.3 基于问题的蚁群算法模型[6]在算法的起初,有m 个快递员和n 个客户点 个快递员的第一个元素设置为它当前所在的客户点.此时各路径上的信息素量是相等的,设τ(0) = C （C 为一个比较小的常数）,下面,对于每个快递员k,路径记忆向量按照访问顺序记录了所有k 到过的客户点的序号.设快递员k 当前所在位置为i,则其选择客户j 作为下一个访问对象的概率为：[][]k ()()(), if j J ()()() 0, otherwise k ijij k is is ij s J i t t i t p t αβαβτητη∈⎧⎡⎤⎡⎤⋅⎣⎦⎣⎦⎪∈⎪⋅=⎨⎪⎪⎩∑ (3. 1) 其中(i)= {1,2,……}- 表示快递员 k 接下来访问的客户.表记录了快递员k 访问的客户.当所有 n 个快递员都加入到中时,快递员k 便完成了一次配送,此时快递员k 所走过的路径便是 问题的一个可行解.(3. 1)式中的η 是一个启发式因子,表示快递员从客户i 访问客户j 的期望程度.在 算法中,η 通常取客户i 与客户j 之间距离的倒数.α和β分别表示信息素和启发式因子的相对重要程度.当所有快递员完成一次配送后,各路径上的信息素根据（3. 2）式更新.()ij ij ij t n t ττρτ∆+*-=+)()1( (3. 2) ∑=∆=∆m k k ij ij 1ττ (3. 3)其中m 是快递员人数;ρ(0 < ρ <1)表示信息素挥发的快慢;△τ表示t 时刻所有快递员在（） 上信息素的增量.△τ表示蚂蚁k 在（） 上的信息素量.如果快递员k 没有经过（）,则△τ的值为零.△τ表示为：k ij τ∆＝⎪⎩⎪⎨⎧当不经过时ｊ时当第ｋ个快递员经过ｉ0L k Q (3. 4)其中 为正常数 表示第k 个快递员在本次配送中所走过路径的长度.定义ij ij d /1=η.快递员k （k ＝１,２,…,m ）在运动过程中,k ij p 表示在t 时刻快递员k由位置i 转移到位置j 的概率：k ij p ＝()()⎪⎪⎩⎪⎪⎨⎧∈∑∈其他0k allowd s is is ij ij allowed j t t k βαβαητητ (3. 5)用蚁群算法解决问题是一个递推过程,当0=t 时,设定每条路径上的信息量初值C ij =)0(τ,每位快递员根据公式(3. 5)决定的概率从客户i 到客户j .)(t ij τ表示曾经有多少快递员经过路径),(j i ;ij η说明较近的客户点有更大的可能性被选中.βα,用来控制两者对快递员选择的影响力程度.经过一次访问后,根据公式(3. 3),(3. 4),(3. 5)计算更新每条路径的信息量)(t ij τ.将所有的),,2,1(m k tabu k Λ=复原,最后求出本次访问的最短路径k L min .这个过程不断重复,直到所有的快递员都选择同样的路径,或者循环次数达到预先设定的最高次数max NC .解决快递配送中n 个客户点的问题算法设计如下：⑴初始化:设定0=t ,循环计数器0=NC ,对每条路径设定初始信息量C ij =)0(τ,0=∆ij τ将m 个快递员选择n 个客户点（为了使问题简化,设定n m =.）⑵设定tabu 集合的索引1=s ,对k 从１到m ,把第k 个快递员放在起始位置,对应的设定集合()k tabu s .⑶重复下面的步骤,直到集合tabu 满为止（这一步将重复1-n 次）:设定1+=s s ;对k 从1到m ,根据公式(3. 5)确定的概率,选择下一步移动的目标客户j ｛在时间t 时,第k 个快递员所在的位置是)1(-=s tabu i k };将第k 个快递员访问客户j ;把j 加入到集合)(s tabu k 中.⑷对k 从１到m ：将第k 个快递员从)(n tabu k 移动到)1(k tabu ;计算第ｋ个快递员所走过的路程和k L ,并更新最小路径k L min ;对每条路径),(j i ： k ij ij ij τττ∆+∆=∆ (3. 6)⑸对每条路径),(j i 根据ij ij ij t n t ττρτ∆+⋅=+)()(计算()n t ij +τ;设定n t t +=;设定1+=NC NC ;对每条路径),(j i ,设定0=∆ij τ.⑹如果max NC NC <,则清空所有的集合tabu ,转到第二步;否则,得出最短的路径.在这儿我们用的是cycle ant -算法,这种算法,每当结束一次访问后,根据公式(3.4)计算k ij τ∆.4 实验案例以快递公司的快递配送路线为例,用蚁群算法进行计算,来验证蚁群算法的可行性. 公司有20台配送车辆,货车油耗为25L ∕百公里,货车行驶速度为50∕h,需要向9个客户送货,货车的最大承重为5t.快递中心的坐标为（450,350）,9个周边配送点的坐标及货物需求量见表1.客户编号横坐标x ∕ 纵坐标y ∕ 货物需求量q ∕t 123456789 100 250 300 550 450 720 400 600 200 200 560 400 300 500 450 100 250 270 2 3 1 3 1 2 4 2 3此快递公司在使用蚁群算法模型优化配送路径,路径见图4.1.图4.1 配送路径配送路径为线路一：（450,350）→（450,500）→（250,560）→（300,400）→（200,270）→（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=7.34,线在此种配送方案下,配送路径的总长度T为13.42.其中线路一的配送长度为1T=6.08.路二的配送长度为2因此,应用蚁群算法来求解快递配送问题,可以快速而有效的求得快递配送的最佳路径.5 结束语本文利用蚁群算法对快递公司的配送优化问题进行求解,详细分析计算结果,数据表明优化后的配送时间和路线长度都缩短,节约配送费用;证明此算法在一定的约束条件下,找到了一条满足约束条件的优化路径,避免了实际工作中司机最优路径盲目性,可以为快递公司配送环节提供参考.通过快递配送路径优化问题的特点,提出了一种基于蚁群算法的优化路径算法.通过改进客户点选择策略,增强蚁群算法的正反馈作用,从而提高了算法的收敛速度和全局搜索能力.实验结果表明,蚁群算法可以快速有效地求得优化快递配送路径的最优解或近似最优解.本文的研究工作,对蚁群算法及快递配送路径优化问题的研究有一定参考价值.参考文献[1] 许星.物流配送路径优化问题的研究[D].浙江大学, 2006年.[2] 李士勇.蚁群算法及其应用[M].哈尔滨工业大学出版社,2004.[3] 左洪浩.蚁群优化算法及其应用研究[D].中国科学技术大学, 2006.[4] 马军建,董增川,王春霞. 蚁群算法研究进展[J]. 河海大学学报：自然科学版, 2005.[5] 曾云.基于改进蚁群算法的物流配送路径优化研究[D]. 北京物资学院,2012.[6] 谢宏,蚁群算法解决问题的研究[J]. 农业网络信息,2007.[7] 李军,郭耀煌.物流配送车辆优化调度理论与方法[M]. 北京：中国物资出版社, 2001.[8] 郭平,鄢文晋. 基于问题的蚁群算法综述[J]. 计算机科学 ,2007.[9] L [J].1997.[10] [J] ,2006,1(4):28-39.A(111, , 723000): a , , a . . .: ; ; ; ; ; .。