（管理科学与工程专业论文）现代物流配送路线优化研究.pdf

中文摘要 配送是物流活动中直接与消费者相连的环节。配送成本占物流的各项成本 的比例相当高。配送线路合理与否影响到配送速度、成本和效益，特别是多用 户配送线路的确定是一项复杂的系统工程。因此，物流车辆路线问题r v e h i c l e r o u t j n g p m b l e m ，简记为v r p ) 成为国内外众多学者竞相研究的课题。 本论文的研究就是围绕物流车辆路线问题而展开的，论文全文包括绪论、 三章主要内容以及结束语部分。绪论部分简单介绍了物流科学研究的背景、重 要意义，指出了人们重视对物流科学研究的原因，引出了物流运输路线优化研 究的重要性。第2 章简要回顾国内外物流配送的研究现状后，提出了亟待解决 的配送路线优化问题。第3 章详细讨论了节约算法，并结合实例进行了研究， 从而指出该方法存在的优缺点；同时分析了扫描法、禁忌搜索法用于配送路线 优化时存在的不足。进而在第4 章提出了用改进遗传算法求解该问题优化的方 法。主要做了以下几点工作：( 1 ) 提出自然数编码的模式定理，为本课题采用 的自然数编码提供理论基础；( 2 ) 分析客户数与种群规模的关系，合理选择种 群的规模；( 3 ) 采取代间覆盖的群体更新方式，优化进化的种群质量，使种群 逐步趋向全局最优；( 4 ) 提出类p m x 的交叉算子，更好地遗传染色体的性能， 减少对其产生的破坏性；( 5 ) 提出具有一定爬山能力的逆转换位算子，进一步 提高群体的演化质量，加快最优解的求解速度；( 6 ) 结合实例，验证该算法的 有效性，说明改进遗传算法具有良好的全局寻优性能，有效地避免了“早熟” 收敛问题，是求解配送路线优化问题的有效算法。结束语部分通过对全文内容 的归纳和总结，提出了进一步研究物流车辆路线问题优化的方向，并展望了物 流科学的发展。 笔者希望通过对物流车辆路线问题的优化研究能给物流科学添砖加瓦，由 于水平有限，也缺乏实际相关工作经验，文中的观点和理论肯定有诸多不足之 处，恳请本领域内外的专家、教授、学者批评指正，笔者在此表示深深的谢意。 关键字：物流配送，节约法，扫描法，禁忌搜索法，改进遗传算法 a b s t r a c t d i s t r i b u t i o ni sa n o p e r a t i o nl i i l k i n gd i r e c t l yw i t hc o n s u m e r s ，锄dt a k e sa c c o u n t f o rc o n s i d e r a b l ep r o p o n i o ni nv a r i i b l ec o s t si nl o g i s t i c s t h ep l a n n i n go fv e h i c l e r o u t i n g i nd i s t r i b u t i o nw i l lh a v es i g r i i f ! i c a n te f f e c to nt h ee f f i c i e n c y ，c o s ta n d b e n e f i t ， e s p e c i a l l y i n d i s t r i b u t i n g f o rm u l t i - c o n s u m e r s h e n c e ，v e h i d er o u t i n gp m b l e m ( v r p ) h a s b e c o m ef o c u so f m a n y s c h o l a r st os t u d y 1 1 l i sr e s e a r c h e x p l o i t sp h y s i c a ld i s t r i b u t i o nv e h i c l ei d u t i n gp r o b l e m t h ep a p e r c o n s i s t so fi n t r o d u c t i o n ，t h r e ec h a p t e r s ，蚰dc o n d u s i 蛐s t h ei m r o d u d i o n 西v e su s ab r i e fp i c t i l r eo ft h ei m p o r t a n c eo ft h el o g i s t i c ss c i e n c er c s e a r c h ，a n dt h em a i n r e a s o nw h y p e o p l ea f ep a y i n gm o r e a t t e n t i o nt oi t ，t h e ni n t r o d u c e st h ei d e at h a tt h e s t u d y o n o p t i m i z i n g t h ed i s t r i b u t i o nr o u t eo f l o g i s t i c st r a n s p o n a t i o n i s v e r y i m p o n 柚t c h a p t e r 咐op r o v i d e st h eo p t i m i z a t i o no fd i s t r i b u t i o nm u t j n gp m b l e m a f 【e rp r e s e n t i n gt h ep r e s e n ts i t u a t i o no ft h es t u d yo n l o g i s t i c sa th o m e a n da b r o a d c h a p t c r t l l r e ef o c u s e do nt h es a v i n g m e t h o d ，b y c a s es t u d y i n g ，m ea d v a l l t a g e sa l l d d i s a d v a n t a g e sa r ep f c i p o s e d w h a t sm o r e ，m ee f f e c t i v e n e s so fs w e e p i n gm e t h o d a n d1 1 a b us e a r c ha l g o r i t l l i i l sw h e nu s e dt oo p t i m i z ed i s t r i b u t i o nr o u t i n g p r o b l e m a r c a n a l y z e d c h a p t e rf o u rp m p o s e st h ei m p r o v e dg e n e t i c 砧g o r i t h m ( i g a ) f o rt h e s o l u t i o n0 ft h i s p f o b l e m s e v e r a lm e a s u i e s 缸et a k e n ：( 1 ) m o t i v a t e ss c h e m a t a t h e o r e i n0 fn a t u r a ln u m b e r c o d i n 岛w h i c hp r o v i d e st h e t h e o r e t i c a lb a s i sf o rf u n h e r r e s e a r c h ( 2 ) s e l e c t s r e a s o n a b l e p o p u l a 廿o n s i z e b ya n a l y z i n gt h er e l a t i o n s h i p b e t w e e nt h en u m b e ro fc u s t o m e r sa n dm e p o p u l a t i o ns i z e ( 3 ) u s i n gt l l e i d e ao f g e n e r a t i o ng a pt 0 o p t i m i z ep o p u l a t i o nq u a l i t y ( 4 ) p f a v i d e sa n a l o g yp a r t a l l y m a t c h e d ( x o s s o v e r ( p m 均o p c r a t o r t oi m p r o v et h ep e d o i i i l a r mo fc h r o m o s o m e a n dd e c r e a s ed e s t r o y ( 5 ) i n t m d u c e si n v c r s i o no p e m t o rt o i m p r o v ee v o l u i i o n q u a l i t yo fp o p u l a t i o na n df a s t e ns o l u t i o nt oo p t i m a lr e s u l t s ( 6 ) t h ec o m p u t a t i o n a l r e s u l t sd e m o n s t r a t ee 疵c t i v e n e s so fi g au s e dt os o l v ed i s t r i b u t i o nr o u 皿g p r o b l e m i sp r o v e d w h i c ha l s oi 1 1 u s t r a t e sf h a ti g a h a s 孕e a tr o b u s t n e s sa n de 饪e c i i v e l ys o l v e t h e “p r e m a t u r e c o i e r g c n c e ”p r o b l e m c b n c l u s i o n sc o n t a i n as u i r l m a r ya n d s u g g e s t 主o n sf b rf u r t h e r r e s e a r c h 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 n ；s a v i i l gm e t h o d ；s w e e pm e t h o d ；7 i 汕us e a r c h h e u r i s t i c ；h p r o v e dg e n e t i ca l g o r i t h m i i 此页若属实请申请人及导师签名。 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名：壹翌堑塾日期 关于论文使用授权的说明 j t 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅： 学校可以公布论文的全部内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究 jo 生签名：狮扩! 导师签墨公日期 注：请将此声明装订在论文的目录前。 0 一叶 l 。 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题研究的背景与研究现状 1 1 1 课题研究背景 随着市场经济发展步伐的加快，作为“第三利润源泉”的物流对经济活动 的影响日益明显，越来越引起人们的重视。美国物流管理协会( n e c o u c i lo f l 0 西s t i c s m a l l a g e m e n t ，c l ，m ) 将“物流中心”定义为：“以适合顾客要求为目的， 对原物料、在制品、制成品与其相关信息，从产地到消费者的间的流程与保管， 为求有效率且最小的机会成本，而进行计划、执行、控制的场所( d e p o t ) ”。 传统的物流配送系统中，由于商品的需求量及种类较少，零售商可凭借较 多的存货及较长的订货周期来减少供货商的配送频率，以降低运输成本。但是 在现代物流配送系统中，零售商为了减少资金积压并提供多样化的商品，必然 要减少各种商品的存货数量，而同时又必须考虑到提供最好的服务品质( 不允 许缺货) 。物流中心的功能之一就在于对商品运输进行有效的统筹规划以降低 配送运输成本。 目前，一般意义上的物流配送运输，指配送中心按照不同客户多频度、小 批量的订货要求进行组织配送，其中主要内容是根据确定的货物量进行车辆的 分配和配送线路的生成，亦即广受研究的车辆路线问题( v c h i c l er o u t i n g p r o b l e m ) 。由于从事物流配送的汽车货运工作尤其是从事城市配送的汽车货运 工作条件复杂，不仅货运点多、货物种类繁多、道路网复杂，而且运输服务地 区内运输网点分布不均匀。因此，如何应用现代数学方法及计算机快速求解路 线优化方案是国内外专家学者普遍探索的重要课题。 为实现运输成本的降低，必须对运输的进行合理规划。运输的合理规划涉 及到时间、财务、环境三方面的因素，首先从时间要考虑准时性、快速响应： 财务上要考虑运输涉及的各种开支( 车辆购置成本和消耗、司机薪酬、油耗等) ： 环境上要尽可能减少不必要的行驶，避免交通拥挤、空气以及噪音等污染。这 些可以通过改进运输方式、线路规划等交通管理来加以改善。其中运输方式属 武汉理工大学硕士学位论文 于“硬”技术的问题。是可以通过设施的完善和提高运输的效率，降低相应成 本。这不属于本文讨论的范围。而运输的线路规划主要是利用各种先进的信息 技术对车辆及其路线进行规划，实现对车辆合理有效的利用，从而节省大量的 时间和成本。 而物流中心配送作业的重点就是如何将车辆有效的使用并决定其最经济 的行驶路线图，使商品能在最短的时间内送到顾客的手中。该问题为：从配送 中心( 物流据点) 用多辆车向多个需求点( 顾客) 送货，每个需求点的位置和 需求量一定，每辆车的载重量一定，要求合理安排车辆路线，使总运距最短， 并满足以下条件：( 1 ) 每条配送路径上各需求点的需求量之和不超过车辆载重 量；( 2 ) 每条配送路径的长度不超过车辆一次配送的最大行驶距离；( 3 ) 每个 需求点必须满足，且只能由一辆车送货。达到一定的目标( 如路程最短、费用 最少、时间尽量少、使用车辆数尽量少等) 。此即为v r p 问题。 1 1 2 课题研究现状 国内外相关领域对v r p 问题的研究始于5 0 年代，在理论研究和实际应用 两方面都己取得了非常显著的成果。随着研究的深入发展，如何使研究的理论 模型更贴近现实中的运输规划问题开始成为研究者们关注的焦点。 车辆路线问题( v r p 问题) 是组合优化领域中著名的n p 难题，近二十年来， 无论在国内还是国外，v r p 问题都是一个非常活跃的研究领域。目前国内外 用于解决该问题的现代数学方法主要分为以下几类： ( 1 ) 精确优化方法。运用线性规划和非线性规划等数学规划技术，来求取 最优决策。 ( 2 ) 启发式方法( h e u r i s t i c ) 。指通过经验法则来求取运输过程满意解的数 学方法。启发式方法能同时满足详细描述问题和求解的需要，较精确优化方法 更为实用，缺点是难于知道什么时候好的启发式解己经被求得。启发式方法中 最具有代表性的就是a a r c k 和w f i g h t 提出的节约法( s a v i gm c t h o d ) 。许多成 功的车辆调度软件就是根据该方法或其他改进方法开发的。g i l l i e t 和m i l l e 提 出的扫描法( s w e e pm e t h o d ) ，先把节点或弧的需求进行分组或划群，然后对每 一组按旅行商( t s p ) 求解，设计出一种经济的线路。各种启发式方法的主要区 别在于收敛的速度和程度不同。 2 武汉理工人学硕士学位论文 ( 3 ) 模拟方法( s i m u l a t i o n ) 。利用数学公式、逻辑表达式、图标、坐标图形 等抽象概念表示实际运输系统内部状态和输入输出的关系，以便通过计算机对 模型进行试验，通过实验取得改善运输系统或设计新运输系统所需信息。 ( 4 ) 交互优化法。这是一种通用方法。在这种方法中，把人为的知识、经 验结合到问题求解过程中去。其思想就是：有经验的决策者应具有确定和修改 参数的能力，并且根据知识直感，把主观的估计加到优化模型中去。 以往的研究广泛采用精确优化方法，其他几种方法则代表了较近的研究思想。 尤其是启发式方法，作为一种逐次逼近的算法，虽然不一定得到最优解，但是 可以高效率的得到具有较高精度的解，而且也易于考虑各种各样实际问题，因 此，已成为解决配送问题的重要方法。 1 2 课题研究的目的与意义 1 2 1 课题研究的目的 车辆配送路线问题为一复杂性颇高的问题，精确算法及启发式算法是用来 求解此类问题的传统方法。采用精确算法可求得问题最优解，但其求解时间往 往随着问题规模的增大而成指数增长，当所需处理的零售商数目较多时，要花 费相当多的时间来求解，因此在实际中的应用范围很有限。启发法通常针对问 题的特性将问题分成数个小问题或模块加以简化，并以较为直观的方式来求 解。启发式算法可以大大减少计算时间及其复杂度，但所求得的结果仅为近似 最优解。 近年来，遗传算法在组合优化问题上的求解成效显著，因其快速运算、自 组织及平行处理的特性，不仅能在可接受的时间内求得满意的答案，在问题的 扩充性方面也颇具弹性。虽然遗传算法的全局搜索能力较强，但是它的局部搜 索能力较弱。因此，本论文引入了局部搜索能力强，具有一定爬山能力的逆转 换位算子，结合遗传算法，设计出一种效率比较高的改进遗传算法，将其应用 在车辆配送路线模型的求解上，以期在合理的成本得到一个满意的路线规划。 综上所述，本论文研究的目的可归纳如下： ( 1 ) 构建以配送总距离最小为目标的车辆配送路线模型。 ( 2 ) 结合遗传算法和逆转换位算子，求得一个较优的可行解。 武汉理工大学硕士学位论文 1 2 2 课题研究的意义 本课题以为从事物流配送的企业提供智能化、决策化支持的目标出发，对 车辆路线问题( v r p ) 进行数学分析，提出了实用性强的改进遗传算法解决车辆 的配送线路的生成。这对物流配送企业实现计算机配送线路优化、降低成本和 提高物流经营管理水平、更快的响应顾客、最终能显著的增加企业的竞争力具 有重要的参考价值。应该说，课题的研究具有较强的理论和实践意义。 1 3 论文的主要内容 本文在对物流配送业务进行详细研究的基础上，针对物流配送中对成本影 响较大的车辆路线优化问题进行了集中的研究。从而建立现代物流配送路线问 题的数学模型，利用现代优化方法论中的遗传算法，借助计算机编程，对该问 题求出最满意解。 本文的具体结构如下：第一章简单介绍了物流科学研究的重要意义，指出 了人们重视对物流科学研究的重要原因，通过对物流运输系统的成本分析研究 引出了物流运输路线优化研究的重要性。第二章简要回顾国内外物流配送业的 研究现状，并提出解决配送路线优化问题的必要性及其对现实的重要性。第三 章详细讨论了节约算法，结合实例进行了研究，从而指出了其存在的优缺点： 同时分析了扫描法、禁忌搜索法应用于配送路线优化时存在的优点和不足。第 四章提出了将改进遗传算法用于该问题优化的具体方法；在改进遗传算法中， 主要做了以下几点工作：( 1 ) 提出自然数编码的模式定理，为本课题采用的自 然数编码提供理论基础，( 2 ) 分析客户数与种群规模的关系，合理选择种群的 规模，( 3 ) 为了优化进化的种群质量，采取代间覆盖的群体更新方式，使种群 逐步趋向全局最优，( 4 ) 提出类p m x 的交叉算子，能更好的遗传染色体的性 能，减少对其的破坏性，( 5 ) 提出具有一定爬山能力的逆转换位算子，能进一 步的提高群体的演化质量，加快最优解的求解速度，( 6 ) 结合实例，验证该算 法的有效性，说明改进遗传算法具有良好的寻优性能，有效的避免了“早熟” 收敛问题。结束语部分通过对全文内容的归纳和总结，提出了进一步研究物流 车辆路线问题优化的方向，展望了物流科学的发展方向。 武汉理工大学硕士学位论文 1 4 主要研究方法 为了达到上述研究目的，本文首先收集了国内外学者专家对车辆路径问题 的相关研究资料：对文献资料进行整理、分类，作为数学模型建立的理论基础； 建立了配送路线问题的数学模型，并对模型进行分析；在求解方法上，本文采 取全局搜索能力较强的遗传算法和具有一定爬山能力的逆转换位算子相结合 的改进遗传算法，最后用c 语言编程实现本文提出的算法，并以一个算例分 析比较该算法的性能。借以证明该算法提出的有效性。 武汉理_ 【_ = 大学硕士学位论文 第2 章国内外物流配送现状分析 2 1 物流配送的概念及功能 随着经济全球化和网络信息技术发展的加快，物流及配送业作为一个新的 经济增长点引起了国人的注意。上海、天津、北京等城市纷纷将物流产业作为 支柱产业，中储、中远、中外运等大型企业都把现代物流作为重点发展领域。 我国证券市场已经形成了由几十家企业构成的“物流板块”，许多商贸流通部 门纷纷介入现代物流配送业【6 n 】。物流及配送业的发展在全国方兴未艾。 2 1 1 配送的概念 理解物流配送概念离不开对物流概念的分析。物流概念最早是在美国形成 的，被称为“p h y s i c a ld i s t r i b u t i o n ”( 即p d ) ，译成汉语是“实物分配”或“货 物配送”。1 9 6 3 年被引入日本，物流被定义为“在连接生产和消费间对物资履 行保管、运输、装卸、包装、加工等功能，以及作为控制这类功能后援的信息 功能，它在物资销售中起了桥梁作用”。因此，现代物流是以满足消费者的需 求为目标，把制造、运输、销售等市场情况统一起来思考的一个产业概念。 配送是物流系统的核心环节之一，配送在英语中的原语是“d e l i v e r v ”，是 交货送货的意思。在日本工业标准j i s 中，将配送定义为“将货物从物流结点 送交收货人”，强调了送货的含义。可以说，物流配送是连接生产与消费之间 的一种中介服务，是物资供应的一种重要形式。配送是“配”和“送”有机结 合的形式，它利用有效的分拣、配货等理货工作，使送货达到一定的规模，以 利用规模优势取得较低的送货成本。 2 1 2 配送的功能 ( 1 ) 推行配送制有利于合理配置资源。由于实施配送可以做到以配送企 业的库存取代社会上千家万户的零散库存，或者说，可以使库存相对集中，因 此，有条件也有可能按照统一计划合理分配和使用资源，做到物尽其用。 武汉理工人学硕士学位论文 ( 2 ) 推行配送制可以降低物流成本，促进生产快速发展。这是因为各种 流通要素相对集中，有益于开展规模经营活动；流通的物质要素相对集中，也 便于合理安排各环节上的物流活动，使总体运动协调一致，最终会减少物流领 域内的劳动消耗和费用支出。 ( 3 ) 推行配送制能够充分发挥专业流通组织的综合优势。推行配送很容 易使不同的流通组织联系在一起，从而构成多功能的、一体化的物流运动。这 种以配送作为媒介而形成的一体化运作较之各个专业企业独立运作更能发挥 流通组织的整体优势和综合优势。 2 2 发达国家和地区的物流配送状况 2 2 1 美国现代物流配送的发展状况 从2 0 世纪6 0 年代起，商品配送的合理化在美国普遍得到重视。为了在流 通领域产生效益，美国企业采取了以下措施：一是将老式的仓库改为配送中心； 二是引进电脑管理网络，对装卸、搬运、保管实行标准化操作，提高作业效率； 三是连锁店共同组建配送中心，促进连锁店效益的增长。美国连锁店的配送中 心有多种，主要有批发型、零售型和仓储型三种类型。首先是批发型。该类型 配送中心主要靠计算机管理。业务部通过计算机获取会员店的订货信息，及时 向生产厂家和储运部发出订货指示单。其次是零售型。以美国沃尔玛商品公司 的配送中心为典型。该类型配送中心一般为某零售商独资兴建，专为本公司的 连锁店按时提供商品，确保各店稳定经营。第三是仓储型。美国福来明公司的 食品配送中心是典型的仓储式配送中心。它的主要任务是接受独立杂货商联盟 的委托业务，为该联盟在该地区的若干家加盟店负责商品配送。 2 2 2 日本现代物流配送的发展状况 在日本，零售业是首先建立先进物流系统的行业之一。便利店作为一种新 的零售业态迅速成长，现已遍及日本，正影响着日本其他的零售商业形式。这 种新的零售商业业态需要利用新的物流技术，以保证店内各种商品的供应顺 畅。因此，日本的物流配送具有以下特点：第一，分销渠道发达。许多日本批 发商过去常常把自己定位为某特定制造商的专门代理商，只允许经营一家制造 武汉理工大学硕士学位论文 商的产品。为了保证有效地供应商品，r 本许多物流公司不得不对原有的分销 渠道进行合理化改造，更好地做到与上游或下游公司的分销一体化。第二，频 繁、小批量进货。日本的物流配送企业的很大一部分服务需求来自便利店，便 利店依靠的是小批量的频繁进货，只有利用先进的物流系统才有可能发展连锁 便利店，因为它使小批量的频繁进货得以实现。第三，物流配送体现出共同化、 混载化的趋势。共同化、混载化的商品配送使原来按照不同生产厂、不同商品 种类划分丌来的分散的商品物流转变为将不同厂家的产品和不同种类的商品 混合起来运送的聚合的商品物流，从而得以发挥商品物流的批量效益，大大提 高了运货车辆的装载率。第四，合作型物流配送。在同本，生产企业、零售企 业与综合商社、综合物流公司之间基本上都存在一种长期的物流合作关系。并 且，这种合作关系还随着日本工业生产的国际化延伸到国外。第五，政府规划 在现代物流配送发展过程中具有重要作用。 2 2 _ 3 我国台湾现代物流配送的发展状况 台湾地区的配送中心多为中小规模、平房仓库，并采用适合本地区特点的 设施设备。台湾地区创造了自己的“本土化物流”。他们认为“自动化”不一 定适应所有国家和地区的物流产业发展，引进技术必须考虑企业的财力规模、 土地成本、建筑成本、设备成本等条件。因此，台湾地区没有完全照搬美国和 日本的发展经验，而是融合这些国家物流现代化的经验，根据自己的需求，尽 量完善自己的物流薄弱环节。另外，物流人才的培养，也是台湾物流企业形成 自己特色的重要原因之一，他们认为物流现代化不仅在于逐步实现物流设施的 现代化，更重要的是在于人才素质的提高。目前，台湾的物流配送发展趋势是 从整合到聚集；在物流配送的发展初期，企业是凭借自身力量与外部竞争；在 发展的阶段，则是通过若干企业间的互助合作与其他企业竞争。而在联合的阶 段则是通过资源共享的结盟来与其他企业竞争，也就是使自己的竞争对手通过 聚集成为自己的一部分。这样就达到了高层次竞争的阶段，即通过提供有差异 的服务进行竞争，而并非仅通过硬件进行竞争。 2 2 4 美国、日本和中国台湾物流配送的不同 第一，商业形态或作业方式有区别。美国由于地大物博，相对的人口密度 武汉理工大学坝士学位论文 较低，城市与城市的间距较远，人们有购物囤积的习惯，通常隔一段时间到购 物中心大量采购满足数天或数星期的需求，所以造成购物中心所提供的货品必 须齐备和货源充足。日本则由于即时送货制度的施行，增加了运送费用与运送 劳力，因此一般商家为了降低运送成本纷纷将货品交由货运公司及物流配送中 心来运送以减少运送风险及提高配送时效。中国台湾的零售商店多，而近来又 由于个性化消费风气的形成，使多样化的货品配送成为商店经营的必备条件， 因此由专业的物流配送来降低配送成本提高配送时效就成为必要条件。 第二，物流配送软硬件的开发及应用的侧重不同。美国物流中心所使用的 资讯系统资料显示，除一般的管理系统外，美国物流配送中心在发展过程中还 存在对多仓储、多配送中心管理系统和分布面积较散的连锁商店之间货品运送 的侧重。日本则因为地域狭窄、交通复杂而具备一个较富弹性且经济的配送系 统。对应于机械自动化程度，美、日等国由于其物流中心的发展历史较久，所 以机械自动化程度较高，作业方式较为纯熟。而中国台湾则由于连锁店规模较 小，订单需求量也较小，所以物流中心中仅有少数几家采用自动仓储。 第三，配送中心的特色功能存在差异。日本配送中心通过提高商品质量、 增加花色品种、增加供货频率等方式强化供货枢纽的战略功能；通过综合物流 管理方式以控制物流成本的功能；通过增强应变能力以适应物流量常随经营规 模的发展不断变化的应变功能。而美国配送中心的特色功能是特别重视单个消 费者服务功能，即尽力满足顾客提出的各种要求。 第四，管理存在差异。物流水平代表一个国家的经济发展程度，物流管理 体现各个国家民族性情和经济模式的差异。日本注重物流成本测算，美国则以 物流机械的现代化作为物流管理切入点。中国台湾的发展趋势为企业问通过资 源共享的结盟来与其他企业竞争，也就是通过对现有物流资源的重新整合达到 双赢的目的，本质是将分散的网络进行连接并使其优化。 2 3 我国的物流配送发展状况 物流配送是现代流通的重要组成部分。近年来，我国物流配送发展出现了 积极趋势，主要体现在以下几个方面： ( 1 ) 各级政府部门采取措施积极推动物流配送的发展。不少省市已经把 9 武汉理工人学硕士学位论文 发展现代物流列入了日程，例如上海、天津、深圳都把物流作为支柱产业。还 有许多省市开始制定物流规划。国家有关部门对商品物流和配送采取了积极鼓 励和支持的政策，在我国流通领域对外丌放政策中，鼓励国外资本投资于物流 和配送设施等。目前国内物流和配送服务已有较快的发展，物流配送已经成为 许多企业降低成本，提高竞争力的重要手段。例如，相当多实行连锁经营的零 售企业建立了自己的配送中心，为企业内部的连锁网点提供物流配送服务，一 些连锁企业配送商品比例已经超过企业经营品种的5 0 。 ( 2 ) 在生活资料领域和生产资料领域出现了各具特色的不同类型的现代 物流企业。一些传统的流通企业，包括运输和仓储业通过改造成为物流企业， 如中远集团、中外运集团和中储集团等：一些国有商业批发企业和大型零售企 业正在积极探索和尝试开展社会化物流配送服务；一些生产企业开始介入现代 物流，如青岛海尔集团；一批专业化的物流企业得到较快发展，物流配送的社 会化、专业化发展趋势日益明显，如深圳中海物流都是比较成功的第三方物流 公司。外资在物流配送服务领域的发展也十分迅速，如中国储运总公司与日本 岗谷钢机株式会社合资组建了天津岗谷物流公司，是集配送、加工、仓储、寄 售、租赁、修理、展销和技术咨询为一体的新型流通组织。像这样的合资物流 公司，在北京、天津、上海等地已有1 0 家之多，它们主要是为在中国投资的 跨国公司提供物流配送服务。这些企业根据各自特点，发挥特长优势，积极开 拓物流服务领域，形成了服务模式多样、多种经济成份并存的现代物流企业群 体。 ( 3 ) 连锁企业内部的配送中心在硬件设施、管理水平、管理信息系统等 方面的建设，获得较大发展，有些已经达到较先进的水平。 ( 4 ) 现代物流技术的开发研究取得一定进展。一些物流配送企业在研究 开发物流信息技术和物流配送管理技术上取得了许多成果，对于推动我国现代 物流发展发挥了积极作用。目前已有相当多的物流和配送技术开始进入中国， 并在企业中得到越来越广泛的应用，例如条形码技术、计算机支持的信息管理 技术、e d i 、m r p 等： 1 0 武汉理工大学硕士学位论文 2 4 我国物流配送存在的问题 尽管我国物流配送业近几年发展很快，但与发达国家相比还处在起步阶 段，不可避免地会遇到这样或那样的问题。当前，主要存在以下几个方面的问 题： ( 1 ) 物流配送市场化程度低，第三方物流配送发展滞后。目前我国大多 数物流配送企业技术装备和管理手段比较落后，服务网络和信息系统不健全， 物流配送市场化程度低，影响了物流服务的准确性与时效性。其主要表现是： 小( 物流配送企业数量小，经营规模小) 、少( 物流配送市场份额少、服务功能少， 大多数企业还只是被动地按照用户的要求，从事单一功能的运输、仓储和配送， 很少能提供物流策划、组织及深入到供应链的全过程管理，物流增值少1 、散f 网 络分割、经营秩序不规范，不能为客户提供包括物流网络设计、预测、订货管 理、存货管理等系统物流服务) 、弱( 竞争力弱和发展滞后，专业化、信息化、 标准化还没跟上，还没有真正了解国际物流企业的运作方式和真正意义上的 “第三方物流”) 。 ( 2 ) 物流基础设施落后，物流配送的整体功能低。一是交通运输设施建 设与物流配送的需要不相适应，即交通运输能力仍不能满足运输需求，主要 运输通道供需矛盾依然突出；二是技术装备水平落后；三是物流系统标准化 程度低。 ( 3 ) 物流配送管理体制和相关制度不完善。一方面，市场竞争机制和市 场管理法规不健全，发展物流配送所需的产业政策和产业规划尚未出台，物流 市场的进入与退出、竞争规则基本上无统一法律法规可循，对社会性的物流缺 乏有效的外部约束，致使不正当竞争较为严重。另一方面，物流配送市场至今 仍被人为地按照部门、地区和行业的行政壁垒分割，物流配送市场管理和行业 管理还没有理顺，各地商委、经贸委、交通局、铁路局、外经贸委等都各自承 担了一部分物流管理职能，各部门间分工又有交叉，造成了物流管理中条块分 割、重复建设等问题，统一、竞争、有序的物流配送市场没有建立起来，严重 影响了物流配送渠道的畅通和高效运转，使物流配送很难达到规模经济和预期 回报。 ( 4 ) 专业的物流配送管理和技术人才短缺。 武汉理工大学硕士学位论文 第3 章物流路线优化的一般方法 3 1 配送路线优化的意义及原则 当前的物流业正向全球化、信息化、一体化发展，配送在供应链中的作用 显得更加重要。由于现代配送具有多频次、小批量、多品种、高效率的特点， 配送要准确做到7 r ( r i g l l tp m d u c t ，r i 班tq u a l i t y ，r j g i l tt i m e ，r i 曲tp l a c e ，r i 曲t c o n d i t i o n ，r j g h tc i l s t o m e r ，r i g l l tc o s t ) ，如何合理、有效的对配送路线进行优化， 就成为非常现实的问题。 通常认为，配送是近距离，小批量，品种比较复杂，按用户需要搭配品种 与数量的服务体系。从配送中心把货物送到所需的各个用户，有很多种不同的 路线选择方案。合理的选择配送路线，对企业和社会都具有很重要的意义。 对企业而言：( 1 ) 优化配送路线，可以提高配送效率，对配送车辆做到物 尽其用，尽可能的降低配送成本。( 2 ) 可以准时、快速地把货物送到客户的手 中，能极大地提高客户满意度。( 3 ) 有利于企业提高效益。 对社会而言，它可以节省运输车辆，缓解交通紧张状况，减少噪声、尾气 排放等运输污染，为保护生态平衡、创造美好家园作出贡献。 进行配送路线优化时，必须有明确的目标，遵循基本的原则。配送路线方 案目标的选择可以从以下几个方面来考虑： ( 1 ) 配送效益最高或配送成本最低。效益是企业追求的主要目标，可以 简化为用利润来表示，或以利润最大化作为目标；成本对企业效益有直接的影 响，选择成本最低化作为目标值与前者有着直接的联系。当有关数据容易得到 和容易计算时，就可以用利润最大化或成本最低作为目标值。 ( 2 ) 配送里程最短。如果配送成本与配送里程相关性较强，而和其他因 素相关性较弱时，配送里程最短的实质就是配送成本最低。则可考虑用配送罩 程最短作为目标值，这样就可以大大简化线路选择和车辆调度方法。当配送成 本不能通过里程来反映时，如道路收费、道路运行条件严重的影响成本，单以 最短路程作为目标就不适宜。 武汉理工人学硕士学位论文 ( 3 ) 配送服务水准最优。如准时配送要求成为第一位时，或需要牺牲成 本来确保服务水准时，则应该在成本不失控的情况下，以服务水准为首选目标。 这种成本的损失可能从其它方面弥补回来，如优质服务可以采取较高的价格策 略。 ( 4 ) 配送劳动的消耗晟小。即以物化劳动和活劳动消耗最小为目标，在 许多情况下，如劳动力紧张、燃料紧张、车辆及设备较为紧张的情况下，限制 了配送作业的选择范围，就可以考虑以配送所需的劳动力、车辆或其它有关资 源作为目标值。 配送路线方案的目标实际上是多元的，但考虑到制定方案所选择的目标值 应当容易计算，一般要尽可能选择单一化的目标值，这样容易求解，实用性较 强。 配送路线方案目标的实现过程受到很多约束条件的限制，因而必须在满足 约束条件的限制下取得成本最低、或路线最短、或消耗最小等目标。其中常见 的约束有：( 1 ) 收货人对货物品种、规格和数量的要求；( 2 ) 收货人对货物送 达时间或时间范围的要求：( 3 ) 道路运行条件对配送的制约，如单行道、城区 部分道路对货车通行的限制；( 4 ) 车辆最大装载能力的限制；( 5 ) 车辆最大行 驶里程数的限制：( 6 ) 司机的最长工作时间的限制；( 7 ) 各种运输规章的限制 等等。 进行配送路线优化时，常用的方法有：节约法，扫描法，禁忌算法，遗传 算法等等。下面将进行逐一介绍。 3 2 节约法( s a v i n gm e t h o d ) 近年来，由于小批量、多批次的及时配送方式的发展，运输费用正在逐年 提升，许多企业的运费已经超越了库存费用。选择有效的配送路线，已成为控 制物流成本的主要措施。那么如何选择有效的配送路线呢? 现代企业已经普遍 接受了一种观点，即有效的配送路线实际上是在保证商品准时到达客户指定点 的前提下，尽可能地减少运输的车次和运输的总路程。在这种思想的指导下， 节约法已成为选择配送路线的主要方法，并受到国内外物流界的青睐m 】。 武汉理工大学硕+ 学位论文 3 2 1 节约法的两种基本实现途径 节约算法有两种基本途径可以实现，一种叫做并行方式( p a r a l l e lv c r s i o n ) ， 另外一种叫做串行方式( s e q u e n t i a lv e r s i o n ) 。这两种方式在初始化时是相同的。 它们的区别在于如何处理回路的合并问题。下面分别对两种方式的具体应用步 骤进行介绍。 ( 1 ) 并行方式：并行方式分3 步完成。 第一步，形成一个初始解。 形成初始解时，需要满足所有顾客的需求，而且所有的约束条件，例如容 量的限制、车辆总数的限制等也得到满足。初始解可以由具有运载限制的最近 邻点法求得。 形成初始解之后，可以得到每个车辆的一个初始的运输方案， 疋； o ，j ，m ，：1 ，2 ，州；f ， p l p ，p s n 。七表示车辆的标号，f 、 ，表示顾客的标号。 第二步，进行节约度的计算。 计算所有点对的节约度c o c = c f o + c o 一c “f ，；1 ，2 ，n 日f 一， 然后对计算结果进行升序排列。 第三步，进行回路的合并。 在并行方式中，采用的合并策略是最可行合并原则。 1 从升序排列的节约度序列中的最上面的值开始，执行下面步骤： 对于一个已知的c 先判断这两个关系到f 、j 的回路是否存在合并的可 能性，如果： 一个回路以( 0 ，f ) 开始： 一个回路以( f ，o ) 结束。 则该回路可以合并，并进行下面的合并操作： 删除两个回路中的部分路径( o ，) 和( f ，o ) ，然后引入新的连接( f ，i ) ， 得到新的回路( o ，f ，o ) 。 ( 2 ) 串行方式：串行方式的节约算法同样也是由3 个步骤来完成，它与 并行方式的节约算法的前两步骤几乎完全一样。它们的区别主要在于第三步。 1 4 武汉理工大等：硕士学位论文 第一步，形成一个初始解。 形成初始解时，在考虑了顾客的需求和约束条件都得到满足之后，就可以 得到相应的初始解。初始解也可以由具有运载限制的最近邻点法求得。 形成初始解之后，同样得到每个车辆的一个初始的运输方案， t ； o ，f ，o ) ，t = 1 ，2 ，肌；i ，j 驯p ，p n 。t 表示车辆的标号，f 、j 表示顾客的标号。 第二步，进行节约度的计算。 计算所有点对的节约度c “ a c - c o + c oj c 目，f ，l ，2 ，n 且f j 然后对计算结果进行升序排列。 第三步，回路的扩充。 这里的合并策略不再是前面并行方式的节约算法那样两个部分的对接，而 是将一个回路中的某一部分替代，实现总运输距离的下降。具体的处理方法如 下： 按顺序对每一个回路( o ，f ，o ) 进行考虑，找到第一个具有节约度的 点c h 或者c ，并将另一个以( 七，0 ) 结尾或者( o ，f ) 开始的一段路径合 并到当前回路中。 对当前考虑的回路不断地进行上面的合并操作，直到所有可行的合并操作 都完成为止。此时，就得到用串行方式的节约算法计算的近优解。 3 2 2 配送计划的制定规划及步骤 3 2 2 1 配送计划的制定步骤 本文以节约法为基础，提出一个配送计划的制定规划及步骤，使运输行驶 总距离最短。 设? p 0 为配送中心，资源及运力充分；毋为用户点( ；1 ，2 ，n ) ，相 应的需求量为缈( = 1 ，2 ，n ) ，它们之间差别较大；如o ，= 0 ，1 ，2 ， n ) 是尸f 与p 之间的最短距离。 发送车辆按其装载量或容积大小不同有m 种，装载量为的发送车有麓 辆( f = 1 ，2 ，历) ，且m 1 0 ： ( 2 ) p f 和p 尚未被分配在相同的路线上； ( 3 ) 将原计划中的。和毋改为”曰，并检查o + 哩，是否超过配送车辆的 最大装载量的限制，并按此要求来修改表3 1 。 如果节约量最大的格子a ，j ) 符合上述条件，则可以连接p f ，毋，即严1 ， 其他的轴值按式( 3 1 ) 来修改。 ( 4 ) 对于幻= o 的，使毋= o ； ( 5 ) 对于畸o 的j ，把他们的田加在一起，