（交通运输规划与管理专业论文）考虑回程的车辆配送模型研究.pdf

摘要 摘要 现代物流，作为我国运输业在2 1 世纪发展的新领域和新的经济增长点，将 在我国新世纪产业发展战略中占有越来越重要的地位，将为国民经济在高起点 上持续发展提供基础动力。如何有效利用运输和配送手段降低物流成本和减少 对城市的负面影响是物流最根本的目标。 论文以城市物流车辆路径问题的现状和发展为背景，站在企业的视角针对 考虑回程的车辆配送问题( v e h i c l er o u t i n gp r o b l e mw i t hb a c k h a u l ，v r p b ) 进 行研究，主要包括以下内容：( 1 ) 设计和实现了面向装卸混合的车辆路径问 题不同需求属性的客户点转换模糊控制系统。针对现有v r p b 问题中装卸转换 点确定方法的不足，从系统的角度同时考虑车辆属性和客户属性，进行装卸分 界点的模糊化研究；( 2 ) 对遗传算法和蚁群算法采用数字计算研究其参数组 合。分别对遗传算法的群体规模、交叉率和变异率的参数组合优化，以及蚁群 算法的挥发系数、伪随机数比例和影响因子的参数组合优化进行研究，为进一 步对v r p b 问题的分析解决提供实验基础；( 3 ) 通过对无时间窗的v r p b 问 题建模的研究，设计了针对问题的遗传算法和蚁群算法，并通过实验计算表明 方法的有效性；( 4 ) 通过对有时间窗的v r p b 问题建模的研究，设计了针对 问题的蚁群算法，并通过实验计算表明方法的有效性；( 5 ) 在对需求动态的 v r p b 问题建模的基础上，提出采用两阶段法对其求解。首先根据确定需求信 息进行路径优化，然后根据动态需求确定插入的路径，在此基础上进行路径内 的改善。 最后，关于进一步工作的方向进行了简要的讨论。 关键词：车辆配送回程模糊分界点时间窗遗传算法蚁群算法需求动态 摘要 a b s t r a c t m o d e ml o g i s t i c s ，a st h en e wf i e l da n dn e we c o n o m i cg r o w t hp o i n to ft r a n s p o r t i nc h i n ai nt h e21s t c e n t u r y , w i l lb ei n c r e a s i n g l yi m p o r t a n tr o l ei nn e wc e n t u r y i n d u s t r i a ld e v e l o p m e n ts t r a t e g ya n d p r o v i d et h eb a s i cp r o m o t i o nf o rs u s t a i n a b l e d e v e l o p m e n tf o rn a t i o n a le c o n o m y i ti st h em o s tf u n d a m e n t a lg o a lo ft h el o g i s t i c s h o wt ou s et h et r a n s p o r ta n dd i s t r i b u t i o nt or e d u c et h ec o s to fl o g i s t i c sa n dt h e p o s i t i v ei n f l u e n c eo fc i t y t h i sd i s s e r t a t i o ni so nt h eb a c k g r o u n do fs t a t u sq u oa n dd e v e l o p m e n to fv e h i c l e r o u t i n gp r o b l e mi nc i t yl o g i s t i c sa n dt h ep e r s p e c t i v ei so nt h ee n t e r p r i s eb a s e do nt h e v e h i c l er o u t i n gp r o b l e mw i t hb a c k h a u l t h e k e yc o n t e n t si n c l u d ea sf o l l o w i n g ：( 1 ) t o d e s i g na n di m p l e m e n tt h ef u z z yc o n t r o ls y s t e mf o rv r p b ss h i f tp o i n tw i t hd i f f e r e n t d e m a n dc o n t r i b u t e s f o rt h ed i s a d v a n t a g eo ft h ee x i s t i n gs h i f tp o i n to ft h ev r p bi ti s c o n s i d e r e dt os t u d yt h es h i f t u s i n gt h ef u z z yt h e o r yt a k i n gi n t ot h es y s t e m a t i c p e r s p e c t i v ef r o mb o t ho ft h ev e h i c l ea t t r i b u t e sa n dc u s t o m e ra t t r i b u t e s ；( 2 ) t os t u d y t h ep a r a m e t e r sc o m b i n a t i o n so fg e n e t i ca l g o r i t h m ( g a ) a n da n tc o l o n yo p t i m i z a t i o n ( a c o ) t h r o u g ht h et e s tc o m p u t a t i o nr e s p e c t i v e l y t h es i z e ，c r o s s o v e ra n dm u t a t i o n p r o p o r t i o no fg aa n dt h ee v a p o r a t i o nr a t e ，p s e u d o r a n d o mp r o p o r t i o na n di m p a c t f a c t o r so fa c 0h a v eb e e ns t u d i e dt op r o v i d et h eb a s i cp a r a m e t e rc o m b i n a t i o nf o rt h e f u r t h e rs t u d y ；( 3 ) t od e s i g nt h es p e c i a lg aa n da c of o rt h i sp r o b l e mv i a b u i l d i n gt h e m o d e lo fv r p b ，a n dt h er e s u l t ss h o wt h ee f f e c t i v e n e s sb yt e s t i n g ；( 4 ) t od e s i g nt h e a c oo nt h eb a s i so fb u i l d i n gt h em o d e lo fv r p bw i t ht i m ew i n d o w sa n dt e s tt h e a l g o r i t h m t os h o wi t se f f e c t i v e n e s s ；( 5 ) o nm o d e l i n gt h ev r p bw i t hd y n a m i c d e m a n d ，a n dt h e nt op r o p o s eat w o s t a g ea l g o r i t h mt os o l v et h i sp r o b l e m f i r s t ，t o a s s i g nt h er o u t e sa c c o r d i n gt ot h ei d e n t i f i e dd e m a n di n f o r m a t i o n ，t h e nt od e c i d e w h i c hr o u t et oi n s e r ta c c o r d i n gt ot h ed y n a m i cd e m a n d ，o nt h eb a s i so ft h a tt o i m p r o v ew i t h i nt h i sr o u t e 摘要 i nt h ef i n a l i t y , t h ep r o b l e m sr e q u i r i n gf u r t h e rs t u d i e sa r ed i s c u s s e d k e yw o r d s ：v e h i c l er o u t i n gp r o b l e m ，w i t hb a c k h a u l ，f u z z ys h i f tp o i n t ，t i m e w i n d o w s ，g e n e t i ca l g o r i t h m ，a n tc o l o n ya l g o r i t h m ，d y n a m i c d e m a n d 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规 定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电 子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、 缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索 以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规 定向国家有关部门或者机构送交论文的复印件和电子版；在不以赢 利为目的的前提下，学校可以适当复制论文的部分或全部内容用于 学术活动。 学位论文作者签名：尸弈矽冰 删年留月j 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进 行研究工作所取得的成果。除文中已经注明引用的内容外，本学位 论文的研究成果不包含任何他人创作的、已公开发表或者没有公开 发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个 人和集体，均已在文中以明确方式标明。本学位论文原创性声明的 法律责任由本人承担。 签名：踏动材 列年g 月炒日 第1 章绪论 1 1 研究背景 第1 章绪论 随着经济全球化和信息技术的发展，现代物流在经济发展中的重要性日益 突出。根据日本学者谷口容一( t a n i g u c h i ) 1 9 9 9 年在澳大利亚举行的第一届国 际城市物流会议上对社会物流的定义【i l ，它是指在市场经济的条件下利用区域 内的交通环境，减少交通拥堵、降低能源消耗的原则下由企业所进行的物流和 交通优化等活动。 物流( l o g i s t i c s ) 也可以理解为是由货物的运输、贮藏、装卸、搬运、流 通加工、配送、情报处理等一系列功能所组成的一个行业或者部门【2 】o 配送是 物流系统中的最后一环，直接面对顾客服务，物流配送过程主要包括以下作业 环节：从生产工厂进货或运达并集结的集货作业；根据各个客户的不同需求， 在物流中心将所需要的货物挑选出来的分货和配货作业；考虑配送货物的重量 和体积，充分利用车辆的载重和容积的货物配装作业；合理确定车辆配送路线 并及时送货的作业。可见，物流配送是一种集集货、分货、配货、配装、送货 等多种功能为一体的物资流通方式。本文的配送特指考虑货物属性、车辆属性 和道路属性，合理确定车辆的配送路线。 我国国民经济继续保持快速健康发展态势，经济外向型程度进一步加大， 工业化和城市化步伐加快，居民消费结构逐步升级，政府的宏观调控职能加 强，可持续发展战略进一步推行，这一切都有力的推动和促进了我国现代物流 业的发展。2 0 0 4 年8 月5 日，国家发改委、商务部等九部门联合下发关于促 进我国现代物流业发展意见的通知，从完善物流企业税收管理、简化通关手 续、拓宽融资渠道和减轻企业负担等方面，明确了支持现代物流发展的各项政 策措施，同时建立由国家发改委牵头，商务部等有关部门和协会参加的全国现 代物流工作协调机制。 同时，电子商务发展得越来越快。电子商务是一种多技术的集合体，是一 种现代商业方法，可以改善产品和服务质量、提高服务传递速度，满足降低成 本的需求。电子商务飞速发展产生的频繁私人货物交付活动及基于低库存和及 时交付的生产与配送活动，引起货物运输量不断地增多而导致城市范围内的货 第l 章绪论 物运输车辆数量以较快的速度不断地增加，这会给原本已经拥挤的城市中心区 域带来更严重的交通问题，如交通阻塞、尾气排放和噪声污染等，不仅会严重 影响城市居民的生活质量，而且还会使得货物运输在实际活动中欲速则不达， 因此不能很好地实现城市货物快速运输【3 1 1 4 1 5 1 。 国家宏观政策的引导，国民经济的发展需要，电子商务提出的新挑战， i t s 的发展，g p s 技术的应用，对物流运输提出了更高的要求。鉴于此，站在 城市的道路资源情况和运输资源情况综合的角度去考虑物流配送问题，研究运 用科学方法合理组织物流运输，可以提高企业的服务质量、减少库存、降低经 营成本、增加经济效益：同时也可以减少城市的交通拥堵，减少环境污染，对 提高生活质量等都有着积极的意义。 1 2 问题定义 1 2 1t s p 问题 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 【6 】，也称为货郎担问题、 巡回销售问题。最早可以追溯到17 5 9 年e u l e r 提出的骑士旅行问题。1 9 4 8 年， 由美国兰德公司推动，该问题成为近代组合优化的一个典型n p 难题。该问题 可以描述如下：在个由有限个城市构成的网络中，已知各个城市间的旅行费 用，以旅行费用最小为目标找一条经过所有城市恰好一次的回路。用图论语言 来描述t s p 问题，给出一个图g = ( v ，e ) ，每条边e e 上有非负权值w ( p ) ， 寻找g 的h a m i l t o n 圈c ，使得c 的总权形( c ) = w ( p ) 最小。 p e e ( c ) t s p 问题根据路径两个方向的费用是否相等可以分为对称和非对称两类 1 7 1 ，一般情况下都是针对对称问题进行求解。用数学语言描述其模型如下【8 】： 设有疗个城市，记c 。，表示点f 到点，之间的成本，定义变量： f 1 若路径中含有路段( i ，j ) “” 10其它 数学模型如下所示。 目标函数： 2 第1 章绪论 约束条件： m i n c i j x i j i = l j = l = 1 j = 0 ，1 ，l ，n i = o x i j = 1 i = o ，1 ，l ，n x = ( 吒) x e 吒= o 或1 ( 1 - 2 ) ( 1 3 ) ( 1 4 ) n 5 、 t s p 问题是一个组合优化方面的问题，已经成为并将继续成为测试组合优 化新算法的标准问题。从理论上讲，使用穷举法不但可以求解t s p 问题，而且 还可以求出该问题的最优解。但是t s p 问题的搜索空间随着城市数刀的增加而 呈几何级数增大，对现有的计算机来说使用常规的穷举法在如此庞大的搜索空 间中寻求最优解，几乎是不可能的。所以，各种求t s p 问题近似解的优化算法 应运而生了【9 j ，目前求解旅行商问题的算法有很多，如近邻法( n e a r e s t n e i g h b o r ) 0 0 1 、贪婪法( g r e e d ya l g o r i t h m ) 、分枝定界法( b r a n c ha n d b o u n d ) 】、最近插入法、最远插入法( f a r t h e s ti n s e r t i o n ) 、双极小生成树法 ( d o u b l em i n i m u ms p a n n i n gt r e e ) 、2 一o p t 法【1 2 】、k o p t 法、l i n k e m i g h a n 法、 神经网络法、禁忌搜索法、模拟退火法、遗传算法、蚁群算法等。 1 2 2v r p 问题 车辆配送问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 于1 9 5 9 年由d a n t z i g 和 r a m s e r 提出后【1 3 l ，很快便引起运筹学、应用数学、组合数学、图论与网络分 析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视，并 一直是运筹学与组合优化领域的前沿与热点问题【l4 1 。在现实生产和生活中，邮 政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度问题、电力调度问 题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为物流配送车辆调 度问题。该问题的一般描述是i l5 j ：有一个配送中心，对，个客户进行服务，假 定每个客户的重量g 均小于额定载重q ，求满足一定的约束条件( 包括车辆费 用与时间费用) 总运输成本最小的车辆数k 和车辆行驶路线。 第1 章绪论 数学模型如下： mi nz = “g j x 驰_ _ - 一j - _v ” i j k e g i y t ，q vk f y ，= 1 i = 1 ，2 l ， k 罗x 泓= y t ，j = 0 ，1 l ，；vk 1ll 乙x 融2 酊 2 ， ，；v ， 罗x 甜= 江0，1l，l；一kyki i l v 乙x 叶2 z2 ， ，； j x 砸j 一1 ，j 覃 x 独= 0 或1i ，= o ，1 l ，；v k y 七，= o 或1i ，j = 0 ，1 , l ，j ；v k ( 1 6 ) ( 1 - 7 ) ( 1 8 ) ( 1 - 9 ) ( 1 - 1 0 ) ( 1 1 1 ) ( 1 - 1 2 ) ( 1 - 1 3 ) 在上述模型中，f 代表配送中心与客户的编号，其中配送中心的编号为o ， 客户的编号为从l 到，；当客户f 的任务由车辆k 完成时，y k i = l ，否则为0 ； 当车辆尼从f 行驶到时，止= 1 ，否则为0 。式( 1 6 ) 为目标函数，式( 1 7 ) 表示 每辆车所装的货物总重量不能超过车辆的载重，式( 1 8 ) 限制的每个客户只能由 辆车服务，式( 1 9 ) 与式( 1 1 0 ) 限定了只能有一辆车从每个客户节点进来与出 去一次，式( 1 1 1 ) 约束配送车辆在任何一个客户自己中不形成回路。 巳表示从f 到的运输成本，可以是距离、费用、时间等评价指标，本文采 用计算方法，如下： 1 ) 当f 表示配送中心时，包括固定费用和运行费用，即 c o = 铴+ c l ，o j = 1 ，人， ( 1 - 1 4 ) 2 ) 当f 表示客户点时，只有运行费用，即 勺2q 0f oj = 0 , 1 , a ，( 1 - 1 5 ) 其中，q 为相对于运行时自j 的费用系数；c o 为车辆的固定费用；t v 为从j 点n j 点的最短路运行时间。 4 第1 章绪论 国内外对v r p 问题进行研究的资料浩如烟海【1 6 】【1 7 】【1 8 l ，就所搜集的资料对 于v r p 问题的分类可以归纳入下表： 表1 1v r p 分类表 序号分类标准说明 1 问题目标单目标、多目标 2 配送中心数目单中心、多中心 3 配送中心属性开放型、封闭型 4 需求属性确定性、随机性、纯装( 卸) 、装卸混合等 5 车辆属性单乍型、多车型 6 路网属性静态或者动态 7 时间属性无时间窗、硬时间窗或软时间窗 8 其他特征路径费用对称或不对称等 1 2 3v r p b 问题 城市车辆的货运工作条件复杂，不仅任务点多、货物种类繁杂、道路网复 杂，而且运输服务地区内运输任务多样化，并且有时候物流配送任务还有对时 间窗的要求。车辆调度的要求是在满足社会对货物运输的需要、保证服务质量 的前提下、遵循车辆调度原则，实现车辆运输距离最短、效益最高、成本最 省、准确性最高等不同的调度目标，真正实现车辆运输效率最大限度的提高。 本文研究的内容是基于回程的车辆配送问题，其基本定义为：在单车场的 情况下，对一系列装货客户点和( 或) 卸货客户点，在满足交发货时间、货物 需求量、发送量、车辆容量限制、行驶里程限制、时间限制等条件下，组织车 辆线路时对装货和卸货同时进行服务，使车辆有序地通过它们，达到一定的目 标( 如路程最短、费用最少、时间尽量少、使用车辆数尽量少等) 。其中，对 于装卸混合的v r p 问题有两种理解，广义v r p b 问题是基于在某一条路径中， 车辆可以在配送中心及一系列装货客户点( 或卸货客户点) 任意两点之间进行 货物的装载和卸载；狭义v r p b 问题指货物的装或卸的某一端必须是配送中 心，即从配送中心装货到卸货客户点卸货以及从装货客户点装货后返回到配送 中心。本论文的回程指狭义v r p b 问题，如果某一个客户点既有装货服务要求 同时又有卸货服务要求则虚拟的看成两个客户点。 v r p b 问题也可以分为经典v r p b 和混合v r p b 两大类【l9 1 。在经典v r p b 中i z ，装货需求始终在卸货需求完成的情况下才能发生。混合v r p b 则可以在 第1 章绪论 一条路径的任意点进行装卸货的转换。一般来说经典v r p b 问题的解质量比较 差但是比较容易找到和执行，而混合v r p b 问题的解质量高但是在实际操作中 会有困难【2 l 】。本文的v r p b 问题针对上述两种分类的优缺点进行综合考虑，提 出自己的解决方案。 1 3 国内外研究现状 1 3 1 国内研究现状 我国对车辆路径问题的研究是在2 0 世纪9 0 年代以后才逐渐兴起。目前，国 内对于车辆路径问题的研究时间不长，研究人数不多。通过中国期刊网数据库 以“车辆路径问题”为主题进行检索，在1 9 9 9 - 2 0 0 5 年这六年时间，在中国的 正式期刊上已经发表该领域的文章1 9 0 篇，主要是对研究现状的综述和利用一 定的启发式算法对相关具体问题进行分析求解。 相关综述方面的文章主要有如下一些。“物流配送车辆优化调度理论与方 法”【2 2 l 一书对车辆调度优化问题作了深刻的阐述，并总结y 2 0 0 0 年以前国内外 学者对车辆调度优化问题所做的工作，关于非满载车辆的调度问题，文中讨论 了多车场问题如何简化为单车场问题，多车型问题简化处理方法：关于多车型 满载车辆的调度问题，其算法中并没有考虑目标成本问题，重点考虑如何完成 调度任务。在“车辆路径问题的模型及算法研究综述”【2 3 】一文中介绍了车辆路 径问题的分类和限制条件，全面综述了国内外关于车辆路径问题的模型及算法 研究现状，重点探讨了车辆路径问题的模型构造、求解算法及其适用范围。 “供应链中车辆路径问题的研究进展及前景 【2 4 】概述了近年来车辆路径问题研 究的现状，介绍了车辆路径问题主要的几种分类方法，总结了车辆路径问题中 几种常见的附加条件，分别介绍了确定车辆路径问题、随机车辆路径问题和模 糊车辆路径问题出现的背景及其具体应用场合，讨论并总结了针对这些问题的 不同建模方法和算法求解思路，以及这些算法的优点、局限和适用范围，简要 介绍了国内该领域的发展现状，并结合供应链应用的需要，指出车辆路径问题 的研究发展方向。 相关算法用于求解车辆路径问题可以分为求解确定的v r p 问题和模糊的 v r p 问题。确定的v r p 问题相对于研究深度和人数都占优，主要是采用不同 6 第1 章绪论 的算法针对具体问题进行设计和求解。主要有：郭耀煌、李军1 2 5 j 分别以分派和 c w 为基础的启发式算法对v r p 进行了求解，从解的过程来看，前者较适用 于任务数较多的情况，而以c w 算法为基础的启发式算法可以处理有众多约束 条件的实际问题；利用遗传算法的文章包括文献 2 6 卜【3 1 】，主要是为了克服进 化中的停滞，采用不同的交叉算子、变异算子，对初始解的产生运用新规则等 方法来求解车辆路径问题，比如文献 2 6 】采用最大保留交叉、交叉率和变异率 自适应变换等技术来解决非满载车辆调度问题，设计了基于自然数编码的遗传 算法，【2 7 】一文中主要用不同的初始化方法产生初始种群，目的是为了克服进 化中的停滞，使进化能够达到更优解；采用蚁群算法的文章包括文献 【3 2 - 3 7 ，主要是为了获得更优解，利用一定的机制，对挥发因子随着信息素 浓度动态调整，信息素和启发函数的影响因子随着迭代次数动态调整等；此外 还有利用禁忌搜索算法【3 8 】【39 1 、模拟退火算法【4 0 】等启发式算法求解v i 冲问题。 西南交通大学的张建勇i 4 l 】对模糊的v r p 问题进行了较为系统的研究，对模糊 需求信息的v r p 引入决策者主观偏好，建立了机会约束模型，并给出了 s w e e p i n g 启发式算法和混合遗传算法；对模糊旅行时间的v r p 问题提出了修 正的c - w 节约算法和基于模糊逻辑的混合遗传算法；对模糊预约时间的多对多 货物收发情况下的v r p 问题建立了混合遗传算法。 另外，相关的学位论文主要还有以下一些。杨锦东【1 4 3 】对有交通条件约束的 车辆配送配载模型及算法进行了相关研究。谢秉磊【4 2 】在其博士论文中对随机顾 客、随机需求和随机旅行时间车辆路径问题进行了相关研究。贺国先【4 3 1 对区域 物流中心和城市配送中心配送环节的相关问题进行了研究。符卓m l 对带路程长 度和装载能力约束的开放式车辆路径问题进行了相关研究，并用旅客列车运行 方案图编制问题进行了实例说明。 通过以上文献的查阅可知，目前国内对于车辆路径问题的研究多是集中在 单程的车辆路径问题上，对于带有回程的v r p 问题的研究人员还比较少，研究 深度还不够。主要有清华大学的蓝伯雄，张跃【4 5 】对带时间窗的装一卸载问题设计 了概率式禁忌搜索算法，主要利用概率式的禁忌搜索方法对装载与卸载问题进 行了算法设计。东北大学的隆颖【4 6 】用采用常规的整数形式编码的遗传算法求解 带回程取货的车辆路径问题。同济大学的霍佳震，张磊【47 】把有时间窗要求的集 货送货一体化满载车辆路径分解为两个阶段进行求解，第一阶段对每一项任务 内部的集货点与送货点进行内部安排行车路线，第二阶段在对各任务之间进行 外部安排行车路线。利用修正的c k 节约启发式算法进行插入式排序对有时间 7 第l 章绪论 窗的集货送货一体化车辆路径规划启发式算法研究。北京交通大学的郎茂祥【4 8 】 利用禁忌搜索算法和模拟退火算法对无时间窗和有时间窗的装卸混合问题进行 了研究。武汉大学荆海霞【1 4 2 】利用c w 节约算法对双向运输车辆路径优化问题 研究。 1 3 2 国外研究现状 1 v r p 研究现状 目前，物流的需求日益旺盛，物流在经济活动中地位和作用不断增加。随 着物流与供应链的发展【4 9 1 ，物流超越了国界范畴，全球物流正在成为最复杂的 综合物流体系。全球物流( 国际物流) 是实物、信息、资金的跨国界流动。物 流在全球范围，连接供应商的供应商和客户的客户。在过去的几年中，随着全 球经济一体化的发展，国际贸易壁垒的消除和以互联网为代表的信息技术的发 展，国际物流得到了明显的增长【5 0 1 。全球综合物流系统( p i l s ) 的发展，将使现 在的运输、仓储等物流外包服务大幅度延展。 国外对于车辆配送车辆路径问题的研究最早可以追溯到1 9 5 9 年，由 d a n t z i g 和r a m s e r 首次提出车辆调度优化问题。最初的研究局限于如旅行商问 题和o 1 背包问题等基本模型问题上，进一步的研究侧重在分析简单的车辆路 径问题( v r p ) f h a i m o v i c h 和r i n n o o yk a n ，1 9 8 5 与一个配送中心多个配送点 的配送策略问题上 r o u n d y ，1 9 8 5 ，也有一些研究致力于较复杂的实际配送问 题、随机库存问题或对这些相关问题的整合。 由于各种配送车辆的容重限制不同，车辆的装载能力成为车辆配送与配载 模型中的重要约束。许多学者致力于对“有装载能力限制的车辆路径模型与算 法”的研究，如p a o l ot o t ha n dd a n i e l ev i g o 1 5 1j 、s h o s h a n a a n i l ya n d j u l i e n b r a m e l 5 2 j 、d a v i d es i m i c h i l e v i 5 3 1 等。 随着物流需求的急剧增长及物流成本节省给企业带来的利润增长，用户基 于零库存与准时配送制( j i t ) 要求考虑，对配送的时间要求越来越严格。但将 时间窗约束融入原有的v r p 模型中时，模型更加复杂化，于是对于车辆路径问 题( v r p ) 以及相应的车辆调度问题的研究更多地集中于探讨有时间窗约束的 启发式算法，如g u yd e s a u l n i e r sa n dd a n i e lv i l l e n e u v e1 5 4 1 、b r a y s yo l l ia n d g e n d r e a um i c h e l 5 5 1 、k o h l n i k l a sa n dm a d s e n ，o l ib g1 5 6 1 、j u l i e nb r a m e la n d d a v i d es i m i c h i l e v i 5 7 1 5 8 1 等的研究。 8 第1 章绪论 有装载能力限制的车辆路径模型、有时间窗约束的车辆路径模型以及它们 的整合模型等，都是将客户集、客户的需求属性以及路网属性看作是确定量， 因而研究的模型属于静态模型。但实际上，客户集、客户的需求属性以及车辆 配送过程中的路网属性都是随客户需求的变化以及路径上交通条件的变化而变 化的，静态模型无法准确表述这种变化。目前有许多学者对动态的车辆路径问 题有所研究，如h a 曲a n i ，a a n ds o o j u n gj u n g 【”】、g a m b a r d e l l a ，l m a n d m o n t e m a n n i r 【o 、h u e y k u oc h e na n dg i n n yf e n g 6 h 。 还有一类研究集中于配送车辆路径与分群的研究。路径与分群问题研究的 重点在于是先确定路径后分群指派车辆( r o u t e f i r s t c l u s t e r - s e c o n dm e t h o d ) 还 是先分群指派车辆后根据各群确定路径( c l u s t e r f i r s t r o u t e s e c o n dm e t h o d ) 。 先路径后分群一般先按t s p 问题将配送网络内所有客户的配送路径确定下来， 然后采用曲线分割法或空间填充法将该路径分成若干配送路线指派到各配送车 辆；先分群后路径一般先将配送网络内所有客户分成若干个群集合，每一群集 合指派一部配送车辆，然后再根据各群内客户的位置确定该车辆的配送路径， 分群的方法一般采用扇形分割法( s e c t o r i a lp a r t i t i o n i n gs c h e m e ) 、圆形分割法 及一般分割法。 2 v r p b 国外研究现状 国外许多学者对v r p b 的求解方法上进行研究，提出了相对的精确式算法 和启发式算法。 d e i f 和b o d i n t 6 2j 提出了著名的节省法( c w 法) 将v i 冲问题进行延伸， 将每一个顾客视为一条路径，然后根据节约值进行计算让路径合并，循环迭 代，直到再没有任何的节省值产生。也就是对连接卸货客户和装货客户的路段 产生的节省值进行修正，利用惩罚值的概念，延迟混合路径的形成。 g o e t s c h a l c k x 和j a c o b s b l e c h a t 6 3j 提出启发式算法，分解的构造与解的改善 两个阶段：构造阶段利用空间填满曲线求得初始解：改善阶段则把问题分为子 问题，分别用贪婪法或k m e d i a n 法作为局部改善依据。在改善阶段，两种方 法的计算路径长度是相等的，但是贪婪法车辆利用率较高，因而使用车辆数较 少。 g u rm o s h e i o v t 删提出两种启发式算法。他利用反复路径分割法( i t e r a t e d t o u rp a r t i t i o n ，i t p ) ，把t s p 基本问题分割成数个子路径，每个子路径由不同 车辆服务，反复循环迭代，以求出最短路径。并利用i t p 求出p d p ( p i c k u p a n dd e l i v e r yp r o b l e m ) 的下限( l o w e rb o u n d ) 。第一种为耗竭反复路径分割法 9 第1 章绪论 ( e x h a u s t i v ei t e r a t e dt o u rp a r t i t i o n ，e i t p ) ，在e i t p 启发式算法中，每辆车沿 着基本的路径运行，直到打破车辆约束。第二种为全容量反复路径分割法 ( f u l lc a p a c i t yi t e r a t e dt o u rp a r t i t i o n ，f c i t p ) ，在f c i t p 算法中可以依照需要 产生跳离( s k i p p i n g ) ，以求得车容量满载，在大部分情况下f c i t p 优于 e i t p 。 p o t v i n 和l a p o r t e | 6 5 】使用遗传算法求解v r p b t w ，其方法分为三个步骤： 步骤一为路径构建，运用贪婪法按优先顺序插入；步骤二为路径内的节点交换 改善；步骤三为路径间节点交换改善。 y a n o 等人利用集合覆盖法求解v r p b t w 问题最优解。 t o t h 和v i g o 6 6 】提出求解对称性和非对称性的v r p b 问题的方法。该文提出 整数线形规划模型和拉格朗日下限，利用切平面法，根据添加法与下限法结合 先去除容量限制，得到一个整体有效的下限值；在拉氏松弛方面，以新的公式 取代v r p b 问题，并将分析过的可行解当作初始解。 另外，d u h a m e l f d ”等人利用禁忌搜索法求解v r p b t w 问题，在文中充分运 用领域的观念，如2 - o p t 、o r o p t 、s w a p 等当作求解时交换的依据，但限制装 货点必须在卸货点完成后才可执行，其首要目标为车辆数最小化，其次为距离 最小化。最后选定s o l o m o n 所提供的国际例题，设定装货的比例加以求解，皆 有良好的表现。 t h a n g i a h t 6 8 】等人路径构建启发式算法和数种区域搜索启发式算法求解 v r p b 问题和v r p b t w 问题。 1 4 本文的研究思路 本文的研究思路主要是围绕“一个点、两个算法和三个问题”来展开的， 具体可以用下面的流程图进行说明。 1 0 第1 章绪论 f 蔓堡至 r 薹；苗矗 l j r - 。 解决问题 l - - 一一一二 ，提出问题 、 研究背景同顾雨1 v r p b 问题界定 第章 j l 厂模糊分界点 、厂 遗传算法和蚁群算法、 针，c i j - v r p b 的模 参数组合优化 糊控制系统 】 第二章第三章 jlj l 厂三个问题、 无时问窗的v r p b 问题 ： 第四章 有时间窗的v r p b 问题i ：-第五章 需求动态的v r p b 问题第六章 1 5 本文主要研究内容 图1 1 研究思路流程图 本文以物流车辆配送路径问题为主要研究对象，结合实际情况以装卸混合 的车辆路径问题为核心研究目标，站在企业的视角以城市配送为内容，以减少 运行等综合费用为目标，利用模糊控制理论和现代优化方法研究基于回程的车 辆配送问题。利用多目标优化进行各部分费用综合，针对无时间窗、有时间窗 第1 章绪论 和需求动态的装卸一体的车辆路径问题进行了深入而细致的研究，取得了一些 阶段性的成果。本文各章的主要内容有： 第一章在对物流领域的相关概念和背景研究的基础上，通过引入t s p 问题 和v r p 问题，对本文研究的v r p b 问题进行界定，并给出本文的研究思路和研 究内容。 第二章在对模糊控制原理和模糊控制系统发展和研究的基础上，将模糊控 制原理用于v r p b 问题的装卸转换分界点的研究。首先对模糊分界点进行定 义，然后从系统的角度同时考虑车辆属性和客户属性，设计和实现了面向 v r p b 问题不同需求属性的客户点转换模糊控制系统，最后通过算例给出具体 的运算步骤。 第三章在对遗传算法和蚁群算法国内外现状和特点分析的基础上，通过对 算法的结构和流程进行梳理，采用实验计算研究遗传算法的群体规模、交叉率 和变异率的参数组合优化，蚁群算法的挥发系数、伪随机数比例和影响因子的 参数组合优化。对第四章、第五章和第六章的实验分析提供基础参数组合。 第四章研究用遗传算法和蚁群算法对无时间窗的v r p b 问题进行求解。在 对无时间窗v r p b 分析基础上建立其数学模型。采用四位数编码的遗传算法， 使其遗传操作方便简捷，并避免造成非法解；蚁群算法设计中增加虚拟配送中 心数目，从而避免子路径构造解，提高算法的有效性和效率，并对装卸不同比 例的参数情况进行算法性能测试。 第五章运用蚁群算法对有时间窗的v r p b 问题进行求解。首先对有时间窗 的v r p b 问题进行定义的基础上，用数学语言对其进行刻画。通过客户对时间 窗的敏感程度不同，确定早到和迟到惩罚系数，对目标函数进行优化；设计并 实现有时间窗v r p b 问题的蚁群算法，进而通过实验计算研究算法性能。 第六章运用蚁群算法对需求动态的v r p b 问题进行求解。在对动态v r p 定 义回顾的基础上，首先对本章研究的动态需求v r p b 问题进行定义，建立数学 模型；然后设计了动态需求v r p b 问题的两阶段蚁群算法，在建立初始解的情 况下，根据新需求的出现进行路径问和路径内改善，进而求得优化解。 第七章对本文的主要工作和研究成果进行总结，并对需要进一步研究的问 题进行简要说明。 1 2 第2 章装卸分界点的模糊化研究 2 1 问题提出 第2 章装卸分界点的模糊化研究 基于回程的车辆配送问题中车辆首先在配送中心进行装货，然后按照一定 的服务顺序进行卸货服务，同时在某一时刻开始装载需要运回到配送中心的货 物，继续按照服务顺序对该路径中所有卸货客户和装货客户进行服务，直至服 务完所有客户。因而v r p b 问题中客户的需求属性有两类，也就是说在同一条 路径中车辆需要满足客户两种不同属性的服务。 一般而言，在进行路径设计中，需要考虑车辆属性、客户属性、路段属性 等多方面因素。在实际的物流配送中，车辆首先在配送中心装载一定量的货物 按照既定的路径顺序进行卸货服务，然后在车辆载重允许的前提下进行装货服 务。由于v r p b 问题中客户需求属性的特征，考虑到车辆装载特性，为了不增 加额外的搬运费用，在卸货到一定比例的情况下，才会去考虑满足装货服务要 求，在传统的处理中往往设置卸货的权重始终比装货权重高，也就是说必须在 卸货完成的前提下才能进行装货服务。或者规定一个卸货总量占装货总量的百 分比的比例值，在卸货服务达到该百分比的情况下进行装货服务。 以上的两种处理的方法都是从车辆载货情况出发，没有综合考虑车辆载货 情况和装货客户具体情况。当车辆在卸货服务进行到一定程度的时候，是否可 以同时进行装货服务呢，传统的做法是否恰当? 在何时何地进行装、卸客户的 转换从而使得整个系统的效益最优，这是一个亟待解决的关键问题。 本章利用模糊控制的基本原理，同时从车辆的载货情况和客户点的情况出 发，解决具有两种客户服务属性的物流配送车辆路径问题，确定其在运输路径 中进行装货和卸货服务转换的客户点。 2 2 模糊控制原理【6 9 】一盯4 】 模糊控制是一种以模糊集合论、模糊语言变量以及模糊逻辑推理为数学基 础的新型自动控制方法，属于非线性控制范畴。它是一种基于“专家知识”， 第2 章装卸分界点的模糊化研究 采用语言规则表示的一种人工智能控制策吲7 5 1 。模糊控制是模糊集合理论与控 制理论相结合的成功典范，不仅改善了经典控制的性能，而且对难以精确控制 的非线性、不确定性、时变性的复杂系统也显示出独特的能力。 2 2 1 模糊集合介绍口邮2 1 在经典集合论中，任何一个元素与任何一个集合之间的关系，只有“属 于”和“不属于 两种情况，两者必居其一，而且只居其一，“非此即彼”， 绝对不允许模棱两可。但模糊集合则是把普通集合中的元素对集合的隶属度只 能取0 和1 这两个值，推广到可以取区间【0 ，1 】中的任意一个数值。即可以用 隶属度去描述论域u 中的元素符合概念的程度，实现了对普通集合中绝对隶属 关系的扩充，从而用隶属度函数来表示模糊集合，用模糊集合来表示模糊概 念。 普通关系只是表示事物( 元素) 间是否存在关联，而模糊关系是描述事物 ( 元素) 间对于某一模糊概念上的关联程度，这要用普通关系来表示是有困难 的，而用模糊关系来表示则更为确切。模糊关系在系统控制、图像识别、推 理、诊断等领域得到广泛的应