（运筹学与控制论专业论文）禁忌搜索技术在车辆调度中的应用.pdf

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意 签名；越日期：冽里! 尘 关于论文使用授权的说明 本人完全了解北京工业大学有关保留，使用学位论文的规定，即；学校有权保 留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容，可以采用影印、缩印或其他复制手段保存论文 ( 保密的论文在解密后应遵守此规定) 摘要 随着科技的进步和生产力的发展，企业之间的竞争变得非常激烈现代物流 作为一种先进的组织方式和管理技术，被广泛认为足企业在降低物资消耗，提高 劳动生产率之外的重要利润来源目前我国多数的物流企业采取手工操作，造成 配送路线安排不合理、运力资源浪费严重等问题，缺乏完善的物流配送车辆调度 方案因此对物流配送车辆调度问题的研究具有重要的现实意义 物流配送中的车辆调度问题( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) 是个n p h a r d 问题，该问题由d a n t z i g 和r a n f l s e r 于1 9 5 9 年首次提出由于很多问题都可以 抽象为这一问题，很快便引起运筹学、应用数学、组合数学、图论与网络分析、物 流科学、计算机应用等学科的专家以及运输计划制定者的极大重视，并一直是运 筹学与组合优化领域的前沿与热点问题 本文在对“朝阳批发有限公司车辆调度问题”调研的基础上，依据实际情况， 在安排车辆线路时综合考虑各个客户的实际情况，从而建立了带有货物权重的单 配送中心、多车型、有载重( 及容积) 限制、单向卸货、有硬时间窗约束的物流配 送车辆调度问题模型 本文根据v r p t w 所具有的特点以及以往对该问题研究，在此基础上把禁忌 算法用到该问题的求解中首先采用p u s h f o r w a r di n s e r t i o nh e u r i s t i c ( p f i h ) 算法构 建初始路径，然后通过禁忌算法求得满意解，在解的禁忌搜索过程同时采用几种 局部搜索技术加强局部寻优能力最后通过在v c 环境实验测试说明该算法能够 较快求解实际v r p t w 问题 关键词：禁忌算法；车辆调度；时间窗；启发式算法 一i 一 北京工业大学理学硕士学位论文 a b s t r a c t w i t ht h ea d v a n c e m e n to ft e c h n o l o g ya n dt h ed e v e l o p m e n to fp r o d u c t i v i t y , c o r n - p e t i t i o na m o n ge n t e r p r i s e sh a sb e c a m ev e r yf i e r c e m o d e ml o g i s t i c sa sa na d v a n c e d o r g a n i z a t i o na n dm a n a g e m e n tt e c h n i q u e s ，i sw i d e l yr e g a r d e da se n t e r p r i s e sa n dl o w e r m a t e r i a lc o n s u m p t i o na n di n c r e a s el a b o rp r o d u c t i v i t yo u t s i d ei m p o r t a n ts o u r c eo fp r o f - i t s a tp r e s e n t ，t h em a j o r i t yo fl o g i s t i c se n t e r p r i s e si nc h i n aa l et a k em a n u a la c t i o n ， r e s u l t i n gi nu n r e a s o n a b l ed i s t r i b u t i o nr o u t i n g ，c a p a c i t ya n dr e s o u r c e sa lew a s t e da n d o t h e ri s s u e s ，t h el a c ko fc o m p r e h e n s i v el o g i s t i c sv e h i c l es c h e d u l i n gs o l u t i o n t h e r e f o r e ， t h el o g i s t i c so fd e l i v e r yv e h i c l es c h e d u l i n gp r o b l e mh a si m p o r t a n tp r a c t i c a ls i g n i f i c a n c e l o g i s t i c sd i s t r i b u t i o nv e h i c l er o u t i n gp r o b l e m ( v e h i c l er o u t i n gp r o b l e m ，c a l l e d v r p ) i sa nn p - h a r dp r o b l e m ，w h i c hb yt h ed a n t z i ga n dr a m s e rw a sf i r s tp r o p o s e di n 19 5 9 s i n c em a n yp r o b l e m sc a nb ea b s t r a c t e da st h ep r o b l e m ，q u i c k l yl e a dt oo p e r a - t i o n a lr e s e a r c h ，a p p l i e dm a t h e m a t i c s ，c o m b i n a t o r i c s ，g r a p ht h e o r ya n dn e t w o r ka n a l y - s i s ，l o g i s t i c s ，s c i e n c e ，c o m p u t e ra p p l i c a t i o n s ，d i s c i p l i n e s ，a n dt r a n s p o r t a t i o np l a n n e r so f g r e a ti m p o r t a n c e ，a n do p e r a t i o n sr e s e a r c ha n dc o m b i n a t o r i a lo p t i m i z a t i o nh a sb e e nt h e f r o n t i e ra n dh o ts p o t s t h i sp a p e ro n “t h ec h a op ic o m p a n yv e h i c l es c h e d u l i n gp r o b l e m ”b a s e do n t h er e s e a r c h ，b a s e do nt h ea c t u a ls i t u a t i o n ，i na r r a n g i n gv e h i c l el i n e st h a tc o m p r e h e n s i v e c o n s i d e r a t i o no ft h ea c t u a ls i t u a t i o no fe a c hc u s t o m e r , t h u sc r e a t i n gt h eo n ew i t ht h e g o o d sq u a n z h o n gd i s t r i b u t i o nc e n t e rd u o c h ex i n g ，al o a d ( a n dv o l u m e ) l i m i t ，o n e w a y d i s c h a r g e ，h a v eah a r d t i m ew i n d o wc o n s t r a i n t sd e l i v e r yv e h i c l es c h e d u l i n gm o d e l t h i sa c c o r d i n gt ov r p t ww i t ht h ec h a r a c t e r i s t i c sa n dp r e v i o u ss t u d i e so f t h ep r o b - l e m ，i nt h i sb a s e do nt h et a b us e a r c ha l g o r i t h mu s e di ns o l v i n gt h ep r o b l e m f i r s to fa l l ， w i t hp u s h - f o r w a r di n s e r t i o nh e u r i s t i c ( p f i h ) a l g o r i t h mt oc o n s t r u c tt h ei n i t i a lp a t h ，a n d t h e no b t a i ns a t i s f a c t o r ys o l u t i o nt h r o u g ht a b us e a r c h ，t a b us e a r c hp r o c e s si nt h es o l u t i o n 一一 r 。， o fs e v e r a ll o c a ls e a r c ht e c h n i q u e sa l s ou s e dt oe n h a n c el o c a ls e a r c hc a p a b i l i t i e s f i n a l l y , t h ev ce n v i r o n m e n ti nt h ee x p e r i m e n t a lt e s ts h o w st h a tt h ea l g o r i t h mc a nq u i c k l ys o l v e r e a l k e y w o r d s ：t a b us e a r c h ；v e h i c l er o u t i n gp r o b l e m ；t i m ew i n d o w s ；h e u r i s t i c s 一一 北京工业大学理学硕士学位论文 目录 摘要 i a b s t r a c t - 第1 章绪论l 1 1 研究背景 l 1 2 车辆调度问题的提出2 1 3 本文研究内容 3 第2 章车辆调度问题的基本模型与算法分类5 2 1v r p 的研究现状- 5 2 1 1 国外v r p 问题的研究5 2 1 2 国内v r p 问题的研究7 2 1 3 车辆调度问题的分类 - - 8 2 2 车辆调度问题的基本模型- 1 0 2 3 车辆调度问题具有代表性的几个算法 11 2 3 1 求解v r p 的精确算法- 1 1 2 3 2 求解v r p 的经典启发式算法- - 1 3 2 3 3 求解v r p 的启发式算法- 1 4 2 4 本章小结 - 1 9 第3 章v r p t w 的两阶段禁忌算法 2 l 3 1 朝批公司货物配送情况分析- - 2 1 3 2 禁忌算法 2 2 3 2 1 初始解算法p f i h 2 2 3 2 2 邻域构造 2 3 一i v 3 2 3 禁忌算法介绍 2 6 3 3 基于实际问题禁忌算法的调整 3 2 3 3 1 大客户货物分装算法 3 2 3 3 2 基于p f m 的路线划分和大客户货物分装的初始解算法3 3 3 3 3 禁忌搜索技术的调整 - 3 3 3 4 实验结果与分析- 3 5 3 5 本章小结 4 l 总结与展望- 4 2 参考文献4 4 致谢 - 4 8 一v 一 第1 章绪论 第1 章绪论 1 1 研究背景 在经济高速发展的今天，物流已被提升到一个战略高度，作为物流主要 组成环节的物流配送，由于其配送成本在物流成本中的比重逐渐加大，选择 有效的配送路线，己经成为控制物流成本的主要措施因此，优化物流配送 运输，降低运输成本，是企业尤其是物流配送企业提高企业竞争力的有效途 径之一 物流配送中的运输成本在整个物流成本中占据很大的比重，据中国仓储 协会的一项调查结果显示，在被调查的1 4 6 个生产企业中，原料物流中运输 费用占总物流费用的5 8 ，成品物流中运输费用要占7 3 ，商业物流中占 5 2 可见，控制运输成本在物流配送中是何等的重要配送车辆调度的合理 与否对配送速度、成本、效益影响都很大，直接影响整个物流系统的运行 为车辆安排好的路径以及进行合理的调度降低运输成本是降低物流成本的 主要手段 采用科学合理的方法对配送车辆进行调度，是物流配送中非常重要的一 项活动对车辆调度优化理论与方法进行系统研究是物流集约化发展，建立 现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础这种调 度优化理论的应用并不仅限于车辆运输领域，像水运、空运、通讯以及工业 管理等都可以应用这种理论已经取得很好应用的有生产计划与调度、电力 配送调度、码头对货船的调度等随着科学技术的进步以及调度优化理论的 不断发展，将来越来越多的行业将会用到这种理论与方法，进而促进这种优 化理论向更高的方向发展 车辆调度就是研究怎样合理运输的问题，所谓合理运输就是在实现物资 产品实体从物流中心至消费地转移的过程中，充分有效地运用各种运输工具 的运输能力，以最少的人、财、物消耗，及时、迅速、按质、按量和安全的完 北京工业大学理学硕士学位论文 成运输任务其标志是。运输距离最短、运输环节最少、运输时间最短和运 输费用最省 车辆调度问题的提出 车辆调度问题( v e h i c l es c h e d u l i n gp r o b l e m ，简称v s p ) 或车辆路径问题 ( v e h i c l er o u t i n gp r o b l e m ，简称之为v r p ) ，最早是由d a n t z i g 和r a m s e r 1 j 于19 5 9 年首次提出的由于该问题是一个n p 难问题，随着节点数目的不断增多， 问题的求解过程将会极大地消耗系统的运行时间和存储空间，因此它的提出 很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算 机应用等学科专家与运输计划制订者和管理者的极大重视，成为运筹学与组 合优化领域的研究前沿与热点问题。 自从车辆调度问题提出以后，很多学者从不同的角度，依据不同的理论 思想构建了车辆调度问题的算法，既有精确算法又有启发式算法由于车 辆调度问题已被证明为n p h a r d 问题，精确算法只能用来解决规模较小的问 题，当问题的规模较大的时候只能构建启发式算法来求解，当然启发式算法 有时只能求得问题的满意解，而无法得到问题的最优解。 车辆调度问题是指存在一个车辆调度中心以及分布在不同位置的有待服 务的客户( 收集的服务或者是卸货的服务) ，安排可行的车辆路径使得所有的 客户得到服务，并且使总的运输距离( 或时间) 最小化，其中，车辆都是由调 度中心出发并且最终返回到调度中心，每一个客户由一辆车访问并且只能被 访问一次，在整个运输过程中车上总的运载量不能超过车辆的最大载重量 车辆调度问题的一般示意图如图1 - 1 所示其中方框表示调度中心或者称站 点( d e p o t ) ，各圆点表示客户所在的位置 2 第1 章绪论 图1 一l 车辆调度问题一般示意图 s 本文研究了带时间窗的车辆调度问题( v e h i c l er o u t i n gp r o b l e mw i t ht i m e w i n d o w s ，简称v r p t w ) ，该问题可以简单描述为t 使车辆从站点出发完成 客户的配送需求，在满足容量和时间窗约束下，选择合适的路径，使得完成 全部客户的配送需求所需的总的成本最小 1 3 本文研究内容 本文的主要工作体现在以下三个方面：一是建立了带有货物权重的有时 间窗约束车辆调度问题的数学模型；二是设计了求解模型的有效算法一基于 w s t w 解码算法的遗传算法，并对算法进行了性能测试；三是将模型与算法 进行了实际的应用，检验了模型和算法的有效性和应用性同时，这三个方 面也是本文的创新点全文共分六章，具体内容安排如下： 第一章：主要概述了课题提出的意义 第二章：主要介绍国内外研究现状及分类，车辆调度的基本模型及常用 算法，为后面的建模做好准备 3 北京工业大学理学硕士学位论文 第三章t 分析朝阳批发公司实际情况，建立了有其特色的车辆调度问题 数学模型 第四章：介绍了禁忌算法的基本理论，并设计了求解车辆调度问题数学 模型的混合禁忌算法，并对模型和算法进行了仿真实验，以检验模型和算法 的有效性和应用性 第五章：对全文进行了小结，总结了论文的主要工作以及有待改进之处， 并对进一步的研究方向进行了展望 其中，第三、第四章是本文研究的重点，体现了本文的工作 4 第2 章车辆调度问题的基本模型与算法分类 第2 章车辆调度问题的基本模型与算法分类 2 1 v r p 的研究现状 2 1 1 国外v r p 问题的研究 自从车辆调度问题由d a n t z i g 和r a m s e r 1 】于1 9 5 9 年首次提出以后，由于 很多问题都可以抽象为这一问题，因而引起整个学术界的关注带时间窗约 束的车辆调度问题( v r p t w ) 是对经典v r p 加上时间窗约束，可以看作是基 本v r p 的一个特殊类，所谓时间窗，即顾客要求服务的时间范围v r p t w 对顾客点得到服务的具体时间作了限制，要求运输车辆到达顾客点开始服务 的时间必须落在容许的范围之内，否则就会影响顾客对服务的满意程度，进 而损害配送企业的效益和信誉时间窗反映了顾客需要服务的紧迫性，实际 上是服务需求者和服务供给者之间的制约关系，从集合论的观点，v r p t w 是v r p 的一个真子集1 9 8 5 年，s a v e l s b e r g h 证明了v r p t w 是一个n p 难问 题，很难求得问题的最优解目前，国内外专家和学者对其求解主要集中在 启发式算法，用以求得问题的近似最优解河行解) d e s r o e h e r s l s 2 等于1 9 9 2 年以集合划分的方式描述了v r p t w 问题，并利 用动态规划对问题进行求解，利用分枝定界法给出问题下界；g e n d r e a u l 3 等 利用禁忌搜索算法对姆问题进行了求解；k o l e n l 4 等采用空间松弛的分枝 定界方法求解带有时间窗的车辆路径问题，目标是总的运输距离最小化，并 给出了求解上下界的方法b a r d 5 】等利用g r a s p 方法搜索可行解，并用分 枝切平面法求得最优解；h e r m i n i a l 6 等采用目标规划方法求解带有软时间窗 约束的车辆路径问题，通过列举一跟随- 优化的方法，即先计算初始可行路 径再选择好的路径l a p o r t e i t 等对旅行购买者问题( t p p ) 进行了研究，将配 送成本分成旅行成本和购买费用两部分，采用两索引法构造模型，未考虑车 辆启动成本的影响，利用分枝切平面法( b & c ) 在2 0 0 个用户的规模上获得了 5 北京工业大学理学硕士学位论文 最优解；n a b i l a 8 等人采用最短路径法求解单车多路径带时间窗的车辆路径 问题，算法分为两步；首先生成多条可行路径，然后根据车辆在一个工作日 内的时间来选择一些路径并进行排序主要用来求解一些易腐烂商品短距离 的运送路径问题。v a n w o e n s e l 9 等人使用排队论的思想来求解车辆调度问题 中动态行驶时间的问题，是根据时间段计算每条弧上的行驶时间，以应付潜 在的交通堵塞。t a g m o u t i 1o 】采用列生成法来求解根据时间确定服务成本的弧 调度问题，首先把弧调度问题转化为节点路径安排问题，然后由列生成法求 解，主要问题是选择服务成本小的路径z h e n g 1 1 等基于进化算法和3 d 效果 图求解无人驾驶飞机的路径规划问题b r y s y 等【1 2 】构造一种快速的进化算法 求解带有时间窗的车辆路径问题，在算法构造过程中把局部搜索、跳出串、 模拟退火以及进化算法结合起来，以提高算法的求解速度和质量通过实例 证明算法的求解速度不亚于当时的其他算法。f l i s b e r g l l3 等采用线性规划和 禁忌搜索算法相结合来求解伐木场的收集与配送问题，由于每个需求点的货 物需要从不同的收集点进行收集，因此是一种特殊的收集配送问题第一阶 段采用线性规划算法构建运输网点，每个网点描述为一个或者是多个收集点 和一个卸货点的满载运输，使所用的车辆数最小化；第二阶段采用禁忌搜索 算法对各网点进行路径安排与优化，通过构建较大的邻域来求得满意解 g e o r g e 1 4 】基于分组和排序的思想使用混合遗传算法求解大规模的多约束条 件的车辆路径问题，遗传算法中的选择与替代机制运用到算法的求解中，直 到混合遗传算法能有效的解决此类问题，最后引进高执行率运算以保证在合 理的时间内得到近似解h o n g 等1 1 5 采用基于并行插入分组和连续线性目标 规划优化相结合的启发式算法求解双目标的带时间窗的车辆调度问题l a u 等【1 6 采用禁忌搜索算法求解有车辆数限制的带时间窗的车辆调度问题，给 定一个可计算的车辆数的上界，并允许接受惩罚的时间窗口松弛，客户是按 照目标函数的优化等级来插入的b e n t 等【1 1 7 构建两阶段的混合局部搜索算 法求解带时间窗的车辆调度问题，首先用模拟退火算法最小化车辆数，然后 6 第2 章车辆调度问题的基本模型与算法分类 通过重置较大数量客户的大邻域搜索( l n s ) 方法最小化运输成本 2 1 2 国内v r p 问题的研究 我国对v r p 的研究开始于上世纪九十年代，一开始仅限于少数高校的 极少数研究者从事这方面的研究进入新世纪以来，随着我国经济的快速增 长，以及物流业的迅速发展，车辆调度问题的研究得到了越来越多的重视， 也取得了一些较为满意的成果 李军【18 等构建以分派算法为基础的启发式算法求解有时间窗的车辆调 度问题，能够求解任务较多的情况郭耀煌等【1 9 】根据贪心算法原理设计一 种交互式优化算法求解单车场满载问题袁建等【2 0 】采用一种改进的平均退 火方法求解随机需求v r p 问题，该方法将模拟退火算法与h o p f i e l d 神经网络 解法相结合，加速了神经网络的收敛并具有与模拟退火算法相当的精度 谢秉磊等【2 1 采用模拟退火算法求解配送收集旅行商问题，采用松弛必须完 成所有配送需求后才服务收集需求的约束，在扩展m e t r o p o l i s 接受准则的基 础上，运用模拟退火算法求得该问题较好的结果李宁等【2 2 】采用粒子群算 法求解带时间窗的车辆路径问题；张丽艳等【2 3 】将粒子群优化算法与模拟退 火算法相结合，提出一种求解带时间窗车辆调度问题的混合粒子群算，通过 实验表明为一种有效的算法张建勇等【2 4 】构建一种由前后双向可推的推一 碰过程确定最佳服务时间的插入式算法求解具有模糊预约时间的动态v r p 问题，通过对顾客服务时间的前推或后推，确定使顾客综合满意度最大的方 案，同时考虑其它的约束条件，使由于新客户的加入而引起的综合成本增加 值得以最小，最后通过算例说明算法的有效性张媛媛等 2 5 分析多周期车队 组合及配送，建立起物流企业动态车队组合优化模型采用d a n t z i g - w o l f 分解 方法对模型进行分解，结合动态规划和分枝定界算法设计符合该模型的精确 算法，并通过数值实验对不同的需求分布，得到了动态车队组合的优化解 刘志硕等【2 6 】构建一种基于两阶段策略的自适应混合蚁群算法求解具有硬时 间窗的v r p 问题，第一阶段采用蚁群算法进行局部遍历构造一个回路，第二 7 北京工业大学理学硕士学位论文 阶段对前一阶段的回路采用近似解优化策略组成可行解，其中引入基于时间 窗的紧迫性因子和匹配度因子，并与节约算法和爬山算法有机结合，实验表 明自适应混合蚁群算法性能优良，能够有效地求解有硬时间窗的v r p 问题 张涛等【27 在求解带有能力约束的v r p 问题中，在不固定车辆数的情况下把 聚类和排序有机的结合起来，并用遗传算法和3 - o p t 算法相结合的混合算法 对问题进行求解，通过实验得到了问题的满意解。李全亮 2 8 】构造一种基于 分组分配的亲和力计算的免疫算法求解带时间窗的车辆调度问题霍佳震等 2 9 采用修正的c w 节约启发式算法和最邻近算法为基础进行插入式排序来 求解配送收集旅行商问题，放松必须在完成所有配送需求后才服务收集需求 这一约束条件，并结合实际情况对模型的分析和处理，实验证明算法能够很 好的求解这类问题。王雪峰 3 0 等对定位一车辆路径问题进行了研究，利用禁 忌搜索和蚁群算法的两阶段c f r s 混合算法进行了求解 2 1 3 车辆调度问题的分类 根据车辆调度问题中约束条件的不同可以把车辆调度问题细分为以下几 种类型的车辆调度问题【3 1 】： ( 1 ) 按物流中心的数目分，有单物流中心问题( 配送系统中仅有一个物流 中心) 和多物流中心问题( 配送系统中存在多个物流中一 ( 2 ) 按客户对货物取( 送) 时间的要求程度分，可以分为硬时间窗问题( 客 户要求货物必须在规定的时间窗内送到或取走，不能提前也不能拖后) 、软时 间窗问题( 客户要求将货物尽量在规定的时间窗内送到或取走，但也可以提 前或拖后，只不过在提前或拖后时可能会给客户带来一些损失，这时要通过 增加补偿费用等方式对配送企业实施一定的惩罚) 和混合型时间窗( 在系统中 有些顾客属于硬时间窗，有些属于软时间窗；对同一顾客，又可能软、硬时 间窗混合使用) 实际上有硬时间窗v r p 可看作有软时间窗v r p 的一种特殊 形式，当问题为硬时间窗时，将违背时间窗约束的惩罚系数设为大数即可 ( 3 ) 按车辆载货状况分，有满载问题( 由于客户需求或供应的货物数量大 8 第2 章车辆调度问题的基本模型与算法分类 于或等于车辆的载重量，故完成一项配送任务需要一辆或更多的配送车辆， 配送车辆需要满载运徜、非满载问题( 由于客户需求或供应的货物数量小于 车辆载重量，多项配送任务可共用一辆配送车辆，车辆在配送过程中经常处 于不满载状态) 以及满载和非满载混合问题( 由于一部分客户需求或供应的货 物数量大于或等于车辆的载重量，而另一部分客户需求或供应的货物数量小 于车辆的载重量，造成一些配送车辆需要满载运行，而另一些车辆则经常处 于不满载状态) ( 4 ) 按配送任务特征分，有纯送货问题( 仅考虑从物流中心向客户送货， 也称为纯卸问题) 或纯取货问题( 仅考虑把各客户供应的货物取到物流中心， 也称为纯装问题) 及取送混合问题( 既考虑将客户需求的货物从物流中心送到 各个客户，同时考虑将客户供应的货物从客户取回到物流中心，也称为装卸 混合问题或集货和送货一体化问题) 为了便于叙述，本文将纯送货或纯取 货的物流配送车辆路径问题称为单向物流配送车辆路径问题，而将取送混合 的物流配送车辆路径问题称为双向物流配送车辆路径问题 ( 5 ) 按车辆类型分，有单车型问题( 所有配送车辆的载重量相同) 和多车型 问题( 配送车辆的载重量不完全相同) ( 6 ) 按车辆对车场的所属关系分，有车辆开放问题( 即车辆完成配送任务 后可以不返回其发出车场) 和车辆封闭问题( 车辆完成配送任务后必须返回其 出发车场) ( 7 ) 按优化目标数分，有单目标问题( 仅考虑一个配送目标) 和多目标问题 ( 同时考虑多个配送目标) ( 8 ) 按客户和路网的特点分，有静态问题( 客户位置、客户数目、客户需 求、天气路况等因素是事先确定的) 和动态问题( 客户数目、客户位置、客户 需求、天气路况等因素不是事先确定的，而足随机变化的) 9 北京工业大学理学硕士学位论文 车辆调度问题的基本模型 物流配送车辆优化调度问题可表述为：对一系列发货点和( 或) 收货点， 组织适当的行车路线，使一定的约束条件( 如货物需求量、发送量、交发货时 间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一定的目标( 如路 程最短、费用最小、时间尽量少、使用车辆尽量少等) 将车场编号为0 ，客 户及车场以点i ( i = 1 ，2 ，礼) 来表示，以表示为从点i 到点j 的运输成本 ( 距离、费用、时间等) ，在此采用客户i 、j 之间的距离奶。目标为使车辆的 总运输距离最短设t 订为车辆从客户i 行驶到客户j 的时间。 其中数学模型如下： 目标函数： m i n z = c 4 j x t j k ( 2 1 ) j - 二o - 一 i = oj = ok = l 约束条件： 蛳= 1 ，i = 1 2 礼， k = l ( 2 2 ) ( 2 3 ) ( 2 4 ) x i j k = o 或1 ，i ，j = 0 ，1 ，几；k = 1 ，2 ，m ， ( 2 5 ) y i k = 0 或1 ，i = 0 ，l ，n ；k = 1 ，2 ，m ， ( 2 6 ) 1 0 m2l = 老n21 = 缸 协 = 知 一叼 z 。渤 m2 l f 后n21 = 七玑 = 七 一够 z n 倒 第2 章车辆调度问题的基本模型与算法分类 其中： z 巧知2 y i k = 车辆忌由点i 驶向点j 否则 点i 的货运任务由车辆k 完成 否则 ( 2 7 ) 在上面的模型中，式( 2 1 ) 为模型的目标函数，即使车辆在完成全部配送任务 时的所需要的最短的运行距离或运行时间；式( 2 2 ) 为点i 的客户由车辆k 完 成的惟一性约束；式( 2 3 ) ( 2 4 ) 为到达某个客户的车辆惟一性约束；式( 2 5 ) 表 示车辆k 是否从点i 行驶到点j ；式( 2 6 ) 表示点i 的客户是否由车辆k 完成； 式( 2 7 ) 为车辆的载重约束，即某辆车所访问的全部客户的需求量不能超过车 辆本身的载重量 2 3 车辆调度问题具有代表性的几个算法 v r p 问题的求解算法有很多，但究其本质来讲，可以分为以下精确算法 和启发式算法两大类 2 3 1 求解v r p 的精确算法 精确算法，就是指能够通过有限的计算和推理得到优化问题的最优解的 算法在最优化问题中能由精确算法得出的解是最优的，没有比这更好的解 了在车辆调度问题中，用精确算法求解就是找到一组车辆路径集合，使得 其目标函数值比其它任何一组可行路径集合的目标函数值更好 m21 = 忌 g 一 k 玑吼 。：l l m h m ll 北京工业大学理学硕士学位论文 精确算法的时间复杂度一般比较大，计算时间随着问题规模的增大呈爆 炸式的增长，所以精确算法解决问题的规模不大，在实际问题中的应用范围 有限常用的精确算法有分枝切平面法( b r a n e h a n d e u t ，简称b & c ) 、动态规划 法( d y n a m i cp r o g r a m m i n g ，简称d p ) 和列生成法( c o l u m ng e n e r a t i o n ，简称c g ) 、 k 度中心树法以及拉格朗日松弛算法等 2 3 1 1 分枝切平面法( b c ) 分枝切平面法足将切平面法与分枝技术结合而成的方法，算法的基本思 想是：首先将问题描述为一个凸集并确定凸集的各个侧面，然后通过分枝操 作将解空间分解为若干个子空间，通过切平面法对子空间进行削减，切去不 包含最优解的子空间，重复上述操作直至找到最优解为止。文献 3 2 基于分 枝切平面法提出了一种精确算法求取最小所需车辆数，算法首先对问题进行 松弛，求得问题的下界，然后利用贪婪随机性自适应搜索过程( g r a s p ) 求得 问题上界，最后通过分枝切平面法求得最优解 2 312 动态规划法( d p ) 动态规划法的基本思想是：首先将问题分解为若干个阶段( 子问题) ，然 后递归求解子问题的最优解，最终求得整个问题的最优解 动态规划法一般有前向递归和后向递归两种方式，前向递归是指首先求 解出第1 个子问题的最优解，然后依次求解出下一个子问题的最优解，最终 求得整个问题的最优解；后向递归是指首先求解出最后一个子问题的最优 解，然后逆推求得前一个子问题的最优解，最终获得整个问题的最优解 2 313 列生成法( c g ) 列生成法是基于集覆盖( 集划分) 问题的一种求解框架，这种求解框架不 需要枚举所有路径，它只要求列举一部分的可行路径，然后针对部分路径集 上的线性规划松弛问题进行求解，最后利用这个解来确定足否还有可以削减 目标值的路径没有包含进来其基本流程可以描述如下； s t e pl ：利用部分路径集上的最优化对偶变量，创建新路径并求解线性 1 2 第2 章车辆调度问题的基本模型与算法分类 规划松弛； s t e p2 ：重复s t e p1 直至最优解被找到 列生成法作为一种求解框架，在求解大规模问题时难以保证其求解效 率，一般和其他算法配合使用，如分枝定界法，列生成法框架可以为分枝定 界法提供较好的下界，然后利用分枝定界法求得算法的最优解 2 3 1 4k 度中心树算法 该方法是c h r i s t o f i d e s 提出的【3 3 】，是把v r p 问题看作是松弛状态下的多 车t s p 问题，但是该方法需要知道所使用的车辆的下界，其模型是从边的角 度建立的，出发点用k 条边来表示，其他点用两条边表示，通过拉格朗日松 弛法，将其中一个约束条件消去，并进一步将原来的最小化问题转化为几个 易于求解的子最小化问题，然后进行求解 2 315 拉格朗日松弛算法 k o h l a 4 在求解v r p t w 时使用拉格朗日松弛法求出下界，然后采用分枝 定界法进行优化，并成功求解了1 0 0 个点的问题 2 3 2 求解v r p 的经典启发式算法 启发式算法是基于局部邻域搜索技术发展起来的一类算法，算法试图在 有效时间内寻求接近于最优解的”近优解”或称”满意解”，与精确算法相 比具有较高的执行效率启发式算法分为经典启发式算法和现代启发式算法 ( 又称亚启发式算法) 两大类经典启发式算法在进行解的改进时是按照一种 降序的方式来搜索的，在每一次迭代中搜索较优的解直到无法找到更优的 解，经典启发式算容易陷入局部最优从而不能搜索全局更优解亚启发式算 法是基于自然进化机制以及自然群体智能的一种搜索算法，是一种全局优化 搜索算法，以其简单通用、鲁棒性强、适用于并行处理以及应用范围广等显 著优点，奠定了它作为新世纪关键智能计算方法之一的地位下面对一些求 解v r p 问题的启发式算法进行简单介绍： 1 3 北京工业大学理学硕士学位论文 2 321c l a r k e - w r i g h t 算法 该算法又称节约算法是由c l a r k e 提出的f 矧，用来解决车辆数不固定的 v r p 问题该算法最初按照要解决的问题中客户的数量礼构建佗条初始路 径，然后计算合并任意两条路径后可节省的成本量，然后按照节约成本量从 最大到最小的顺序以及是否满足容量约束进行路径的归并，直到不能归并任 何路径为止，即不能找到更好的解 2 3 2 2s w e e p 算法 该算法足由g i l l e t t 提出的【洲，首先计算出所有要访问的点的极坐标，并 按照角度从小到大排序，然后在满足容量约束的前提下，按照角度大小归并 到不同的子路径中，把问题转化为求解多车t s p 问题，最后再根据t s p 的优 化算法对所得到的子路径进行优化 2 3 3 求解v r p 的元启发式算法 2 3 3 1 禁忌搜索算法( t a b us e a r e h ，简称t s ) 禁忌搜索算法( t a b us e a r c h 或t a b o os e a r c h ，简称t s ) 是由g l o v e r 3 7 】最先 提出的，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对 人类智力过程的一种模拟t s 算法通过引入一个灵活的存储结构和相应的 禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态， 进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传 算法，t s 足又一种搜索特点不同的m e t a h e u r i s t i c 算法迄今为止，t s 算法在 组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的 成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势 本章将主要介绍禁忌搜索的优化流程、原理、算法收敛理论与实现技术等内 容 2 3 3 2 蚁群算法( a n tc o l o n v ) 9 0 年代d o r i g o 3 8 提出了蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 来解 决计算机算法学中经典的”货郎担问题”如果有n 个城市，需要对所有n 个 1 4 第2 章车辆调度问题的基本模型与算法分类 城市进行访问且只访问一次的最短距离 在解决货郎担问题时，蚁群优化算法设计虚拟的“蚂蚁”将摸索不同路 线，并留下会随时间逐渐消失的虚拟。信息素”虚拟的“信息素”也会挥 发，每只蚂蚁每次随机选择要走的路径，它们倾向于选择路径比较短的、信息 素比较浓的路径根据“信息素较浓的路线更近”的原则，即可选择出最佳 路线由于这个算法利用了正反馈机制，使得较短的路径能够有较大的机会 得到选择，并且由于采用了概率算法，所以它能够不局限于局部最优解 蚁群优化算法对于解决货郎担问题并不是目前最好的方法，但首先，它 提出了一种解决货郎担问题的新思路；其次由于这种算法特有的解决方法， 它已经被成功用于解决其他组合优化问题，例如，图的着色( g r a p h c o l o r i n g ) 以及最短超串( s h o r t e s tc o m m o ns u p e rs e q u e n c e ) 等问题 2 3 3 3 遗传算法( g e n e t i ea l g o r i t h m ，简称g a ) 遗传算法( g e n e t i ca l g o r i t h m s ) 是基于生物进化理论的原理发展起来的一 种广为应用的、高效的随机搜索与优化的方法其主要特点是群体搜索策略 和群体中个体之间的信息交换，搜索不依赖于梯度信息它是在7 0 年代初期 由美国密执根( m i c h i g a n ) 大学的霍兰( h o l l a n d ) 3 9 教授发展起来的1 9 7 5 年霍 兰教授发表了第一本比较系统论述遗传算法的专著自然系统与人工系统 中的适应性( a d a p t a t i o ni n n a t u r a la n da r t i f i c i a ls y s t e m s ) 遗传算法最初 被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化 规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的 迄今为止，遗传算法是进化算法中最广为人知的算法 近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用方 面，取得了一些令人信服的结果，所以引起了很多人的关注在发展过程中， 进化策略、进化规划和遗传算法之间差异越来越小遗传算法成功的应用包 括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备 布置与分配、交通问题等等 1 5 北京工业大学理学硕士