（管理科学与工程专业论文）基于沿途补货策略的车辆路径问题模型与算法.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 当前的物流配送业务发生了很大的转变：从区域上来说，物流业务范围扩大， 物流服务区域进一步整合；从时间上来说，下游需求企业需求批次增多、需求周 期和供货提前期缩短；从物流企业服务水平标准来说，快速响应市场需求和物流 系统更大的柔性成为衡量其物流能力的重要指标。可见，现代物流系统已形成了 服务大区域多仓库、多需求点的物流配送网络格局，此种物流系统需具备快速响 应的能力和更强的满足随机需求的柔性结构。传统的基于分区的配送模式逐渐不 能满足当前的物流网络发展需求。 本文打破分区的配送格局，从整体上直接构建跨区域多对多的联合配送网 络，并且在进行车辆路径规划时考虑采用沿途补货策略，这样不但平衡了区域间 物流负载、促使物流资源在大区域上的共享，而且还提高了系统柔性和快速响应 需求能力。全文建立了新配送模式下的一系列数学规划模型与启发式算法，如下： ( 1 ) 基于沿途补货策略的闭环车辆路径问题模型与算法，形成了闭合回路的沿 途可补货的车辆路径，其中基于几何分析的分批插入启发式算法构造的是一条单链 的车辆路径，而改进的渐次节约启发式算法建立的是一个具有多链的车辆路径方 案。仿真试验的结果表明，较之分区配送模式下的车辆路径，优化效果均达到l o 左右。 ( 2 ) 基于沿途补货策略的开放式车辆路径问题模型与算法，包含了两组模 型和算法：基于沿途补货策略有时间约束的开放式车辆路径问题模型和渐次节约 的启发式算法，此模型对于曲线路径实例进行了求解，优化程度明显；基于沿途 补货策略的多品种随机开放式车辆路径问题模型，对于此模型只是将其转化为确 定性问题，以便于采用软件或确定性问题的算法进行解决。 ( 3 ) 基于沿途补货策略的混合车辆路径问题模型与算法，也包含了两组： 基于沿途补货策略的混合车辆路径问题模型和带补货控制因子的蚁群算法：基于 沿途补货策略带软时间窗的混合车辆路径问题模型及其蚁群算法。仿真试验结果 表明算法具有较高的优化水平和良好的稳定性。 ， 结语部分指出了上述模型与算法的不足之处和未来的发展方向。 关键词：沿途补货跨区域联合配送开放式车辆路径问题混合车辆路径问题启 发式算法 第l 页 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 日期：2 口9 跨b 月弓日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中师 范大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位 论文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 糊签名力 日期：乙p d 净b 规定享受相关权益。回童途塞握銮卮进卮；旦圭生；旦二生；旦三生筮查17 名：泓眠孙签名力气 日期：1 。9 净b 月乙日 日期：79 p 净1 ) 月j 7 日i 几 丕 月 何，广 川jp 一烈 名p 弛沙 者期 硕士学位论文 m a s t e r st h e s i s 1 绪论 1 1 研究背景与课题来源 区域经济一体化，产品分散化网络制造以及客户需求的多样性转变，使得当前 企业的物流配送业务发生了很大的变化：一是单个配送中心的服务区域持续扩大， 相邻区域之间边界更加模糊。这使得区域之间的交叉运输频繁发生，逐渐打破了基 于配送中心分区的服务模式，而相邻分区在边界区域的重复服务造成大量的物流资 源浪费。二是配送作业由传统的大批量、小批次向小批量、多批次转变。单个需求 点的单次需求量大幅减少，而订货次数则相应增加，组织一次订货和配送的单位产 品边际成本增大，返程空驰等情况大量存在。三是各需求点对配送服务的时间要求 越来越高。如何满足市场对时间资源的要求也成为物流服务部门设计物流系统的关 键考虑因素之一。四是配送业务的随机性增强。个性化转变的市场以及应急需求使 得下游销售企业在需求品种、需求量和需求时间上都表现出更大的随机性。 综上，现代的物流配送系统发生了很大的转变：从区域上来说，物流业务范围 扩大，物流服务区域进一步整合；从时间上来说，需求方的需求批次增多、订货周 期和采购提前期缩短；从物流企业服务水平标准来说，快速响应市场需求和物流系 统更大的柔性成为衡量其物流能力的重要指标。总之，现代物流系统需具备服务大 区域多仓库、多需求点的物流配送网络格局，此种物流配送系统需具备快速响应的 能力和更强的适应随机需求的柔性结构。如何改进当前的物流配送系统，以适应新 环境的发展需求是物流配送优化研究的一项重要内容。 在对配送系统优化研究中，车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 是 其中的重要组成部分和关键技术。本研究尝试打破传统的分区配送模式，关注于构 建跨区域联合配送模式、配合采用沿途补货策略( s t r a t e g yo fr e p l e n i s h m e n ta l o n g r o u t e ，s r r ) ，以求解具有多配送中心、多需求点跨区域联合配送系统中v r p 的若 干模型与算法。 本论文的研究受到了多个基金项目的资助，其中包括： ( 1 ) 教育部人文社会科学研究青年基金项目：“基于时间竞争的集成物流管 理研究( n o 0 5 j c 6 3 0 0 7 4 ) ”； ( 2 ) 武汉市社会科学基金项目：“促进湖北省中小企业发展的集成物流服务 第1 页共6 3 页 顾士学位论文 m a s t e r st h e s i s 体系研究( n o 0 6 0 3 0 ) ； ( 3 ) 北京大学联泰供应链系统研究与发展中心公开招标课题：“中小企业动态 集成项物流管理模式与方法研究 。 本文的研究作为各资助项目中的配送系统路径优化子模块的部分内容。 1 2 研究综述 1 2 1 车辆路径问题 v r p 是物流管理研究中的一项重要内容，它由d a n t z i g r a m s e r ( 1 9 5 9 ) 首先 提出，立刻便引起了运筹学、管理学、计算机应用、组合数学、图论等学科的专家 学者的高度重视。他们对此问题进行了大量的理论研究和实验分析，取得了很大的 研究进展，研究成果在运输系统、物流配送系统、快递收发系统中都已得到了广泛 应用( 郭耀煌& 李军，1 9 9 5 ) 。v r p 一般定义为：对一系列发货点和或收货点， 组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件( 如货物需 求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下，达 到一定的目标( 如路程最短、费用最小、时间尽量少、使用车辆尽量少等) ( f i s h e r ， 1 9 9 5 ) 。 1 2 2 车辆路径问题模型 1 2 2 1 模型分类 一般来说，v r p 可以构造成整数规划模型，也可以构造成图论及其他模型， 这些模型之间存在着某种联系。但从建立模型时的出发点考虑，大多数模型都可 看成是下面三种模型的变形与组合：( 1 ) 以车流为基础的模型；( 2 ) 以物流为基 础的模型；( 3 ) 聚覆盖模型。在v r p 模型方面，常见的主要有以下分类： ( 1 ) 车载容量有限制的v r p ( c a p a c i t a t e dv r p ，c v r p ) 是v r p 中的最基 本类型，其它类型的问题都是在此基础上派生出来的。 ( 2 ) 有时间约束的v r p ，包括：带时间窗的v r p ( v e h i c l er o u t i n gp r o b l e m w i t hh a r dt i m e w i n d o w s ，v r p h t w ) ，带软时间窗的v r p ( v e h i c l er o u t i n gp r o b l e m w i t hs o f tt i m e w i n d o w s ，v r p s t w ) 。另一变异分支，带最后时间期限的v r p 第2 页共6 3 页 硕士学位论文 m a s t e r st h e s i 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 ed e a d l i n e s , v r p t d ) 。 ( 3 ) 在带取送作业的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 ) 中，每 个需求点，货车既需送货过去后又需带回货物。 ( 4 ) 随机需求v r p ( v e h i c l er o u t i n gp r o b l e mw i t hs t o c h a s t i cd e m a n d ， v r p s d ) ，这里包括需求点随机的v r p ，需求量随机的v r p ，需求时间、到达时 间随机的v r p 。 ( 5 ) 多车型v r p ( m i x e d h e t e r o g e n e o u sf l e e tv e h i c l er o u t i n gp r o b l e m ， m f v r p h f v r p ) ，主要包括单车型v r p 和多车型v r p ，不同的车型其配载量也 不同，服务路径长度也不同。 ( 6 ) 动态v r p ( d y n a m i cv e h i c l er o u t i n gp r o b l e m ，d v r p ) ，在车辆运行路 网的路段运行成本( 时间) 随出发时间变化或依概率随机变化的情况下，车场安 排车辆和运输路线以满足系统要达到的目标。 目前较为前沿的研究主题有主要有以下几种： ( 7 ) 开放式诤( o p e nv r p ，o v r p ) ，相对闭环v r p 提出，指路径不闭 合的v r p 。( s a r i k l i s & p o w e l l ，2 0 0 0 ；s c h r a g e ，1 9 8 l ；b r a n d a o ，2 0 0 1 ) ( 8 ) 集货供货一体化的v r p ( v r pw i t hp i c k u p sa n dd e l i v e r i e s ，v r p p d ) ： 即车辆在送货之前要先取货的问题。( m o n t a n e & g a l v a ，2 0 0 6 ) ( 9 ) 分批交货v i 冲( s p l i td e l i v e r y v r p ，s d v r p ) - 相当于满载问题，一个 客户的需求需要多个车来满足。( h o & h a u g l a n d ，2 0 0 4 ) 1 2 2 2 建模方法 ( 1 ) 专家离线构建模型+ 计算机辅助求解的建模方法。过去一般都采用这种 方法，此种模式比较适用于配送流量集中，问题条件固定的物流活动。对于现代 更多涉及的动态、随机车辆路径网络效果不是很好。 ( 2 ) 智能建模方法。王征，向阳和胡祥培( 2 0 0 7 ) 以人类建模思维规律为 依托，提出了基于结构差异的智能建模方法，实现了v r p 的智能建模系统，增 强了人机交互和虚实结合的元素，解决了v r p 动态性导致问题建模不能实现的 瓶颈。 1 2 3 车辆路径问题算法 v r p 求解算法可以分为精确算法与启发式解法，其中启发式算法又可以分为 第3 页共6 3 页 顾士学位论文 m a s t e r st h e s i s 纯启发式算法和亚启发式算法( l a p o r t e ，g e n d r e a u ，p o t v i n ，2 0 0 0 ) 。 1 2 4 1 精确算法 求解v r p 问题的精确算法主要有分枝定界法、割平面法、动态规划法、网 络流算法等。 ( 1 ) 分枝定界法。该方法是l a p o r t e 等( 1 9 8 6 ) 提出的，p a d b e r g ( 1 9 9 1 ) 对此方法进行了改进。 ( 2 ) k 度中心树算法。该方法是c h r i s t o f i d e s t 等( 1 9 8 1 ) 提出的。对固定m 的m t s p 进行k 度中心树松弛。f i s h e r ( 1 9 9 4 ) 对它做了进一步的改进，可求解 有1 3 4 个客户的v r p 。 ( 3 ) 列生成方法。r a o & z i o n t ( 1 9 6 8 ) 引入了列生成方法进行求解v r p ， 其算法本质上是最短路径算法同时结合了分枝定界算法。l o r e n a ( 2 0 0 4 ) 对v r p 的列生成方法进行了改进。 ( 4 ) 拉格朗日分解法。k o h l & m a d s e n ( 1 9 9 7 ) 用拉格朗日松弛算法求解带 有时间窗的v r p ，f u m e r o ( 2 0 0 0 ) 提出了修正拉格朗日松弛及子梯度优化方法。 精确算法主要适用于解决问题结构比较清晰、所含各元素之间的关系明确、 边界清楚的良性结构问题。7 但是，实际中许多v r p 不具有良性结构，并且往往 不存在严格最优解，因而常常无法避开指数爆炸问题，该类算法只能有效求解小 规模的v r p 问题。 1 2 4 2 纯启发式算法 实质上，v r p 的求解方法，基本上可分为纯优化算法和纯启发式算法两大类： 由于纯优化方法在实际中应用范围很有限，为此，专家学者们主要把精力花在构 造高质量的纯启发式算法上。目前已提出的纯启发式算法相当多，大体上可分为 以下几类： ( 1 ) 先分组后安排路线的方法。这种方法先按节点和或弧的要求进行分组 或划群，然后对每一组设计一条经济的路线。如s w e e p 算法( g i l l e t t & m i l l e r ， 1 9 7 4 ) ，然而此算法为非渐进优化算法，一般仅适用于装货或卸货问题。 ( 2 ) 先安排路线后分组的方法。这种方法首先构造一条或几条很长的路线 ( 通常不可行) ，它包括了所有需求对象，然后再把这些很长的路线划分成一些 短而可行的路线。具体进行时，一般是先解一个经过所有点的旅行商问题，形成 第4 页共6 3 页 硕士学位论文 m a s t e r s t h e s i s 一条路线，然后根据一定的约束( 如车辆容量等) 对它进行划分。 ( 3 ) 节约插入算法。c l a r k & w r i g h t ( 1 9 6 4 ) 提出的节约法，该算法简单快 捷，但是也存在未组合点零乱、边缘点难于组合的问题。刘向，李延晖( 2 0 0 6 ) ， l i u & l i ( 2 0 0 6 ) 应用一种渐次节约的启发式算法求解了基于沿途补货特征的闭 环v r p 问题和基于时间约束的o v r p 问题，均取得了良好的优化效果。 ( 4 ) 改进交换法。在始终保持解可行的情况下，力图向最优目标靠近，每 一步都产生另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到 不能再改进目标函数值为止。 ( 5 ) 基于数学规划的算法。把问题直接描述成一个数学规划问题，根据其 模型的特殊构型，应用一定的技术( 如分解) 进行划分，进而求解已被广泛研究 过的子问题。 1 2 4 3 亚启发式算法 ( 1 ) 禁忌搜索算法( t a b us e a r c ha l g o r i t h m ) 是对局部邻域搜索扩展后的一 种全局逐步寻优算法。该算法由g l o v e r ( 1 9 8 6 ) 首次提出。该算法的搜索速度快， 效率高，适用于大规模的优化计算，w i l l 棚( 1 9 8 9 ) 、c h a o ( 2 0 0 2 ) 、s c h e u e r e r ( 2 0 0 6 ) 、 b r a n d l i o & j o s 6 ( 2 0 0 4 ) 、h o & h a u g l a n d ( 2 0 0 4 ) 、m o n t a n e & g a l v a o ( 2 0 0 6 ) 、袁 庆达等( 2 0 0 1 ) 分别用此算法求解了不同类型的v r p 。而f u & e g l e s e ( 2 0 0 5 ) 、 钟石泉、杜纲( 2 0 0 7 ) 等则分别用改进的禁忌搜索算法求解了多目标的o v r p 、有 能力& 距离约束的o v r p 。 ( 2 ) 模拟退火法( 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 ) 是由k i r k p a t r i c k 等( 1 9 8 3 ) 提出的一种求解组合最优化问题的算法。该算法法具有收敛速度快、全局搜索的 特点，o s m a n ( 1 9 9 3 ) 对v r p 的模拟退火算法进行了研究，他提出的模拟退火方法 主要适合于解决路线分组。b e n t & v a n ( 2 0 0 4 ) 则首先用模拟退火算法将车辆路线 的数量最小化，然后用大邻域搜索法将运输费用降到最低。u l u n g u & t e g h e m ( 1 9 9 4 ) 对此种算法进行了改进，可以解决多目标问题。p i s i n g e r & r o p k e ( 2 0 0 7 ) 提出基 于模拟退火算法的自适应的大规模邻域搜索启发式算法求解o v r p 问题。 ( 3 ) 神经网络算法( n e u r a ln e t w o r k sa l g o r i t h m s ) 由m c c u l l o c h & p i t t s ( 1 9 4 3 ) 提出，模型主要是利用神经网络中神经元的协同并行计算能力来构造的优化算 法。袁健和倪勤( 2 0 0 1 ) 用神经网络算法求解了随机需求情形的v r p 问题。神 经网络算法求解v r p 问题可能会导致网络最终收敛于局部极小解，并且，网络 第5 页共6 3 页 硕士学位论文 m a s t e r st h e s i s 最优的最终结果很大程度依赖于网络的参数，参数鲁棒性较差。 ( 4 ) 遗传算法( g e n e t i ca l g o r i t h m s ) 具有求解组合优化问题的良好特性，h o l l a n d ( 1 9 9 2 ) 首先采用遗传算法编码解决有时间窗的v r p ，最近也有不少学者在做这方 面的工作( b e r g e r ，b a r k a o u i ，o l l i b r a y s y ，2 0 0 3 ；b e r g e r & b a r k a o u ，2 0 0 4 ) 。钟 石泉，杜纲和贺国光( 2 0 0 6 ) 开发了的遗传算法求解了有时间约束的o v r p ，均 取得了良好的效果。由于遗传因子的表现依赖于设计者的能力，算法以延长计算 时间为代价，所以现在多数学者采用混合策略，o m b u l d ( 2 0 0 2 ) 提出了用遗传算 法进行路线分组，然后用禁忌搜索方法进行路线优化的混合算法。 ( 5 ) 蚁群算法( a n tc o l o n ya l g o r i t h m ) 。g a m b a r d e l l a & d o r i g o ( 1 9 9 5 ) 最 早将该算法应用到路径规划问题上来。此后，g a m b a r d e l l & d o r i g o ( 1 9 9 6 ，1 9 9 7 ) 、 s t u t z l e & h o o s ( 1 9 9 7 ) 、b u l l n h e i m e r 等( 1 9 9 9 ) 以及m a z z e o l o i s e a u ( 2 0 0 4 ) 都有分别用该算法解决路径规划问题并获得成功。李延晖，刘向( 2 0 0 8 ) 开发了 带有补货控制因子的蚁群算法，求解了具有沿途补货特征的多车场、带软时间窗 的o v r p 。但是这种算法常常搜索时间较长，且容易出现停滞现象。 ( 6 ) 粒子算法是由k e n n e d y & e b e r h a r t ( 1 9 9 5 ) 提出的一种基于群智能方法 的演化计算技术。用粒子算法求解v r p 问题具有收敛速度快、依赖的经验参数 少、简便易行等特点。黄岚等人( 2 0 0 3 ) 通过引入交换子和交换序的概念，构造 出一种特殊的粒子群优化算法求解旅行商问题。肖健梅等人( 2 0 0 5 ) 设计了一种 新的实数编码方案，将v r p 转化成准连续优化问题，并采用罚函数法处理约束 条件，从而把粒子算法应用于v r p 的求解。但与其他进化类优化算法一样，存 在易于陷入局部最优的缺陷。 此外，近年来也有学者借鉴了免疫系统的自组织学习、自适应调节的特点， 提出了用免疫算法来求解v r p 问题。例如，免疫克隆算法能快速收敛于全局最 优解，克服了遗传算法中易陷入局部最优解和收敛速度慢的缺点，可有效地解决 物流配送车辆路径优化问题。 1 2 4 对研究现状的简要评述 ( 1 ) 在建模方法上，对于多配送中心、多需求点的车辆路径规划，多采取 分区的求解策略，先分组后安排路线，将问题转化为单配送中心、多需求点的 v r p 。此种处理方法方便易行，且在企业实践中普遍使用，但是如何分区、如何 确定每一配送中心的服务半径又成为一难点，并且分区的不合理往往导致不同分 第6 页共6 3 页 硕士学位论文 m a s t e r st h e s l s 区的物流负载不均衡。此外货车与配送中心多有专门的隶属关系，配送完成之后 即须返回始发点。 ( 2 ) 在路径设计策略上，对于货车载量有限制的v i 冲，处理方法或者是只 组织一次配送即停止配送、或者是返回原出发点补充货物接着进行下一阶段配送 任务，没有考虑货车就近于其他配送中心( 非始发点) 补充货物的情况。 ( 3 ) o v r p 是v i 冲的一大分支，然而近几年才逐渐引起人们的关注，目前 国内外在此领域的研究都不多，将o 冲和闭环v r p 结合起来构建实用性更强 的混合路径v r p 的研究就更少。 1 3 目的与意义 1 3 1 研究的目的 ( 1 ) 突破传统的基于配送中心分区的服务模式，采用沿途补货策略，构建跨 区域多对多的配送系统网络结构； ( 2 ) 根据决策环境的不同，建立几种符合管理实践的、基于沿途补货策略的 v r p 模型； ( 3 ) 设计合适的启发式算法对模型进行求解或对模型进行模拟，开发相应的 算法程序或模拟程序，使建立的模型具有实用性，同时，使设计的算法具有实际 可操作性。 1 3 2 研究的意义 ( 1 ) 本研究可充实物流配送管理理论研究的内容体系 v i 心是物流配送管理理论研究的重要内容之一，虽然对v r p 的研究由来已 久，但当前的研究主要是基于配送中心分区的服务模式，极少考虑跨区域配送的 问题，也没有采用沿途补货的配送策略。而本研究将在一个统一的研究框架指导 下，对基于s r r 的跨区域配送v r p 的相关问题进行探讨，内容之间既相对独立 性又彼此相关，预期的研究成果将丰富和充实物流与供应链管理理论研究的内容 体系。 ( 2 ) 本研究可为物流配送管理实践提供有力的理论指导 在当前的跨区域配送频繁发生的市场环境下，迄今为止还没有一套适应该环 第7 页共6 3 页 硕士学位论文 m a s t e r st h e s i s 境的车辆路径优化方法和技术，供应链整体响应时间过长、物流成本过高、车辆 利用率低下、返程空驰等现象普遍存在，企业的管理者迫切需要学术界对相关问 题进行结合实际的、系统深入的研究，并因此为他们的实际管理行动提供相应的 理论依据。本课题研究从企业的管理实践中提取科学问题，每一项研究内容都是 以现实为基础的理论探讨，相关的研究成果将为物流配送管理实践提供有力的理 论指导。 ( 3 ) 本研究有助于企业提高竞争力 基于沿途补货的车辆路径安排问题有利于优化企业的配送系统，提高企业的 物流能力。同时，该系统并不是一个孤立的系统，新的管理模式、运作方式、优 化调度技术等必然对企业的组织结构、企业文化等企业经营管理的方方面面带来 深远的影响，为整个企业管理的变革提供契机，从而帮助企业提高整体竞争力。 1 4 内容与创新点 1 4 1 内容如结构 本文在供应链管理、物流管理、系统工程、计算机程序设计等理论与方法的指 导下，对基于沿途补货的v r p 的若干模型与算法进行了研究。全文共分六章，主 要内容如下： 第一章，绪论部分。介绍本文的研究背景和课题来源；从问题描述、模型与分 类、精确算法、纯启发式算法、亚启发式算法几个方面对国内外相关研究进行了综 述，并进行了简要的评述；明确了研究的目的和的重要意义；对本文的主要工作进 行了简要的介绍；阐述了本研究的主要创新之处。 第二章，跨区域配送与沿途补货的v l 冲。说明了跨区域配送与沿途补货的含义， 探讨了采用该策略的优势；介绍了车辆路径安排的不同形式；在此基础上给出了基 于s 1 迥的v r p 与一般v r p 之间的区别，并说明了其适用范围。 第三章，基于s i 汛的闭环v l 冲模型与算法研究。本章包含了一个数学模型和 两个算法，其中基于几何分析的分批插入启发式算法构造的是一条单链的车辆路 径，而改进的渐次节约启发式算法建立的是一个具有多链的车辆路径方案。分别有 仿真实验对上述算法进行模拟测试。 第四章，基于s i 汛的0 v l 心模型与算法研究。本章包含了两个问题：基于s r r 有时间约束的o v r p 模型和算法，基于s i 讯的多品种随机0 v r p 模型。对于前者， 第8 页共6 3 页 顾士学位论文 m a s t e r st h e s l s 建立了数学模型与启发式算法，并进行了实例演算：对于后者，采用的方法是将其 转化为一个确定性问题，然后可以采用类似前者的算法来解决。 第五章，基于s r r 的混合v i 冲模型与算法研究。包含了两个模型、算法以及 仿真实验：一是基于s r r 的混合v 】廿模型与带补货控制因子的蚁群算法；二是基 于s r r 带软时间窗的混合v r p 模型与带补货因子的蚁群算法。 第六章，总结和展望。综述对比文中所提出的所有数学模型的异同，分析文章 的不足之处以及以后的研究方向。 1 4 2 主要创新点 ( 1 ) 跨区域联合配送体系 目前，多数物流企业仍然采用传统的基于分区策略的配送模式，强制构建“一对 多”的分割配送体系，且配送路径设计也是建立在出发时一次装载货物和闭环运输 基础上的。这一点与现在物流配送作业的区域广泛、客户众多并分散、业务量大且 频繁等特点是不相适应的，造成了大量的物流资源浪费，并且很难满足实际配送的 服务需求。故而本文打破这种配送格局，直接构建多对多( m 龃y - t 0 m 锄y ) 的跨区 域配送网络，在更大范围上寻求物流配送业务运作的整体最优化。该部分属于模式 创新的范畴，是基于s r r 的理研究的基础。 ( 2 ) 基于沿途补货的路径设计策略 在跨区域的联合配送网络中，采用沿途多对多的仓库补货策略可以有效提高物 流运输的服务水平和加强物流资源的有效整合。因为货车无需长距离返回始发仓库 补充货物，而是直接选择临近仓库直接补充货物继续下一阶段物流配送，但是目前 多数物流配送路径设计很少考虑采用沿途补货的配送策略。基于沿途补货的路径设 计策略是属于方法创新的范畴。 ( 3 ) v r p 的两个新研究领域 对于0 v l 冲的研究，目前国内外均处于起步阶段，本研究在这方面展开讨论， 并且与沿途补货的路径设计策略结合了起来，是对前沿领域的有益探索：而对于混 合式强，即将闭合式和o v i 冲结合起来研究，是本研究所提出的一个新的研究方 向。 第9 页共6 3 页 硕士学位论文 m a s t e r st h e s i s 2 基于沿途补货策略的车辆路径问题 2 1 跨区域联合配送与沿途补货策略 对于处理多仓库多需求点的物流网络，传统的v r p 解决办法是采用分区策略， 强制构建“一对多”( o n e t o m a n y ) 的分割配送体系，且车辆路径的设计建立在货车 出发时一次装载货物和闭环运输基础上的，如图2 1 所示。在这种多层管理结构和 分区的配送模式下，各配送中心( d c ，d i s t i l b u t i o nc e n t e r ，圆形表示) 只负责其 辖域内的分销点( r s ，r e s e l l e r ，三角形表示) 的货物供应，配送网络的优化也 多集中于各分割的区域内部。这种配送策略在网络需求点较少、批量较大且批次 较少的情况下是高效的。如图2 1 ，其中d c l 区域货车的折回是因为要回配送中 心补充货物。 图2 1分区策略下的配送路线 但是目前环境的变化，上述配送策略在一定程度上割离了区域之间的联系， 物流资源不能有效共享。从各区来说，某些出现了一定程度的物流能力剩余、物 流资源的闲置，而又有一些则出现了物流能力的不足，物流服务在各区之间的不 均衡，例如d c l 的物流繁忙程度就较其它两区要高。 本研究尝试打破区域界限，从整体上直接构建跨区域多对多( m a n yt om a n y ) 的配送网络结构，并且相应考虑采用沿途补货路径设计策略，即从任一配送中心 始发的货车可在途径的多个配送中心补充货物，对整个联合区域内的缺货需求点 进行货物供给。如图2 2 ，从d c 0 出发的货车完成一段运输任务之后在d c l 处 补充货物，再完成下一阶段的配送任务，最后停靠于d c 2 点。货车无需如传统配 送路径设计中的那样长距离返回始发仓库补充货物，而是直接选择临近仓库直接补 第1 0 页共6 3 页 顾士学位论文 m a s t e r st h e s i s 充货物继续下一阶段物流配送。 图2 2 跨区域联合配送下的车辆路径 相对分区配送策略来说，采取基于沿途补货的策略具有如下优势： 其一，这种策略强化了区域之间的合作和物流资源共享，在大区域上考虑物 流路径优化，物流资源统筹规划，解决了某些区域内的物流能力相对过剩和相对 不足问题，平衡区域物流负载。并且，现代企业信息系统的建立，信息化工作的 完善，也为跨区域、集成化的管理提供了条件。 其二，针对物流需求向小批量、多批次的转变，此种配送模式集中了更多需 求点的货物组织配送，进而可以提高运输批次，缩短运输周期，满足了需求点的 时间要求。 其三，就路径设计细节来说，减少了返程空驰、交叉运输等情况，提高了物 流工作效率。由于货车是就近补充货物，不必在长距离返回出发点，所以一定程 度上较少了返程空驰的问题；同样，由于是整体规划，排除了交叉运输的情况。 最后，由于在更大范围上整合物流网络，放宽了各种限制条件，在更大系统 中寻找解决方案称为可能，理论上来说对于此种系统可以获得更优解。并且，现 代建模技术和新算法的迅速发展，为大规模、大区域组合优化提供了强有力的支 持。 2 2 车辆路径安排的不同形式 v r p 分为：闭环车辆路径问题( c l o s e dl 0 0 pv r p ，c l v i 冲) 和o v r p 。本研究 主要对s r r 下c l v r p 、o 以及二者结合的模型与算法进行研究。下面对相关 概念作出较为详细的说明。 闭环车辆路径问题要求车辆完成运输任务后必须返回始发配送中心，整个车辆 路径路线为闭合的，一般也简称为v r p 。它的一般定义为：对一系列发货点和或 第1 1 页共6 3 页 硕士学位论文 m a s t e r st h e s i s 图2 7 混合车辆路径 2 3 沿途补货的车辆路径问题 沿途补货策略是相对一次装载货物策略而言的( 一般是指货车在开始出发时一 次装载货物) 。而在沿途补货路径设计策略下，货车可以多次装载货物，并且不限 于装载时间、地点和装载频次。如图2 2 所示，货车从d c 0 出发，途径d c l 时补 充车载货物，继续下一阶段的配送任务。 v r p r r 与一般v r p 的不同点在于：一般v r p 的起始点和到达点均为仓库， 配送路线上除此之外的其它各点均为需求点，货车仅为这一组需求点配送货物； 而v r p r r 除起讫点为仓库之外，行驶路线中包含多个待配送的需求点和可中途 停靠补货的仓库，货车在行驶过程中选择恰当的仓库进行补货从而为多组需求点 配送货物。从路线形态来看，v r p r r 路线似乎只是多个一般v r p 路线的简单连 接，其实不然，两者之间是有实质性差别的：一般v r p 强调单条( 局部) 路径 最优，多个单条( 局部) 最优路径的简单连接并不能保证获得整个配送区域内的 全局配送路线最优，而v r p r r 却强调全局路线最优和货车利用率最大化。 v r p r r 适用于以下两种情况：( 1 ) 单组车辆从某一车场( 仓库) 出发，旅行所 有需求点，中途车载不够时就近在仓库补充货物，以至完成所有需求点的运输任务， 最后停靠在仓库：( 2 ) 从不同仓库出发的多组车辆完成不同的一段或多段路线上各 需求点的配送任务，最后分别停靠在仓库。当对配送任务有更多的限制条件时，则 容易出现这种情况，比如对配送时间有严格限制，一队货车在给定配送时间内很难 完成配送任务，需要将这一路段分成多段，各段起点仓库的货车同时出发完成各段 货物的配送任务。 第1 3 页共6 3 页 硕士学位论文 m a s t e r st h e s i s 3 基于沿途补货策略的闭环车辆路径问题 3 1 基本假设 本文的模型假设： ( 1 ) 不考虑d c 的缺货情况； ( 2 ) 货车载量有限制； ( 3 ) 任一r s 的需货情况已知； ( 4 ) 货车起讫点可以不同，但每个配送中心的货车数量配送前后需维持不 变； ( 5 ) 任一r s 的需货量不会大于货车的载量，且由一辆货车供货。 在一般情况下，d c 的货物的存储量被认为是充盈的，发生缺货情况概率较 小，因此假设条件( 1 ) 成立；相对于无载量限制的v r p 问题，假设条件( 2 ) 更符合实际情况；通过企业的信息系统，r s 的需货信息可以由各r s 的p o s 销 售终端得到，假设条件( 3 ) 满足：为区别于一般的v r p 问题，假设条件( 4 ) 是本问题所必须；管理实践中，r s 的需货量可能会大于单辆货车的载量，但此 时可以用车队替代“货车”，则假设条件( 5 ) 可以满足，在这里我们仅用“货车” 进行表述以简化问题。 3 2 数学模型 3 2 1 符号定义 _ ，) ： 下标集： m d c 数量，m = 1 ，2 ，聊； ，r s 数量，i = 1 ，2 ，毋； r 与m 的并集，r = i u m 。 决策变量： 而j o 1 变量，表示货车由f 地到歹地( 1 表示由i 到，0 表示i 不到 第1 4 页共6 3 页 顾士学位论文 m a s t e r st h e s i s 从f 地到地的运输量。 常数： 铂从f 地到地的运费： d i i 地的需求量： w 货车载量。 3 2 2 数学模型 目标函数是使得整个配送系统的总费用最小，该问题是一个混合整数非线性 规划： 舟月 m i n f = 勺而 ( 3 1 ) i - ij 硝 胄 s t b = 而= 1( v i e i ，i # j ) ( 3 2 ) = l户l ( v k m ) ，= 矗f w( v ie l ，mem ) r ( 一嘭) o ( v j f ，) rr ( - d ) = x j , w j ,( v j # i ，j e i ) i = 1k = l ( 3 3 ) ( 3 4 ) ( 3 5 ) ( 3 6 ) x , j o ，1 ( v f j ，i ，_ ，尺)( 3 7 ) 目标函数( 3 1 ) 使物流系统的总费用最小。约束条件( 3 2 ) 使从各r s 进出 的路径都只有一条；约束条件( 3 3 ) 保证进出各d c 的路径条数相等，这使得每 个d c 保持有一辆货车可以派遣：约束条件( 3 4 ) 表示从d c 出发的货车的运输 量为货车载量，此条件为约束条件( 3 5 ) 、( 3 6 ) 的初始条件；约束条件( 3 5 ) 表示进入任一r s 之前，货车有足够供给这个r s 的货物，而对于进入d c 时则 无货运量的限制；约束条件( 3 6 ) 表示货车经过r s 点是运输量的改变关系式； 约束条件( 3 7 ) 保证x 为o 一1 变量。 第1 5 页共6 3 页 ，闰 = h ，渊 硕士学位论文 m a s t e r 。st h e s i s 3 3 形成单链的启发式算法 3 3 1 基于几何分析的分批插入启发式算法 本文所考虑的问题涉及沿途多次补货的情况，选取哪些d c 参与补货尚不确 定，故直接应用上述算法不妥。由问题的特殊性，本文开发出一种分批插入的启 发式搜索方法，并将该搜索方法与n o r b a c k & l 0 v e ( 1 9 7 7 ) 提出的几何法 ( g e o m e t d ca p p r o a c h e sm e t h o d ) 相结合，所形成的启发式算法可以避免求解非 线性规划，并且在简化模型、提高求解速度的同时，达到在较短的时间内得到问 题较优解的目的。 总体思路为：首先通过对各访问点构成的几何图形的分析，可以得到一条初 始路径；然后进行二次搜索，并采用分批插入r s 、d c 的策略，确定不在初始访 问路径上的r s 、d c 点的插入顺序和插入位置，从而最终构成一条可以进行沿途 补货的、历经所有需求点的配送回路。为了方便算法描述，给出以下几个名词的 定义： 定义1 ：最大补货范围某一d c 的满载的货车，沿确定路径，对r s 补货， 最多可补足的点的集合。 例如下图所示，其中货车的载量为5 吨。 需货量( 吨) 1 81 71 6 1 5o1 92 o 0 2 1 卜i 广圆 卜谗卜广一 r s d c r s i r s2 r s 3 r s4 d c l r s5 r s 6 d c2r s7 则d g 的最大补货范围为 兄蜀，兄s ，兄是 或f 飚，飚，d c 2 ) ，其中月& 、d c 2 为d c l 可到达的最远点。 定义2 ：不满足条件路段除两端是d c 外，其余点都是r s 的路段，且沿 此路段方向任一d c 可到达的最远点都不能达到另一端。 算法步骤如下： s t 印1 ：找出欲访问点( r ) 构成的凸包； s t 印2 ：在凸包上的点，按其出现的自然顺序访问( 不要使访问路径自交) ， 从而形成一初始访问线路q ； s t e p 3 ：将不在初始访问路线q 上的各r s 点d ( 位于凸包内的访问点) 与已在 访问路线上的所有点相连，设p ，q 为已在访问路线上的任两相邻点，设么只d o q o 第1 6 页共6 3 页 顾士学位论文 m a s t e r st h e s i s 为所有l p o q 角度中的最大者，则将d o 插入到p 0 ，q o 之间； s t e p 4 ：重复s t e p 3 ，每次在访问路线上增加一个新点，直到所有r s 点被引入 到访问路线中； s t e p 5 ：若形成的回路不经过任何d c ，将各d c 点z 与已在访问路线上的所 有点相连，设nu 为已在访问路线上的任两相邻点，设l z o z o u o 为所有l f z u 角 度中的最大者，则将z o 插入到，矾之间； s t e p 6 ：考察已形成的回路，对不满足条件路段进行调整，设k l ( k ，l 为两 端点d c ) 为不满足条件路段，将x 、三沿此路段方向的最大补货范围的交集记 为彳，则： ( 1 ) 若a 中元素个数大于1 ，将各d c 点d 与a 中任意两相邻点口、c 相 连，设么鼠或c 0 为所有么肋c 角度中的最大者，则将d o 插入到b o ，c o 之间； ( 2 ) 反之，设敏) 可到达的最远点为y ，而y ( 忉的后续( 前续) 点为 只回，将各d c 点丁与( y ，d 、( g ，h ) 分别相连，设么虼瓦磊为所有z y t f ，z g t h 角度中的最大者，则将死插入到，凡之间； s t e p 7 ：重复s t e p 6 ，每次在访问路线上增加一个新点，直到回路中不存在不 满足条件路段为止。 即得沿途可补货的链式配送路径。 3 3 2 算法复杂度分析 设凸边形中包含r s 点的数目为口( 口 d ，包含d c 的数目为6 ( 6 刈坳，则插入 其余二口个r s 点，需要比较的角的个数为( 口+ 6 ) 似口) ，故循环次数n s t e p 3 - 4 = ( 口+ 6 ) 似口) ， 在不符合条件处插入d c 点，因在何处也要视具体情况而定，而若在链中任何两 相邻r s 点中都需插入d c 时，相邻r s 最多有 1 个，故需要比较的角的个数为 m ( i - 1 ) ，即有循环次数玎，印” m ( ，一1 ) ，综上，本算法可在多项式o ( m i ) 复杂度 范围内完成 3 3 3 仿真实验 图3 1 为某电子商务企业在某一天的物流配送网络截图，包含4 个d c 和1 6 第1 7 页共6 3 页 个r s ，现将4 个彼此分离的配送区域组合成一个联合配送区域，此时问题为： 如何制订配