（管理科学与工程专业论文）集送一体化条件下的车辆路径优化问题研究.pdf

摘要 车辆路径问题( v r p ) 是物流系统调度中的关键一环，它可以提高物流经济效 益化，实现物流运作科学化及高效化。随着物流业在我国的不断发展以及物流专 业化水平的不断提高，我国物流配送业近年来也得到了迅速的发展。在物流配送 活动中，配送车辆的路线问题是配送合理化的核心问题，对于企业提高服务水平、 降低物流成本、增加企业经济效益的影响也最大。配送和集货一体化把配送和集 货两个目标结合在一起，统筹安排，能更好的实现成本最小化和效益最大化的根 本目的，因此配送和集货一体化将是现代物流配送的发展方向。所以对配送和集 货一体化下的车辆路线问题进行研究是具有很强的理论价值和现实意义的。 文章主要研究内容与创新点归纳如下： ( 1 ) 考虑到传统启发式算法的不足以及现实运输中车辆数量会对物流成本有 较大的影响，分析了可重复运输的车辆路径问题的数学模型，根据运输过程中运 载量的大小首先限制车辆的使用数量，改变了一辆车只能通过一个任务点的传统 方法，并通过设置变量参数，判断车辆及任务点能否进行可重复运输，提出了解 决思路和方法，有效的解决了该问题。 ( 2 ) 论文讨论并完善了集货和送货一体化无时间窗和带时间窗的车辆路径问 题的数学模型，提出了把时间窗和配送量与集货量之差作为路线设计时的两个 参考参数，以该模型为本文研究对象，从硬时间窗和软时间窗两个方面来进 行研究。 ( 3 ) 本文设计了适合求解该问题的一种启发式算法。在该算法中，论文根据 两个参数的优先性，把时间窗以及配送集货量之差经过适当的变形，作为总成 本的一部分进行综合考虑。根据节约算法的思路，求得的综合成本最低的那条 线路即为我们要求的方案。通过案例显示，该改进方案可以有效解决该问题， 取得满意的结果。 关键词：路径规划、集货和配送一体化、时间窗、节约算法 a b s t r a c t v e h i c l er o u t i n gp r o b l e mi sav e r yp i v o t a lp r o c e s si nt h ev e h i c l e s c h e d u l i n g i tc a nh e l pt oi m p r o v el o g i s t i c se c o n o m i cb e n e f i ta n dr e a l i z e s c i e n t i f i cl o g i s t i c s a l o n gw i t ht h ed e v e l o p m e n to ft h es p e c i a l i z e dl e v e lo f l o g i s t i c si nc h i n a ，d i s t r i b u t i o ni n d u s t r yh a sd e v e l o p e df a s td u r i n gt h e d i s t r i b u t i o na c t i v i t y , t h ev e h i c l er o u t i n gi st h ec o r ep r o b l e mo fd i s t r i b u t i o n r a t i o n a l i z a t i o n ，a n di sa l s ov e r yi m p o r t a n tt oi m p r o v et h es e r v i c el e v e l ， r e d u c e l o g i s t i c sc o s ta n di n c r e a s ee c o n o m i cb e n e f i t v e h i c l er o u t i n g p r o b l e mw i t hp i c k u p sa n dd e l i v e r i e sc o m b i n e st h ep i c k u p sp r o b l e mw i t h t h ed e l i v e r i e sp r o b l e ma n dg i v e sa no v e r a l l c o n s i d e r a t i o n ，w h i c hc a n a c h i e v et h e g o a l o ft h em i n i m u ml o g i s t i c sc o s ta n dt h em a x i m u m e c o n o m i cb e n e f i t s s ou n i t i z i n gt h ea c t i v i t i e so fp i c k u p sa n dd e l i e v e r i e s w i l lb et h et r e n d i ti so ft h e o r e t i c a la n dp r a c t i c a ls e n s e st os o m ee x t e n t s t os t u d yt h ev e h i c l er o u t i n gp r o b l e m d i r e c t i n gt o w a r d st h el a c k i n go ft h et r a d i t i o n a lh e u r i s t i ca l g o r i t h m a n dt h en u m b e r so ft h ev e h i c l ei n f l u e n c et ot h el o g i s t i c sc o s t ，t h eo b j e c t o ft h i sp a p e ra n a l y z e st h em a t h e m a t i cm o d e lo fv e h i c l er o u t i n gw i t h r e p e a t a b i l i t yf i r s t ，l i m i tt h en u m b e ro f t h ev e h i c l ea c c o r d i n gt h e b u s l o a d ，w h i c hc h a n g e st h et r a d i o n a lw a yt h a tad o to n l yc a nb ep a s s e db y av e h i c l e w ea l s os e tu pav a r i a b l ep a r a m e t e ri no r d e rt od e c i d ew h i c hd o t s h o u l db ep a s s e dr e p e a t l y b yt h i sw a yw ep r o p o s et h es o l u t i o n s u c c e s s f u l l y o nt h eb a s i so ft h es o l u t i o n ，w ep e r f e c tt h em a t h e m a t i c m o d e lo ft h eu n i t i z i n gt h ea c t i v i t i e so fp i c k u pa n dd e l i e v e r yw i t ht i m e w i n d o w a n dw em a k et h et i m ew i n d o wa n dt h eb a l a n c eo ft h ep i c k u p s a n dd e l i v e r i e sb ev a r i a b l ep a r a m e t e ri nt h er o u t i n gp r o c e s s t h r o u g ht h e e x a m p l eo ft h em o d e l ，w et a k er e s e a r c hf r o mt w os i d e sa st h ef i x e dt i m e w i n d o wa n dt h et r a n s f o r m a b l et i m ew i n d o w t h ep a p e rd e s i g n sa h e u r i s t i ca l g o r i t h mb e i n gf i tf o rt h ep r o b l e m i nt h ea l g o r i t h m ，t h ep a p e r t h i n k st h et i m ea n dt h eb a l a n c eo ft h ep i c k u pa n dd e l i v e r ya sl o g i s t i c c o s t ，a sap a r to ft h et o t a lc o s t a c c o r d i n gt ot h ed i f f e r e n tp r i o r i t ya n dt h e t h o u g h to fs a v i n ga l g o r i t h m ，t h er o u t i n gw h i c h h a st h el e a s tc o s ti st h e o n ew ew a n tt og e t i nt h ee n dc a s ep r o v et h a tt h em e t h o dc a ns o l v et h e p r o b l e ms u c e s s f u l l y k e y w o r d s ：v e h i c l er o u t i n gp r o b l e m ，p i c k u p sa n dd e l i v e r i e s ，t i m ew i n d o w , h e u r i s t i ca l g o r i t h m 青岛大学硕士学位论文 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文 中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意 义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论 文或成果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名丁多衣 学位论文知识产权权属声明 日期：咔铜归 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本 人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单 位仍然为青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密田。 ( 请在以上方框内打“”) 做作者躲丁亏毋 吼中月伯 导师签名：童湃存日期：冲年6 月心日 ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使用) 4 2 第一章绪论 第一章绪论 1 1 选题的背景及目的和意义 物流是使商品在需要的时问到达需要的地点的经营活动的过程，是提高商品 流通效率的重要途径，运输、储存、包装、装卸搬运、流通加工、配送和信息组 成了物流的七个功能要素，而其中运输和配送起着尤为重要的作用。在物流过程 中，运输是实现物质实体由供应方向需求方的移动，也就是创造空间价值的过程， 根据一般综合分析计算社会物流费用，运输费占6 0 的比例，有些产品运输费用 甚至高于产品的生产费用。可见，运输成本是影响物流成本的重要因素，物流总 成本的大小和运输成本的大小直接相关。 交通运输是国民经济的动脉，它对社会经济发展和人民生活起着极为重要的 作用。据美国物流研究委员会估计，运输业占美国国民生产总值的1 5 。据北美 和欧洲的大量实际应用表明，对物流配送过程进行优化，可以在总运输成本中获 取5 一2 0 的节省，而总运输成本在商品最终成本中占1 0 - 2 0 。中国仓储协会对 1 4 6 个企业的调查显示，运输的费用占到整个物流费用支出的比例分别为：在生产 企业原料物流中占5 8 ，在生产企业成品物流中占7 3 ，在商品企业物流中占5 2 。 另外，根据拥有四千多辆货运车的上海市汽车运输公司粗略统计，如果减少空车 行驶，使货运车里程利用率提高1 ，在一年之内就可以减少运输成本一百万左右， 节约汽油约7 0 万公升。 据测算，我国物流成本占g d p 的比重高达2 0 9 g ，超过2 万亿元，发达国家一般 只有1 0 左右，物流成本降低l 到2 个百分点，将产生社会效益1 0 0 0 至a j 2 0 0 0 亿元。 因此，控制物流总成本、降低运输成本对我国的经济建设有着十分重要的意义。 另外，配送制可以使库存相对集中，有条件也有可能按照统一计划合理分配和使 用资源，做到物尽其用；实施配送也有利于建立起合理的库存结构和运输结构， 进而能够提高物流设施的利用率和物流设备的工作效率。在库存结构和运输结构 的分散状态下，汽车的货物实载率一般比较低，有的只有2 5 ，而在结构合理、 运力集中的状态下，车辆的货物实载率可提高蛩j 7 0 - 8 0 。 物流作为第三利润源泉，已经越来越引起人们的重视。降低物流成本成为人 青岛大学硕+ 学位论文 们考虑物流的一个重要方面。实际上物流产业一直缺乏现代运输及物流配送的路 径优化系统，车辆在进行运输配送集货的时候不得不行驶更多的路，需要更多的 车辆，这就导致了货运的空载率过高及空载行驶单程过大，极大的浪费了物流资 源，带来了很大的物流运输成本。 车辆调度是物流管理非常重要的一部分。随着社会的发展以及消费者对服务 质量要求的不断提高，高效的车辆调度不但有利于降低物流中货物库存的费用， 缩短商品上市周期，而且逐渐成为物流成败的关键。研究车辆调度，以提高物流 效率、降低物流成本、提高服务质量对于促进经济健康稳定的发展具有重要意义。 因此集货配送系统优化成为很多企业和政府机构降低成本、节约能源、追求更高 利润的手段。 集货和送货一体化的思想在国外已有一定的应用，有关研究正在深入的进 行，在实际中的应用也正在扩展中，在对该问题的一些初步尝试应用中，已经取 得了明显的效果，这对促进该问题的进一步深入研究起到了很大的作用。美国洲 际商业委员会新闻报估算通过使用回程集货每年可节约的燃料为4 2 0 0 万加仑； k e a r n e 总结了企业在1 9 7 8 年至u 1 9 8 3 年间为了提高物流的多样性而执行的项目，第 一个项目就是协调开出的车和返回的车从而提供自有车辆的回程集货，这项项目 已被8 3 的支持者采用。y a n o 等描述了以密歇根为中心的铁路链近4 0 家商店和一 个在托利多附近的配送中心的情形，商店使用了1 l 辆车，其载重量和容量是确定 的，这些车是用来配送货物到商店并从附近的供应商处收集货物，最后，所有配 送中心的司机要在路线结束后回到配送中心。1 9 8 6 年沃尔玛公司用配送和集货一 体化的思想为车辆分配线路，发现使用自有车辆从供应商处集货比另外派车节约 了4 5 0 ，0 0 0 美元。 进行集货配送系统优化，主要就是车辆路径优化调度，它主要是指通过最少 的路程来完成所有的任务，通过载重量一定的车辆对每一个结点完成送货、配送 等任务，其中每一个结点都有一定量的货物的需求或供给。它要求不能超出车辆 的载重限制，同时尽量使车辆行驶距离最少。从使用范围来上说包括集货路线优 化、货物配装及送货线路优化，以及集货、货物配装和送货一体化优化，它有有 时间窗限制与无时间窗限制之分。物流配送车辆的优化调度是物流系统优化中关 键重要的一环，对配送车辆进行优化调度，可以提高物流经济效益、实现物流科 学化。可以说对物流配送车辆优化调度理论与方法进行系统研究是物流集约化发 2 第一章绪论 展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展 电子商务的基础。 本文选题的主要目的及意义具体体现在以下几点： ( 1 ) 构建可重复运输的路径优化模型，为将来的研究提供一种可行的思路， 同时也为企业在安排车辆路径的时候提供一种新的参考模型。 ( 2 ) 提供一种解决可重复运输的路径优化的方法。为企业减少行驶车辆、降 低运输距离提供一种简单可行的解决办法。 ( 3 ) 针对集货送货一体化的特点，根据企业对时间要求的严格程度，对运输 问题，从无时间窗和有时间窗两个方面提出方法来解决一体化运输的问题。并且 把时间和集货送货量之差作为一个成本来进行考虑，利用节约算法的原理来解决 这些限制条件。 i 2 国内外研究动态 车辆路线问题( v r p ) 最早是由d a nt z i n g 和r a ms e r 在1 9 5 9 年首次提出的， 它是考虑从一个或多个站点出发，车辆把货物运送到空间任意分布的一系列客 户点，有序的通过它们，满足客户的需求且每个顾客只能被服务一次，组成适当 的行车路线，在车辆容量等约束条件下使总行驶费用最小( 行驶费用可以用路程、 时间等表示) 。 对于路径优化的研究经历了一个很长的发展阶段，从初期的无车辆容量及车 辆服务约束的t s p 问题，到有车辆容量限制和对每辆车的最大服务客户数及行驶 距离、行驶时间的限制( 即传统的v r p 问题) ，再到客户性质( 主要是物流中心、 集货客户和配送客户) 的增加，主要可以分为回程时集货的问题( v r p b ) 以及集 货供货一体化问题( & o v r p p d 问题) 。随着客户对时间要求的增加，时间窗 ( v r p t w 问题) 也逐渐增加到这一问题当中。另外，考虑到实际情况，多供货 点问题( m d v r p ) 和随机问题( s v r p 或者d v r p i h 题) 也被提出来。 初期路径优化的问题，由于本身的复杂性较低，车辆的限制条件较少，主要 是单纯的路线设计问题，因此大多数人是从t s p 角度出发来解决v r p 问题的，采 用精确解法实现算法。p a d b e r g 等的分枝剪枝法、f i s h e r ( 1 9 9 4 ) 提出的k 树法、k o h l 和m a d s e n ( 1 9 9 7 ) 用拉格朗日松弛算法求解带有时问窗的v r p 、f u m e r o ( 2 0 0 0 ) 等的 3 青岛大学硕士学位论文 修正拉格朗日松弛及子梯度优化方法、l o r e n al u i z ( 2 0 0 4 ) 等对列生成方法的改进 等。 精确算法主要适用于解决问题结构比较清晰、各元素之间的关系明确、有判 定解的可行性和最优性的明确准则的问题，求解工作所需的计算量不大，所需费 用不多。而越来越多的实际v r p 问题不存在严格最优解或者要得到最优解需花费 过大的代价，当采用精确算法求解这种类型的问题时难以得到理想的效果。 在应用过程中，越来越多的学者把实际问题添加到v r p 问题当中，其中最 主要的限制就是车辆容量和最长行驶距离的限制。改进c l a r k e 和w r i g h t 提出的 c - w 节约算法是最常用的一个算法。如汪爱娇【1 】用属于贪婪算法的一种平行节约 算法来解决车辆路径问题。在每次迭代中，它通过解点组间的匹配问题，合并多 组点组。它实际上就是将传统节约式算法的每一条路线看作一个点组，来进行启 发式算法的运作。宋伟刚1 2 】等提出了首先对车辆数量进行估计，并应用节约算法 对路径优化问题进行了求解，但是他并没有把车辆数量作为一个限制。李作秋1 3 l 将扫描算法和节约式算法结合在一起，首先以配送中心为原点按顺时针方向进行 扫描，以车辆容量为约束条件可将网络中的结点分为不同的组，然后在组内运用 启发式算法来设计路线。但是这种设计但在算法中存在着某些边缘点难于组合以 致于影响寻优率的缺点。b a k e rb 4 应用遗传算法，对编码方式进行了改进， 用一种隐含编码方式的遗传算法解决了车辆的调度的问题。a t s u s h ih a t a b u 巧1 提 出双种群遗传算法，然后从两个群体中选出的最优解进行杂交，打破平衡态，互 相进入对方种群，获得全局最优解。 因为车辆数目也是运输成本的一个重要方面，很多研究人员开始把车辆的使 用也作为一个很重要的目标来考虑。如尹传忠等6 1 提出了不把车辆的行驶距离 作为唯一的衡量指标，把车辆的数量也作为一个重要的指标，使问题更贴近实际。 吴兴华订1 首先车辆数目固定，用遗传算法来解决确定车辆数目车辆配送问题。 邹彤噶1 用遗传算法，提出了一种基于不确定车辆数的编码方法，能在搜索最短 路径的同时实现对车辆数的自动寻优，此算法在搜索最短路径的过程中，会自行 寻找满足要求的最少车辆数。骆正山9 1 提出一种基于模糊可能性的混合遗传算 法。文章在对模糊需求描述的基础上，以车辆数最少和运行距离最短，引入决策 者主观偏好的概念，并通过随机模糊的方法，研究了决策者主观偏好对最终决策 目标的影响作用。对于车辆的载重限制的研究1 3 4 1 也成为车辆限制的一个方面。 4 第一章绪论 马辉民n 0 1 提出了一个评价函数。把配送终端按照评价值从小到大进行顺序排列， 则得到一个优先关系。根据优先权的高低排序来确定初始的车辆数目及路线，再 进行选择、交叉、变异，也很好的解决了这一问题。刘哲n 用并行多蚁群算法 来解决车辆数较少的车辆路径问题。kd o e r e rrf 1 1 2 j 等通过竞争蚁群算法，使得 运输车辆总成本最低。 对于目标函数的改进也是也是对v r p 闯题丰富的一个很重要方面，王宗原等 n 3 1 对目标函数做出了一些修改，综合考虑道路级别、道路流量、转弯限制等实 际问题，并对该问题提出了求解。马小伟n 4 1 把路径问题和仓库的选址问题结合 在一起，把费用分为三部分，车辆的行驶费用( 与距离有关) 、出车费用( 与车 辆数有关) 、和仓库的建造费用，提出了一个总费用最少的解决思路。 随着运输对时效性要求的提高，时间窗成为一个很重要的考虑因素。霍佳震 1 5 1 应用节约算法，将车辆固定成本和变动成本同时加入到节约值计算中，在考 虑时间约束的基础上参考节约值最大或机会节约值最大两种策略选择任务连接， 是对节约式算法的一个很大的改进。刘云忠n 们建立了基于蚁群算法的带时间窗 车辆路径问题的启发式算法，将启发式算法和蚁群算法结合在一起，利用两种算 法的优点，从而提高了算法的效率。李显生n 7 等建立了追求总体效益最优的车 辆调度多目标决策模型，并设计分派一节约启发式算法求解该模型，并且提出了 时间效应成本的概念，使问题解决更易于量化。杨宇栋u 8 1 建立了基于直观描述 的数学模型，根据有时问窗车辆路径问题的特点构造了求解该问题的改进模拟退 火算法。钟石泉【1 9 】运用了多初始解和全局禁忌表等各种措施来减小解的不稳定性 和扩大搜索范围，并根据容量约束和时间窗约束性质的不同，结合惩罚函数和各 约束的性质来联合控制车场的分配。另外电子商务下的物流配送也有人进行过相 关研究1 3 2 1 0 随着现代物流不仅仅局限于集货或配送，而是将两者有机的结合在一起。相 对于集送一体化的应用，国内外对它的研究比较少，有文献中提到的v r p b 问题， 即回程收货的作业方式，碰到客户点同时有配送、集货需求时，会造成重复访问 和车辆资源浪费的现象，并且容易导致车辆的路线规划缺乏弹性，增加运输的距 离和成本，第一类问题，取消先配送后集货的限制，每一个客户只进行单纯的集 货或配送业务，第二类问题，不仅取消对先配送后集货的限制，而且允许客户点 同时有集货和配送的需求，这一类研究还处于初步阶段。 5 青岛大学硕士学位论文 第一类问题最早有g o l d e n 伽1 等人提出，使用基于在收货客户的路线中插入 送货客户的方法解决该问题。c a s c o 乜门等利用节约算法构造有配送需求客户的初 始路径，有集货需求客户则是使用g o l d e n 等人的插入法，期思路是当剩余的配 送量足够少时，才允许集货点插到配送点之前。 m i n 首次求解了第二种类型的问题，即当客户既是集货客户又是配送客户时 的情形。解决思想是首先把客户分组接着求解每组的旅行商问题。h a l s c 用先分 组后分配路线的方法求解了该问题，首先把客户分配给车辆，接着在安排路线的 过程使用3 - o p t 方法优化。g e n d r e a u 等研究了带取货和送货的旅行商问题，首先 在不考虑取货和送货的情况下求解t s p 为问题，然后在t s p 的路线中确定取货和 送货次序。 郭耀煌、李军采用了网络启发式算法，对带有时间窗要求的集货送货一体化 满载车辆路径规划进行了研究，应用重载点，从而简化了模型的规模。g r o n a l tm 勿针对集送一体化问题给出了几种基于节约法的启发式算法。胡大伟晒1 通过 多阶段启发式算法，先把多站点转换为单一站点问题，再使用基于s f c 的分组方 法来构造初始解，并运用3 o pt 算法优化回路，之后采用插入算法改善解的可行 性，解决了多站点的一体化问题。曹剑东【2 6 】利用改进的节约法求解，对得到的结 果采用2 o p t 搜索算法进行修正，求解了带物流中心的多站点的一体化问题。o u a n l u ! 冽在解决集送一体化问题时不仅考虑运输距离，同时也把任务点等待时间作 为一个重要考虑因素，用启发式算法解决了这个问题。a r i l dh o f f 2 9 1 用禁忌式算 法也解决了类似问题。 在v r p 研究过程中，解决方法多种多样，互有优势，研究方法主要集中在启 发式算法，遗传算法、模拟退火算法、禁忌搜索算法和蚁群算法几个方面。 启发式算法是一种简单的、易实现的算法，具有快速求解n p 难题、对初值 要求不严格等优点，便于计算机系统的实现。因此研究启发式算法不失为一种可 行的方向。 遗传算法通过多个个体间的选择、交叉等的遗传操作，相互协力地进行解的 探索，容易发现更好的解。然而解决过程中的遗传因子型的表现依赖于设计者的 能力。并且该算法所得结果的好坏，主要依赖于遗传代数和解组规模，为得到问 题的全局最优解，需要以延长计算时间为代价，如郎茂祥2 7 1 混和遗传算法以及 赵建友3 用启发式遗传算法进行求解。 6 第一章绪论 蚁群算法【3 3 】具有群体合作、正反馈选择、并行计算等三大优点，并且可以 根据需要为人工蚁加入前瞻、回溯等自然蚁群所没有的特点。因此，该算法具有 很强的发现较好解的能力。但是这种算法也存在一些缺陷，如搜索时间较长，容 易出现停滞现象，不利于发现更好的解。现在对该算法的研究大多数都集中在对 这些缺陷进行改进上，如最大最小蚁群算法。 禁忌搜索算法的搜索速度快，效率高，适用于大规模的优化计算，因此随着 v r p 复杂性的提高和问题领域的延伸，很多复杂的问题都用该算法解决。但是禁 忌搜索算法对初始解有较强的依赖性，鲁棒性很差，并且搜索过程中只能对一个 解操作，所以往往需要使用别的启发式方法，先获得一个较好的初始解。 模拟退火算法可人为地控制迭代次数，反复求解然而该方法所得解的好坏 与初始状态、温度函数等都有一定的联系，降温较快的效果不一定很好；效果好 的，其降温过程又极其缓慢。但是就其运算过程和得到的解来说不如遗传算法的 效果好。 对现代智能算法的应用，多是相互结合在一起共同使用的。如刘志硕2 3 1 提 出的一种基于可行解两阶段构造策略的自适应混合蚁群算法，张丽艳以1 等将粒 子群优化算法与模拟退火算法结合，提出的一种求解车辆路径问题的混合粒子群 算法。 随着方法的增加以及实际问题复杂性的增加，尤其是集送一体化问题同时间 窗问题结合在一块，在使问题更加贴近实际操作的过程中，使问题变的更加复杂， 属于更复杂的n p h a r d 问题。 1 3 问题的提出及解决方法 目前，国内外学者对于路径优化的研究很多，还存在一些不足之处，具体体 现在以下几个方面： ( 1 ) 对于目标的考虑尚欠周全，主要集中在车辆的运输路经最短或总运费最 小进行讨论，忽视了车辆调度的优化目标的多样性。 ( 2 ) 目前对路径优化的研究主要集中在不可重复运输上面。这种方法对于车 辆的运输成本考虑的还欠周全，还需进一步改进和完善。 ( 3 ) 随着对集货送货一体化的要求越来越多，原有的方法由于不能充分考虑 7 青岛大学硕+ 学位论文 车辆的行驶成本，造成了大量的运输成本。 ( 4 ) 对集货送货的时间的要求使我们在路径优化的时候要考虑时间窗的限制， 在这方面还需深入研究。 ( 5 ) 对于车辆的利用，多限制在用同一类型的车辆上，考虑到各车辆路线的 货物量不同，同一类型的车辆的使用不利于车辆的利用率的提高，因此应该增加 不同载重量的车辆，当然势必会增加路线的设计难度。 本文拟研究内容主要集中在以下几点： ( 1 ) 考虑到车辆数量会对运输成本造成很大的影响，构建可重复运输的路径 优化模型，降低车辆的使用数量，为企业在安排车辆路径的时候提供一种新的参 考模型。 ( 2 ) 构建一个为可重复运输的判断依据，提供一种解决可重复运输的路径优 化的方法。为企业减少行驶车辆、降低运输距离提供一种简单可行的解决办法。 ( 3 ) 针对集货配送一体化的特点，根据企业对时间要求的严格程度，对运输 问题，从无时间窗和有时间窗两个方面来提出解决一体化运输的问题，将时间窗 和集货量与配送量之差，经过整合转化为成本，通过节约式算法的思想来形成路 线形成的依据。 ( 4 ) 以从物流中心出发车辆的方式进行运输，针对该问题，设计一个案例，通 过案例的形式来证明算法的可行性。 具体内容见图1 - 1 所示。 8 第一章绪论 研究背影与意 基于可重复运输 的解释镧制研究 i 否 弋竺少是 ， v 旦- l 黧翥嚣卜一 、 “ 丫 否 无时间窗的集送 时间窗条件下集 一体化研究 洪一体化研有 1 r 得出结论 图1 - 1 本论文结构图 本文解决问题拟采取的方法： ( 1 ) 在路径优化的研究中，不同的方法有不同的优点，我们根据各种算法 的特点，选用启发节约式算法来解决运输过程中产生的路径优化问题。 ( 2 ) 在选用启发节约式算法的同时，本文也借鉴其它算法的优点，混合使用， 改进启发式算法，使这种方法更适合实际需要，以便于获得更优的解。 ( 3 ) 由于车辆的运营费用远远大于车辆行驶路程的费用，我们把车辆的数 目也作为一个重要的指标，本文对目标函数进行修改，不把路程作为唯一的指标， 使问题更加贴近实际需要。 ( 4 ) 根据选用的方法的不同，本文选用一定的案例计算结果进行比较，来比 较不同解决思路方法的可应用性。 9 青岛大学硕士学位论文 第二章基于可重复运输的路径规划研究 2 1 问题简介 路径优化问题是指行驶尽量少的路程来完成所有的任务。通过载重量一定的 车辆对每一个结点完成集货或配送等任务，其中每一个结点都有一定量货物的供 给或需求任务。它要求不能超出车辆的载重限制，同时尽量使车辆行驶距离最短。 国内外对路径优化的研究主要集中在启发式算法，遗传算法、模拟退火算法、禁 忌搜索算法和蚁群算法几个方面。 目前国内外大部分的研究将注意力放在不可重复运输上，即每项任务只能有 某一辆车来完成，这样虽然降低了研究的复杂度，但同时也可能会造成需要更多 的车辆来完成运输配送的任务，由于出动一辆车的固定成本远远大于车辆的一定 里程内的行驶成本，对于一个具体的问题，寻求能完成任务的最少车辆数是减少 成本的有效方法。实际上有的时候一个任务点在被两个车辆服务时，不但会减少 车辆的使用数目，并且可能还会使总路程减少，进而降低总的运输费用。因此， 寻求在最少车辆的情况下，来降低行车距离就是本章节将要研究的内容。 节约法的基本思想可以以图2 1 表示，以c 妒表示车辆从点i 行驶到点_ ，的距 离，得到点i 和点歹连接在一条线路上的费用节约值勺= + c 0 一c _ f 。把c ： 排列 成序，在安排路线时，尽量首先安排节约值大的，这样使总路程最少。若超出车 辆的行驶里程或者超出车辆的载重限制，则结束这条路线，重新进行选择。 集货中心0 图2 1 连接任务点前后的路线比较 在传统节约算法搜索合并中，每次都是取m 内的第一项，即节约值最大 1 0 第二章基于可重复运输的路径规划研究 的那个，考察它们的货物量是否满足车辆的载重要求，然后确定合并两个结 点之间的路线与否。这样仅仅是考虑了合并过程中的局部最优性，没有考虑到整 体最优性。为降低这种局部最优性，我们在实施车辆合并后，考察其车辆的剩余 载重量与总任务的尚不满足一辆车的货物量，根据大小，确定是否进行下一步的 货物收集任务，来进一步完善路径，降低空载率。 可重复运输的可行性依据参见图2 2 。 八 ( 2) u 图2 2 实施可重复运输前后比较示意图 用圆表示客户。假设，车辆到达客户1 之后，剩余的车辆容量已经不能够再 完全容纳客户2 和客户3 的货物；同理，车辆在到达客户3 之后也不能再完全容 纳客户2 的货物，按照传统启发式算法，这时需要三辆车来运输，总路程为： 六一2 c o l + 2 c 0 2 + 2 c 0 3 而可重复运输的路径优化如图二所示，所用车辆为两辆，总路程为： 厶一c 0 1 + c i 2 + c 0 2 + c 0 2 + c 0 3 + c 2 3 实际上， 一厶可表示为厂，厂；万一，2 。c o t + c 0 3 一c 1 z c 2 3 ；厂可能大于 f 厂o 时，车辆减少一辆，路程减少厂 等于零或者小于零，l 厂 o e 寸- ，车辆减少一辆，路程增加厂； 可见，在这种情况下降低车辆的使用数量，并且在按照某种原则选择结点时， 也会降低路程。当路程增加，时，但车辆的运营权数高于车辆配送距离的权数， 所以由于车辆数的降低，总费用也会降低。在进行选择任务点时，有一个需要遵 循的原则，就是尽量把重复运输的点延后，这样一方面可以在保证车辆数量最少 的前提下，能不重复运输，就尽量单独运输，以降低运输的距离。这是因为，以 原线路最后一点f 为例，重复集货点，和集货点0 为例，进行重复运输，必然比 青岛大学硕十学位论文 原来线路多的里程数为：勺+ c j o q o ( 单条线路) 。 2 2 可重复运输路径规划模型构建 2 2 1 问题描述 假设有一个物流集货中心，编号为o ，拥有多台载重量为q 的车辆。现在有 m 项货物运输任务需要完成，以1 ，2 ，f ，m 表示，已知任务i 的货运量为 g i ( f = 1 ，2 ，m ) ，r g i q ，并修改收集点j 的货物收集量为q 一吁，同时， 令反= 0 ，转s t e p 3 ，否则转下步； s t e p 7 ：令膨= m ，转s t e p 3 通过案例，我们可以发现，本方法是可行的。 2 3 案例分析 某一集货中心向1 2 个客户i ( f = 0 ，1 ，2 ，1 1 ，1 2 ) 收集货物，各客户的收 集量毋( 单位：吨) 由表1 给出，集货中心0 及各客户间的距离( 单位：公里) 由表 2 给出，这些集货任务由集货中心发出的容量q = 3 吨的车辆来完成，并且每辆车 运行最大路程为l = 1 0 0 公里。把各点间的距离作为费用，试制定最优的集货路线。 1 5 青岛大学硕+ 学位论文 表2 - 1 各客户需要收集的货物量( 单位为吨) 客户i 1 234567891 01 11 2 需求量t0 81 50 8o 71 41 50 6 0 80 70 61 1 1 3 表2 2 集货中心与各客户中心之间的距离( 单位为公里) c ： l - 0 z2 1z2 2l2 3 z2 4z2 5l8 6 z 。7 l 。8 z 9l 。1 0 z 。1 11 。1 2 1 = 0o 1 097888341 0751 7 ，= 1 1 00491 41 81 81 31 4 1 1467 ，：2 94051 01 41 71 21 31 5897 - 3 7950591 51 01 11 71 31 18 ：4 81 41 05061 31 11 21 81 591 0 = 5 81 81 496o71 01 21 81 51 19 ，= 6 81 81 7 1 51 3 70681 71 51 21 0 ，：7 31 31 2 1 01 11 06 021 11 01 01 4 ，：8 41 41 31 1 1 21 28 2091 151 2 _ ，= 9 1 0 1 1 1 51 71 81 81 71 1 9 0886 ，= 1 0 7 4 81 31 51 51 51 01 1801 01 2 ，= 1 1 5691 191 121 0581 0d8 ，= 1 2 1 77781 091 01 41 261 280 传统方法可以得到表2 - 3 优化路径数据： 表2 - 3 传统方法路径优化数据 线路结点 运输距离( k m )载重量( t ) 空载率 1 o 一9 1 2 1 o3 32 86 7 2 0 2 3 4 。02 73o 3 0 6 5 02 32 93 3 1 6 第二章基于可重复运输的路径规划研究 40 1 1 7 8 02 12 51 6 7 50 1 0 0 1 4o 68 0 合计 1 1 81 1 8 2 1 3 ( 平均) 经过我们的可重复运输，我们可以得到表2 - 4 优化路径数据： 表2 - 4 可重复运输路径优化数据 线路结点运输距离( k m ) 载重量( t ) 空载率 10 9 1 2 1 0332 86 7 2 0 2 3 4 0 2730 30 5 6 7 024 3 0 40 1 0 1 1 7 8 o3330 合计 1 1 711 8 1 6 7 ( 平均) 根据对比数据，我们可以发现重复运输能够极大的提高运输效率，降低了我 们的运输成本。 可重复运输给我们提供了一种解决路径优化问题的新的思路和方向，为我们 解决更复杂问题，如集送一