（载运工具运用工程专业论文）基于禁忌搜索算法求解带时间窗的定位路线问题研究.pdf

摘要 近年来，物流业在我国取得了较快的发展，物流专业化水平得到了较大的提高，如 何有效降低物流成本成为企业越来越重视的问题。随着现代社会人们生活节奏的加快， 为提高企业的生产效率，各企业对物流的服务时间要求更加严格，特别是以现代物流发 展最新模式精益物流以及即时配送( j u s th 1t i m e ，j i t ) 为原则的物流系统，时间要 素变的越来越重要。在传统物流决策过程中，物流设施的建设位置及运输车辆的行驶路 线问题是引起广泛关注的两个方面，但出于物流活动集成化要求，设施选址和车辆行驶 路线必须同时考虑，才能有效降低物流成本，基于此因素考虑，本文研究两者的组合优 化问题定位路线问题，同时将时间窗引入，有利于满足企业对服务时间的要求。因 此本文对带时间窗的定位路线问题进行研究具有一定的理论价值和现实意义。 本文对多站点、带时间窗的定位路线问题进行了研究。首先从物流基本概念入手， 阐述了定位配给问题、车辆路线问题和定位路线问题的相关含义、分类及数学模型。然 后，通过在基本的定位路线问题模型的基础上添加时间窗约束建立了带时间窗的定位路 线问题的数学模型，并运用l i n g o 软件和较小规模的数据对该模型的正确性进行了验证。 对大规模数据的带时间窗定位路线问题设计了禁忌搜索算法来求解。禁忌搜索算法 的特点是禁止重复前面的工作，为了回避邻域搜索陷入局部最优的不足，禁忌搜索算法 用一个禁忌表记录已经到达过的局部最优点或达到局部最优的一些过程，在下一次搜索 中，利用禁忌表中的信息，不再或有选择地搜索这些点或过程，以此来跳出局部最优点。 通过在相同的条件下和l i n g o 计算结果及国内研究学者的研究结果比较发现，本文设计 的禁忌搜索算法求解速度较快，解的精度较高。针对不同规模数据的问题，利用车辆路 线问题的国际标准测试数据构造了2 5 个点、5 0 个点、1 0 0 个点、1 5 0 个点的带时间窗的 定位路线问题的测试数据，通过测试分析，本文所设计的算法稳定、求解速度快，从而 证明了本文设计算法的有效性和可行性。 关键词：物流，定位路线问题，时间窗，禁忌搜索算法 a bs t r a c t h lr e c e n ty e a r s ，l o 百s t i c sd e v e l o p e dv e r yf 酤ti i lo u rc o u 蛐s p e c i a l i z a t i o nl e v e lo fl o 百s t i c si m p r o v e d g r e a t l y 孤dh o wt or e d u c e1 0 9 i s t o c sc o s tb e c o m e 锄i m p o r t a n tp r o b l e mf a c i n gb yc o m p a n y s w i mm c d e v e l o p r n e mo fm o m d e nl i f er h y t 锄di i lo r d e rt oi n l p r o v em ep r o d u c t i o ne m c i e n c yo fc o m p a l l y l o 垂s t i c ss e r v i c et i m eo fe v e 叫c 伽叩a n yb e c o m em o r es 仃i c t ，s o ，t i m eb e c o m em o r e 孤di n o r ei m p o r t a n t ， e s p e c i a l l yl o 百s t i c ss y e s t e ml l s i i l g l a t e s tl o g i s t i c sn l o d e ，l e a i ll o g i s t i c sa n dj u s ti i lt i m e l e o h lm e 仃a d i t i o n l o 酉s t i c sd e c i s i o n - m k i i l gp r o c e s s ， m el o c a t i o no fl o g i s t i c sf a c i l “i e s孤dm ef o u t 啦o f 呻o n a t i o n v e 址c l er e c e i v e dr e s e a r c h c r s d b r o a da n e t n i o n ，b e c a u s eo fm ei n t e g m t i o no fl o 舀s t i c sa c t i 、，i 吼 0 n l yf a c i l i t ) ，l o c a t i o n 锄d 慨塔p o r t a t i o nr o u t ec o l l s i d e rs i i i l u l t a l l e o u s l y 龇c o s to fl o g i s t i c sc mr e d u c e d e 虢c t i v e l y b a s e0 nn l i sc o i l s i d c r a t i o n ，n l i sp a p e rs t l l d ym ec o n l b i n dp r o b l e mo f t l l ea b o v ep r o b l e m l o c a t i o n r o u t i n gp r o b l e m ，锄dw ea d dm et i m ew i i l d o w sm i tt 0m a k ei tc l o s et 0t 1 1 er e l 瓠t i c s s o ，i ti so ft i l e o r e t i c a l a n dp m c t i c a ls e i l s e st 0s o m ee x t e n tt 0 咖d yt l l e1 0 c a t i o nr o u t i n gp r o b l e mw i mt i i ，1 ew i n d o w s 7 i 1 1 eo b j e c to f “sp a p e ri st or e s e a r c ht h ei n u l t i p l e d 印o tl o c a t i o nr o u t i n gp r o b l 锨w i m t i m ew i n d o w s i ti n t r o d u c e sb a s i ck n o w l e d g eo fl o 百s t i c s ，d e v e l o pt h em e a n i n g ，c l a u s s i f i c a t i o n m l dm o d e lo fl o c a t i o na l l o c a t i o np r o b l e m s ，v e h i c l er o u t 洫gp r o b l 锄sa 1 1 dl o c a t i o n r o u t i n g p r o b l e m s 血s t 血l dt h e n ，b a s e do nl o c a t i o nr o u t i n gp r o b l e m ，t h i sp a p e rf o u i l d st h em a t h m o d e lo ft h el o c a t i o nr o u t i n gp r o b l 锄w i t ht i m e - w i n d o w sb ya d d i n gt h et i m ec o n s 仃a i n to ni t ， a i l dc h e c k sm ec o r r e c t n e s so ft h i sm a t hm o d e l i ns m a us c a l ep r o b l e mu s i n gl i n 9 0s o 胁a r e m s p 印e rd e s i 印st a b us e a r c ha i g o r i t l l i i lt os o l v el r p t 、矾l o c a t i o nr o u t i n gp r o b l 锄 w i t ht i m ew i n d o w s ) f o rl a 玛es c a l ep r o b l e m t h ec h a r a c t e r i s t i co ft a b us e a r c h “g o r i t hi s f 0 r b i dt h ew o r kh a sb e e i ld o n eb e f o r e h lo r d e rt oe v i t em eb a c k g r o u i l do fl o c a ln e i g h b o r s f i l e ds e a r c hi m m e r s ei n t om el o c a lo p t i m i z a t i o n t a b us e a r c ha l g o r i m mu s eat a b ul i s tt 0 m e m o r i z et h e1 0 c a l0 p t i m i z a t i o np o i n t sa i 】l dt h ep r o c e s so fi t ，w h e ns e a r c ht h ep o i mn e x tt i m e ， “m a k eu s eo fm ei n f o m l a t i o ns t o r e di nta _ b u1 i s t ，a n dn om o r eo rc l l o o s et h e s ep o i n tt os e a r c h ， i no r d e rt oj u m pf r o mt h el o c a lo p t i m i z a t i o n a r e rc o r n p a r em er e s u l to fo u rm e t h o da n d l i n g os o f 撕a r e 肌do t h e rd o m e s t i cr e s e a r c h e r s ，w ef o u n dt h a tt h ed e s i g n e dt a b us e a r c h a l g o r i t h mi s 凰t e ra 1 1 dm o r ea c c u r a t em a l lo t h e rm e t h o d s f o r t h ed i 腩r e n ts c a l ed a t ep r o b l 锄， w ec o n s t m c t e d2 5 p o i n t s ，5 0 p o i n t s ，1o o p o i m sa n d15 0 p o i n t sf o rt h el r p t wf i o mt h e i n t 锄a t i o n a ls t a l l d a r dd a t eo fv r p a r e rt e s ta n da n a l y s i s ，w ef o u n dt h ed e s i 笋e dt a b us e a r c h a l g o r i t h mi ss t a b l e ，s p e e di sq u i c k l y ，i tp r o v e sv a l i d a t ya n df e a s i b i l i 妙o fd e s i 朗e da l g o r i t h m - k e yw o r d s ：1 0 9 i s t i c s ；l o c a t i o nr o u t i n gp r o b l e m ；t i m e - w i n d o w s ；t a b us e a r c ha l g o r i t m 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究 工作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任 何未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：魏睦暇 知。歹年产月艿日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 敝作者签名：弧啦q 2 0 0 罗年尹月多箩日 导师签名：铜衣中 卵7 年乒月2 罗日 长安人学硕士学位论文 1 1 选题的背景和研究意义 第一章绪论弟一早三百t 匕 物流产业在国际上被喻为促进经济发展的“加速器”，并将对中国经济的健康发展 产生积极的影响。物流产业的发展之所以受到国际社会的广泛重视，其原因在于物流产 业的发展对现代社会的经济发展具有重要意义，并成为促进经济发展的“催化剂 。首 先，物流产业发展在促进制造业降低产品成本，提高经济效益的同时，调整了传统的粗 放型的经营组织形式，有助于制造业企业提高核心竞争能力。其次，物流产业的发展能 够促进新型商业企业和业态形式的发展。第三，物流产业能够促进运输服务方式的创新 和传统运输企业的发展。第四，物流产业发展还会带动和促进许多相关领域的发展，如 物流设备制造行业、以互联网技术为基础的电子商务的发展等【l 】。 物流是一个复杂的系统，根据国家标准g b 1 1 8 3 5 4 2 0 0 6 中华人民共和国国 家标准物流术语，物流是“物品从供应地到接收地的实体流动过程，根据实际需要， 将运输、储存、装卸、搬运、包装、流通加工、配送、信息处理等基本功能实施有机结 厶，【2 】 口 。 物流中心选址作为物流运作的基础，对物流总成本影响较大，并且对整个地区和城 市的经济发展影响深远。 物流中心的建立基于以下几个条件：城市之间经济交往促进物流量的急剧增加， 给物流中心提供了设立的可能性。物流配送系统的广泛建立，使物流中心之间的干线 运输与在城市区域内的配送有效的组合成新型的现代物流系统，从而完善了整个物流系 统。城市环保与可持续发展促进物流中心的建立，通过合理的物流规划和物流组织， 限制汽车在城市中的运行时间和运行数量，减少货运铁路、专用线、货运站场在城市内 的占地等，促进城市可持续发展。科技进步对物流中心提供了全方位的科技支持。例 如，完善的计划系统可以对时间做出精确的安排，有效地末端物流系统可以保证集货、 配送的准时，先进的装卸系统可以实现多种形式的火车与汽车之间直接衔接，计算机网 络可以保障各个业务环节的畅通等。 物流配送作为物流系统的重要组成部分，对其进行优化研究也可以大大降低物流费 用。物流配送是指在经济合理区域内，根据用户要求，对物品进行拣选、加工、包装、 分割、组配等作业，并按时送达指定地点的物流活动【2 1 。物流配送过程主要包括以下作 第一章绪论 业环节：从生产工厂进货并集中的集货作业；根据各个客户的不同需求，在物流中心将 所需要的货物挑选出来的分货和配货作业；考虑配送货物的重量和体积，充分利用车辆 的载重和容积的货物配装作业；合理确定车辆配送路线并及时送货的作业。由此可见， 物流配送是一种集集货、分拣、配货、配装、送货等多种功能为一体的物资流通方式。 由于配送是对顾客服务的最后一环，因此，配送的地位十分突出。配送中心是连接 工厂与客户的中间桥梁，其选址方式往往决定着物流的配送距离和配送模式，进而影响 着物流系统的运作效率。因此，研究物流配送中心的选址具有重要的理论和现实应用意 义，所建立的配送中心能实现快速而准确的配送是企业在经营方面必须解决的重要课 题。 在物流配送业务中，配送车辆的调度问题涉及面较广，需要考虑的因素较多，对提 高配送服务质量、降低物流成本、增加经济效益的影响也较大。车辆调度作业的重点是 如何将车辆有效的使用并决定其最经济的行驶路线图，使得商品能在最短的时间内送到 顾客的手中。消费者需求的多样化，与商品生命周期的缩短，使得送货时间日趋苛刻， 加上交通负荷繁重，停车、卸货困难，更加体现出问题的严重性。目前，城市物流配送 面临如下问题： ( 1 ) 服务水平与质量较低。 信息流与物流的矛盾会导致整个电子商务服务水平低效。电子商务要求有与其相对 应的快速、高效的物流配送体系。 ( 2 ) 控制物流成本困难。 人工调度的传统物流配送活动只适合在交易量较小的系统中运作。面对巨大交易量 的电子商务环境，需要建立合理的、自动的物流配送调度系统。 ( 3 ) 影响城市交通状况。 物流配送调度的不合理，会增加物流配送的运行车次与路程，从而加重城市交通运 输的负担。因此，建立合理的物流配送调度系统，有利于缓解拥挤的城市交通。 可见，对物流配送作业的优化意义重大。而事实上，车辆后期的路径选择和前期物 流配送设施的选择有着密切的联系，前期选址的结果直接影响后期的路线安排。为了从 整体上优化物流配送渠道的服务质量，可以从前期选址阶段就结合后期的车辆路径选择 对配送渠道进行全面优化。 由此，出现了结合设施定位和运输路径选择的设施定位一运输路线安排问题 ( l o c a t i o nr o u t i n gp r o b l e m s ，u 冲) 。由于u 冲从集成物流系统整体出发，以系统的眼光 2 长安大学硕士学位论文 分析研究物流系统的优化问题，从而能够达到优化物流系统整体的目的。所谓集成化物 流系统就是要求我们在一个整体的基础上以集成的观点来考虑问题，而不是单个地隔离 开来考虑系统的某一个组成部分。单个的局部的最优不等于全局的( 即系统的) 最优。 本文要研究的带时间窗的定位路线问题( b c a t i o nr o u t i n gp r o b l 锄sw i mt i m e w i n d o w s ，u o t m 正是在这一思想的指导下进行的。本文要研究的u 理问题，而不是 以往单独地考虑车辆运输路线冲( v e l l i c l er o u t i n gp r o b l e m ) 和设施定位“心( l 0 c a t i o n a 1 l o c a t i d np r o b l 锄) 。显然这样更有利于整个物流系统最优化的实现。同时，由于现代社 会人们生活节奏的加快，以及为提高企业的生产效率，各企业对物流的服务时间也提出 了更高的要求，特别是作为现代物流发展最新模式精益物流，我们将时间窗引入 l l 冲这样更贴近实际情况，更便于在现实中的应用。现实中此类问题很多，典型的有宅 急送速递业务，在扩展业务建立网点的时候要考虑服务顾客的时间。还有牛奶加工企业， 在确定分销处的位置时，需要同时考虑在规定时间内将鲜奶送往客户终端这个因素，以 使在满足客户需求的前提下达到利益最大化。不仅在牛奶加工企业，其他各种鲜活货物 配送企业往往都会遇到同样的问题。 1 2 国内外研究现状 1 2 1 国外研究现状 关于u 冲概念的研究可以追溯到1 9 6 1 年v o nb o v e n t e r 关于运输问题中的运输成本 和设施选址成本的相互关系【3 】o 早期研究一般是集中在l r p 的复杂性方面，后来才逐渐 意识到选址定位和运输决策之间的协调性。到7 0 年代末，8 0 年代初，伴随着集成系统 物流概念的出现，l i 冲才开始逐渐被重视，但是其发展速度依然缓慢。直到8 0 年代以 后，由于实际应用和计算机的快速发展，u 心的研究才有了真正意义上的发展。典型的 代表是1 9 8 6 年l a p o n e 关于u 冲精确解法的描述【4 1 。从此以后，各国学者从l r p 模型 的扩展问题和其解法等方面进行深入研究，例如： t u z u i l 等给出了两阶段禁忌搜索启发式算法求解l i 诤问题，其算法结构能对解空 间进行有效搜索，但其模型未考虑设施容量约束【5 】oy u p oc h a l l 和w i l l i 锄b c a n e r 等人 运用s f c ( s p a c ef i l l i n gc u r s e ) 法来求解多设施、多运输车辆的随机型u o 模型【6 1 。w u 等采用两阶段模拟退火启发式算法求解具有多种类型车辆且数量给定的l r p 问题1 7 j 。 b o u l l a f s 和l y a i l l i n e 用模拟退火和蚁群组合算法求解了两阶段定位路线问题【8 1 。l i l l ， c k y 和k w o k ，r c w 对模拟退火算法和禁忌搜索算法求解定位路线问题进行了比较【引。 3 第一章绪论 b a 仃e t o ，s e 晤。用聚类分析法解决了带容量约束的定位路线问题【1 0 】。r d s e m a r yt ，c o l l e t t e r ，m a r ks 用分枝定价算法( b r a n c h a n d p r i c e ) 求解了具有1 0 个潜在设施、1 0 0 个客户节点 的带距离约束的l r p 【l l 】。r o b e r tr u s s e l l ，w b n c h ”a i lc h i a n g ，d a v i dz 印e d a 采禁忌搜索算 法针对v r p 中涉及大量多品种印刷品具有时间窗约束的配送问题进行了有效求解【1 2 】， 求解过程中考虑了地域因素的影响。 表1 1 【l3 】总结了近年来各国学者对u 心所研究过的问题： 表1 1 近年来l r p 研究过的问题汇总表 问题类型相关文献 随机l i 冲 l a p o r t ee ta l ( 1 9 8 9 ) 动态l r p l a p o r t ea n dd e j a x ( 1 9 8 9 ) h 觚n i l t o n i a np 中值b m 】oa n dc o e m o ( 1 9 9 0 ) 道路一车辆路线 s e m e t ( 1 9 9 5 ) 车辆路线配给问题m p ) n a s c i m 肌t oa 1 1 db e a s l e y ( 19 9 6 ) 多点对多点的l r p 问题 n a g y a l l ds a l k ( 1 9 9 8 ) e u l e r i a i l 定位问题 a i l i 姐dl a p o n e ( 1 9 9 9 ) 带混合车队的l r p 问题w ue ta 1 ( 2 0 0 2 ) 定位一路线一库存 l i ua 1 1 d l e e ( 2 0 0 3 ) 工厂循环定位问题p c l p l a b b ee ta 1 ( 2 0 0 4 ) 多点对多点的l r p 问题w a s n e r 锄dz a p f e l ( 2 0 0 4 ) 多级定位路线仓储问题 知n b r o s i n oa i l ds c u t e l l a ( 2 0 0 5 ) 确定型l r p a l b a r e d a s a n l b o l ae ta 1 ( 2 0 0 5 ) v r a p ( 中值环问题m c p )l a b b ee ta 1 ( 2 0 0 5 ) 带非线性成本的l r p 问题m e l e c h o v s 埘e ta 1 ( 2 0 0 5 ) 平面l i 冲( 单设施点) s c h w a r d ta n dd e 也l o f f ( 2 0 0 5 ) 多约束的v r a pg u n n a r s s o ne ta 1 ( 2 0 0 6 ) 平面l r p ( 多设施点) s a l h ia n dn a g y ( 2 0 0 7 ) 虽然l r p 的发展经历了不短的时间，但是l r p 作为一个包含了两个n p 难问题的 n p 问题仍然有很多问题没有解决。最关键的一点就是作为l r p 子问题的l ”和v r p ， 这二者是相互关联的，它们之间在这个系统中相互影响，但是很多学者却忽略了这一点。 因此，作为u 心拓展问题的l r p t w 的研究更是为数不多。多数都是将l r p t w 分成 l a p 和v r p t w 进行分别求解，如i 沁b 瞰r u s s e l l ，w e n c h ”a nc h i a l l d a v i dz 印e d a 采 用禁忌搜索算法针对v i 冲中涉及大量多品种印刷品具有时间窗约束的配送问题进行了 有效求解 1 2 】。 1 2 。2 国内研究现状 国内关于l i 冲问题的研究文献较少，汪寿阳、赵秋红是最早在国内开始l r p 问题 4 长安大学硕士学位论文 研究的学者，两人2 0 0 3 年的论文详细介绍了国内对于集成物流管理系统中u 冲问题的 研究进展，分析了u 冲的主要内容和特征，提出有关求解问题的算法分类，并对以后 该领域的研究方向提出了几点建议【1 4 l 。张潜、高立群等从算法优化的角度出发，对l i 理 问题中的定位配给、运输车辆路线安排、定位一运输路线安排三类问题的具体优化方法 进行了分析和比较，并在此基础之上提出两阶段启发式算法来求解u 渖问题【1 5 】。张长 星等用遗传算法求解了定位一运输路线安排问题【1 6 】。张潜、高立群等提出了基于最小包 络聚类分析及带有控制开关的遗传算法的两阶段启发式算法来解决u 心问题【1 7 】。邱晗 光、张旭梅运用基于遗传算法、模拟退火算法的改进粒子群算法，对一个开放式定位一 运输路线问题进行了求解【1 8 】。胡大伟、胡勇、朱志强等人利用空间填充曲线和动态规划 法对定位路线问题进行了求解【1 9 l 。徐丽蕊、胡大伟、林晖钢等人用禁忌搜索算法求解了 多站点的定位路线问题【2 们。 9 0 年代以来，随着集成物流管理的概念被愈来愈多的企业所接受和全球贸易的快 速增长，提高分销效率成为了企业生存与发展的必由之路，l r p 的研究在各相关领域得 到了特别的关注，对u 冲的研究主要是向以下几个方向发展【1 5 2 1 】： ( 1 ) 随机性 目前多数u 强的研究都局限于具有确定性参数的模型，实际上，客户数量、需求、 位置以及车辆的运输时间等事先并不一定知道，应把它们当作随机变量来看待。故未来 的研究应考虑可能存在不同的客户需求方式以及车辆运输时间的变化等随机性因素。” ( 2 ) 时间窗 目前很少文献考虑带时间窗的u 冲，但实际问题中有些客户的服务是有时间限制 的，特别是在以及时配送( j u s th lt i m e ) 为原则的物流系统里。目前国内有马小伟【2 2 】将组 合的启发式算法引进带时间窗的l i 心问题进行了求解。 ( 3 ) 多计划期间 现有的u 冲研究多为开发静态的模型，很少分析l i u 参数随时间变化的特性。例 如，随着仓库雇员工资和利率的波动，仓库定位的成本将随时间变化。再如，在一定的 时间范围内，公司需要根据情况的变化来重新决策设施的定位、运输路线及运输车辆的 调度。也就是说，l r p 参数具有时间敏感性的内在特点。因此，在l i 冲模型中加入动 态特性，在实时或在线物流管理中，会极大地提高与现实接近的程度。 ( 4 ) 多目标 实际的物流系统中，不管是在专用部门还是公共部门，普遍存在着相关联的多个目 第一章绪论 标。例如，最小成本的路线安排，最初以客户代码在空间的分散情况为基础，可能会不 满足客户对及时配送服务的需求。因此，尽管问题的难度会加大，未来的l r p 应解决 多目标决策的问题。 ( 5 ) 增值供应链的垂直方向集成 设施中的物流活动分为两个不同的区域，货物的入站流动( 货物的收集) ，货物的出 站流动( 货物的配送) 目前的研究多为试图建立出站或入站最优路线的安排，而不是同时 考虑这两个方面，未来的研究应建立多阶段的决策模型，即通过探讨出站和入站流之间 的相互关系，对收集和配送的顺序进行决策，使供应链在垂直方向的价值增加，并通过 整个供应链对其决策效果进行监控。 ( 6 ) 多方物流运作的水平方向集成 由于问题的复杂性增加，时至今日很少有文献分析定位、运输路线和存货控制之间 错综复杂的关系。需要指出的是，u 心模型应探讨定位、路线安排、存货控制决策之间 的相互作用。例如，库存水平对仓库的容量和数目有很大的影响，同时对运输模式的选 择和路线安排也有很大的影响。因此，未来的l i 冲应考虑定位、运输和库存之间的关 系。 1 3 本文的研究内容 本文核心内容包括两个方面：一是物流配送系统中l i 冲t w 数学模型的建立；二是 针对该类模型的禁忌搜索算法设计研究。首先，通过对物流配送系统进行分析；在此基 础上进行l r p 相应的数学理论模型( 如定义、目标函数、约束条件) 介绍和建立其扩 展模型，采用小规模数据运用“n g o 软件对建立的理论数学模型进行检验。其次，模型 确认无误后，对系统模型进行算法设计，并运用相应的算法语言( 如c + + ) ，采用大规 模标准测试数据( 如s o l o m o n 数据) 进行测算。在实际操作过程中，我们对该求解方法 ( 如邻域的构造) 进行了相应改进，以便于所求优化解与最优解更加接近。 1 4 本文的研究方法 1 4 1 本文的求解方法 本文将重点研究大规模u 冲t w 的模型及求解其的禁忌搜索算法。其目标是针对物 流配送特点，建立满足物流配送的u 心t w 模型并找出有效算法。由于l r p t w 问题属 于n p - h a r d 问题，运用常规优化方法难以进行求解，故采用启发式算法对所建立的理论 6 长安大学硕士学位论文 模型进行算法设计。相对于其他启发式算法而言，禁忌搜索算法能够跳出局部最优，具 有收敛速度较快、计算效率较高、求解质量好等优点，国内已成功将其应用于生产调度、 车辆路线问题、电网重构等方面，结合禁忌搜索算法的优点和其成功应用的基础，本文 采用禁忌搜索算法( t a b us e a r c h ) 对大规模l r p t w 进行求解。求解过程中，对智能算 法中的参数进行数值模拟计算，找出较好的参数搭配，分析算法对解的质量影响，并对 s o l o m o n 标准测试数据进行相应改造，计算测试结果。同时通过l i n g o 软件验证建立的 数学模型和进行小规模测算对比分析，通过计算机编程，在可接受的计算时间内得到满 足一定精度的相对优化解，为解决城市物流大规模选址一配送问题奠定理论基础。 1 4 2 本文的技术路线 本文的技术路线如图1 1 所示。 图1 1 本文技术路线图 1 4 3 本文的实验方法 运用l i n g o 软件检验建立模型的正确性，数据采用s o l o m o n 系列标准测试数据，并 进行选择构造。大规模问题求解运用c + + 语言编程计算，并与其他学者的l r p t w 模型 的计算结果对比，以验证模型和算法的有效性和先进性。 7 第二章定位配给问题及车辆路线问题 第二章定位配给问题及车辆路线问题 现代企业的生产和运作过程中，对成本的严格控制是企业生存的根本。为了在众多 竞争对手中保证价格成本上的优势，提高产品的竞争力，必须对物流成本进行严格的控 制。在降低物流成本的过程中，定位配给问题和运输路线安排问题是得到较多关注的两 个方面。 2 1 定位配给问题 为了降低运输成本、加强作业效率，对设施的评价和选择成为配送业非常重要的决 策之一。l a p 考虑设施( 工厂、库存点、配送中心等) 的定位与货物配给之间的相互关系， 通过在已有的候选设施中选择合理的服务设施点数量、位置，并将需要服务的客户点分 配给这些服务设施点，使得服务设施的运作成本及车辆的运输成本最低。 2 1 1 定位配给问题的定义 l a p 可定义为：依据客户点的地理分布与货物分配关系，确定出某一地理范围内设 施的数量和位置，目的是对设施的数量、位置进行决策，使设施的运作成本及车辆的运 输成本最低2 3 1 ，如图2 1 所示。在l 垤中，一般认为设施到客户的运输路线是放射线状 的，即运输车辆每次访问一个客户后，就返回到设施点。 o 表示客户叫 表示路线 图2 1l a p 示意图 2 1 2 定位配给问题的分类 l a p 实质上是一个依据优化路径的原则来确定在什么地方设置设施的过程。根据 j o l l l lc u r r e n t 等学者对此问题的综合研究剀，对l a p 问题进行了分类。c u r r e n t 的方法是 根据问题的目标函数来分类，作为分类依据的目标函数共分四种： 8 长安大学硕上学位论文 费用最小化； 客户需求导向； 利润最大化； 其它相关考虑。 2 1 2 定位配给问题的数学模型 定位配给问题的模型建立基于如下假设： 己知潜在设施( 配送中心) 的集合r 以及设施厂p r ) 的潜在位置； 己知客户点的集合、客户歹的位置及其需求量g ，( j ) 。 在建立模型时，如果潜在设施到用户的运输费用为g ；建设配送中心固定费用为 g ，；配送中心容量为k ；决策变量z ，表示客户，是否由配送中心，服务，是为1 ，否则 为o ；只9 足) 为是否在r 处建立设施，是为1 ，否则为o 。则定位配给问题( l a p ) 的 数学模型可表示为2 5 】： s t 咖q 乃+ g ，蚱 一一 qu 二一 ，。l r e r j j r e r z 哆= 1 ，歹， ，置 yr z 呼，r r ，j j ， 口，z 哆一，r ， j e j 乃= o ，1 ，兄， y ，= o ，1 ，r ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) 其中，( 2 1 ) 为目标函数，使得包括设施建设费用和由设施为客户提供服务费用的总 费用最小；约束( 2 2 ) 保证每个客户只由一个设施提供服务；约束( 2 3 ) 保证为客户提供的 设施一定是建立的设施：约束( 2 4 ) 确保由一个设施服务的所有客户的总的需求量小于设 施的容量；( 2 5 ) 和( 2 6 ) 是表示纫和只为o ，1 变量。 2 2 车辆路线问题 在已经建设好的服务设施的基础上，企业往往要决策每个设施服务客户的走行路 9 第二章定位配给问题及车辆路线问题 线，这样可以节约服务时间和提高效率，还能降低成本，这就引入对车辆路线问题强 的研究。 2 2 1 车辆路线问题的定义 冲可定义为：运输车辆从一个或多个设施到多个地理上分散的客户点，优化设计 出一种货物运输路线方案，前提是要满足一系列的约束条件。该问题的前提条件是设施 位置、客户位置和道路情况已知，由此确定车辆运输路线方案，以满足目标函数和约束 条件的要求【2 6 】。v r p 示意图如图2 2 所示。 o表示客户叫表示路线 口表示设施 图2 2 心示意图 2 2 2 车辆路线问题的分类 车辆路线问题可按照约束条件的不同划分为不同的类别【2 7 矧： 有容量限制的车辆路线问题( c a p a c i t a t e d 强，c 冲) 在c 强中，所有客户的需求量都是预先确定的，而且不能分割配送，站点单一且 只有一种车型，车辆有容量限制，即车辆服务客户的总需求不得超过其最大容量，目标 是服务所有的客户使总费用最小。 带时间窗的车辆路线问题( r pw i t l lt i m ew i n d o w s ，v r p t w ) 客户对服务的时间有确定要求，最早服务时间和最迟服务时间限定了车辆服务的时 间段，即每一客户只能在一个确定的时间窗内才接受服务。 多车场的车辆路线问题m d 冲( m u l t i p l ed 印o tv r p ，m d v r p ) 有多个站点可以发车，来为顾客提供服务，且站点之间有交互性，需要统一规划多 个配送中心的路线。 送货集货一体化的车辆路线问题( v r pw i t hp i c k u pa n dd e l i v e r y ，v r p p d ) l o 长安人学硕士学位论文 在送货集货一体化的车辆路线问题中，每一个客户都有一定的配送量和集货量，对 每一个客户，车辆不仅要为客户送货，还要从客户处把货物带走并配送到其指定的客户 或站点，于是存在下面的优先约束：任一客户f 当满足其配送需求的货物源点，不是站 点时，必须早于客户f 接受服务；客户f 集货再配送的目标客户不是站点时，必须 晚于客户f 接受服务。 带回程取货的车辆路线问题( v 1 计w i t hb a c k h a u l s ，强b ) 带回程取货的车辆路线问题是经典车辆路线问题的一种延伸，它将客户分为两类： 配送客户( 有一定的货物需要配送) 和取货客户( 有一定的货物需要收集到站点) 。在 强b 问题中，配送客户和取货客户之间存在一个优先约束：在一条服务两类客户的路 线上，所有的配送客户必须早于取货客户接受服务。 分割配送的车辆路线问题( s p l i td e l i v e r y 姆，s d 姆) s d 心是指一个顾客可以允许多个车辆来提供服务。如当顾客的需求超过车辆的 最大载质量，或顾客需求多种类型的货物时等。 随机车辆路线问题( s t o c h a s t i c 姆，s 姆) 在冲问题中，当客户数、客户需求量、服务时间或旅行时间等因素中有一个或多 个因素是随机变化时，就变成了s v i 冲。 周期性车辆路线问题( p 耐o d i c 姆，p 婢) 周期性的车辆路线问题是将经典车辆路线问题中规划期由一天延伸至r 仃 1 ) 天， 在丁天内每一顾客需七次的配送( 1 七丁) ，车辆从站点出发在一天之内可以不返回站 点，在一个周期( 丁天) 内，每一个客户至少被访问一次。在顾客的配送次数、数量及 配送时期已知的情况下，需要针对z 天中的每一天进行车辆路线规划，以使得客户可以 获得应有的配送次数和数量，同时使得一个周期( 丁天) 内的总成本最小。p 冲不仅 需要解决一天内多车辆路线规划问题，还需要迸一步规划顾客配送时期的组合，因此 p v i 强比冲( m v i 冲) 问题更复杂。 2 2 3 车辆路线问题的数学模型： 车辆路线问题的模型建立基于如下假设： 物品流向为双向( 即涉及的设施或称仓库中的一部分既要有输入又要有输出) 。 供需特征满足确定型的特点( 指物品供应需求量是已知的，并在一定时期内相 第二章定位配给问题及车辆路线问题 对稳定) 。 运输工具数量为多车辆，同时满足单车的容量大于运输路线上客户的总需求量。 每辆车在完成全部运输任务后回到出发点。 目标函数为单目标，满足v i 冲的目标是总费用( 包括运输费用和车辆使用费用) 最小。 在建立如的数学模型之前，假设s 为客户和设施的集合( 0 表示设施) ，且客户 和设施均由f ，来表示，y 表示所有车辆集合；g 为节点f 到节点的平均运输成本； 劬为客户0 ) 需求量；q 为运输车辆尼的容量；决策变量啄( f ，s ) 表示车辆后是 否从节点f 向节点提供服务，是为1 ，否则为o ；虼为是否由车辆尼为客户f 提供服 务，是为1 ，否则为0 ；为辅助变量。则婚的数学模型为2 6 】： 坳 g + e 而豇 ( 2 7 ) 七e yi e 5 ，e s七e 矿 _ ，e s g j z 驰q ，尼矿， ( 2 8 ) l x 仕= y j j ，k v乙x 弘2y 挑，j j ，k y 拓s - x 潞：) ，珞，f ，尼矿 2 一x 班2y 雎，z ，七 j e s u 傲一uj kj 卜n x | j ksn 一1 ，l ，j j ，k y ， = o 或1 ，s ，七y ，f ， y 趾= o 或1 ，f s ，七y ， u 腩o ，后矿， 其中，( 2 7 ) 为目标函数使得包括运输成本和车辆使用成本的总费用最小；约束( 2 8 ) 为车辆容量限制条件；( 2 9 ) 表示每个客户只由一辆车提供服务；( 2 1 0 ) 和( 2 1 1 ) 表示每个 客户只能被访问一次；( 2 1 2 ) 为路线子循环约束；( 2 1 3 ) 和( 2 1 4 ) 表示和为o 、1 变量； ( 2 1 5 ) 为辅助变量约束。 1 2 d 动 筇 砷 $ ， 1 l l 1 1 1 0 q q q 仁 亿 仁 长安大学硕士学位论文 2 3 组合最优化问题及其解法概述 2 3 1 组合最优化问题 组合最优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是通过数学方法的研究去寻找离散时间 的最优编排、分组、次序和筛选等，是运筹学( o p e r a t i o n sr e s e a r c h ) 中的一个经典和 重要的分支，所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络 等诸多领域。 最优化问题的数学模型的一般描述是： 哩毋厂( 工) ， j e ， 其中，x 为决策变量，厂( x ) 为目标函数，为可行域，f 中的任何一个元素成为该 问题的一个可行解，满足厂( x ) = m i n 厂( 力i x f ) 的可行解茗+ 称为该问题的最优解， 对应的目标函数值( ，) 称为最优值【2 9 1 。 组合最优化问题的特点在于，可行域f 表示的是有限个点组成的集合。通常情况下， 可行域f 可表示为 x ix d ，g ( x ) o ) ，所以组合最优化问题的一般形式为： 池厂o ) ， s t g ( x ) o ， x d 。 因此，一个组合最优化问题可用三个参数( d ，f ，厂) 表示，其中d 表示决策变量的定 义域，f = xix d ，g ( x ) o ) 表示可行解区域( 可行域) ，厂表示目标函数。组合最优 化的特点是可行解的集合，为有限点集，决策变量的定义域d 通常也是有限点集。由直 观可知，只要将d 中有限个点逐一判别是否满足g ( 曲的约