（载运工具运用工程专业论文）基于改进蚁群算法的物流配送车辆路径优化方法的研究.pdf

摘要 物流配送是物流活动中直接与消费者相联系的环节。在物流的各项成本中，配送成 本占了相当高的比例。配送中车辆路径的合理与否对物流配送服务水平、成本和效益影 响很大。采用科学、合理的方法来进行车辆路径的优化，是物流配送领域的重要研究课 题。其中尤其是带时间窗的物流配送车辆路径优化问题( v e h i c l er o u t i n gp r o b l e mw i t h t i m ew i n d o w s ，v r p t w ) 更是当前研究的重点。 带时间窗的车辆路径问题计算复杂，属于n p h a r d 问题。本文研究了带时间窗的车 辆路径问题模型的构建，引入了蚁群算法( a n ts y s t e m ，a s ) ，将其进行了改进，并成 功运用于求解带时间窗的车辆路径问题。 蚁群算法存在搜索时间比较长，容易出现停滞现象且存在陷入局部极小可能性的缺 陷。本文针对蚁群算法的不足，分别通过对初始解的启发、信息素更新策略的选择和状 态转移概率的改进，对蚁群算法进行了改进：并采用s o l o m o n 问题中r 1 0 1 作为实例数 据基础，采用面向对象的c + + 语言编写了计算程序，对改进蚁群算法进行了计算验证， 证实了该算法可行性和有效性；同时对部分s o l o m o n 数据进行了多次验证，结果表明改 进蚁群算法与其它启发式算法相比具有优越性；最后对改进蚁群算法中的各项参数进行 了对比分析，探讨了所用参数的最优组合。 关键词：物流配送，蚁群算法，改进蚁群算法，v r p t w ，信息素 a b s t r a c t l o g i s t i c sd i s t r i b u t i o ni sd i r e c t l yl i n k e dt oc u s t o m e ri nl o g i s t i c sa c t i v i t i e s i nt h ec o s to f l o g i s t i c s ，d i s t r i b u t i o nc o s t sa c c o u n tf o rav e r yh i g hp e r c e n t a g e v e h i c l er o u t i n gg r e a t l y i n f l u e n c el o g i s t i c ss e r v i c e s ，c o s t sa n db e n e f i t si nd e l i v e r y i ti sa ni m p o r t a n ta r e ao fs t u d yf o r u st ou s eas c i e n t i f i ca n dr a t i o n a la p p r o a c hf o ro p t i m i z i n gt h ev e h i c l er o u t i n g s o ，v e h i c l e r o u t i n gp r o b l e mw i t ht i m ew i n d o w s i sc u r r e n tf o c u so ns t u d y v e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w si san p h a r dp r o b l e m i nt h i sp a p e r , t h e m o d e lo fv i 冲t wi sb u i l t ，t h e ni n t r o d u c e sa n di m p r o v e sa n ts y s t e m ，w h i c hi ss u c c e s s f u l l y a p p l i e df o rv r p t w a n ts y s t e mh a ss o m ed e f e c t s ，j u s ta sr e l a t i v e l yl o n gt i m ei ns e a r c h ，p r o n et os t a g n a t i o n a n dp o s s i b i l i t yo fal o c a lm i n i m u m b a s e do nt h ed e f e c t so fa si nt h i sp a p e r , f i r s t l yi t i m p r o v e s t h r o u g ht h ei n s p i r a t i o no ft h ei n i t i a ls o l u t i o n ，u p d a t e dt h ep h e r o m o n eo nt h ec h o i c eo fs t r a t e g y a n dp r o b a b i l i t yo ft h et r a n s f e r ；t h e ni tb a s e so nt h ee x a m p l e so fp r o b l e m si nt h es o l o m o n s r 10 1d a t a u s i n go b j e c t o r i e n t e dc + + l a n g u a g et op r e p a r eap r o g r a mt oi m p r o v ea st h a ti s c a l c u l a t e dv e r i f i e d ，c o n f i r m i n gt h ef e a s i b i l i t ya n de f f e c t i v e n e s so fi t ；a tt h es a m et i m e ，s o m eo f s o l o m o nd a t ai sv e r i f i e d ，c o m p a r e dw i t ho t h e rh e u r i s t i c st h er e s u l t ss h o w e dt h a tt h e i m p r o v i n g a si s s u p e r i o r i t y ；f i n a l l y ，t h ep a r a m e t e r s o ft h e i m p r o v e d a n t c o l o n ya l g o r i t h m i s c o m p a r a t i v e l ya n a l y s i s ，a n dt h e ni td i s c u s s e st h eo p t i m a lc o m b i n a t i o no nt h ep a r a m e t e r s k e yw o r d s ：d i s t r i b u t i o n ，a n ts y s t e m ，i m p r o v e da n tc o l o n ya l g o r i t h m ，v r p t w ， p h e r o m o n e 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究工 作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何 未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：酃套炙 矽2 年奎月日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借i 竭以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名：酃套霪 导师签名：f 聋* 象f 1 刎年上月髟日 口。形年厂月彩日 长安大学硕一t z 学位论文 1 1 问题的提出 第一章绪论 在经济全球化快速发展的进程中，物流作为“第三利润源”对经济活动的影响越来 越强，而它作为当前经济最重要的竞争领域，在优化国内外两个市场的资源配置中起着 尤为重要的作用。物流的现代化水平己成为反映一个国家现代化程度和综合国力的重要 标志，它对经济产生的巨大拉动作用也被喻为是经济发展的“加速器”【1 1 。 根据g b t 1 8 3 5 4 2 0 0 6 物流术语，配送指：“在经济合理区域范围内，根据客户 要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流 活动。 配送不是单纯的运输或送货，而是集货、配货、送货、装配等活动的有机组合。 配送流程如图1 1 所示，a 卜a 2 、a 3 代表物流配送公司，b l 、b 2 、b 3 代表客户。随着电 子商务的发展，出现了一些新的配送模式，使得储存不再是必然的环节。 图1 1 物流配送不葸图 物流配送在美国、日本和西欧发展较快，已经形成了比较成熟的理论体系，不论是 硬件方面还是软件方面都达到了相当高的水准。近年来，国内配送业务也得到了长足发 展，并形成了自身的特点： ( 1 ) 配送是从物流据点到用户之间的一种特殊送货方式。 ( 2 ) 配送是连接物流其他功能的环节，提高了物流系统的价值增值部分。 ( 3 ) 配送是复杂的作业体系，通常伴随着较高的作业成本，但却能快速降低库存 成本和快速反映商品市场需求变化。 ( 4 ) 配送在固定设施、搬运设备、运送工具、组织形式和通信信息等方面可集成 系统化的运作体系。 随着物流配送向集约化、一体化方向发展，常将配送的各环节综合考虑，其核一i i , 部 分是配送车辆的集货、配货和送货过程。配送系统优化，主要是配送车辆的优化调度( 包 括集货路线优化、货物装配和送货路线优化) ，以及集货、配货和送货一体化优化。车 第一章绪论 辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 是配送环节的重要组成部分。合理安排车 辆数和车辆路线是减少浪费、提高经济效益的重要手段，不但可以降低商品的物流成本， 还可以提高客户的满意度，扩大潜在市场，这对于整个物流运输速度、成本、效益有着 重要的影响。 近年来，国内外专家对v r p 问题的研究日趋深入，但多数集中于对某个单一目标 的优化研究，并假设满足某些约束条件。而在实际车辆调度过程中，经常涉及到时间或 空间各方面的约束。因此，多目标问题比单目标问题就更常见。v r p 问题有多种模型， 其中：带时间窗的车辆路径问题( v e h i c l er o u t i n gp r o b t e mw i t ht i m ew i n d o w s ，v r p t w ) 是一个具有代表性的带约束多目标问题。与典型的旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ，t s p ) 相比，增加了车容量、时间窗等约束条件，其中两个目标维度分别为车 辆数与总时间耗费( 或总路径长度当速度定义每单位时间耗费为1 时) ，其目标是在满 足空间容量限制和时间限制的条件下，求使总成本最小的最优解。 目前，v r p 问题的求解算法很多，可大致分为精确算法和启发式算法两大类。精 确算法的计算量一般随着问题规模的增大而呈指数增长，所以多用于规模较小的问题。 而对于求解大规模的n p ( n o n d e t e r m i n i s t i cp o l y n o m i a lp r o b t e n a ) 难题，则较常用模拟 退火算法( s a ) 、禁忌搜索算法( t s ) 、遗传算法( g a ) 、神经网络f n n ) 、蚂蚁算法( a s ) 等 现代启发式算法。 蚁群算法 2 , 3 1 最初由意大利科学家d o r i g o m 【4 】于19 9 1 年提出，是一种基于群体、用 于求解复杂组合优化问题的通用搜索技术。该方法首先被应用于t s 科5 1 ，并在一系列阃 题中得到应用，诸如二次分配、j o b s h o p 、图着色问题、v r p 问题、集成电路设计以及 通信网络负载等离散优化问题等。但蚁群算法搜索时间长、易于停滞( 即搜索到一定程 度后所有个体所发现的解完全一致) ，存在不能扩大对解空间继续搜索的缺陷。本文则 通过改进蚁群算法中的状态转移概率和信息素更新策略，并采用最近邻域算法确定初始 解，构建了一种用于求解v r p t w 的改进蚁群算法。 1 2 国内外研究现状 1 2 1 国内外v r p t w 问题研究现状 ( 1 ) 国内外v r p 问题研究现状 v l 冲问题是由g d a n t z i n g 和j r a m s e r 于1 9 5 9 年最早提出的【6 1 。定义为：已知有一 批客户，各客户点的位置坐标和货物需求已知，配送中心有若干可供派送的车辆，运载 2 长安大学硕十学位论文 能力给定，每辆车都必须从配送中心出发，完成若干客户点的运送任务后再回到配送中 心。其目标是：要求以最少的车辆数、最小的车辆总行程，来完成货物的派送任务。下 面从v r p 问题的现有分类和求解方法两个方面介绍v r p 研究现状。 1 ) v r p 问题可以分为以下类型： 按任务目标区分：分为纯装问题或纯卸问题( p u r ep i c ku po rp u r ed e l i v e r y ) 和装卸 混合问题( c o m b i n e dp i c ku pa n dd e l i v e r y ) 。 按车辆载货状况区分：分为满载问题( 货运量不小于车辆容量，完成一项任务需 要不只一辆车) 和非满载问题( 货运量小于车辆容量，一辆车可完成多项任务) 。 按车场( 或货场配送中心等) 数目区分：分为单车场问题和多车场问题。 按车辆类型区分：分为有单车型问题( 所有车辆类型和容量相同) 和多车型问题( 执 行任务的车辆类型和容量不完全相同) 。 按车辆对车场的所属关系区分：分为车辆开放问题( 车辆可以不返回其发车场) 和 车辆封闭问题( 车辆必须返回其发车场) 。 根据v r p 问题中各项任务是否有时间限制来区分：分为v r p 和v r p t w ，而 v r p t w 又分为带硬时间窗的车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hh a r dt i m e w i n d o w s ，v r p h t w ) 和带软时间窗的车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hs o f t t i m ew i n d o w s ，v r p s t w ) 。硬时间窗是指任务必须在给定的时间范围内完成，否则得到 的解视为不可行解。而软时间窗指如果任务不能在给定的时间范围内完成，则同时给予 一定的惩罚。 2 ) 求解算法 求解v r p 问题的方法非常多，基本上可以分为精确算法和启发式算法两大类。 精确算法 求解v r p 问题的精确算法主要有分枝定界法【7 】、割平面法【8 】、动态规划、法【9 1 、网络 流算法【1 0 1 等。由于精确算法在求解时引入了严格的数学方法( 手段) ，因而无法避开指数 爆炸问题，从而使该类算法只能有效求解小规模的v r p 问题。并且，这些算法一般都 是针对某一特定问题设计的，适用能力较差，因此在实际中其应用范围很有限。 启发式算法 启发式算法可以分为构造启发式算法、两阶段启发式算法和智能启发式算法三类。 a 构造启发式算法：在求解v r p 问题时通常是从初始解出发，以邻域搜索的方式 实现解的改进，并在较短的时间内获得一个可以接受的解。它包括：节约算法、最近邻 第一章绪论 域法、最近插入法和扫描法。 b 两阶段启发式算法：c h r i s t o f i d e s 、m i n g o z z i 和t o t h 于1 9 7 9 年提出了两阶段启发 式算法，以改进构造算法求解的不足。该算法第一阶段常用构造启发式算法来求得一个 可行解，第二阶段常用i n s e r tm e t h o d 、2 - e x c h a n g e 、2 - s w a p 、2 - o p t 、3 - o p t 等改善技术， 通过对点的调整，在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一 个可行解以代替原来的解，使目标函数得以改进，一直继续到不能再改进目标函数为止。 两阶段法在求解过程中，常常采用交互式优化技术，把人的主观能动作用加入到v r p 的 求解过程中。 c 智能化启发式算法：2 0 世纪9 0 年代以来，由于人工智能方法在解决组合优化问 题中的强大功能，不少学者开始将人工智能引入v r p 问题的求解中，并构造了大量的 基于人工智能的启发式算法( 智能化启发式算法) 。智能化启发式算法包括：禁忌搜索算 法【1 1 】、模拟退火法【1 2 】、遗传算、法【13 1 、微粒群算法【1 4 1 和蚁群算法。 此外，近年来也有学者借鉴了免疫系统的自组织学习、自适应调节的特点，提出了 用免疫算法来求解v r p 问题。该算法模拟了生物免疫系统对外来抗原的排除，把抗原 对应于待求解的问题，抗体对应于问题的一个解。在国内，方霞等人于2 0 0 3 年利用免 疫算法的全局搜索能力和收敛性，将新型的启发式算法用于解决v r p 问题，而章兢等 人于2 0 0 4 年则构造了一种免疫克隆算法来求解v r p 问题，并在算法中引入了克隆选择、 克隆删除、受体编辑、体细胞高频变异、抗体循环补充等思想。免疫克隆算法能快速收 敛于全局最优解，克服了遗传算法中易陷入局部最优解和收敛速度慢的缺点，可有效解 决v r p 问题。 v r p 是n p h a r d 问题，如果用精确算法来求解，只能解决规模较小的问题，而且求 解过程需要的运行时间较长。因此，启发式算法，尤其是智能化启发式算法，成为求解 v r p 问题的主要方法。需要说明的是，启发式算法虽然能够比较快的解决有关阎题，但 该算法的优劣往往取决于算法设计者的实际经验以及处理的样本空间的大小。在求解过 程中，应根据各类算法的适用范围，并针对配送优化问题的具体情况，寻找最适合的求 解方法，搜索最优配送路径。对于大规模客户集的配送路径优化问题或者是多约束的复 杂v r p 问题，可以考虑利用多种算法相结合的办法来解决。 ( 2 ) 国内外v r p t w 问题研究现状 v r p t w 属于v r p 的扩展，已被证明是n p h a r d 问题【15 1 。从集合论的观点看，v r p t w 是v r p 的一个真子集，它限定客户了必须在指定的时间段内接受服务。每个客户i 的时 4 长安人学硕上学位论文 间窗包含起始时间e i 和结束时间l i ，车辆必须在e i 时刻或者之前到达，服务完成时间必 须早于或等于l i 。s o l o m o n 和d e s r o s i e r s l 6 , 7 】总结了有关时间窗的v r p 的文献，讨论了有 关时间窗的一些延伸问题，比如带有时间窗的旅行商( t r a v e l i n gs a l e s m a np r o b l e mw i t h t i m ew i n d o w s ，t s p t w ) 、带时间窗的最短路径问题( t h es h o r t e s tp a t hp r o b l e mw i t ht i m e w i n d o w s s p p t w ) 和带时间窗的d i a l a r i d e 问题( t h ed i a l a r i d ep r o b l e mw i t ht i m e w i n d o w s ，d 舢冲t w ) ，同时讨论了一些应用于v r p t w 的精确算法和启发式算法。 s o l o m o n 求解归纳了一系列求解v r p 的启发式算法，比如用节约方法和扫描算法来求 解带硬时间窗的问题。他将c l a r k e 的节约法，加入时间窗条件限制来考虑，使时间窗上 界较早的需求点应该得到服务；而最近邻域法所考虑的近邻点包含两个需求点间的距 离、运输时间或服务下一个需求点所需要的等待服务时间。插入法是应用m o l e 和 j a m e s o n ( 1 9 7 6 ) 的插入方法，加入时间窗的考虑，并结合最近邻域法与节约法的观念， 依序将需求点插入路径中；最后s o l o m o n 所提出的扫描法，应用了g i l l e t t 和m i l l e r ( 1 9 7 4 ) 求解传统v r p 的启发式解法，并在第二阶段建构路径时，利用插入法来安排需求点的 路径位置，如果有需求点超过时间窗的条件限制时，则先排除此需求点，等所有需求点 均完成路径指派时，再重复扫描指派尚未被指派的顾客点，直到完成所有需求点的路径 构建。 除此之外，p o t v i n 与r o u s s e a u ( 19 9 3 ) 以平行路线建构算法取代循序算法；k o s k o i d i s ( 1 9 9 2 ) 等人修正了f i s h e r 和j a i k u m a r 的一般指派启发式解法用来求解v r p t w 问题； r u s s e l ( 1 9 9 5 ) 提出一个混合的启发式解法来求解v r p t w 问题；k o n t o r a v d i s 和b r a d ( 1 9 9 2 ) 提出g r a s p 启发式解法，利用随机数随机选取候选的顾客点插入平行构建的 路径中；刘风华和沈思渊( 1 9 9 9 ) 改进了c l a r k e 与w r i g h t 所提的节约法并结合最小成 本插入法的观念提出了以插入为主的成本节省算法。 为进一步改进v r p t w 问题的启发式解法，t h a n g i a h 和o s m a n ( 1 9 9 4 ) 延伸了o s m a n ( 1 9 9 1 ) 的路径间交换改善法，利用禁忌搜寻法与模拟退火法的混合搜寻法来求解； h o m b e r g e r 和g e h r i n g ( 1 9 9 9 ) 则提出一个进化的启发式解法来求解v r p t w 问题；刘 凤华和沈思渊( 1 9 9 9 ) 提出一个以近邻结构为基础的两阶段启发式解法，其近邻结构考 虑了路径和节点的关系，以套迭平行的方式来建构路径，且当仅剩少数顾客点尚未安排 时( 低于门槛值) ，利用特殊的程序来处理；h a y 和k e ( 2 0 0 1 ) 将s o l o m o n ( 1 9 8 7 ) 所 提出的最小成本插入法，与c h r i s t o f i d e s ( 1 9 7 8 ) 和o s m a n ( 1 9 9 3 ) 等人所提的九插入区 域搜寻改善法，运用到g a 算法里来求解v r p t w ；c o r d o n e 和c a l v o ( 2 0 0 1 ) 的启发式 第一章绪论 算法包含使用传统的k o p t 来改善解，并利用一个程序来减少所用的车辆数，同时使用 一个程序来脱离局部最优解。c o r d e a u 、l a p o r t e 和m e r c i e r ( 2 0 0 1 ) 提出一个集合的禁忌 搜索法来求解v r p t w 问题，考虑了求解的速度和弹性。 通过以上研究可以发现，在过去的几十年中，v r p 问题得到了广泛的关注，对于该 问题算法的研究也朝着效率越来越高的方向进行。但是，实际中的问题往往比较复杂， 所以需要有更接近实际的问题模型和效率更高的算法的出现，以便能有效解决现实中的 v r p 问题。 1 2 2 蚁群算法研究现状 蚁群算法( a n ts y s t e m ，a s ) 是一种新生算法，具有很强的通用性和鲁棒性。从提 出到现在，仅短短十余年的时间，但其在离散型组合优化问题的求解中，表现出强大的优 越性，所以引起人们的关注。目前蚁群算法的研究学者主要集中在比利时、意大利、德 国等国家，美国和日本在近几年也开始了对蚁群算法的研究。国内的研究始于1 9 9 8 年 末，主要在上海、北京、东北少数几个学校和研究所开展了此项工作。 蚁群算法作为一种新型的智能优化算法，与其它优化算法相比，具有正反馈、分布 式计算以及贪婪的启发式搜索等主要特点。正反馈过程使得该算法能够发现较好解；分 布式计算使得该算法易于并行实现，更快得到较好解；与启发式算法相结合，使得该算 法易于发现较好解，这些特点为更好解决复杂的组合优化问题提供了可能。由于在蚁群 算法中所有个体都要进行信息素更新，造成了信息素分配的浪费和分配畸形，所以蚁群 算法的性能并不很理想。d o r i g o m 等人在蚁群算法又提出了改进的蚁群系统( a n tc o l o n y s y s t e m ，简称a c s ) ，在蚂蚁选择下一城市时使用的转移概率中加入伪随机分配概率，以 避免出现蚁群算法中的信息素分配畸形。尽管蚁群系统与蚁群算法相比提高了算法的性 能，但它仍然使用蚁群算法中的全局信息素更新原则和局部信息素更新原则，即对所有 个体进行信息素更新，造成了信息素的大量冗余，弱化了好信息素的强度。 目前，所有蚁群算法的改进基本上都是建立在蚁群算法基础之上。国内最早开始研 究蚁群算法的主要有：吴庆洪等人【1 6 】首先提出了具有变异特征的蚁群算法，克服了原有 蚁群算法中选择次最短距离的概率很小的缺点，增加了解的全局性。随后又出现了其它 引入启发式因子或策略的改进蚁群算法，如信息素更新分段化【1 7 】、引入扰动因子【1 引、引 入杂交策略【19 1 、自适应进化算子1 2 0 】、增强型信息素更新规则【2 1 】等改进算法。这些启发 式因子或策略的引入对于蚁群算法的改进途径主要有三个：改进选择概率，增加选择概 6 长安大学硕上学位论文 率的自适应性，使选择概率能够以定概率选择次好解；改进信息素更新原则，增加信 息素的自适应性，使信息素的分配合理，即不出现信息素分配畸形，又避免信息素分配 的大量冗余；使用其它启发式策略对蚁群算法求出的解进行进一步搜索，实际上是多种 邻域搜索结构的结合，增加了解的多样性【2 2 2 3 ，2 4 1 。用这些改进算法，可以解决一些比较 复杂的大规模组合优化问题。自1 9 9 8 年，第一届蚂蚁优化国际研讨会召开以来，已经 是第三届了，大大推动了蚁群算法的发展。蚁群算法已经引起越来越多的关注，尽管还 缺乏完善的理论分析，对它的有效性也没有给出严格的数学解释，但回顾模糊控制的发 展历史，理论的不完善并不妨碍应用，有时应用是超前于理论的，并推动理论的研究， 伴随着研究的不断深人，蚁群算法必将迎来一个光明的前景。 1 2 3 蚁群算法求解v r p t w 研究现状 近年来，许多学者利用蚁群算法对各种v r p 问题进行了大量的研究，设计了各种 类型的蚁群算法【2 5 4 3 1 ，而对v r p t w 研究不是很多，具体有： 刘志硕、申金生、柴跃廷畔】为求解v r p h t w ，提出了一种基于可行解的两阶段构 造策略的自适应混合蚁群算法。实验结果表明，自适应混和蚁群算法性能优良，能够有 效地求解v r p h t w 。 陈幼林、王劲恺【4 5 】提出一种求解v r p t w 问题的改进蚁群算法，通过增加虚拟配送 中心的数量，将v r p t w 转化为t s p 进行求解，使每只蚂蚁都可以构建一条可行路径， 避免在该问题中多只蚂蚁协同合作来构造解的低效性，通过实验计算表明该方法是可行 的。 万旭、林健良、杨晓伟【4 6 1 利用最大最小策略改进信息素，该算法减d , y 蚂蚁算法 陷入局部陷阱的可能性。基于对最大最小信息素策略和信息素更新方式的改进，结合 快速产生初始解的算法，提出了一种新方法。把该方法应用于v r p t w 问题，试验结果 表明该算法是有效的。 刘哲、李建国【4 7 1 提出了一种并行多蚁群算法( p m a c s 冲t ，首先利用 q u i c k a c s 生成初始解，然后利用a c s v e i 和a c s t i m e 分别优化车辆数和行程距 离，试验表明该算法是可行的。 由上述分析可知，启发式算法成为研究并解决v r p t w 问题最有效的途径，但遗传 算法、禁忌搜索算法及模拟退火算法等启发式算法在求解v r p t w 问题时仍存在缺陷， 蚁群算法的产生及其所具有的正反馈、分布式计算以及贪婪的启发式搜索等主要特点对 7 第一章绪论 解决v r p t w 提供了一个有效的途径。实验表明，求解v r p t w 问题时，和其他算法相 比，蚁群算法更具优势。但蚁群算法自身的特性，决定了它在求解具体问题时，存在搜 索速度慢、容易陷入局部最优的缺陷。因此，为满足现阶段物流配送的实时性和科学性 的要求，迫切需要研究一种改进蚁群算法求解v r p t w 问题，特别是针对大规模、结点 数较多的v r p t w 问题。 1 3 本文主要研究内容 本文研究的重点为更好的改进蚁群算法，为求解较大规模的v r p t w 问题奠定基础。 主要研究工作如下： ( 1 ) 以配送中心的角度，通过对v r p t w 模型的复杂性分析，构建合理的v r p t w 数学模型。 ( 2 ) 通过对目前蚁群算法分析，对比各种算法的优劣，提出改进蚁群算法，以快 速、有效地求解v r p t w 问题，这是本论文的核心部分。 ( 3 ) 通过对蚁群蚁群算法的分析，利用面向对象的思想实现该算法，采用s o l o m o n 问题对算法进行测试，以验证利用改进蚁群算法求解v r p t w 问题的有效性。 论文研究内容框图如下： 问题提出i lv r p t w 模型构建与分析 基本蚁群算法研究 最近邻域法j 信息素动态： 状态转移概： 1r 改进蚁群算法 上与其他算法j 算法分析 得出结论 初始解。 计算； 比较 图1 2 论文研究内容框架图 长安大学硕士学位论文 第二章v r p t w 模型的构建与分析 v r p t w 作为组合优化问题中的一类，本章提出了该问题的基本求解思路，界定了 v r p t w 问题，并在一般v r p 数学模型的基础上，构建了本文所要解决的v r p t w 问题 的数学模型。 2 1v r p t w 问题的求解思路 2 1 1v r p t w 问题描述 v r p t w 问题具体的描述如下：一队固定车容量的车辆被安排去访问一组客户，访 问客户的时间不得晚于客户要求的时间窗的结束时间；如果到达客户处的时间早于时间 窗的开始时间，则要求车辆必须等待一段时间直到时间窗的开始时间：每个客户有不同 的服务时间，且都必须在时间窗的结束时间到达之前完成服务。问题的其他一些假设如 下： ( 1 ) 被服务客户的货物配送量要求由一辆车一次服务完成。 ( 2 ) 所有车辆构成的路线由配送中心出发并且结束于配送中心。 ( 3 ) 一条线路上整个送货量总和不得超过车容量限制q 。 v r p t w 的目标是：运输总成本最小，并且服务时间准时。运输总成本包括固定成 本和变动成本，减少固定成本主要是使车辆数目最少，减少变动成本主要是使行驶路程 最短，即总行车路线最短。全程总服务时间最短主要是等待时间和行走时间最短。 2 1 2 求解思路 v r p t w 包含了几个n p h a r d 问题：t s p 、v r p 、背包问题等，表明v r p t w 也是 n p h a r d 问题。s a v e l s b e r g h l 4 8 】己经证明了，对于固定车辆数的v r p t w 问题，甚至找一 个可行解的问题也是n p h a r d 问题。因此，对于v r p t w 问题，不存在多项式时间算法。 在可以接受的时间范围内，精确算法只能解决输入长度约为1 0 0 的实例。如果需要解决 更大规模的实例，则必须耗费很长时间。所以单单依靠提高计算机的速度对问题的解决 是非常有限的，找到一个有效的近似算法对该问题的解决非常重要。 针对上述解决v r p t w 问题的困难，启发式算法的出现成为研究并解决v r p t w 这 类组合优化问题的最有效途径。启发式源于英文单词h e u r i s t i c s ，启发式算法意为通过对 过去经验的归纳推理以及实验分析来解决问题的方法，即借助于某种直观推断或试探的 9 第一二章v r p t w 模型的构建与分析 方法。用启发式算法求解问题是通过迭代过程实现的，即首先拟定出一套解的搜索规则， 为得到满意解，在整个迭代过程中不断吸收新的信息，必要时改变原来拟定的不合适策 略，建立新的搜索规则，注意从失败中吸取教训，并逐步缩小搜索范围。见图2 1 。 图2 1 启发式算法求解v r f r w 问题过程图 根据以上分析，本文首先建立v r p t w 问题的数学模型，然后采用启发式算法( 改 进蚁群算法) 来求解该问题。 2 2v r p t w 模型的构建 2 2 1v r p t w 问题的研究目标 ( 1 ) v r p t w 问题研究的意义： l o 长安大学硕j ：学位论文 1 ) 提高服务质量。目前，物流配送反应时间较长，导致物流配送系统服务水平较 低。 2 ) 降低物流成本。随着网络交易规模的扩大、交易量的增加以及交易速度的加快， 配送调度中会产生大量不合理的调度，物流成本无法控制。 3 ) 减小城市交通的负担。物流配送调度的不合理，会使物流配送的行车路线变长， 导致在运车辆增加，从而给本己拥挤的城市交通加重负担。 ( 2 ) v r p t w 问题研究目标的确定： 1 ) 按照客户的要求准时送货以提高物流服务质量，以下称准时到达。客户在订货 时，经常会规定货物到达的时间，如何安排配送，以达到客户对时间的要求，是这个系 统最重要的目标。 2 ) 合理安排物流配送路线以实现总成本最低，以下称为成本最低。这是物流配送 公司提高经济效益的重要途径。 以上两个目标之间是相互联系、彼此影响的，组成一个目标体系，所要解决的 v r p t w 是一个目标规划问题。从系统目标的重要程度来看，一般认为准时到达最重要， 成本最低次之。 2 2 2v r p t w 模型的构建 ( 1 ) 基本假设条件： 1 ) 每个配送中心所对应的需求点以及每个需求点的需求量为已知。 2 ) 车辆巡回对每个需求点服务，在需求点只卸货而不装货。 3 ) 需求点相互之间以及需求点与配送中心的路径和距离已知。 4 ) 每个需求点只由一辆车服务一次。 5 ) 每辆车由各自所属的配送中心发出，最后又回到配送中心。 6 ) 配送车辆的车种单一，且最大容量己知。 7 ) 车辆的平均行驶速度已知，行驶的路径长短与车辆行驶时问成正比。 ( 2 ) 基本约束条件： 1 ) 车辆的载重量在送货线路上，所有需求点的需求量之和不大于车辆的最大载荷。 2 ) 路线的单向性，即车辆从配送中心出发，经过几个任务点后回到原地。每个需 求点的货物全部由唯一的车辆提供，并且车辆在任务点之间的行驶方向是一致连续的， 不能发生折返，即每个在线路上的需求点只被一辆车服务一次。 第二章v r p t w 模型的构建与分析 3 ) 由于道路限制，所有需求点并不都是两两连通的，有些需要绕道经过其他的需 求点才能与原点间接地相连，某些道路还有单行的限制。 ( 3 ) 变量和参数符号设置： 嘭一表示车辆七对顾客需求点j 开始服务的时间； 勺一表示顾客需求点净0 顾客需求点的距离； 喀一结点f 的需求量； 岛一结点f 最早开始接受服务的时间； 一结点f 最迟开始接受服务的时间； 一结点集合，o 代表配送中心； q 一车辆容量； 勺一在边( f ，) 上的行驶时间，且勺包含了结点f 的服务时间； v 一车辆集合； 菇一决策变量，如果车后是由f 驶向j ，且f j ，值为1 ，否则为0 。 ( 4 ) v r p t w 问题的优化模型 v r p t w 问题在一般冲问题基础上加入了时间窗约束，即各个顾客需求点均有一 个时间窗。设：完成顾客需求点i 任务需要的时间( 装货或卸货) 为，而顾客需求点f 任务的开始时间需在q 劈的时间范围内。如果车辆到达f 的时间早于岛，则需在f 处 等待，而到达时间晚于，则顾客需求点f 拒绝服务。求满足上述要求的费用最少的车 辆行驶线路，即是本文要研究的带时问窗的车辆路径优化问题。 以醋表示车辆到达顾客需求点f 的时刻，勺表示车辆由顾客需求点行亍驶到顾客需求 点j 的时间，t i 表示车辆在顾客需求点f 的等待时间，s t ，表示车辆在顾客需求点f ，显然， 以下关系式成立： 醚= 0 ( 2 1 ) 够= 酵+ f f + t o + s f f v i ，w ，v k v ( 2 2 ) 1 2 长安大学硕十学位论文 e isb ：st i t f = m a x e i - b ；，0 ) ( 2 3 ) ( 2 4 ) 将时间窗约束函数结合到一般车辆路径问题模型中，可建立带时间窗的车辆路径问 题的优化模型： 目标函数： 约束条件： m i n z = c 0 4 k e v i e n j e n 噶= l k e v j e n 苟= 1 k e v i e n v i en i o v i n i o ) d i 苟q v kn i e n j e n ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) 一k = o v he n o ，v k v ( 2 9 ) f e j e n x 0 5 = 1 v k v( 2 1 0 ) ，e | v ， o x ；o = 1 v k v ( 2 1 1 ) 旭 o 硝( 嘭+ ， ) 矽 v i n ，v jen ，v k v ( 2 1 2 ) e i 6 j ，f v i n v k v( 2 1 3 ) 呓 o ，1 ) v i n ，v j n ，v k v ( 2 1 4 ) 目标函数( 2 5 ) 表示使总路径距离最小化或是运输总成本最小化，总路径距离是指 每部车辆由配送中心出发，完成所指派的所有需求点的服务后回到配送中心所经过的所 有路径距离的总和；约束式( 2 6 ) 和( 2 7 ) 确保一个需求点仅被一辆车服务一次，且 每一辆车辆都是从配送中心出发；式( 2 8 ) 表示任何车辆在任何路径中的载货量都不能 超过车辆的最大容量限制；式( 2 9 ) 表示车辆k 进入需求点，接着一定会从需求点离开； 式( 2 1 0 ) 和( 2 1 1 ) 表明每辆车必须离开并最后返回到配送中心；式( 2 1 2 ) 表明第k 辆从客户需求点f 到- ，的车在b e + 岛之前不能到达歹结点；式( 2 1 3 ) 表示服务的开始时 间必须在每个顾客需求点的时间窗之内；式( 2 1 4 ) 表明参数范围约束，确定参数为o 1 之间的数。 与已有v r p t w 问题的优化建模比较本模型把车辆对客户服务完毕后返回配货中心 第二章v r p t w 模型的构建与分析 这一约束条件加入到上述模型中，因为这样有利于配送中心的管理以及车辆的使用，因 此所建立的数学模型更为合理。 1 4 长安大学硕： = 学位论文 第三章蚁群算法的数学模型、特点及应用 蚁群算法是受自然界中真实蚁群觅食行为的启发而提出的一种模拟进化算法，具有 较强的鲁棒性、优良的分布式计算机制、易于和其他算法相结合等优点【2 钔，广泛应用于 组合优化、机器学习、自适应控制、规划设计和人工生命等领域，在解决许多复杂优化 问题方面已经展现出其优异的性能和巨大的发展潜力。 3 1 蚁群算法原理、模型及算法实现 人类丰富的创造力皆来源于自然界，通过与自然界相互作用、相互影响人类才对各 种事物有了清晰的认识。自然界中有许多自适应现象不断给人启示：生物体和自然生态 系统可以通过自身的演化就使许多人类看起来高度复杂的优化问题得到完美的解决。蚁 群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 就是其中的一种。 蚂蚁种群的特征包括个体的自治性、全面分布式控制、容错、直接或者环境中继 ( e n v i r o n m e n t m e d i a t e ) 的通信、与每个个体相关的复杂行为、集体和协作策略、自组 织等，这些独特特性的同时出现使得蚂蚁社会称作设计新算法和新型多系统的启发模 型。 十几年以来，蚂蚁社会模型的建立极大的推动了科学家在机器人学、行为研究、电 信等领域的研究活动，而这个领域内的不同模拟和实现都以“蚂蚁算法”命名。蚂蚁算 法中一个特别成功的研究方向，蚁群优化算法已经将蚂蚁种群模型应用到离散优化问题 上来。目前a c o 已经成功应用到诸如邮递员问题、调度问题、以及电信网络上的路由 问题的研究中。 3 1 1 蚁群算法基本原理 蚁群寻找食物时，总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻 找路径时会在路径上释放出一种特殊的化学物质。当它们碰到一个还没有走过的路口 时，就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长， 释放的激素浓度越低。当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径 概率就会相对较大。这样形成一个正反馈，最优路径上的激素浓度越来越大，而其它的 路径上激素浓度却会随着时间的流逝而消减，最终整个蚁群会找出最优路径。 ( 1 ) 蚂蚁寻食过程及蚁群行为分析 第= 章蚁群算镕的数学模型、特点发麻用 单只蚂蚁的能力和智力非常简单，但它们通过相互协调、分工、合作可以完成筑巢、 觅食、迁徙、清扫蚁穴等复杂行为。在日常生活中，我们总能看到大量蚂蚁在巢穴与食 物源之间形成近乎直线的路径，而不是曲线或者圆等其他形状，如图3 1 ( a ) 所示。蚂 蚁群体不仅能完成复杂的任务，而且还能适应环境的变化，如在蚁群运动路线上突然出 现障碍物时，一开始各只蚂蚁分布是均匀的，不管路径长短，蚂蚁总是先按同等概率选 择各条路径，如图3i (