（机械设计及理论专业论文）并行遗传算法在带软时间窗车辆路径问题中的应用研究.pdf

武汉理工大学硕士学位论文 摘要 配送是物流系统中很重要的一个环节。在物流的各项成本中，配送成本占 了相当高的比例。配送线路合理与否对配送速度、成本、效益影响很大。特别 是多用户配送线路的确定更为复杂。因此，车辆路径问题( v e h i c l er o 面n g p r o b l e m ，简记v r p ) 成为众多学者竟相研究的热门话题。在高度发展的商业社 会中，消费者对时间的要求越来越严格，以往的到货“日”已转换成到货“时”。 特别是随着i n t e m e t 的普及，电子商务以及其他信息技术和信息服务的研究和发 展，在现代的商务及企业管理过程中，滞后的物流供应管理成为一个亟待解决 的问题，如何通过合理规划配送车辆路线，降低配送成本，来满足消费者曰益 多变的需求，吸引了企业决策者和理论研究者们的普遍关注。 车辆路径问题是配送系统中的核心问题。也是研究热点之一。路径安排合 理能有效提高运输效率、降低服务成本。随着商品运输呈现出小批量、多品种、 多频次、及时性等趋势，运输路径的优化更加复杂。 本文首先分析了目前车辆路径问题的研究现状，再结合实际提出了本文的 研究问题带软时间窗的车辆路径问题( v r p s l w ) 。通过对v r p s t w 的数 学建模，明确定义了问题的目标函数及约束条件，在比较了多种求解方法后， 作者采用扫描法、并行遗传算法求解v r p s l w ，其求解过程为：首先采用扫描 法生成问题的一个初始解，然后采用遗传算法对初始解进行优化，得到一个最 优或近似最优解。在用遗传算法优化初始解的过程中，针对本文研究问题的特 点，作者设计了遗传编码、适应度函数以及遗传操作策略。因为遗传算法本身 存在易“早熟收敛”的缺陷，所以在计算过程中还设计了并行策略，采用多个 并行体同时计算，然后让各并行体间进行信息交换，有效的克服了遗传算法潜 在的早熟现象，改善了遗传算法求解的性能，同时还加快了计算的速度。 最后根据提出的求解v r p s t w 的方法用v c + + 编程在计算机上实现。计算 结果表明了这种遗传算法解决此类问题的有效性。 关键词：车辆路径问题，时间窗，扫描法，伪并行遗传算法( p p g a ) 。 武汉理工大学硕士学位论文 a b s t r a c t d i s t r i b l l t i o np l a y sa i li m p o r t a n tr o l ei nl o g i s t i cs y s t e m ，a n dt a k e sa c c o u n tf o r c o n s i d e r a b l ep m 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 删n go f v e h i c l er o u t i n g i nd i s t r i b u t i o n 、i nt a k eg r e a te 丘e c to n l ee 伍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 n d i s 廿i b u t i l l gf o r m l l l t ic o n s u m e r s s o ，v e l l i c l er o u t i n gp m b l e m1 1 a db e c o m ef o c u so f m 砒1 ys c h o l a r s t os t i l d y h lt l l ed e v e l o p e dc o m m e r c i a ls o s d e 吼r e q u i r e m e n to f c o n s u m e rf o rd e l i v e r yt i i n ei sl l i g h 盱趾d 圭l i 曲盯s ot l l a td e l i v e r yd a yf o m e r l yh a d t 哪e dt od e l i v e r yh o u rn o w w 也p o p u l a r i z a t i o no fi n t e m e ta i l dd e v e l o p m e mo f s u p p l yc h a i l lm 锄a g e n l e n t ，e - c o m m e r c ea i l di n f b m a t i o nt e c h n o l o 鼢l el a g g e d l o 西s t i cm a n a g e m e n tb e c o m e sa ne m e r g e n ti s s u e i no r d e rt oq u e n c hm ev e r s a t i l e r e q l l i r e m e n t so ft 1 1 ec l l s t o m e r s ，m 柚yd e c i s i o n m a k e r so fe m e i p r i s e sa n dr e s e a r c h e r s h a v es h o w ng r c a ti m e 陀s t si nd e c r e 粥i n gm et r a n s p o n 砒i o nc o s tb ye 伍c i e n tr o u t i i l g a l l ds c h c d u l i n g v e h i c l er o l n i n gp r o b l e mi s 圮k e yq u e s t i o n 趾do n eo fr e s e a r c hh o ts p o t si n t l l el o g i s t i cd i s 伍b u t i o ns y s 蛐。ar e 觞o n a b l em u t i n ga r r a i l g e m e mc a nl a r g e i y i m p r o v et h e 仃a n s p o r t a 6 0 ne m c i e n c ya i l dr e d u c em es c r v i c ec o s t w i 血an e w 仃e n d o fm o r e 虹n d s ，l e s sb a t c h s ，h i g hf e q u e n c ya n dt i r n er e s t r i c t i o ni nm a t e r i a l s d i s 廿i b u t i o n ，m eo p t i l n 洲o n so f 也ed e l i v e r yr o u t eb c c o m em o r e 锄dm o r e c o m p l i c a t e d t h j sp 印c rg i v e sar e v i e wo f 也ep a s tr c s e a r c h e so nv e h i c l er o u d n gp r o b l e m s a i l dt l l e i rs 0 1 u t i o nm “h o d s o nm eb 雏eo fr e a l i 劬w ep u r p o s et l l er e s e a r c hp r o b l e m v e l l i c l er o 埘n gp r o b l e mw i t l l s o f tt i 眦谢n d o w ( v r p s r 忉m e a n w h j l e ，w e c o n s t m c tam a m e m a t i c a lm o d e l ：d e f m e s 髓o b j e c t i v e 矗m c t i o na n dc o n s 蜘n t s m 拙e m a t i c a l l yt l l e ns o l v e si tb 髂e do ns w e 印舢g o 删吼sa n dp s e u d o p a r a l l e l g e n e t i ca i g o r i t h m ( p p q a ni n i d a ls o l u t i o ni sc o n s t n j c t e db yn l cs w c c pl l e l l r i s t i c t h e np g ai sl l s e dt oi m p m v ei tt o q l l i r eab e s to rb e 他rs o l u t i o n w bp r o p o s e c o d i n gs t r a t e g y ，腼e s s 如n c t i o na i l dm r e eg e n e t i co p c r 砒i o 璐w h e nu s i n gp g a c o n s i d e r i n gt l ：怆d i s a d v 趾t a g eo f p r e i n a n l r e c o m m o n l yi n ( 遗，吐l ep a r a l l e lo fg a i s a p p l i e dd u r i n gt l l ee v o l u t i o np r o c e s s i nt h ep g a ，t l l eo p t i m u mv a l u ei ne v e r y i i 武汉理工大学硕士学位论文 p m l l e li sc h a n g e de a c ho t l l e rmp m p 盯t i i n e 洫o r d e rt oo v e r c o m e 也ep h e i l o m e n o n o f p r e m a t u r e a n di m p m v et 1 1 ep e r f o r m a n c eo f g a f i n a l l y ，t l l i sm e m o di si m p l e m e n t e do nc o m p u t e ri nv c h t h er e s u l tp r o v e s t h e p g a i sae m c i e n t w a y t 0s l o v e t h e v n k e ) w o r d s ： v e l l i c l e r 0 l n i n gp r o b l e m ， t i m e 晰n d o w s ，s w e e p舢g o 咖m s p a r a l i e l i z a t i o ng e n e t i ca l g o r i m m s g a ) i i i 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题的研究背景及意义 物流( l o g i s t i c s ) 是供应链中最重要的组成部分，是商品从生产者经过诸 流通环节最终到达消费者手中的过程。早在上世纪6 0 年代，彼得杜拉克曾说 过“物流是一片经济增长的黑色大陆”。据中国社会科学院工业经济研究所1 9 9 5 年在北京、郑州、石家庄三地对5 0 多种日用品销售的调查显示：在不计算税金 的零售价格中，流通费用高达4 6 ，包括运费1 4 、包装费3 、装卸费4 、 保管费3 、销售费1 2 、商业企业利润1 0 ，这说明商品在流通中其附加值 大增，流通费用在总成本中的比重太大，从而加重了消费者的负担，因此整合 销售环节，减少销售费用，成为增加企业利润的加快发展企业物流运输系统重 要环节，这被经济学术界称为“第三利润源泉”i l 】。 物流作为“第三利润源泉”，对现代经济活动的作用日益明显，也越来越引 起人们的重视。在经济全球化和信息化的大环境下，现代物流业已从早期的为 社会提供传统的运输仓储服务向产品包装、分拣、配送、流通加工等增值服务 扩展。 配送是物流系统中很重要的一个环节，是国际物流业创造的最佳的一种服 务形式，也是我国物流业今后相当一个时期发展的重点。将配送作为企业发展 的战略手段，看作是企业活动的主要部分，只是近一二十年的事情。其原因是 随着生产劳动生产率的提高，人们逐渐认识到了配送在流通和物流过程中的增 值潜力，加之生产经营模式变革产生的工业配送需求、商业连锁产生的商业配 送需求、消费方式变化产生的大众需求和电子商务产生的实物配送需求都促使 了配送活动的快速发展。 配送由一般送货形态发展而来，但又绝不只是个送货系统。一般送货是有 什么就送什么，配送则是客户需要什么就配送什么。而要做到需要什么配送什 么，就需要完成库存主体的转化，用配送的集中库存替代客户的分散库存，通 过合理地配置资源，根据快速反应，连续补充库存和有效客户反应等先进的供 应链模式，才能建立起高效、有竞争力的配送系统。 配送是一系列狭义的物流活动的集成，是以送货上门为目的，有确定组织、 武汉理工大学硕士学位论文 确定渠道、有一定制度的高水平的商业活动，是商流与物流紧密结合的一种综 合的、特殊的，也是物流过程中的关键环节，其基本任务如图1 1 所示。 卜一销售市场调查 卜一销售市场分析 卜_ 一配送任务执行 卜一配送周期控制 l 一仓库管理 一车辆管理 卜_ 一财务管理 计划 卜一转运 图卜1 配送活动的基本任务 为实现配送成本的降低，必须对配送运输进行合理规划。配送运输的合理 规划涉及到时间、成本、环境三方面的因素，首先从时间上要考虑准时性、快 速响应；成本上要考虑配送运输涉及的各种开支( 车辆的购置成本和损耗、司 机薪酬等等) ；环境上要尽可能减少不必要的行驶，避免造成交通拥挤、空气以 及噪音等污染。这些可以通过改善运输方式、路径规划来加以改进。其中运输 方式属于“硬”技术的问题，可以通过设施的完善和改进来提高配送效率，相 应地降低成本，但这不属于本文讨论的范围。而配送运输规划主要是利用各种 先进的信息技术对车辆及其路径组合进行规划安排，以更好的利用各种资源满 足客户的要求，对于降低配送成本有很大的影响。配送运输规划中一个很重要 的环节是：通过点对点之间配送货物或载客的车辆的行程安排，实现对车辆的 合理有效的利用，可以节约大量的时间和成本。 配送运输的路径规划直接或间接影响时间、成本和环境三方面因素【5 0 】，配 送路线越长，占用的车辆越多，配送成本也越高。由于配送成本为运筹学、人 工智能等领域研究者关注的一个热点。从理论上来讲，配送的路线规划问题是 2 武汉理工大学硕士学位论文 组合优化问题的一种，对应的优化目标是在满足车辆容量等约束条件的前提下 使运送货物的车辆、时间、路程的组合达到最小。 1 2 问题的提出 车辆路径问题中最常见的决策问题就是，寻找合适的配送工具在最佳的路 线上配送，同时，尽可能缩短配送时间或配送距离，从而在降低配送成本的同 时改善顾客服务的水平。 为了对现实问题进行理论研究，往往需要抽象出一个模型，该模型既要便 于计算机处理，又要尽量真实地反映实际问题。所以有必要探讨车辆路径问题 的模型，以便于进一步地研究。 理论上，最简单的路径规划问题可以追溯到旅行商问题【2 1 ( t r a v e l i n g s “e s m a i lp r o b l e m ，简称t s p ) 。该问题研究的是一个旅行商从城市网络中的某 节点出发，遍历城市网络所有节点且每节点仅访问一次后回到起始点的行程路 线安排。t s p 只包括了地理因素，即只考虑了地理上的路径最短问题。而在实 际问题中，路径规划常常还需要考虑各种约束条件，比如车辆行驶的时间所需 的时间，到达每个节点的时间是否有延迟，顾客的需求量等等。 车辆路径问题【3 j ( v e l l i c l er o u t i n gp r o b i e m ，简称心) 是一种特殊的t s p 问题，其中配送网络中每个结点都存在货物需求，负责满足这些需求的车辆都 有容量限制，每辆车负责运送的货物不能超过自身的容量限制。因此冲不像 t s p 那样只单纯考虑地理上的路径最短，还要考虑各个节点处的顾客需求量以 及车辆容量等实际的约束条件，因此冲相对t s p 来说，更接近实际配送中 的路径规划问题，对v r p 的研究也更具有实际的应用价值。 v r p 是许多实际路径规划问题的基本模型，实际的运输路径规划往往根据 需要给问题加上一些有意义的约束，形成了各种v r p 的变形问题，如多配送中 心的强问题( 简称m d 冲) 、带时间窗( 即客户对送货时间区间的要求) 的v r p 问题( 简称v r p t w ) 等等。随着顾客日益“苛刻”的要求，企业正在 由以前的“生产导向型”转变为“消费导向型”，企业必须建立“以客户为中心” 的服务理念，以满足客户需求为首要考虑因素，甚至有时需要适当的牺牲成本， 以提高客户满意度。现实中客户常常会对货物送达的时间有特定的要求，而 v r p t w 就是研究在满足客户对货物、服务时间等要求的前提下，使车辆行驶 3 武汉理工大学硕士学位论文 总成本( 路程或时间) 尽可能最优，因此研究v r p t w 对企业制订具体配送路 径具有更为现实的意义。 由于v i 冲t w 是n p h a r d 4 】( n o n p o l y i l o m i a l _ h a r d ) 的问题，因而目前对 v r p t w 的理论研究多集中在求解最优或近似最优解的算法的发现和改进上。 本文正是基于这种目的，着重于对v r p t w 的一种i v r p s t w 的优化算法研 究，采用基于扫描法、最近邻居法、并行遗传算法生成v 】冲s t w 的最优或近似 最优解。 1 3 国内外的研究现状 车辆路径问题最早是由d a i l 乜i g 和r a m s e r 于上个世纪5 0 年代末期在一篇 学术论文中提出的口】。在当时。车辆路径问题主要集中在静态的车辆调度问题 上，描述的是一个运筹学中的优化问题。有一个配送中心( 或车场) ，车辆的数 目一定，而且服务对象一定，总优化目标是用最少的车辆，使总的行驶路程最 短，而对服务时间没有具体要求。在国外，对v r p 的理论研究和实际应用都已 取得了非常显著的成果。随着研究的深入，随着研究的深入发展，如何使研究 的理论模型更贴近现实中的路径规划问题已成为研究者们关注的焦点。由于带 时间窗的车辆路径问题在竞争激烈的当今社会具有十分现实的意义，近几十年 来已经出现了许多关于带时间窗的车辆路径问题的研究文献。 1 9 8 3 年，b o d i n 等人对一般的车辆路线规划问题做了详尽的综述【6 】，之后， s o l o m o n 和d e s r o s i e r s 等人考虑将时间约束加入到一般的车辆路径问题中f 7 】最 早对带时间约束的车辆路径问题进行了研究，1 9 8 5 年，s a v e l s b e r 曲证明了 v r p t w 是一个n p 疑难问题，很难求得问题的最优解f 8 】。1 9 8 8 年d e s r o c h e r s 进一步对用于求解带时间窗的车辆路径问题的各种优化方法做了简明的总结概 括嘲。1 9 9 1 年t h a n g m ，1 啦和1 9 9 3 年j o e 分别用遗传算法求解v r p t w ，但是 都存在“早熟收敛”的问题。1 9 9 4 年，p 咄【1 等人提出了重复匹配的方法， 该算法在其模型里同时考虑了时间约束和能力约束，因此适用于这类具有强约 束的v r p 。重复匹配算法也可求解较大规模的问题( 1 9 9 个客户) 。由于时间因 素在实际路径规划问题中是很常见、很重要的因素之一，所以在2 0 世纪9 0 年 代以后带时间窗的车辆路径问题就开始引起了运筹学、人工智能领域学者的极 大关注。 4 武汉理工大学硕士学位论文 作为一种组合优化问题，带有时间窗的车辆调度问题与一般的车辆调度问 题相似，其求解方法主要是基于精确算法和启发式、距启发式算法几类。k 0 1 e n 、 d e s r o c h c r s 、f i s h e r 、k o h l 等人将各种精确算法如分支定界算法等应用于 v r p t w 【“j 。由于v r p t w 是n p - h a r d 的问题，这意味着所有能精确求解这类 问题的算法在最坏的情况下需要指数级的时间。采用精确算法虽然可以得到最 优解，但庞大的计算量会消耗大量的计算时间，只能用于解决有限规模的问题， 不适用于现实中的大规模配送路径问题，已往的研究结果也证明了这一点。 采用精确算法求解v 砌，t w 的另一个缺点是：精确算法往往是针对具体的 问题设计的，不具备普适性，因此精确算法虽然可成功求得一个问题的最优解， 但对于同样问题的其它情况可能就无法正确求解。s o i o m o n ( 1 9 8 7 ) 最早将用于 求解简单v r p 的路径构建启发式方法扩展应用于v r p t w 的求解中m 】，他的研 究结果表明这些启发式求解v r p t w 问题的复杂度为0 ( 舸) ，h 为有待访问的客 户的数目，即可在多项式时间内得到问题的近似最优解，说明了启发式方法求 解v r p t w 的可行性和有效性。s 0 1 0 m o n 的此项研究为以后启发式方法和亚启 发式算法在带约束的车辆路径问题中的应用奠定了理论基础。用于求解 v r p t w 的启发式方法还有k o m o r a v d i s 的贪心随机自适应搜索法【1 q 、k o s k o s i d i s 的一般分配法以及p o t v i n 的并行插入法等【”。 在上面提到的这些方法的基础上，后来的研究者提出了各种改进解的方法 求解v r p l w 【1 8 】f 】”，通过初始解中边的交换和结点的交换来改进初始解的性能。 由于启发式方法在求解大规模复杂问题方面具有优越性，国外许多研究者都致 力于研究新的高效率的启发式算法来构造或改进v l 冲t w 的解。近几年来禁忌 搜索法( t a b us e a r c h ，简称t s ) 、模拟退火( s i i i l u l a t c da 衄e a l 证2 ，简称s a ) 以及遗传算法( ( 艳n 戚i ca l g o 蒯m s ，简称c 徂) 等亚启发式方法陆续被引入到 v r p t w 的求解中口“，并取得了显著优于传统启发式方法的结果。蚁群算法 ( a m c o l o n ys y s t e m ，简称a c s ) 作为一种比较新的启发式仿生算法，也被应 用于v r p t w 问题求解中1 2 1 ，研究结果表明该算法具有良好的性能。由于这些 启发式方法具有强大的全局优化性能和通用性，因此研究遗传算法等启发式方 法求解v r p t w 已成为目前研究者们关注的一个领域。 在我国，一些专家和学者也开始尝试v i 冲t w 的研究。1 9 9 8 年，李大卫等 人口2 1 对适用于t s p 的最近距离搜索启发式算法进行修正，构造出评价函数，并 据此提出一个求解冲t w 的启发式算法。2 0 0 0 年，谢秉磊等人【2 3 1 将货运量约 5 武汉理工大学硕士学位论文 束和时间窗约束转化为且标约束，设计了基于自然数编码的可同时处理软、硬 时间窗约束的遗传算法，实验分析获得了较好的结果。2 0 0 1 年，周贤伟和李光 远口”根据车辆装载g p s 设备的特性，建立了货物运输v r p t w 的数学模型，并 设计了遗传算法求解。2 0 0 2 年，张丽萍等人【2 5 l 通过引入新颖交叉算子，构造了 一种改进遗传算法。该算法摆脱了对群体多样性的要求，不存在传统遗传算法 常见的“早熟收敛”问题，可用于解决v r p r 问题。2 0 0 3 年，宋厚冰和蔡远 利口”针对冲t w 问题，在标准遗传算法的基础上，将分组信息与每一个染色 体结合，并辅以补交换局部搜索技术，构造了一种改进遗传算法，使得求解结 果更接近最优解。同年，宾松和符卓1 2 7 1 通过引用一种新的编码方法及交叉和变 异概率的自适应机制，构造了改进遗传算法来求解带软时间窗的v r p t w 。2 0 0 4 年，刘小兰等人口”为了克服原有大规模邻域搜索算法不能有效求解时间窗较宽 v r p 的缺陷，介绍了v r p t w 的通用数学模型。通过分析各主要变量之间的关 系，构造了一种简单、快速的确定性初始算法，并通过引入“短路径优先策略” 构造了改进的大规模邻域搜索算法，该策略也可嵌入到求解时间窗比较窄的 v r p 中，达到加速搜索的目的。 1 4 本文的主要工作及框架结构 作者在阅读了大量文献后，对车辆路径问题按照涉及到的实际配送路径规 划中的不同约束条件进行分析和总结。在此基础上提出了本文研究的问题 带“软”时间窗的车辆路径问题( 冲s t w ) ，即在不违背车辆容量、最大路径 时间等约束条件的前提下，合理规划配送时的车辆路径安排，以尽可能小的成 本满足客户对货物和服务时间区间的要求；然后从解决方法的角度对求解车辆 路径问题的各种算法进行了分类和总结，奠定了本文求解v r p s 州r 的基础；接 着本文定义了一个多目标的成本函数作为心s t w 优化的目标函数，希望在最 小化总的行驶路程的同时，尽可能减少由于违背时间窗而增加的成本，即尽可 能减少使客户不满意的情况发生。在具体解决v r _ p s t w 时，本文先采用扫描法 构建问题的初始可行解，然后采用遗传算法的全局搜索策略优化扫描法得到的 初始解，最终得到一个最优或近似最优解；最后通过v c + + 编程在计算机上实 现，采用一个配送中心，1 0 0 个客户的试验数据对本文的方法进行测试，得到 了问题的满意解。 6 武汉理工大学硕士学位论文 本文的结构安排如下： 第一章主要从理论和应用两方面讨论问题提出的背景以及研究的意义， 并提出本文的研究目标、研究思路及研究框架。 第二章描述和定义一般车辆路径问题，并针对实现中的约束条件，对车 辆路径问题的各种衍生问题进行了简明的综述。其中重点对带时间窗的车辆路 径问题进行了理论上的描述，为后文的研究奠定了基础。 第三章首先对v r p t w 作了详尽的数学描述，并针对本文研究的具体问 题一带软时间窗的车辆路径问题( v r p s t w ) ，建立了数学模型，然后简单介绍 常见v r p 问题各种求解方法。最后采用扫描法生成初始解，并详细阐述生成初 始解的过程。本章是本文的一个重点。 第四章本章首先介绍简单遗传算法的基本原理、流程、特点，然后说明 本文引入并行思想的原因，简单介绍了伪并行遗传算法的算法描述。然后详细 介绍了伪并行遗传算法的设计过程及应用流程，这部分是最能体现本文工作量 和价值的部分。 第五章 针对v r p s t w ，列举了实例，并以三、四章中提出的方法在计算 机上的具体实现，给出了运行结果，并对结果进行了比较、分析，评价了算法 的性能及其适用性。 第六章对本文进行小结，总结了论文的主要工作及论文有待改进之处， 并对进一步研究的方向进行了展望。 其中第三、四、五章是本文的核心内容，体现了本文的主要工作量。 7 武汉理工大学硕士学位论文 第2 章车辆路径问题的研究 车辆路径问题( v e l l i c l er 0 m i n gp m b l e m ，简称v r p ) 这一名词最早是在2 0 世纪5 0 年代末期由d 矾纪堙和r 册坫p r 在一篇学术论文中提出的 2 9 1 ，而后由n c 埘s t o f i d e s 对其进行总结深化1 30 1 。它主要解决的是在已知客户位置及货物需求 量的情况下，如何派车，派多少辆车，每辆车走什么样的路线才能既保证满足 客户要求，又能使成本最低的问题。车辆路径问题是组合优化领域中著名的 n p h a r d 问题之一，与众多的实际问题都有相似性，如铁路运输、公交调度、 水道航线、路由选择等，v r p 研究具有相当大的实际意义。 我国在车辆路径问题方面的理论研究相对薄弱，且现存的文献多是介绍解 决车辆路径问题的某种算法。本章主要分析了目前对车辆路径问题的理论研究 现状，对由实际运输问题中约束条件衍生的各种变形问题进行简单的介绍，然 后详细描述了本文重点研究的带时间窗的车辆路径问题，为以后的数学建模打 下基础。 2 1 旅行商问题 最著名的同时也是最简单的车辆路径问题是旅行商问题【3 1 】( t r a v e l i n g s “e s m a np r o b l e m 简称t s p ) ，旅行商问题是v r p 问题的一个特例( 即当v r p 问题中只包括一条路径，且没有能力约束的时候，就成为旅行商问题) ，t s p 问 题是运筹学、图论及组合优化中的著名难题，由于其有广泛的应用背景，引起 了人们的极大兴趣，现己归入n p 栅d 问题类。t s p 本身可以直接用于解决类 似t s p 的最优巡回线路等问题。 口代表配送中心 图2 1 一个典型的t s p 问题的解 8 武汉理工大学硕士学位论文 t s p 一般描述为旅行商从驻地出发，经每个目标城市至少一次后返回原地， 应如何安排其旅行线路，才能使总的旅行距离( 或时间、费用等) 最少。一个 典型的t s p 问题的解如图2 一l 所示。旅行商问题之所以著名，有两方面的原 因：一是实际中有很多应用问题都可以归结或转化为旅行商问题，如物资运输 路线问题、管道铺设问题等等，同时它又是许多复杂模型的基础；二是由于旅 行商问题的难于求解性，特别是对规模较大的问题，从而吸引了许多有志者从 事其有效求解算法的研究。 在m t s p 问题中，m 个旅行商要遍历所有城市且每个城市只被一个旅行 商访问。每个旅行商从同一个城市出发( 物流中心) ，在旅行后又返回这个城市。 求解目标是最小化所有旅行商走过的路径总长度。从以上的描述可知，t s p 和 m t s p 问题都是纯粹的路由问题。 2 2 经典车辆路径问题及其扩展分类 2 2 1 经典车辆路径问题 所谓经典车辆路径问题，其实就是在车辆路径的规划中，仅仅考虑最基本 的货车载重量约束( 或容量约束) 的最一般化的运输问题，即有容量约束的车 辆路径问题( c a p a c i t a t e dv e h i c l e r o m 协g p r o b l e m ，简记为c v r p ) 。具体可描述 为：有一个配送中心，车辆数目及客户数目一定，每个客户需求量固定，每辆 车( 旅行商) 都有一定的容量限制，即分配给每辆车路径上客户的需求量之和 不能超过车的容量。所有车辆从配送中心出发，服务客户后再返回配送中心， 要求每个客户都被访问到且仅访问一次，对服务时间没有要求，总目标是用最 少的车辆，使总的行程最短，即费用最少。图2 2 所示为一个典型v r p 问题 的解。 7 ( 1 5 ) 1 7 、 o 是客户 ) 车的载重量为3 0 单位 8 ( 8 ) 图2 2 拥有三条路线的一般v r p 的一个典型解 9 武汉理工大学硕士学位论文 从图论的角度来说，v r p 可以描述为基于一完全无向图g = ( 矿，一) ，其中 净 o ，1 ，n ) 是顶点集合，而e t ( f ，d ：f ，以f _ ，) 是连接两两顶点的 线段的集合。顶点0 代表服务顾客的车队所在地，而其它顶点则表示有待服务 的顾客的集合。在e 上可以定义一个非负的距离或成本矩阵d = 西 ，这里靠 代表从顶点( 顾客) i 到顶点( 顾客) j 的距离或成本。 在v r p 中，约束有以下几种口2 】： 1 ) 能力约束。与每个客户或城市对应的需求是个非负的值，任意车辆路径 的总重量不能超过该车辆的能力负荷。 2 ) 任意路径所含城市数的上界为q 。 3 ) 总时间约束。任意路径的长度不能超过预先给定的界l ：该长度由车辆 在城市间的旅行时间。和在该路径里的每个城市f 的停留时间占l 所构成。 4 ) 时间窗口。必须在时间区间【a ，b 】里访问城市f ，并允许在城市f 等待。 5 ) 多个顾客间存在服务的优先次序，必须在服务顾客j 之前服务顾客i 。 2 2 2v r p 问题的扩展及分类 根据研究重点的不同，v r _ p 存在多种分类方式。按已知信息的特征可分为 确定性v r p 和不确定性v r p ，其中不确定性v r p 可进一步分为随机车辆路径 问题( s v r p ) 和模糊车辆路径问题( f v r p ) ：按约束条件可以分为带有容量限 制的车辆路径问题( c v i 冲) 、带时间距离约束的车辆路径问题( d v r p ) 以及 带有时间窗的车辆路径问题( v r p t w ) ：按需求是否可切分，又可分为可切分 的v r p 和不可切分的v r p 。 按每个顾客需求量是否超过车的容量来分，可以分为满载车辆路径问题和 非满载车辆路径问题；按配送中心的多少来分可以分为单车场车辆路径问题 ( s v r p ) ，即一般车辆路径问题( v r p ) ，以及多车场车辆路径问题( m v r p ) ， 其中m v r p 又可以根据是否每辆车都有固定的终点车场分为终点车场固定的车 辆路径问题和终点车场不固定的车辆路径问题。 以下是肠n b 陀e 幽历提出的一种v r p 分类方式，按问题的约束条件可分为 以下三类： ( 1 ) 与客户相关的约束。这种类型的约束条件与客户需求的本质特点相关， 由于企业的经营理念向“客户为中心”转变，因此这一类型的约束往往是车辆 路径问题研究的重点。 l o 武汉理工大学硕士学位论文 ( 2 ) 与车辆相关的约束。这种类型的约束条件与为客户提供服务的车辆的 特征相关。 ( 3 ) 与配送中心相关的约束。般是指配送中心是单配送中心还是多配送 中心的情况。 表2 1 常见的各种车辆路径问题 类 别 常见约束条件描述 相关研究文献 提货、送货混合 车辆从供货处提货，再发送至 d e i f & b o d i n ( 1 9 8 4 ) ，节约法 有货物需求的客户点。常发生 g o e t s c h l c l 。( ( 1 9 8 6 ) 。两阶段法 ( v r p b ) 在工厂各分部和连锁店。 t h g i a h ( 1 9 9 4 ) ，顺序插入法 客 单个客户由多个车辆提供服 户 分割送货( s p l i t务。如客户需求超过车辆最大 相 d e l i v 容量。或客户需求是多类型的 d r o “1 9 9 0 ) ，综述 等。 关 客户对服务时间有明确要求， s o l o m n ( 1 9 8 7 ) ，节约法、插入法 时间宙定义了最早服务时间、最晚服等 ( v r p t w )务时间限制了车辆服务的时 t h g i a h ( 1 9 9 1 ) ，遗传算法 间区间。 b l a n t o n ( 1 9 9 3 ) ，遗传算法 车辆在服务其路线上所有客 最大路径时间户最晚返回配送中心的时间， mb ”e d a m ( 1 9 9 5 ) ，两阶段法 常对应配送中心的工作时间。 盔 辆 异质车队服务客户的车辆在容量或型 g o l d e n & c h e y s e n s ( 1 9 8 4 ) ，节约 相 ( f s m v r p ) 号上不同。法 关 车辆行驶速度会受到一些可 车速随时间变预测( 如交通堵塞) 和不可预 a h r i s h i n ( 1 9 9 1 ) ，插入法 化a d 理) 测( 如交通事故或车辆发生故 m a l 趾d r a 姑( 1 9 9 2 ) ，最近邻居法 障) 因素的影响。 s o u r n j a ( 2 0 0 0 ) ，禁忌搜索 配 送 多个配送中心为客户提供服 由 多配送中心务，配送中心之间存在交互 l a p o n ee ta l _ ( 1 9 8 8 ) ，线性规划 心 ( m d 诤)性，需统一规划多个配送中心 r e n de ta 1 ( 1 9 9 6 ) ，禁忌搜索 相的路径。 s a l h ie ta 1 ( 1 9 9 8 ) ，遗传算法 关 本文在表2 一l 中总结了v r p 各种常见的约束条件，并给出了近年来以这 些约束条件为研究对象的相关文献。 武汉理工大学硕士学位论文 最简单的车辆调度问题旅行商问题( t s p ) 通过扩展旅行商的数目进 而可以得到多旅行商问题( 即m t s p ) ，在m t s p 的基础上，给每个旅行商( 车 辆) 加上容量约束就得到了一般车辆调度问题( v r p ) ，然后继续将各种约束条 件加入到问题的实际模型中，就可以得到各种车辆调度问题。这是一个理论研 究逐渐逼近实际问题的过程。表2 一1 只是将现实中存在的约束条件做了一个简 单的分类，并不说明这些约束条件是互相排斥的。事实上对于车辆路径问题的 研究，考虑的约束条件越丰富，往往越接近实际运输问题，但是解决问题的难 度也随之大大增加，目前这方面的研究较少。上m 和鼬册曾对带时间窗和异质 车队两种约束条件的车辆路径问题( f s m 心t w ) 进行了研究吲。 表2 1 中的带时间窗的车辆路径问题是本文主要研究对象，将在下一节详 细加以介绍。表2 1 中的相关研究文献可见i ”】p ”。 以上分类中带有时间窗的车辆调度问题( v r p t w ) 是本文的主要研究对象， 将在下一节进行详细阐述。 2 3 带时间窗约束的车辆路径问题( v r p t w ) 2 3 1v r p t w 的概念及基本描述 时间窗是一个时间段胁，f i ，是由客户f 要求的最早服务时间日和最晚服 务时间 确定的一个服务时间区间。在v r p 问题的基础上给每个顾客加上服务 所允许的时间窗( t i m ew i n d o w s ) 约束，v r _ p 就扩展成了v i 冲t w 。 v r _ p t w 问题可简单描述如下：在不违背车辆限制的条件下，用于送货的若 干车辆从配送中心出发，在返回到配送中心前，应以最低的总成本( 路程或时 间等) ，满足处在不同地理位置的客户对供货数量、品种和服务时间的区间要求。 4 ( 1 1 ) 【5 5 ( 10 ) 2 ，3 【o ，1 5 】6 ( 6 ) 3 ，6 】 ( 1 5 ) ( 4 ，7 】 o 表示顾客点 车的载重量为3 0 单位 图2 3 拥有三条路线的v p r t w 的一个解 1 2 武汉理工大学硕士学位论文 图2 3 是一个v r p t w 的典型解的示意图，其中车辆的容量为3 0 个单位， 圆括号内为各顾客点的需求量，方括号内为该顾客的服务时间窗，方块代表配 送中心或车场，此图可与图2 2 对比与简单v r p 的区别。其中车辆的容量限 制为3 0 个单位，共有8 个客户等待服务，每个客户的需求量如图示，另外配送 中心和所有客户均有时间窗的限制。从车辆的容量限制可以看出至少需要3 辆 容量为3 0 个单位的车为这8 个客户提供服务，各路径中客户的具体访问次序还 有综合考虑距离和时间因素来确定。 在现实生活中，许多与时间相关的运输调度问题都可以归结为v r p t w 问 题来处理，如j i t 模式下的物料配送、邮局邮件的投递以及电子商务环境下的 网上销售货物的配送等。由于v r p t w 具有现实意义，而其处理结果的好坏却 直接影响着一个企业的效益和顾客的需求满足水平，因而近年来许多领域的学 者对带时间窗的车辆路径规划问题进行了广泛深入的研究【”】【3 7 】【”】f ”】。 2 3 2 时间窗的分类 ( 1 ) 按形式来分 按形式来分，时问窗有单边和双边时间窗之分，常见的单边时间窗对应的 车辆路径问题为带最后期限( d e a d l i n e ) 的v r p ( v r p t d ) ，即从双边时间窗中 去掉了对最早服务时间的限制。客户不再要求车辆最早服务时间，而只要求在 某个时间点之前为其提供服务。有关v r p t d 的解决方法可参看文献【4 0 】。 目前研究最多的是带双边时间窗的车辆路径问题，即只有在客户指定的最 早时间之后和最晚时问之前，客户才能接受服务。若车辆在客户指定的最早时 间之前到达客户所在地，则车辆必须等待直至到了客户要求的最早时间，才能 对客户提供服务；另外车辆还必须在最晚服务时间之前为客户提供货物或服务， 否则就视为延误。 ( 2 ) 按客户满意度来分 v r p t w 难度较之v r p 大大增加，如果严格按照顾客设定的服务时间为其 服务，可能造成企业的配送成本迅速攀升；如果允许在某些客户点适当地有点 延误，可能使运输成本大为减少，即使对该延误现象给予一定惩罚。所以，可 以根据决策者在对客户满意和成本二者权衡时偏好的不同，时间窗还可分为硬 时间窗( h a r dt i m ew i n d o 、v s ，简称h t w ) 和软时间窗( s o f tn m ew i n d o w s ， 简称s t w ) 和混合时间窗( m i x e dt i m ew _ m d o w s ，简称m t w ) 三种情况。 1 3 武汉理工大学硕士学位论文 ( 1 ) 硬时间窗( h a r dt i m ew i n d o w s ) ：指配送车辆必须在规定时间段内将 配送货物送达到顾客手中，顾客拒绝接受在此时间段之外提供的服务。如图2 4 为一惩罚函数( p e n a l t yf u i l 矾o n ) ，当配送货物送达时间超过了规定的时间段( b ， d ，其惩罚值p ( t ) 等于一个非常大的正值，以表示硬时间窗的限制。 在带硬时间窗的车辆路径问题( v r p h t w ) 中，车辆可以在最早服务时间 之前到达客户所在地，但必须等待直至到了最早服务时间才能对客户提供服务； 另外车辆不能在最晚服务时间之后到达客户所 在地。如在j u s t - h 卜t i m e 生产系统中，送货车 辆到达时间若迟于指定的最晚到达时间，会导 致整个生产线的延误和闲置，造成时间成本的 增加和效率的降低，因此这种情况下往往不允 许违背时间窗的约束。对于v 】冲h t w 问题来 说，服务所有客户所需的车辆数目也是决策变 刑 埘 pl 图2 4 硬时间窗 量，一般来说，所用车辆越少，对应的成本也越小，如何能用最少的车辆在不 违背车辆容量及客户时间窗的约束的前提下。为所