一种快递最佳路径算法设计研究

题 目 一种快递最佳路径算法设计研究

学生姓名 卢斌 学号 1109014022

所在学院 数学与计算机 科学学院

专业班级 数学教育1101班 指导教师 和斌涛

完成地点 陕西理工学院

2015年 06 月 10 日

陕西理工学院毕业论文

一种快递最佳路径算法设计研究

(陕西理工学院,数学与计算机科学学院学院,数教11级,陕西 汉中723000)

指导教师: 和斌涛

[摘要] 研究快递配送路径优化问题,是现代快递配送服务的关键环节之一,需要有一个快捷而

有效的求解算法,来提高快递的服务质量.本文通过构建快递配送路径优化的数学模型,运用蚁群算法来解决快递配送路径优化的问题,同时,通过改进客户点的选择策略,来提高算法的搜索效率和全局寻优能力.结果表示,蚁群算法能够在最短的时间内找到快递配送的最优化解,是解决快递配送路径优化的有效算法.

卢斌

[关键词] 快递配送;路径优化;蚁群算法;选择策略;信息素

1 引 言 1.1 背景介绍

快递配送是企业出产进程中的关键之一,也是现代快递体系研究范畴中的重要内容之一.快递配送是由客户订货的要求和时间规定,在快递配送中心按时完成分货、配货,并将装配完成的货物用汽车往返运送的方式及时投递客户的小范围、近距离、小批量、多品种、为多客户服务的运输.在快递配送的办理上,需要有可行计划来寻觅一组使得费用最小的最佳路径,能将货物配送到每一位客户的手中,即所谓快递路径最优化题目.快递配送路径的公道与否,对降低配送本钱、加快配送速率、进步服务质量及增添整体经济效益影响庞大.因此,必需采纳科学合理的方法来确定快递配送路线,这是配送过程中一项非常重要的事情之一.

快递配送路径最优化问题是一类组合优化问题,其计算的研究过程十分复杂.随着市场经济的繁荣,快递配送业已取得了快速发展,越来越多的当代企业感受到快递配送在其企业出产与销售中的重要性.企业规模逐步扩展,营业越来越多,配送网点的数目自然而然的增多了起来,因此,快递配送中的路径选择的好与否对物流的配送效率、服务质量及配送费用都会

[1]

有直接影响.

1.2 最佳路径问题的研究方向和特点

快递配送中的配送路径选择问题是一个典型的NP困难问题,其与铁路运输、水道航路、公交调剂选择十分相似,对于快递配送路径问题,很多学者举行了深入的研究,讨论出很多种求解方式,如系统仿真法、精确解法和人机互动法等.这些方法是提供了解决问题的思维想法,但事实上它们都各自存在不足.在系统仿真法中,现实中的快递景象逻辑化不能为仿真程序的可行性获得有效的保证;在精确解法中,会因为题目量大而求解耗时,效果低;在人机互动法中,办理者必须具备快递配送专业知识,因此主观性比较强,针对配送路径选择具有随意性.是以这些不足限定了这些方法的利用.启发式算法是指按照办理题目过去经验采用归纳推理和分析,从而来解决问题,目标是在可接受的价格下得出待解决问题的满意解,既节省了求解时间,又满足了解决问题的现实要求.因此,由于启发式算法的实现简单、效力高等优点引起了优化钻研范畴的高度重视,并在近年来取得了飞速的成长.

第1页 共8页

陕西理工学院毕业论文

蚁群算法是一种新的种群启发式算法,其通过模拟自然界蚁群从巢穴到食物源的最短路径的寻找食物的过程来求解一些难题,它具有正反馈、并行计算、较强的鲁棒性,是基于总体优化的方法,在很多领域有着广泛的应用.蚁群算法原型本身就是一个寻找最短路径的模型,因此,它在路径优化方面都占据上风,应用蚁群算法对快递配送路径最优化进行求解,实验结

[2]

果表明通过蚁群算法可以快速的找到一条最优的快递配送路径.

2 蚁群算法概念

2.1蚁群算法的提出

蚁群算法(Ant Colony Algorithm,ACA),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法.它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为.蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.

蚁群算法之所以能引起相关领域研究者的关注,是因为这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来.其中,寻优的快速性是通过正反馈式的信息传递和积累来保证的.而算法的早熟性收敛又可以通过其分布式计算特征加以避免,同时,具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答.这种优越的问题分布式求解模式经过相关领域研究者的关注和努力,已经在最初的算法模型基础上得到了很大的改进和拓展.研究蚁群算法的改进方法以及其发展和应用的趋势,

[3]

为蚁群算法在更多领域有更多的应用价值来说是十分必要的. 2.2 蚁群算法原理 2.2.1蚁群算法的概念原型

各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物.当一只找到食物以后,它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失,信息素浓度的大小表征路径的远近)来实现的,吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物.有些蚂蚁并没有像其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果另开辟的道路比原来的其他道路更短,那么,渐渐地,更多的蚂蚁被吸引到这条较短的路上来.最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复着. 2.2.2 蚁群算法的原理

蚁群算法是一种“自然”算法,它是由于受自然界生物的行为,对自然界蚂蚁的寻求方式进行模拟而得出的一种算法.蚂蚁在运动过程中,能够在它所经过的路径上留下一种信息素（pheromone）的物质进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并且以此来指引自己的运动方向,因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大.在时间规定范围内,短路径会被很多的后来蚂蚁选择,因此,积累的信息量越来越多,在后面过程中被其他的蚂蚁选择的希望就越大.这个过程会一直延续到全部的蚂蚁都沿着最短的那条路径走为止.最终整个蚁

[4]

群会找出最优路径.如下图就显示了这样一个模拟的过程.

第2页 共8页

陕西理工学院毕业论文

（a） （b） （c）

在（图a）中,有一群蚂蚁,假如A是蚁巢,E是食物源（反之亦然）.这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶.假如在A和E之间突然出现了一个障碍物（图b）,那么,在B点（或D点）的蚂蚁将要做出决策,到底是向左行驶还是向右行驶？由于一开始路上没有前面蚂蚁留下的信息素（pheromone）,蚂蚁朝着两个方向行进的概率是相等的.但是当有蚂蚁走过时,它将会在它行进的路上释放出信息素,并且这种信息素会议一定的速率散发掉.信息素是蚂蚁之间交流的工具之一.它后面的蚂蚁通过路上信息素的浓度,做出决策,往左还是往右.很明显,沿着短边的的路径上信息素将会越来越浓（图c）,从而吸引了越来越多的蚂蚁沿着这条路径行驶. 2.3蚁群算法的特点 2.3.1 人工蚁群的特点

基于以上蚁群寻找食物时的最优路径选择问题,可以构造人工蚁群,来解决最优化问题,如TSP问题.

人工蚁群中把具有简单功能的工作单元看作蚂蚁.它们的相似之处在于都是优先选择信息素浓度大的路径.较短路径的信息素浓度高,所以能够最终被所有蚂蚁选择,也是最终的优化结果.它们的区别在于人工蚁群有一定的记忆能力,能够记忆已经访问过的节点.同时,人工蚁群再选择一条路径的时候是按一定算法规律有意识地寻找最优路径,并不是盲目的.例如在TSP问题中,可以预先知道当前城市到下一个目的地的距离.以TSP问题为例：

(1)人工蚂蚁具有一定的记忆能力,为保证不会重复走相同的路径,它可以记住走过的路径,然而现实的蚂蚁没有记忆能力.

(2)人工蚂蚁不仅依据信息素确定了要走的路径,而且引入了与问题相关的启发信息,比如相邻边的长度,这个构造的启发信息对下一步的搜索具有一定作用.

(3)人工蚂蚁是在一个离散的时间环境下,而现实中的蚂蚁是在一个连续的环境状态下.

[2]

因此,人工蚂蚁会根据问题的需要相对灵活加入相应的规则,来更加有效的解决实际问题. 2.3.2 蚁群算法的框架：

第3页 共8页

陕西理工学院毕业论文

根据蚁群算法的原理得到,蚁群算法的框架主要由三个部分组成： （1）蚁群的活动; （2）信息素的挥发; （3）信息素的增强.

3 快递配送路径优化问题的数学模型

3.1 问题描述

快递配送路径优化一般可以描述为：设某快递公司有N个货物需求点和M个配送中心,处于在不同地理位置的客户,在满足必要的约束前提下,从M个中心出发,合理地选择行车路线一次访问N个客户,最后回到配送中心,同时要使配送费用最小. 3.2 快递配送中路径优化问题的假设及条件

本文的路径优化问题是针对单车快递路径优化模型进行假设,即从一个快递中心出发,在每一个客户的地理位置和订单货物已知的情况下,按照配送车辆的里程限制,合理安排行车线路,使车辆有序地经过它们,在满足必要的约束前提下,如交货时间、发送量、行驶里程限定、车辆容量限定、时间限制等,到达一定的目标使总费用最小,如路程最短、费用最少、时间最少,使得目标函数达到最优（本文的最优要求为最短路径）.

为了建立数学模型,做了以下假设：

（1）快递中心和要访问的所有客户的位置已知且固定;

（2）客户所分布的位置在配送区域,每个需求点只由一辆车服务一次,每辆车只能服务

一条路线;

（3）客户与快递中心及客户需求点之间距离已知;

（4）车辆一律由配送中心出发,任务完成后回到快递中心; （5）快递车辆配送过程中无装货,只有卸货的情况;

（6）最终的目标是寻找一条快递配送路径使得配送费用最小. 3.3 基于TSP问题的蚁群算法模型

在算法的起初,有m个快递员和n个客户点 ,m个快递员的第一个元素设置为它当前所在的客户点.此时各路径上的信息素量是相等的,设τij(0) = C （C 为一个比较小的常数）,下面,对于每个快递员k,路径记忆向量按照访问顺序记录了所有k到过的客户点的序号.设快递员k当前所在位置为i,则其选择客户j作为下一个访问对象的概率为：

???(t)?????(t)????ij???ij??, if j?Jk(i) pk(t)?? (3. 1) ????is(t)????is?ij?s?Jk(i)??0, otherwise[6]

其中,Jk(i)= {1,2,??,n}- tabuk 表示快递员 k 接下来访问的客户.表tabuk记录了

快递员k 访问的客户.当所有 n 个快递员都加入到tabuk中时,快递员k便完成了一次配送,此时快递员k 所走过的路径便是 TSP 问题的一个可行解.(3. 1)式中的ηij 是一个启发式因子,表示快递员从客户i 访问客户j 的期望程度.在 AS 算法中,ηij 通常取客户i 与客户j 之间距离的倒数.α和β分别表示信息素和启发式因子的相对重要程度.当所有快递员

第4页 共8页