（计算机应用技术专业论文）物流配送路径优化问题的研究.pdf

浙江大学硕士学位论文 摘要 物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中，配 送成本占了相当高的比例。配送线路安排的合理与否对配送速度、成本、效益影 响很大，特别是多用户配送线路的确定更为复杂。采用科学、合理的方法来进行 配送线路优化，是物流配送中非常重要的一项活动。 物流配送路径优化问题有很高的计算复杂性，属于n p 完全难问题，高效的 精确算法存在的可能性不大。本文研究了物流配送路径优化问题及其方法，将蚁 群算法改进并成功运用于解决物流配送路径优化问题，提出了基于蚁群算法的物 流配送路径优化算法。 本文章节组织如下： 第一章介绍了物流配送路径优化问题的相关知识，通过对研究现状的分析讨 论，引出本文的研究目的和工作重点。 第二章对物流配送问题进彳亍描述。分析了物流配送问题中路径优化的评估标 准，建立了带约束条件的物流配送问题的数学模型。 第三章中引入了蚁群算法，详细描述了蚁群算法在物流配送路径优化问题中 的实现方案，分析讨论了蚁群算法的优缺点，并将蚁群算法运用到物流配送路径 优化问题中，实现了多次配送、多种车型情况下的物流配送路径优化算法模型。 第四章针对蚁群算法的缺点，提出了对蚁群算法的几项改进，包括：在蚁群 算法中引入遗传操作、修改信息素更新策略等。最后将改进后的蚁群算法运用于 物流配送路径优化问题。经过多次实验和计算，证明了用改进的蚁群算法优化物 流配送线路，可以有效地求得问题的最优解或近似最优解。 第五章对本文的工作进行了总结，并分析了存在的问题和需要进一步研究的 内容。 关键词：物流配送，路径优化，蚁群算法，蚁群系统 浙江大学硕士学位论文 a b s t r a c t l o g i s t i cd i s t r i b u t i o ni s a l l o p e r a t i o nl i n k i n gw i t hc o n s u m e rd i r e c t l y , a n dt a k e s a c c o u n tf o rc o n s i d e r a b l ep r o p o r t i o ni nv a r i a b l ec o s t si nl o g i s t i c s t h ep l a n n i n go f v e h i c l er o u t i n gi nd i s t r i b u t i o nw i l lt a k eg r e a te f f e c to nt h ee f f i c i e n c y , c o s ta n db e n e f i t ， e s p e c i a l l yi nd i s t r i b u t i n gf o rm u l t ic o n s u m e r as c i e n t i f i ca n dr e a s o n a b l em e t h o dt o v e h i c l es c h e d u l i n gi sa ni m p o r t a n to p e r a t i o ni nl o g i s t i cd i s t r i b u t i o n o p t i m i z i n gl o g i s t i cd i s t r i b u t i o nr o u t i n gi san p - h a r dp r o b l e m h i g he f f e c t i v e e x a c ta l g o r i t h mi si m p o s s i b l et oi t t h i sp a p e rs t u d i e so nt h eo p t i m i z i n gl o g i s t i c d i s t r i b u t i o nr o u t i n gp r o b l e ma n ds o l v e st h ep r o b l e mu s i n gi m p r o v e da n tc o l o n y a l g o r i t h ms u c c e s s i v e l y t h et h e s i si so r g a n i z e da sf o l l o w s ： c h a p t e r1 ：d i s c u s st h eb a s i cp r o b l e ma b o u tl o g i s t i cd i s t r i b u t i o na n dt h er e l a t i v e r e s e a r c hw o r k s t h em a i nr e s e a r c ha i ma n do u rw o r ka r ea l s oi n t r o d u c e d c h a p t e r2 ：f i r s t , d e s c r i b et h el o g i s t i cd i s t r i b u t i o np r o b l e mw i t hm a t h e m a t i c e x p r e s s i o n s t h e n ，d i s c u s st h ee x p r e s s i o n so ft h ec o n s t r a i n t si nl o g i s t i cd i s t r i b u t i o n a n db u i l dt h em a t h e m a t i c a lm o d e l c h a p t e r3 ：a f t e ri n t r o d u c i n gt h ea n tc o l o n ya l g o r i t h m ( a c a ) ，af l o wc h a r to f s o l v i n gl o g i s t i c d i s t r i b u t i o np r o b l e mw i t ha c ai sg i v e n t h ea d v a n t a g ea n d d i s a d v a n t a g eo f a c a a r ea l s od i s c u s s e di nt h i sp a r t c h a p t e r4 ：t oi m p r o v et h ea c a ，s e v e r a lm e t h o d sa r ep r o p o s e d t h er e s u l to f e x p e r i m e n t sd e m o n s t r a t e st h a tt h eo p t i m a lo rn e a r l yo p t i m a ls o l u t i o n st ot h el o g i s t i c d i s t r i b u t i o nr o u t i n gc a nb ee a s i l yo b t a i n e db yi m p r o v e da n tc o l o n ya l g o r i t h m c h a p t e r5 ：s u m m a r i z ea l la c h i e v e m e n t so ft h i sd i s s e r t a t i o n ，r e v i e wi n n o v a t i o n p o i n t sa n dd e f e c t s ，a n dg i v et h ef u r t h e rw o r k i nt h ef u t u r e k e yw o r d s ：l o g i s t i cd i s t r i b u t i o n ，o p t i m i z i n gr o u t i n g ，a n tc o l o n ya l g o r i t h m ( a c a ) ， a n ts y s t e m ( a s ) 2 浙江大学硕士学位论文 第一章绪论 【本章摘要】本章主要介绍了物流配送路径优化问题的研究背景及研究意义， 国内外在物流配送路径优化问题上的研究现状。根据本文的研究背景，提出了 本文的主要研究内容。本章的最后简要介绍了本文的章节组织。 1 物流配送路径优化问题概述 1 1 1 物流配送路径优化的基本概念及相关问题 市场经济的繁荣，推动了物流配送业的迅猛发展。物流配送是指按客户的订 货要求，在配送中心进行分货、配货，并将配好的货物及时送交客户的活动。在 物流配送业务中，存在许多优化决策问题，本文讨论物流配送路径的优化，即通 过制定合理的配送路径，迅速而经济地将货物送到客户手中。 优化配送路径问题类似“旅行商”( t s p ) 问题，要求遍历所有的客户点，不 同的是，物流配送问题是由多辆车对客户点进行遍历，每辆车负责配送的客户点 以及配送路径都是不确定的，这正是配送路径优化所要解决的问题。 优化配送路径是一个n p 难问题，只有当客户和路段较少时，才能求得精确 解；启发式算法成了求解该问题的一个重要方向，且出现了多种算法，如c l a r k e 和w r i g h t 提出的节约法，g i l l e t t 和m i l l e r 提出的扫描法等，为求解配送路径的优 化提供了有益的参考，但也存在一些问题，如：节约法的组合点零乱和边缘点难 以组合，扫描法为非渐进优化等。 1 1 2 优化配送路径的意义 从应用方面看，物流配送路径优化，是物流配送优化中关键的一环，也是电 子商务活动不可缺少的内容。对货运车辆进行路径优化，可以提高物流经济效益、 实现物流科学化。对货运车辆路径优化理论与方法进行系统研究是物流集约化发 展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。优 浙江大学硕士学位论文 化配送路径问题是n p 难问题，般无法给出撮优解。研究者们努力的目标就是 尽量逼近最优解。因此优化配送路径问题是一个十分有应用价值的问题。 从理论研究方面看，本文主要用到的蚁群算法从提出至今只有十几年，还停 留在仿真阶段，尚未能提出数学解释，不过虽然研究时间不长，但己显示出在求 解复杂优化问题方面的优势，其应用前景非常广阔。可以看出，蚁群算法是一个 处于发展阶段，并有广阔的发展空间和巨大的发展潜力的算法，只要投入足够的 精力，就可能在理论上有所突破，这就体现出其巨大的理论研究价值。本文还运 用遗传算法对蚁群算法进行改进，遗传算法是较为成熟的优化算法，被广泛地运 用于解决实际组合优化问题。本文将遗传算法和蚁群算法相结合，对组合优化问 题的研究是一种新的尝试。 近些年来，人们在用各种优化算法解决现实中的各种组合优化问题上进行了 探索，如在生产调度问题中的应用，但在车辆路径问题中的应用才刚刚开始。本 文对现有的优化算法进行了分析和改进，将改进的蚁群算法运用于物流配送路径 优化问题中，为继续深入研究各种组合优化问题和物流配送车辆调度优化的计算 机实现等打下基础。 1 1 3 国内外研究现状 1 1 1 1 物流配送路径优化方面的研究 物流配送路径优化问题最早是由d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出，自 此，很快引起运筹学、应用数学、组合数学、圈论与网络分析、物流科学、计算 机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合 优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研究及 实验分析，取得了很大的进展。 m i l l e r & g i l l e t ( 1 9 7 4 ) m g 7 4 提出扫描法( s w e e pm e t h o d ) ，目的在于求解车 辆调度问题，并针对当时几个求解相似问题的算法进行比较，证明该算法所求得 的解较优于其它的方法。 w i l l a r d ( 1 9 8 9 ) 5 v i l 8 印首先将禁忌搜寻法应用于车辆路线问题上，设计重复的 浙江大学硕士学位论文 虚拟物流中心，将车辆路线问题转换成旅行商问题( t s p ) ，利用2 - o p t 或3 - o p t 方法求解车辆路线。 g e n d r e a u ，h e r t za n dl a p o r t e ( 1 9 9 4 ) g h l 9 4 使用插入法求解旅行商问题，再 用贪婪法( g r e e d ym e t h o d ) 进行路线切割，从而产生初始解。 b a r b a r o s o g l u & o z g u r ( 1 9 9 9 ) 8 0 9 9 1 利用禁忌搜寻法为土耳其某物流公司构建 一套决定货车配送点顺序的方法d e t a b a ，以二种乱数选取节点的方法产生初始 解，找到其中最佳的解作为初始解，再以插入法( i n s e r t i o np r o c e d u r e ) 作为搜寻 邻近解的移步方法，最后以2 - o p t 改善方法找到最优解的值。 s u & c h e n ( 1 9 9 9 ) s c 9 9 成功地将自组织影射网络应用在车辆配送区域及路 线规划问题的求解上，其算法的主要概念是利用类神经网络快速运算、自我组织 与平行处理的特性，配合m 个一维环状网络拓扑来表现车辆路线配送问题。 随着人工智能技术的引入和不断发展，模拟退火算法和遗传算法等新方法以 及人工神经网络和专家系统等新技术，为解决大规模、多目标车辆调度问题提供 了新的辅助手段。浙江大学蔡延光“光9 8 增人运用模拟退火算法和遗传算法求解 多重车辆调度问题，并将其集成为智能算法库，作为设计智能运输调度系统的依 据。鞍山钢铁学院李大卫【+ “9 轴等和东北大学姜大立【姜“9 9 等分别针对有时间窗 和无时间窗约束下的车辆路径问题用基因编码遗传算法求解，结果在较快速度下 得到了近似优解。 1 1 1 2蚁群算法的研究现状 蚁群算法由意大利学者m d o r i g o t m 。9 6 等人于首先提出。 1 9 9 6 年g 锄b a r d e l l a 和d o r i g o o d 9 6 】又提出了一种修正的蚁群算法，称之为“蚁 群系统”。 1 9 9 9 年吴庆洪【2 “籼明等人提出具有变异特征的蚁群算法，以克目艮蚁群算法收 敛速度较慢的问题。 德国学者t h o m a ss t u t z l e 与h o l g e rh o o s 提出了另一种改进的蚁群算法“最 大最小蚁群系统”( m a x - m i na n ts y s t e m ，m m a s ) ，这也是一种较好的通用优 化算法。 浙江大学硕士学位论文 2 0 0 1 年，陈烨8 ”o 1 提出的带杂交算子的蚁群算法。 2 0 0 2 年，王颖l “0 2 等人提出的自适应蚁群算法等。 蚁群算法已经在若干领域获得了成功的应用。其中最为成功的应用是在组合 优化问题的应用，其典型代表有t s p ，q a p ( q u a d r a t i ca s s i g n m e n tp r o b l e m ) ， j o b s h o p 调度等经典组合优化问题。 d c o s t a 【c 皿8 卵等人在m d o r i g o 等人研究成果的基础上，提出了一种求解指派 问题的一般模型，并用来研究图着色问题。 g b i l c h e v ，i c p a r m e e t b p 9 5 1 以及魏平i 甓+ 。1 垮人研究了求解连续空间优化问 题的蚁群系统模型。 蚁群算法在动态环境下也表现出高度的灵活性和健壮性，如其在电信路由控 制方面的应用被认为是目前较好的算法之一【b d t 删。目前，国内也有一些学者对 蚁群算法及其在电信领域的应用开展了研究。虽然对此方法的研究刚刚起步，但 是已有的一些初步研究结果已经显示出蚁群算法在求解复杂优化问题方面的一 些优越性。 在旅行商问题中，由于每一个节点( 城市) 之间的距离是已知的，从任意节 点到下一节点，有哪些节点可供选择也是己知的，当用蚁群算法解决t s p 时， 若蚂蚁处于某节点上，可以直接计算各条路径的选择概率，从而确定下一个最适 合选择的节点。蚁群算法从其机理来说是一种天然的组合优化方法，相对其它的 各类启发式搜索算法，具有明显的优越性，特别是在求解最短路径问题上，蚁群 算法的模型较其它组合优化算法有天然的优势，能更好地应用于路径优化问题。 配送路径优化问题和旅行商问题一样属于求解最短路径的问题，因此将蚁群 算法应用于物流配送路径优化问题已经受到国内外越来越多研究者的重视，蚁群 算法凭借其在路径优化问题中天然的优势，目前在配送路径优化问题上有许多成 功应用的例子。 1 2 本文的研究背景 本文的研究主要以物流配送在杭州五丰冷食有限公司的应用为背景。公司下 辖杭州、湖州、嘉兴三大生产基地及杭州、浙北、温台、宁波、浙中、上海、苏 浙江大学硕士学位论文 州、无锡等八大销售分公司，客户网点几百个，已经形成了一个基地一销售分公 司一客户网点的三级销售配送网络。为了能够实现快速物流配送，公司拥有两个 车队及维修中心，车辆几十辆，负责基地到销售分公司的销售、调拨任务。每个 销售分公司也管辖一定数量的车辆，负责完成客户网点的配送任务。公司下设物 流部门，管理物流配送中的各种业务。物流部门设置了专职的计划调拨中心，负 责每天基地一基地和基地一销售分公司之间的货物调拨。此外，每个销售分公司 也设置了兼职调度员，负责优化运输线路，调度车辆运输客户货物。 五丰冷食的业务以冷冻产品为主，因此在物流配送中有以下几个特点： 1 ) 线路总长不能超过车辆最大保温里程； 2 ) 根据业务需求，配送车辆一般有两三种型号，不是单一的车型： 3 ) 由于有明显的淡旺季之分，因此在旺季配送车辆不足的情况下，允许针对 客户需求状况对配送任务设置优先级。 1 3 主要工作 本文根据研究背景，主要研究基于蚁群算法的物流配送路径优化问题。 本文首先对物流配送优化问题的研究情况进行了概述，针对物流配送中的约 束条件，建立了物流配送的数学模型。采用蚁群算法对物流配送线路进行优化， 针对蚁群算法的特点和物流配送的数学模型，建立了运用于物流配送线路优化问 题的蚁群算法模型。本文还将对蚁群算法提出几项改进，以提高算法的收敛速度 和全局搜索能力。 1 4 章节组织 论文中其他章节按照以下方式组织： 第二章对物流配送问题进行描述。分析了物流配送问题中路径优化的评估标 准，建立了带约束条件的物流配送问题的数学模型。 第三章引入蚁群算法，详细描述了蚁群算法在物流配送路径优化问题中的实 现方案，分析讨论了蚁群算法的优缺点。并将蚁群算法运用到物流配送路径优化 浙江大学硕士学位论文 问题中。 第四章继前一章对蚁群算法的分析，针对蚁群算法的缺点，提出了对蚁群算 法的几项改进最后将改进后的蚁群算法运用于物流配送路径优化问题。 第五章对本文的工作进行了总结，并分析了存在的问题和需要进一步研究的 内容。 浙江大学硕士学位论文 第二章物流配送问题的研究 【本章摘要】本章对物流配送问题进行了概述，分析了在物流配送问题中路径 优化的约束条件和评估标准，并建立了物流配送问题的数学模型。 2 1 物流配送问题的描述 一般配送路径问题可描述如下： 有三个客户点，已知每个客户点的需求量及位置，至多用世辆汽车从配送中 心到达这批需求点，并且在完成配送任务后，返回物流中心，每辆汽车载重量一 定。要求安排车辆行驶线路使得运输距离最短，且满足以下几个约束条件： 1 ) 每条线路上的客户点需求量之和不超过汽车载重量； 2 ) 每条配送路径的总长度不超过汽车一次配送的最大行驶距离； 3 ) 每个客户点的需求必须且只能由一辆汽车来完成。 其目的是使总成本( 如距离、时间等) 为最小。 。蔓：二： 物流中心 o客户点 + 配送线路1 卜 配送线路2 一一配送线路3 图2 - 1 图2 1 是一个简单的物流配送线路的例子：1 个物流中心、5 个客户点，3 条 - 1 2 浙江大学硕士学位论文 配送线路；配送线路1 负责右边3 个客户点的配送任务，线路2 和线路3 分别负 责左边和下边的一个客户点；3 条配送线路可以由3 辆车同时进行，也可由1 辆 车分3 次完成；车辆从配送中心出发，按顺序遍历指定线路上的客户点，最后返 回配送中心。 “有时间窗车辆路径问题”( 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 ， v r p t w ) 是在上述一般路径优化问题中加上了客户被访问的时间窗约束。它要 求每项任务f 在时间范围陋bb j l 内完成，并可根据时闻约束的严格与否，分为“软 时间约束”和“硬时间约束”： “软时间约束”要求车辆尽可能在规定时间范围内访问需求点，否则将产生 等待或延迟损失，从而求得成本最小的配送路径。 “硬时间约束”要求车辆必须在给定的时间范围内访问需求点，如果超出这 个时间范围，所得到的配送路径为非可行解。 在本文研究的物流配送问题中，由于冷冻食品有较明显的淡旺季之分，车辆 调度通常在淡季比较宽松，而到了旺季就会比较紧张。如果我们选择“硬时间约 束”，那么在旺季的车辆调度中就常常会由于车辆安排紧张而找不到可行解；所 以，我们选择“软时间约束”。若车辆无法在用户规定的时间内送货到达，则在 成本中加入“惩罚成本”，这样就能兼顾淡旺季的车辆调度情况，给出合理的配 送路径方案。 2 2 配送路径优化目标 配送路径合理与否对配送速度、成本、效益影响颇大，因此，采用科学的合 理的方法确定配送路线是配送活动中非常重要的一项工作。确定配送路线可以采 取各种数学方法和在数学方法基础上发展和演变出来的经验方法。 无论采取何种优化方法，我们首先都要明确物流配送路径的优化目标，才能 有效地针对目标进行优化。 目标的选择根据配送的具体要求、配送中心的水平、实力及客观条件而定， 可以有以下多种选择： 1 ) 效益最高：在选择以效益为目标时，通常以企业当前的效益为主要考虑因 浙江太学硕士学位论文 素，同时兼顾长远的效益。效益是企业整体经营活动的综合体现，可以用利润来 表示。因此，在计算时是以利滑数值最大化为目标值。但由于效益是综合的反映， 在拟定数学模型时，很难与配送路线之间建立函数关系，所以一般很少采用这一 目标。 2 ) 成本最低：计算成本比较困难，但和以效益为目标相比有所简化，在成本 和配送路线之间有密切关系、且成本对最终效益起决定作用的情况下，采用以成 本最低为目标实际上等于选择了以效益为目标，比较实用可行。 3 ) 路程最短：如果成本和路程相关性较强，而和其他因素是微相关时，则可 以选择路程最短为目标，这样可以避免许多不易计算的影响因素，大大简化计算。 但需要注意的是，有时候路程最短并不意味着成本最低，如果道路条件、道路收 费影响了成本，单以最短路程为最优解则不合适了。 4 ) 吨公里最小：吨公里最低是长途运输中常作为选择目标，在多个发货站、 多个收费站、整车发到的情况下，选择吨公里最低为目标可以取得满意结果。在 配送路线选择中，以吨公里最小为目标在一般情况下并不适用，但在采取共同配 送方式时，也可以作为目标。 5 ) 准时性最高：准时性是配送中重要的服务指标。以准时性为目标确定配送 路线就是要将各客户的时间要求和到达各客户点的先后顺序进行协调安排，这样 有时难以顾及成本问题，甚至需要牺牲成本来满足准时陛要求。但对准时性的要 求必须建立在控制成本的基础上。 6 ) 运力利用最合理：在运力非常紧张、运力与成本或效益有一定相关的情况 下，为了节约运力、充分运用现有运力，而不需外租或新购车辆，也可以运力安 排为目标，确定配送路线。 针对不同的物流配送问题，要根据具体情况选择优化目标。本文研究的物流 配送问题根据五丰公司物流系统的特点，将优化目标设定为；路程短、准时性高、 运力利用合理。 浙江大学硕士学位论文 2 3 配送数学模型的建立 2 3 1 符号的定义 三：客户点总数； 客户点i 的货物需求量，其中卢1 ，2 ，上； e 1 客户点哟对货物需求的时间窗系数，值越大表示时间窗越大，则要货的 紧急程度越低，当e 产l 时，表示客户f 没有限制到货时间。= 1 ，2 ，厶 弘：超时惩罚系数； 由：从客户点f 到客户点，的距离。特别的，当f ，产。时，表示配送中心，例如： 壳3 表示从配送中心到客户点3 的距离，如表示从客户点2 到配送中心的距离。 f ，产0 ，1 ，2 ，三： 丘：车辆的总数； 甄：车辆女的最大装载量，其中扣l ，2 ，k ； 仇：车辆i 的最大行驶距离，其中扣l ，2 ，茁： ”“车辆七配送的客户总数，当 产0 时，表示车辆七没有参与配送。妇l ，2 ， 足： 风：车辆七配送的客户点的集合。当，轳o 时，r k = 中；当n 群o 时， 疋= 以，砰，妒 互 1 ，2 ，三) ，其中“表示该客户点在车辆的配送线路中顺序 为f 。= 1 ，2 ，茁。 2 3 2 约束条件 件 根据前文对物流配送路径优化问题的描述，我们可以提取出以下几个约束条 1 ) 每条线路上的客户点需求量之和不超过汽车载重量： h g s 鳞，n # o i f f i l 2 ) 每条配送路径的总长度不超过汽车一次配送的最大行驶距离 浙江大学硕士学位论文 啦 善+ 。b ，删 3 ) 每个客户点的需求必须且只能由一辆汽车来完成： r ln r t 2 = m ，k l k 2 4 ) 配送线路遍历所有客户点 2 3 3 优化目标 u 曩= l ，2 ， 0 h i 三 = 三 根据本文中物流配送路径优化问题的优化目标，我们先分别列出各优化目标 的数学形式： 1 ) 总路程 s = 粪陲+ 0 s 曲。)踮荟【莓+ 。卜k ) s s n k ) = h o , 兵n k 在1 2 1 超时惩罚成本尸： 我们可以用车辆行驶的路程来近似替代行驶时问。假设，客户点，在车辆k 的配送路径中排在第s 位( s 9 j ) ，那么车辆k 到达客户点s 所行驶的路程为： d “ i = 1 客户z 的时间窗系数为e ，则车辆的无惩罚路程为 这样我们可以写出超时惩罚p ： p = z s g n ( 1 + e a p e ，i d 一一( 1 怕p 。“ i = 1 l i = 1 j 浙江大学硕士学位论文 其中， s 出小f ：? 菇一 p p f = 0 ，x , t 删一o + e ，弦。，0 i = l p e ，d 一- 一( 1 + p ，弦。， 0 i = 1 3 ) 运力利用率成本t r ： 我们以车辆的满载率来表示运力利用率， t r = 综合上面各式，可以得出物流配送路径优化问题的目标函数 m m 卜一甜 其中，a ，b ，c 为权重系数，z a ，z az 伪放大因子。 至此，我们已经将物流配送问题的约束条件和优化目标用数学公式表示，建 立了配送问题的数学模型。这是优化物流配送路径的前提，我们之后的算法讨论 都将围绕着这一数学模型展开，其中目标函数： z 划p + 描。 为本文算法的评估函数，用于评估算法结果的优劣。 2 4 本章小结 本章对物流配送问题进行了详细描述，通过对描述的问题的分析，列出了物 流配送模型的约束条件和优化目标，并用数学公式表示，建立了物流配送优化问 题的数学模型。 本章的数学模型将作为本文中算法研究的基础。 浙江大学硕士学位论文 第三章基于蚁群算法的物流配送路径优化 问题的研究 【本章摘要】本章详细介绍了蚁群算法的基本原理和模型的建立，分析了蚁群 算法的优缺点，并将蚁群算法运用到物流配送路径优化问题中，提出了基于蚁 群算法的物流配送路径优化算法。 3 1 引言 蚁群算法是受到人们对自然界中真实蚁群的集体行为的研究成果的启发而 提出的一种基于种群的模拟进化算法，属于随机搜索算法，由意大利学者m d o r i g o 等人首先提出。m d o r i g o 等人首次提出该方法时，充分利用了蚁群搜索 食物的过程与著名的旅行商问题( t s p ) 之间的相似性，通过人工模拟蚂蚁搜索 食物的过程( 即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的 最短路径) 来求解t s p 。 蚁群算法可用来解决各种不同的组合优化问题，如旅行商问题( t s p ) 、二次 分配问题( q a p ) 、作业安排调度问题( j s p ) 等等。它具有通用性和鲁棒性，是 基于总体优化的方法。 目前对蚁群算法的研究，不仅有算法意义上的研究，还有从仿真模型角度的 研究，并且不断有学者提出对蚁群算法的改进方案：有的将蚁群算法同遗传算法 相结合，有的给蚁群系统加入变异特征，还有的提出所谓最大最小蚁群算法 ( m m a s ) 。应当指出，现阶段对蚁群算法的研究还只是停留在仿真阶段，尚未 能提出一个完善的理论分析，对它的有效性也没有给出严格的数学解释。但是， 从以前模糊控制所碰到的情况看，理论上的不完善并不妨碍应用，有时应用还会 超前于理论，并推动理论研究，蚁群算法也是如此。 蚁群算法原型本身就是一个寻找最短路径的模型，因此它在路径优化方面有 着天然的优势，目前已经有不少蚁群算法在t s p 问题中成功运用的例子。物流 配送路径优化问题和t s p 问题相比有共同点都是寻找遍历所有客户点的最 短路径的问题，也有其特性有更多更复杂的约束条件和优化目标。本文就是 浙江大学硕士学位论文 要研究一种基于蚁群算法的优化路径算法，使得其在物流配送路径优化问题中有 较好的实际效果。 3 2 蚁群算法的基本原理 蚁群算法是一种由于受自然界生物的行为启发而产生的“自然”算法。它是 从对蚁群行为的研究中产生的。正如m d o r i g o 等人在关于蚁群算法的第1 篇文 章中指出的：蚁群中的蚂蚁以“信息素”( p h e r o m o n e ) 为媒介的间接的异步的联 系方式是蚁群算法的最大的特点。蚂蚁在行动( 寻找食物或者寻找回巢的路径) 中，会在它们经过的地方留下一些化学物质( 我们称之为“信息”) 。这些物质能 被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后到者的行动( 具体表现 在后到的蚂蚁选择有这些物质的路径的可能性，比选择没有这些物质的路径的可 能性大得多) ，而后到者留下的信息会对原有的信息素进行加强，并且如此循环 下去。这样，被越多蚂蚁选择的路径，在后到蚂蚁的选择中被选中的可能性就越 大( 因为残留的信息浓度较大的缘故) 。由于在一定的时间内，越短的路径会被 越多的蚂蚁访问，因而积累的信息量也就越多，在下一个时间内被其他的蚂蚁选 中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路径 为止。如图3 1 所示 h 辞篓h 辞2 三0 l=0时刻t=l时刻 图3 - 1蚁群系统示意图 图3 1 中，设a 是巢穴，e 是食物源，h c 为一障碍物。由于障碍物存在， 蚂蚁只能从a 经过h 或c 到达e ，或者从e 经过h 或c 到达a 。各点之间的距 离如图1 所示。设每个时间单位有3 0 只蚂蚁由a 到达b ，有3 0 只蚂蚁由e 到 达d 点，蚂蚁过后留下的信息为l 。为了方便，设该物质停留时间为l 。在初始 浙江大学硕士学位论文 时刻，由于路径b h 、b c 、d h 、d c 上均无信息存在，位于b 和d 的蚂蚁可以 随机选择路径。从统计的角度可以认为它们以相同的概率选择b h 、b c 、d h 、 d c 。经过一个时间单位后，在路径b c d 上的信息量是路径b h d 上信息量的二 倍。t = l 时刻，将有2 0 只蚂蚁由b 和d 到达c ，有1 0 只蚂蚁由b 和d 到达h 。 随着时间的推移，蚂蚁将会以越来越大的概率选择路径b d ，最终完全选择路径 b c d 。从而找到由蚁巢到食物源的最短路径。由此可见，蚂蚁个体之间的信息交 换是一个正反馈过程。 在自然界中，蚁群的这种寻找路径的过程表现为一种正反馈的过程，与人工 蚁群的寻优算法极为致。如果我们把只具备了简单功能的行为体视为“蚂蚁”， 那么上述寻找路径的过程可以用于解释人工蚁群的寻优过程。由以上分析可知， 人工蚁群和自然界蚁群的相似之处在于，两者优先选择的都是含“信息量”浓度 较大的路径；较短的路径上都能聚集比较多的信息量；两者的行为体( 蚂蚁) 都 是通过在其所经过的路径上留下一定信息的方法进行间接的信息传递。而人工蚁 群和自然界蚁群的区别在于，人工蚁群具有一定的记忆能力。它能够记忆已经访 问过的节点；另外，人工蚁群在选择下一条路径的时候并不是完全盲目的，而是 按一定的算法规律有意识地寻找最短路径( 如在t s p 问题中，可以预先知道下 一个目标的距离) 。 3 。3 蚁群算法的模型 由于蚁群算法最早提出是结合t s p 问题建立模型的，所以我们以求解n 个城 市的t s p 问题为例说明蚁群系统模型。 首先引进如下记号：设m 为蚁群中蚂蚁的数量，献，_ 1 ，2 ，o 表示城市i 和城 市之间的距离，6 一o 表示r 时刻位于城市f 的蚂蚁数量，m = 6 ，以力表示城r i - 1 刻在| ：，连线上残留的信息量，初始时刻，各条路径上信息量相等，设 “o ) = c ( c = c o n s l ) 。蚂蚁k ( k = l ，2 ，埘) 在运动过程中，根据各条路径上的信息量 决定转移方向，露( f ) 表示在f 时刻蚂蚁t 由位置骷移到位置f 的概率， 浙江大学硕士学位论文 棚：j 芒躺i f j 叫黼咄( 3 - 1 ) 露( f ) = 矗e 盯慨， 一。 。 ( ) 【0 o t h e r w i s e 其中，a l l o w e d 庐 0 ，1 ，n 1 卜t a b u f l 莨示蚂蚁i 下一步允许选择的城市。与真实 蚁群系统不同，人工蚁群系统具有一定的记忆功能，这里脚硝肛1 ，2 ，m ) 记录 蚂蚁七目前走过的城市。珊表示蚂蚁从城市移动到黟动到城市f 的期望度，可根据 某种启发式算法具体得到：口、鼢别表示蚂蚁在运动中所积累的信息和启发式 因子在蚂蚁路径选择中所起的不同作用。随着时间的推移，以前留下的信息逐渐 消逝，用参数1 硪示信息消逝程度，经过”个时刻，蚂蚁完成一次循环，各路 径上信息量要根据下式作调整， r u ( t + n ) = p b ( f ) + ( 3 - 2 ) 勺= ( 3 _ 3 ) 表示第帜蚂蚁在本次循环中留在路径扯的信息量，笱表示本次循环中 留在路径扩上的信息量。 峥 h 嬲扎第嚣蚁选择路烈力 ( 3 _ t ) 其中，q 是常数，厶表示第t 只蚂蚁在本次循环中所走路径的长度。在初始时刻， 勺( o ) = c ，气= o ，其中，i ，产o ，l ，1 ”，栉一1 。根据具体算法不同，气 g ) 其中， t 表示车辆女已配送的客户点的个数。 2 ) 每条配送路径的总长度不超过汽车一次配送的最大行驶距离： d 一。+ d 矿。d k ，”薛。 这一约束条件要求车辆从目前所在客户点到下一客户点的距离再加上从下一客 户点返回物流中心的距离不大于车辆剩余的可行驶的距离。我们将这样的客户点 的集合记为t a b u a ： 加a “。= f | l 姐，z ，三l o 。，+ 4 。) + 喜d t 一，t 取 其中， 表示车辆七己配送的客户点的个数，矿表示车辆女目前所处的客户点。 3 ) 每个客户点的需求必须且只能由一辆汽车来完成： r l n 震1 2 = 巾，k l k 2 这个约束条件与经典蚁群算法中的约束条件一致，我们将这样的客户点的集合记 t a b u o ： t a b u 。= u 韪 其中，r k 表示车辆已配送的客户点的集合。 综合以上三个约束条件，我们可以确定t a b u 为： t a b u = t a b u 。ut a b u du t a b u 口 车辆在每次选择一个客户点之后，就要更新细6 吣t a b u a 和m b u o ，然后在 a l l o w = o ，1 ，2 ，三1 f 曲“中选择新的客户点或返回配送中心。 3 5 2 3车辆序列的初始化 在物流配送模型中，所有车辆是相互独立的，无须考虑车辆前后顺序的问题。 然而在优化算法的执行过程中，我们需要依次对每一辆车进行配送线路安排，配 浙江大学硕士学位论文 送线路的产生是有先后顺序的。由于本文的物流配送模型中，参与配送的车辆有 不同的装载量，这样在线路搜索中，不同类型车辆线路搜索的先后顺序就会对结 果产生影响，如果每次搜索都是按照相同的顺序，那么就很可能无法找到全局的 最优解。例如： c 4 物流中心0客户点 图3 - 6 车辆序列对优化结果的影响 图3 - 6 中，假设有3 t 和5 t 车各一辆负责配送任务，且每次搜索都是先搜索 3 t 车的线路，再搜索5 t 车的线路，那么，3 t 车在选择时有很大的可能会选择 线路c 0 - ) c i c 2 c 0 ，线路长度为3 。5 ；那么5 t 车只能选择线路 c 0 - ) c 4 - ) c 5 - ) c 3 - c 0 ，线路长度为8 ，这样线路的总长度为1 1 5 。如果由5 t 车先选择，则很可能选择的线路为c o - - c i - - ) c 2 - - ) c 3 - ) c 0 ，线路长度5 ，3 t 车 只能选择c 0 - ) c 4 - ) c 5 - ) c 0 ，线路长度为5 ，这样线路总长度为1 0 。 这个例子说明车辆序列会影响搜索结果，而且蚁群算法具有正反馈的特性， 会不断地对结果重复加强，这样就使得范围越缩越小，很可能遗漏了全局最优解。 为了避免这种影响，我们在每只蚂蚁搜索之前，随机产生一个车辆序列，让 这只蚂蚁按照随机产生的序列进行搜索，这样就避免了相同搜索序列对结果盼影 响，扩大了搜索范围。 我们采用d v c 法产生随机序列，以( 1 ，2 ，3 ，4 ) 的全排列为例，所有不 同的排列总数为41 = 2 4 ，其构造c 按词典序，则构造的第一位元素取最小标号， 以后各位依次增大，1 2 3 4 是首构造，首向量矿是i i i 。含义为每次都是取剩下的 浙江大学硕士学位论文 最小的标号。末构造为4 3 2 1 ，末向量为4 3 2 。序号d 、向量矿和构造c 就构成 了d v c 表，如表3 一l 所示 d矿 c dy c l 1 1 l1 2 3 41 3 3 1 13 1 2 4 21 1 2 1 2 4 31 43 1 23 1 4 2 31 2 l 1 3 2 4 1 5 3 2 13 2 1 4 41 2 21 3 4 21 6 3 2 23 2 4 1 51 3 11 4 2 31 73 3 14 3 1 2 6 1 3 21 4 3 21 83 3 23 4 2 1 72 1 l 2 1 3 4 1 9 4 1 l4 1 2 3 82 1 22 1 4 32 04 1 24 1 3 2 92 2 l 2 3 1 4 2 1 4 2 14 2 1 3 1 02 2 22 3 4 12 24 2 24 2 3 l 1 l 2 3 12 4 1 32 34 3 l4 3 1 2 1 2 2 3 22 4 3 1 2 4 4 3 24 3 2 1 表3 - 1l 4 排列的d v c 表 我们随机产生序号d ，通过d nv i c 转换来完成d i c 转换。 d v 转换公式如下： 砜= d v 0 _ | ! 置d ：* - l 强l 1 x n ld ，= 口一t 一【v ，一一0 其中h 为构造的位数，i - - 1 ，2 ，n - 1 ，v = v l v 2 k l 。 v c 转换是通过向量v 的指针功能来确定构造c 。如v = 2 3 1 ，则有： v l - - - 2 1 2 3 4 c 1 = 2 v 2 = 3 1 3 4c 2 - - 4 n = 1d c 3 = 1 c 产3 c = c i c 2 c 3 c 4 = 2 4 1 3 浙江太学硕士学位论文 3 5 2 4车辆不足情况及惩罚成本 根据本文的研究背景，在进入旺季时，物流中心往往出现车辆短缺的情况， 每一辆配送车辆在完成一条配送线路之后还会有第二条甚至第三条配送线路。在 大多数物流配送路径优化问题的研究中，当配备的车辆无法一次完成所有的配送 任务时，则认为任务不可完成，这在实际运用中显然是不合理的。 一种简单的解决方法就是不限定车辆的数量，让算法自由分配线路，这样当 算法得到的线路数量大于车辆数量时，就说明有车辆需要完成多条配送线路的任 务。这种方法有效地解决了车辆不足时，多次配送的问题，但同时也带来新的问 题，由于算法认为车辆是无限的，因此每条配送线路在算法中均为首次配送，并 非像实际中那样有首次配送和二次配送的区分。在实际配送中，客户都希望能够 尽早地得到需要的货物，如果客户的货物在第二次配送线路中，那么同首次配送 线路相比，客户的满意度肯定会大打折扣。 我们在建立物流配送模型时，已经引入了“惩罚成本”这一概念，当用户得 到货物的时间超过用户的期望时间时，这次配送就要加上一定的惩罚成本。这项 成本不仅在算法排定配送路线上客户的先后次序时起作用，在多次配送的情况下 也应该有所体现。 一个客户点i 的惩罚成本计算过程是： 1 ) 计算车辆在该配送线路中已经行驶的距离，假设为s ； 2 ) 计算客户期望时间( 以距离代替) ：( 1 + e ，) d 。( e j 0 ) ： 3 ) 判断是否需要惩罚成本：如果s 一0 + 口，) d o ， o ，( p ，0 ) ，则需要惩罚成 本； 4 ) 当需要惩罚时，计算惩罚成本：芦b 一( 1 + 毛) d o i 】。 这是对首次配送的惩罚成本的计算，对于多次配送，我们依然采用实际数量 的车辆。在所有车辆都有配送任务，而还有客户点没有派送时，算法并不判断为 不可完成，而是重新在