（企业管理专业论文）物流配送企业集配货一体化VRP研究.pdf

物流配送企业集配货一体化v r p 研究 摘要 配送车辆的路径规划问题，是物流配送优化中的一个关键环节，也是困扰物 流配送企业由来已久的难题。从文献查阅来看，目前对车辆路径规划问题的研究 大都集中于单向的物流配送，而对集货业务和配货业务同时存在的双向物流的研 究还很不成熟。本文从企业实际配送需求出发，考虑客户点同时存在集配货混合 作业的双向物流情况，允许在客户点同时进行集货作业和配货作业，即配送车辆 只需服务客户一次，就可以满足客户点的配货和集货需求，展开集配货一体化路 径规划问题研究与实例分析。 首先，本文介绍了研究背景，回顾了车辆路径规划问题的研究现状，针对前 人的不足，阐述了本文研究的意义，并提出了本文的主要研究内容。 其次，通过对现实问题的深入研究，对车辆出行成本加以考虑，并考虑车辆 从物流配送中心出发时的满载情况，设定了问题的假设条件和参数，并对各种约 束条件进行抽象化、数学化，最终建立了集配货一体化车辆路径规划问题的更加 符合现实情况的数学模型。 然后，选择了模拟退火算法对集配货一体化车辆路径规划问题数学模型进行 求解。介绍了模拟退火算法的基本原理及其在组合优化方面的应用，并分析了其 优缺点。针对其存在的缺点，本文对算法邻域操作策略进行了改进，以扩大其搜 索解空间的能力，为算法添加了记忆功能，以得到算法每次计算的最优解，并改 进了算法的终止准则，以合理节省算法的迭代步数。进而将其应用于求解集配货 一体化车辆路径规划问题。 最后，本文选取了权威数据对算法进行测试计算，结果表明，本文设计的算 法具有可行性和优越性。进而以某物流配送企业位于长沙定王台的图书配送中心 为实例，进行了集配货一体化车辆路径规划问题的应用研究。 关键词：物流配送企业；集配货一体化；车辆路径规划问题；模型优化；模拟退 火算法 l i 硕卜学位论文 a b s t r a c t t h ev e h i c l e sr o u t i n g o p t i m i z a t i o ni sak e yl i n ki nt h el o g i s t i c sd i s t r i b u t i o n o p t i m i z a t i o n ，a sw e l la si st h eh a r dp r o b l e mo fl o g i s t i c sd i s t r i b u t i o ne n t e r p r i s e s b u t t h es o l u t i o no ft h ev e h i c l er o u t i n gp r o b l e mi nf o r m e rr e s e a r c ho f t e nf o c u s e so n u n i d i r e c t i o n a ll o g i s t i c sd i s t r i b u t i o n a n dt h er e s e a r c ho fb i d i r e c t i o n a ll o g i s t i c si ss t i l l i m m a t u r e a c c o r d i n gt ot h er e a l i t y , t h i sa r t i c l ec o n s i d e r s t h es i t u a t i o nt h a tac u s t o m e r p o i n te x i t sb i - d i r e c t i o n a ll o g i s t i c sa n di sa l l o w e dt od e l i v e r ya n dp i c ku pg o o d sa tt h e s a m et i m e i no t h e rw o r d s ，t h ev e h i c l em e e t st h ec u s t o m e r s n e e d so fp i c k u pa n d d e l i v e r yb yo n l yo n c es e r v i c ew h i c hc a l l e dt h ev e h i c l er o u t i n gp r o b l e mw i t hp i c k u p a n dd e l i v e r y ( v r p p d ) t h i sp a p e rr e s e a r c h e so nt h ev r p p da n da n a l y s e sa ne x a m p l e o f i t f i r s t l y , t h ep a p e ri n t r o d u c e st h er e s e a r c hb a c k g r o u n da n dr e v i e w st h e c u r r e n t r e s e a r c hs t a t u so fv e h i c l er o u t i n gp r o b l e m a c c o r d i n gt o t h el a c ko fp r e v i o u s r e s e a r c h e s ，t h ea u t h o rd e s c r i b e st h es i g n i f i c a n c eo ft h i sr e s e a r c ha n dp u t sf o r w a r dt h e m a i nc o n t e n to ft h i sp a p e r s e c o n d l y , t h ep a p e rs e t s t h e a s s u m p t i o n s a n d p a r a m e t e r s o fv r p p db y r e s e a r c h i n gp r a c t i c a lp r o b l e m sa n dc o n s i d e r i n gt h ev e h i c l ef i x e dc o s ta n d t h ef u l ll o a d o fv e h i c l ew h e ni ts t a r tf r o md i s t r i b u t i o nc e n t e r t h r o u g ht h ea b s t r a c t i o na n d m a t h e m a t i z a t i o no fv a r i o u sc o n s t r a i n t sa n ds e t t i n gu pt h ep a r a m e t e ra n dp r e m i s eo ft h e r e a s e a c h ，f i n a l l y , t h ep a p e rb u i l d sam o r er e a l i t ym a t h e m a t i c a lm o d e lo f v r p p d t h e n ，t h ep a p e rc h o o s e ss i m u l a t e da n n e a l i n ga l g o r i t h mt o s o l v ev r p p d ，a n d i n t r o d u c e st h eb a s i cp r i n c i p l e so fs i m u l a t e da n n e a l i n ga l g o r i t h ma n di t sa p p l i c a t i o no f c o m b i n a t o r i a lo p t i m i z a t i o na n da n a l y s i so fi t sa d v a n t a g e sa n dd i s a d v a n t a g e sa sw e l l a c c o r d i n gt oi t sd i s a d v a n t a g e st h ea u t h o rt r yt oi m p r o v et h ea l g o r i t h ms t r a t e g y t o e n l a r g et h ea b i l i t yo fs e a r c h i n gs o l u t i o ns p a c ea n dd e s i g n san e w s i m u l a t e da n n e a l i n g a l g o r i t h mw i t hm e m o r yf u n c t i o nf o rv r p p d f i n a l l y , t h ep a p e rs e l e c t sa u t h o r i t a t i v ed a t et ot e s tt h ea l g o r i t h m c o m p a r e d t ot h e e x p e r i m e n t a lr e s u l t s ，t h ea l g o r i t h md e s i g n e db yt h i sp a p e r i sf e a s i b i l i t ya n ds u p e r i o r i t y a tl a s t ，t h ea l g o r i t h mi sp r o v e dw o r k i n gw h e nt h ep a p e rt a k e st h ee x a m p l eo fa l o g i s t i c se n t e r p r i s ei nc h a n g s h a f o rd i n g w a n g t a ib o o k sd i s t r i b u t i o n k e yw o r d s ：l o g i s t i c sd i s t r i b u t i o ne n t e r p r i s e ；p i c k - u pa n dd e l i v e r y ；v e h i c l er o u t i n g p r o b l e m ；m o d e lo p t i m i z a t i o n ；s i m u l a t e da n n e a l i n ga l g o r i t h m i i i 物流配送企业集配货一体化v r p 研究 插图索引 图1 1本文研究技术路线图1 4 图2 1硬时间窗图1 7 图2 2软时间窗图17 图2 3混合时间窗图17 图3 1 线路内2 - o p t 示意图一2 5 图3 2 线路内3 - o p t 示意图一2 5 图3 3线路间0 1 型交换”2 5 图3 4 线路间1 1 型交换“2 6 图3 5 m e t r o p o l i s 接受准则概率函数图一2 8 图3 6 局部搜索算法示意图3 2 图3 7模拟退火算法示意图3 2 图3 8改进模拟退火算法流程图3 7 图4 1测试算例近似最优解路线规划图4 2 图4 ，2 测试算例算法模拟退火过程图4 2 图4 3测试算例算法模拟退火过程处理图4 3 图4 4企业应用实例近似最优解路线规划图4 6 图4 5企业应用实例算法模拟退火过程处理图4 6 图4 6企业应用实例电子地图路线图4 7 v i 硕士学位论文 附表索引 表1 1 集配货一体化v r p 研究综合8 表3 1启发式算法分析比较表一2 3 表3 2 距离矩阵表2 4 表4 1测试算例客户综合信息表一4 0 表4 2 运用改进模拟退火算法计算结果4 1 表4 3测试算例近似最优解路线表4 1 表4 4 以配送距离为目标与文献 5 0 的不完全比较4 2 表4 5企业应用实例客户综合信息表一4 4 表4 6企业应用实例近似最优解路线表4 5 v i l 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 阁考纽 j 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 闷豸鬓 御毂钆 日期：弘憎年 日期沙咯年 r 月co 日 厂月f o 日 硕上学位论文 1 1 研究背景及意义 第1 章绪论 物流已成为企业的“第三利润”源泉，随着经济的不断发展，在全球范围内进 行资源配置已成为现实，物流业将变得越来越重要。现代物流系统是通过采购、 装卸、仓储、运输、包装、配送、信息等全面综合管理，以缩短商业流程，降低 企业生产成本、物流成本，增加企业的时间效益。其中，配送是物流中的一个重 要的、直接与消费者相连的环节。配送一般定义为：将货物从物流结点送到集货 人的过程。配送是在集货、配货的基础上，完全按客户要求，包括种类、品种搭 配、数量、时间等方面的要求所进行的运送，是“配 和“送”的有机结合形式。 有效率的配送系统期望在距离最短、时间最少、成本最小的目标之下，规划最适 的配送路线，以满足不同地理位置的客户需求。而物流配送车辆的路线优化，是 物流配送优化中的一个关键环节。 物流业从最实际的角度出发，就是要完成两大目标：( 1 ) 降低成本；( 2 ) 满足客 户需求。换句话说，就是在满足某些“约束条件 的基础上实现“最节约成本 的配送方案。物流业的最主要成本投入有两大块：一是前期投入，建立仓库、配 送中心，安排配送工具，如卡车；二是实际运行中的管理和配送消耗。因此物流 配送的一个重要目标就是在满足客户需求的前提下，投入最少的配送成本( 主要是 各种运输线路上的损耗) 。在网络化的今天，由于信息流通便捷，各部门协同工作 的能力越来越强，实现诸如“整合运输 、“最低库存”、“快速反应”的客观条件 越来越现实。因此，如何充分利用现有条件，达到物流配送的最小成本消耗已经 成为一个越来越受重视的问题。特别当传统配送模式向小批量、多批次的配送模 式转变时，更使得原来的单线的，仓库一一单个客户一一仓库的配送模式被完全 推翻，取而代之的是每个运输单位运输不同的货物到不同的客户手中，也就是仓 库一一多个客户一一仓库的配送模式；而不是像往常那样，每个配送单位分配给 单个客户，把货物运到客户手中就立即返回，造成路程上的大量浪费。 当前物流业正向全球化、信息化、一体化发展，配送在供应链中的作用显得 更加重要。由于现代配送具有多频次、小批量、多品种、高效率的特点，配送要 准确做到7 r ( r i g h tp r o d u c t ，r i g h tq u a l i t y ，r i g h tt i m e ，r i g h tp l a c e ，r i g h tc o n d i t i o n ， r i g h tc u s t o m e r , r i g h tc o s t ) ，设计合理、有效的车辆运输路线方案就变得非常重要。 我国物流业起步较晚，大部分配送中心还处于手工配货阶段，尤其是专业的第三 方物流发展不尽如人意。第三方物流的一个主要功能就是配送，而在我国大多数 物流配送中心对于配送路线的规划是采取人工分配的方式，依赖司机对城市道路 物流配送企业集配货一体化v r p 研究 的熟悉程度，临时决定配送路线，主观随意性很大，运输路线的选择因而具有一 定的盲目性。但面对越来越庞大数量的客户需求点、不同的配送车辆容量、各客 户需求性质的不同，人工分配的方式实在很难在短时间内完成理想的路线规划， 因此一种快捷、行之有效的车辆配送路径规划方法对配送企业是非常重要的，由 此企业界和学界都对其产生了浓厚的兴趣。由于客户数目的巨大，这一问题的可 行解数目非常巨大，甚至不可能用类似于枚举法的方法在能够接受的时容量间范 围内得到最优解或者较优解，并且客观约束条件复杂而多，因此该问题已经成为 一个公认的物流难题。 从文献查阅来看，车辆路径规划问题的研究大都是假设某个客户需求点存在 单纯的配送业务( p u r ed e l i v e r y ) 或者单纯的集货业务( p u r ep i c k u p ，即逆向物流) ， 即使允许配送车辆集货，也是假定在所有的配送业务完成后再回程进行集货业务。 本文所研究的问题是考虑某个客户需求点存在集货业务或者送货业务或者同时存 在集货与送货业务( p i c k u pa n dd e l i v e r y ) ，允许在客户需求点同时进行集货作业和 送货作业，即配送车辆只需服务客户一次，就可以满足客户需求点的送货和集货 需求，我们称之为集配货一体化车辆路径规划问题( v e h i c l er o u t i n gp r o b l e mw i t h p i c k u pa n dd e l i v e r y ，v r p p d ) 。 现实生活中有很多这样的实例，如啤酒的配送及其空瓶的回收等，其中图书 的配送是最典型的例子。例如：书籍产品的物流配送，由于书籍产品的退货率非 常高，约有3 4 成左右，书店在有配货需求的同时，几乎都存在把未卖出的图书： 送回配送中心的需求。因此，对书籍产品的配送，在路线规划方面就有必要考虑 同时集配货的问题。 从社会角度来看，我国每年出版新书均超过1 0 万种，通过调查估算【l 】，2 0 0 2 年我国仅用于图书物流的总成本约8 0 亿元( 物流费率按1 5 计算、退货率按1 0 计算) ，其中，用于图书配送的成本为4 1 亿元，图书退货的物流成本为7 3 亿元。 可知图书业用于送货和退货业务的成本占了图书物流总成本的六成以上。因此若 把退货业务和送货业务归并到一起来考虑，规划书籍产品配送网络，优化配送路 径，减少配送距离，将有很大的成本下降空间，给社会带来巨大的经济效益。 对企业而言，正确合理地安排车辆的配送线路，可以有效的减少车辆的行驶 距离，减少车辆的空驶率，提高车辆的利用率，实现合理线路运输，从而降低运 输成本、节约运输时间、提高客户服务水平、维护企业良好的形象、提高经济效 益，达到科学化的物流管理。 本文正是基于此，针对图书这类商品的特性，在路线规划方面考虑同时收、 送货的问题，从文献综述中的旅行商问题( 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 ) ，车辆 路径规划问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) ，考虑集配货一体化车辆路径规划问 题( v r p p d ) 的解决方式，并依照研究假设和相关约束条件建立v r p p d 的数学模型， 硕上学位论文 找出适合解决v r p p d 的启发式算法，并且评估这个算法的求解质量及求解的效 率，以期实际应用于相关物流配送中心。 1 2 国内外相关文献综述 1 2 1 关于旅行商问题研究 旅行商问题( 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 ) 【2 】是数学领域中很有名的问题， 是一个典型的n p 难题。 t s p 问题的描述如下：假设一个有刀个城市( 节点) 的集合，及一位推销员，这 位推销员需从一个城市出发，确实地访问所有的城市一次，最后必须再回到原出 发的城市。问题是应如何安排访问各城市的顺序，以使总旅行的距离( 行经过的路 途) 最短。以n 个城市的t s p 问题为例，从最早的起始城市出发，一直到回到原来 出发的城市，要使用数学方法找到最短的路径组合，可使用p ( f ，) 的矩阵来表示各 个节点间的距离，如果f 和，之间的道路是遗失的或是不可通行的，则以o 。来表示。 随着城市数目增多，路径的条数成级数增长，求解最短路径的时间也会变成天文 数字般大小，以致在非多项式时间内无法求解出该问题的最优解，即为一个n p 难题。 国外学者对t s p 问题的研究由来已久，提出了各种精确算法，还引入了图论、 启发式算法以求解t s p 问题。我国学者大都在借鉴国外学者的研究基础之上，对 模型算法加以改进，提出了很多新的解决t s p 问题的方法。 李军民等在论文用混合遗传算法求解多目标t s p 问题中，针对多目标t s p 问题，提出了非群体迭代型多目标遗传算法与局部阶段搜索算法相结合的混合遗 传算法【引。其中非群体迭代型多目标遗传算法通过个体的被优越数和种群的分布情 况计算个体适应度，采用基于路径表示的编码方法进行编码，使用竞争选择策略、 部分匹配交叉和变换变异进行遗传操作。 王会颖等在论文一种求解t s p 问题的分段交换蚁群算法中介绍了一种求 解t s p 问题的分段交换蚁群算法【4 j 。分段交换蚁群算法把小窗口、随机分段优化 求解、模拟退火充分交换的思想引入蚁群算法，把蚁群算法和模拟退火算法融合。 该算法在蚁群算法陷入局部最优解的情况下，能改进其局部最优解，并可减少迭 代次数。 1 2 2 关于车辆路径规划问题的研究 车辆路径规划问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 的基本定义如下：设有一物 流中心，共有聊辆货车，有刀位顾客，每位顾客有其需求量d ，货车从顾客f 到顾 客，的运送成本为q ，。车辆路径规划问题即必须在不违反车辆容量限制条件下，使 用v 辆货车自场站出发服务所有的顾客后再回到场站，以满足顾客的需求，而且每 物流配送企业集配货一体化v r p 研究 位顾客仅能被一辆车服务，使所有车辆配送路线的总成本为最小。 如果把t s p 问题中的推销员看成是一辆车，并限制车容量，t s p 问题就变成 了v r p 问题，v r p 问题每一个回路就是一个t s p 问题。v r p 问题是由d a n t z i g 和 r a m s e r 于1 9 5 9 年首次提出的，由于此问题在交通运输、工业生产管理等领域具有 广泛而重要的应用，因此多年来其研究得到很大重视，并且是网络最佳化问题中 最基本的问题型态之一，在学术研究和实务应用上有许多不同的延伸和变化型态。 根据约束条件的不同，v r p 可扩展出不同的具体问题【5 1 ，常见的主要有以下 几类： ( 1 ) 车辆容量：若无车辆容量约束则为经典t s p 问题； ( 2 ) 时间窗：包括软时间窗和硬时间窗约束； ( 3 ) 车辆服务限制：限制每辆车所能服务的最多客户数或是所能行驶的最大距 离、运行最长时间等； ( 4 ) 优先约束：限制在访问客户，之前一定要先访问客户f ； ( 5 ) 相容性约束：如某些货物不能同时装在同一辆车上； ( 6 ) 车型约束：对每种车型的数量进行限制； ( 7 ) 路线中客户的性质：如集货客户和配送客户等。 本文研究的问题即为在时间窗约束的条件下，根据路线中客户性质划分的同 时集货和送货的车辆路径规划问题，将在下节中详细讲述。 由于v r p 问题具有重要的经济意义，国内外研究v r p 问题的文献较多。对 v r p 问题的求解，主要分为两大类方法，一类是精确算法，另一类是近似算法。 近年来，学者们用精确算法和近似算法求解v r p 问题，并都取得了一定的进展。 精确算法主要有分枝定界法，c o l u m ng e n e r a t i o n ，l a g r a n g i a nd e c o m p o s i t i o n 和k 树状算法。l a p o r t e 和n o b e r t 提出了多种分枝定界法【6 】。e l e n ih a d j i c o n s t a n t i n o u 等 用动态规划放宽空间变量解决v r p 问题【_ 7 1 。f i s h e r 提出用两阶段优化方法解决带 有时间窗限制的v r p 问题【8 l 。d i m i t r i sj b e r t s i m a s 和d a v i ds i m c h i l e v i 提出先用 c o l u m ng e n e r a t i o n 法分组，再使用分枝定界法来求解v r p 整数规划问题【9 】。 关于近似算法，c l a r k e 和w r i g h t 于1 9 6 0 年首先提出一种启发式节省算法来建 立车队配送路线，即著名的c w 节约算法【l o 】。g l o v e rf 首先将禁忌搜索算法应用 于求解v r p 问题【1 1 】，随后l a p o r t e 用禁忌搜索算法提高了求解v r p 问题的精度【1 2 1 。 模拟退火方法具有收敛速度快、全局搜索的特点，o s m a n 对车辆路径问题的模拟 退火算法进行了研究，他提出的模拟退火方法主要适合于解决路线分组【1 3 1 。遗传 算法具有求解组合优化问题的良好特性，h o l l a n d 首先采用遗传算法编码解决有时 间窗的车辆路径问题【l4 1 。现在多数学者采用混合策略，分别采用两种智能化的启 发式方法进行路线分组和路线优化。o m b u k i 提出了用遗传算法进行路线分组，然 后用禁忌搜索方法进行路线优化的混合算法【1 5 】。b e n t 和v a nh e n t e n r y c k 则首先用 硕上学位论文 模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法将运输费用降到最 低【l6 1 。g o l d e n 等提出了一种“基于配送顾客数 的插入方法，首先构造完全由有 配送需求的顾客组成的路径，根据插入收集顾客所增加的成本和插入点后的配送 顾客数，依次插入各个收集顾客【1 7 】。c a s c o 等提出了“基于载重量 的插入方法【”】， 插入收集顾客的成本考虑增加的路径成本和还未配送的载重量；s a l h i 等扩展了这 种方法，一次插入多个收集顾客，构成了一种簇插入方法【l 引。m o s h e i o v 提出两种 启发式算法，一种是利用问题与t s p 的相似性，由t s p 的解出发构造t s p d 的一 个可行解，另一种对传统的节约插入法进行拓展，形成节约可行插入法【2 0 1 。 国内学者蔡延光等用模拟退火和禁忌搜索算法求解带时间窗的多重运输调度 问题1 2 。张涛等用禁忌搜索算法和3 - o p t 组合优化方法解决多车队运输调度问题 【2 引。李军等用序列优化启发式算法求解组合运输调度问题【2 3 1 。郎茂祥针对遗传算 法在局部搜索能力方面的不足，提出将爬山算法与遗传算法相结合来求解物流配 送路径优化问题【2 4 1 。邓爱民把这种混合遗传算法应用到了城市配送系统的路径优 化上，并提出了基于c r m g i s 的智能化可视配送系统【2 5 1 。张潜等在重点考虑总成 本最小和准时两个目标的基础上，提出一种先用优先级综合聚类分析法将客户分 类，再用带有控制开关系统的改进遗传算法求解多目标v r p 的优化方法【2 6 1 。崔雪 丽等给出了一种可快速求解v r p 的蚂蚁搜索算法，该算法通过定义基本的人工蚂 蚁状态转移概率，并结合局部搜索策略，用迭代次数控制算法的运行时间1 27 1 。黄 红针对某烟草物流配送系统应用g i s 技术，将其配送路径抽象为t s p 问题，完成 现实空间到问题空间的映射，并采用单纯形法和贪婪法配合使用来求解【2 引。刘敬 青采用t r a n s c a d 技术为v r p 问题提供了另一种解决方案【2 9 1 。 1 2 3 关于集配货一体化v r p 的研究 集配货一体化车辆路径规划问题比v r p 问题更复杂，也是一个n p 难题，最 初可以追溯到上世纪8 0 年代逆向物流概念的提出，随着大家对逆向物流的关注， 把正向物流的配送和逆向物流的回收服务糅合到一起，形成了v r p p d 问题。纵观 国内外文献，v r p p d 问题乃是根据路线中顾客需求性质把v r p 问题划分为三类 中最复杂的一类。根据路线中顾客需求的性质，可以把v r p 问题划分为： ( 1 ) 纯粹送货或纯粹集货( p u r ep i c k u po rp u r ed e l i v e r y ) ：这是传统的车辆路径规 划问题，所有顾客的需求只能是纯粹送货或纯粹集货。 ( 2 ) 只允许回程集货：此类问题将顾客需求点分成两个集合：一个是送货的集 合：另一个是集货的集合。并且限制送货点与集货点不能混合作业，亦即车辆在 每一个路径规划中，必须先服务送货点的顾客后，才可以服务集货点的顾客。 ( 3 ) 允许同时处理集货和送货的混合作业：此类问题是假设当某一顾客需求点 同时存在送货需求和集货需求时或存在单纯的集配货需求，允许在该顾客点同时 进行送货作业和集货作业。即只对该顾客访问一次，并完成送货和集货的作业。 物流配送企业集配货一体化v r p 研究 只允许回程集货的作业方式强调必须送完货后才可集货，但当某个需求点同 时有送、集货的需求时，将会造成对一个需求点访问两次。另外限制集货作业只 能在所有送货作业完成后才可发生，会使车辆的路径规划规划比较缺乏弹性，可 能会因为要满足这一项限制，而增加运送距离和运送成本。因此，允许在顾客点 同时进行送货作业和集货作业，只对顾客访问一次，就完成顾客点的送货和集货 作业具备良好的成本优势。由于允许同时集配货，就存在一个重新整理货柜或货 品摆放的问题。对此的初步解决办法是，为配送车辆设计两个搬运出口，一个用 于送货，一个用于集货，并最开始给车辆留一定的比例空间( 比如说2 0 ，可以因 情况而变化) 用于集货，按照先进后出( f i l o ) 原则对需要配送的货品进行堆放。 故本研究所考虑的带时窗集配货一体化车辆路径规划问题可以描述为：设有 一物流中心，共有足辆车容量都为q 的货车，有，位顾客，每位顾客的坐标及其所 需配货量吐和集货量b 已知，并且客户要求在一定时间段【巨，厶】内获得服务，货车 从顾客f 到相邻顾客，的运输距离为口，。v r p p d 问题即必须在不违反车辆容量限制 条件下，使用k ( 0 k k ) 辆货车自物流中心出发服务所有的顾客后再回到中心， 同时满足顾客的集配货需求，且每位顾客能且仅能被一辆车服务一次，要求总配 送成本为最小。 国内外关于v r p p d 问题的研究较少，从目前研究的进展来看，主要在于 v r p p d 数学模型研究及v r p p d 求解算法方面的研究。v r p p d 数学模型主要 基于两种形式1 3 0 j ：一种以车流为基础，针对单车型，有装载能力约束的v r p 编制的基于三下标车流变量的数学模型，如模型l 。这种模型主要优点是建模 简单，考虑的约束条件较少，能够很快求出问题的解，但是正因为其考虑的 约束条件少，导致其模型与现实情况不尽相符，其求得的解也不尽如人意。 另一种模型是以物流为基础，针对多车型、有最长行驶距离限制、车容量限 制的双下标物流变量组成的数学模型，如模型2 。相较于第一种数学模型，该 模型具有以下特点：( 1 ) 目标函数和约束条件较为全面和接近实际；( 2 ) 决策变 量、目标函数和约束条件的表示较为自然、直观和易于理解。但是其求解也 复杂的多。 此外，孙小年等提出了基于车辆使用数和运行距离最短双目标优化的数 学模型【3 。和前两种模型相比，这种模型的最大不同主要体现在目标函数的 不同上，其第一目标函数为使配送车辆数尽可能少，第二目标函数为使包括 与配送距离相关的成本和车内货物整理费用总配送成本为最小。这种模型最大 的特点是扩展性好，可以多目标优化。同样其求解也很复杂。 从使用频率来说，大部分学者的研究都是基于第一种数学模型或其变形 形式，占据了主流位置，如j a nd e t h l o f f t 32 1 ，l a uh c 等【3 ”，谢秉磊等【34 1 ，霍 佳震等【3 5 】等都是使用的该模型。郎茂祥【3 6 1 在姜大立等【3 7 1 的基础上提出了基于 硕上学位论文 直观描述的第二种数学模型。孙小年等使用的则是第三种数学模型【3 1 1 。三种 数学模型描述如下： 模型1 ： m m z = 勺嘞 目标函数模型： z = 乙乙乞勺嘞 目标函数 i = 0j = 0k = l ， l j i d , y , k q ， k = l ，k b 虼q 车辆载重约束 虼= l ，后= i k = l i r 基本任务约束 z y o 。= k i k = l j ，、 = ，j = o ，1 ，；七= 1 ，kl i = 01 ， 道路约束 x u k = 坛，i = o ，1 ，i ；k = 1 9 o ，k i s o = 0 x 噼2 1 s i + | i + | u2 s j f ，y = 0 ，l ；i 歹 e jss js l j ，j = 、，i = m a x e , 一i ，0 时间窗约束 啄i , j 嚣0 , 1 兰i ；k = 兰k 峨卜 = ，= 1 ，j 模蛐m i n z=浆ear,一sign(n,)k=l i = 1) 目标函数 模型2 ： z = i。+ 吒咯。l 目标函数 吼q f 掌l 壹+ n k 吼毁，歹：l ，体一1 i = 1 i = j + l 雌 q t = l 车辆载重约束 q 一、 乃 一 哆 ，一坛 一 一 一 0 物流配送企业集配货一体化v r p 研究 噍厢+ 咯。j 忉( 体) 皿 道路约束 ，= l 茹k l l 体= ，l = i 1 ， ，i - 1 ，n k f 基本任务约束 r = i 1 ，班 ， i & 厂、& = 囝乞j ，+ + 乞q r k v - l ，+ 2 屯1 = m a x a , 一t ，0 ) = 1 川2 时间窗约束 一t ，) i s i ：蚓互一厶，o ) ，总的因时间 窗产生的费用则为两部分之和。本文就是针对这种时间窗来建立数学模型的。 综上所述，本文将模型的优化目标设定为：使车辆出行成本，与距离相 关的配送成本和因未在规定时间窗完成服务造成的成本这三者的综合配送成 本为最低，其基本目标函数式为m i n z = k * c - i - w 木d + 8 。其中k 表示配送方案使用 的车辆数，w 为每公里配送成本，d 表示配送总距离，6 表示客户未能在规定时 间窗内获得服务产生的成本。 2 2 模型假设 物流配送企业集配货一体化v r p 研究 配送路线方案目标的实现过程受到很多约束条件的限制，因而必须在满 足约束条件的限制下取得成本最低的目标。其中常见的约束有：( 1 ) o r 货人对 货物品种、规格和数量的要求；( 2 ) 收货人对货物送达时间或时间范围的要求； ( 3 ) 道路运行条件对配送的制约，如单行道、城区部分道路对货车通行的限制； ( 4 ) 车辆最大装载能力的限制；( 5 ) 车辆最大行驶里程数的限制；( 6 ) 司机的最长 工作时间的限制；( 7 ) 各种运输规章的限制等等。 v r p p d 是一个非常复杂的问题，要建立其数学模型，如上所述需要考虑 很多因素和约束条件。为了简化问题，方便建立v r p p d 问题数学模型，本文 提出以下假设： ( 1 ) 只有一个物流中心； 本文所研究的问题是关于集配货体化的物流配送，配送范围相对较小， 一般针对一个城市，通常来说，企业在某个城市只有一个物流中心。这样就 可以把问题简化了。因此，可以假设一个物流中心对应多个用户需求，并且 物流中心之间是相互独立的，于是就不存在多个物流中心货物重叠问题。 ( 2 ) 物流中心与需求点的坐标位置及需求量皆为已知； 物流中心和各需求点位置是固定的，可以通过电子地图软件测量出来， 因此是可知的。需求点的需求量通常由需求点向物流中心申报，因此也是可 以在安排线路之前知晓。 ( 3 ) 配送车辆车型一致，即车容量一样； 现实中，物流中心通常都拥有不同型号的配送车辆，以应对不同货物量 的配送。但是，相同型号的配送车辆便于管理，可以提高工人装载货物的效 率。本文假设配送车辆车型一致，可以大大简化问题的复杂度，从而减少解 的复杂性，提高算法的搜寻速度。 ( 4 ) 考虑配送受软时间窗限制，即客户对货物的需求有时间窗的规定； 如客户未能在规定的时间窗内获得服务，则要遭受惩罚，产生一定的成 本，该成本计入优化目标函数中。车辆在客户i 停留的时间除了等待时间之外， 还有货物的装卸时间，假设装卸时间与货物量成正比，每单位货物需要的装 卸时间为，则所需的装卸时间为t ( p i + 玑) 。 ( 5 ) 每辆车服务一条回路，由场站出发且最终回到场站；