（系统工程专业论文）具有快运需求的物流配送车辆调度模型研究.pdf

学位论文版权使用授权书 l i i ii iii i iii i i ii ii iiii y 17 8 0 3 6 4 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：氏崩字 导师签名： 当够詹 签字日期：弘加年多月f 日 签字日期：咖一年6 月侈日 作者姓名：代辉 导师姓名：李海鹰 学位类别：工学 学科专业：系统工程 学号：0 8 1 2 1 2 5 5 职称：副教授 学位级别：硕士 研究方向：自动控制 北京交通大学 2 0 1 0 年6 月 致谢 本论文的工作是在我的导师李海鹰教授的悉心指导下完成的，李海鹰教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢二年来 李海鹰老师对我的关心和指导。 王莹老师悉心指导我完成了实验室的科研工作，在学习上和社会工作上都给 予了我很大的关心和帮助，在此向王莹老师表示衷心的谢意。 郎茂祥教授的博士论文和著作对于我的科研工作和论文有很大的启发，受益 颇多，在此表示衷心的感谢。 感谢许鸿飞师弟对论文的协助工作。 最后感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 没有他们，我撑不到今天。 i 匕塞交通太堂亟堂僮论塞 生室撞蔓 中文摘要 摘要：随着世界经济的发展和现代科技的进步，物流产业作为国民经济中的 一个重要服务行业，正在全世界范围内迅速发展，并逐渐成为国民经济的基础产 业。配送是物流服务的必需的一个部分，它已经发展成为一个独立的业务，在服 务业占有重要的地位。 随着经济的发展，客户需要把一些小批次货物在一定时限内运到目的地。为 了满足这些客户，以占有市场，实现最大收入，物流商必须提供相应的快运物流 配送服务。 论文站在物流服务商的角度，用经济成本来衡量物流配送行为：在概念上将 快运定义为单位时间的运货量和送货的客户数，与“时间窗 做了区别。 论文从系统工程的观点出发，分析了物流配送的含义、类型以及制约快捷配 送的主要因素。在对物流配送车辆调度重要模型和算法进行分析比较基础上，分 别建立了以货物卸完和货物送到为时段要求适用于小批次货物运输的单向物流配 送车辆调度模型；并设计算例，利用遗传算法对模型进行了验证。 关键词：快运需求；车辆调度；遗传算法；v r p 1 j 匕哀变通态堂亟堂僮论褒旦墨i b 丛 a b s t r a c t a b s t r a c t ：w i t ht h er a p i dd e v e l o p m e n to fw o r l de c o n o m ya n dm o d e mt e c h n o l o g y , l o g i s t i c si n d u s t r ya so n eo ft h em o s ti m p o r t a n ts e r v i c ei n d u s t r yi nn a t i o n a le c o n o m yi s g r o w i n gq u i c k l ya l lo v e rt h ew o r l d i ti st h ef u n d a m e n t a li n d u s t r yo fn a t i o n a le c o n o m y d e l i v e r yi st h em a i np a r to ft h el o g i s t i c sa n dg r o w s a l li n d e p e n d e n tb u s i n e s s w i t ht h ed e v e l o p m e n to fe c o n o m i c ，t h e r ea r em a n yc a r g o sw h i c ha r ee x p r e s s e d t h e yn e e dt ob ed e l i v e r e dt ot h ed e s t i n a t i o n i no r d e rt og e tp r o f i ta n df i tf o rt h en e e do f m a r k e t , t h el o g i s t i c sb u s i n e s sh a st os u p p l yt h el o g i s t i c ss e r v i c e w i t hl o g i s t i c sp r o v i d e r ss t a n d i n gp o i n t ，t h ep a p e ru s ee c o n o m i cc o s tt om e a s u r et h e b e h a v i o ro fl o g i s t i e sa n dd i s t r i b u t i o n ；a r t i c l em a d ead i s t i n c t i o n w i t h t i m ew i n d o w i n c o n c e p ta n di nt h ec u r r e n ts t u d y , t h ee x p r e s ss e r v i c ei sd e f i n e da st h ev o l u m ep e ru n i t t i m eo ft r a n s p o r t a t i o na n dd e l i v e r yo fc u s t o m e rn u m b e r s a c c o r d i n gt ot h ev i e w so fe n g i n e e r i n gs y s t e m ，t h ea r t i c l ea n a l y z e st h em e a n i n ga n d t y p e so fl o g i s t i c sd i s t r i b u t i o na n dd e s i g n st h es y s t e m t h ea r t i c l ee s t a b l i s h e st h e c o n f i g u r a t i o ns t a n d a r d so ft h el o g i s t i c st om a k es u r ew h e t h e rt h ep r o d u c ei st h eb e s t t h ec o s tm o d u l ea l s oi sd i v i d e d t h ea r t i c l ee s t a b l i s h e st w om o d e l si ns m a l lb a t c h e so fg o o d sw h i c hc a nb ea p p l i e d t ot h eo n e - w a yc a r g od i s t r i b u t i o n t h e s et w om o d e l sa r ea p p l i e dt ot h es i t u a t i o n sw h i c h t h ec u s t o m e rl i m i t st h et i m et of i n i s hu n l o a d i n gt h eg o o d sa n dt h et i m et od e l i v e rg o o d s w i t hg e n e t i ca l g o r i t h ma n ds i m u l a t i o ns o f t w a r e ，t h em o d e l sa r ev a l i d a t e d k e y w o r d s ：e x p r e s s e d ；v e h i c l es c h e d u l i n g ；g a ；v r p 目录 中文摘要i i i a b s t r a c t i v l 绪论1 1 1研究背景l 1 2国内外关于快运需求物流配送的研究概述2 1 2 1 车辆调度问题2 1 2 2 存储卸车管理3 1 3论文的理论出发点4 1 4本文研究内容5 2 快运需求物流配送系统分析6 2 1配送的定义6 2 2配送的类型和形式7 2 3配送最优化衡量9 2 4 制约快捷配送的主要因素1 0 2 5货物配送网络的分类1 2 2 6本章小结1 2 3物流配送车辆调度问题概述。13 3 1物流配送车辆调度问题简介1 3 3 2物流配送车辆调度问题的描述1 3 3 3物流配送车辆调度问题的数学模型1 4 3 4 模型研究方法概述15 3 4 1 旅行商方法1 5 3 4 2 动态规划法1 6 3 4 3 扫描法1 7 3 4 4 分区配送算法1 8 3 4 5 遗传算法原理和局限性2 0 3 4 6 禁忌搜索算法原理和局限性2 l 3 4 7 混合遗传算法2 2 3 4 8 爬山算法原理和局限性2 3 3 4 9 遗传算法与禁忌算法的复合2 3 3 4 1 0 遗传算法与爬山算法复合2 4 4 有总时段单向物流配送车辆调度模型。2 6 4 1有总时段单向物流配送车辆调度送到卸完模型2 6 4 2 总时段单向物流配送车辆调度送到模型2 7 4 3算例验证2 8 4 3 1 基于遗传算法的部分m a t l a b 编码3 0 4 3 2 模型一计算结果：3 4 4 3 3 模型二计算结果3 6 4 4本章总结3 6 5 本论文总结和展望。3 8 5 1本论文总结3 8 5 2有待于进一步研究的问题3 8 参考文献4 0 作者简历4 2 独创性声明4 3 学位论文数据集：4 4 j 匕塞交道叁堂速堂僮论童 绪论 1 绪论 1 1 研究背景 在经济全球化和信息化的浪潮中，现代物流业己经从为社会提供传统的运输 服务，扩展到以现代科技、管理和信息技术为支柱的综合物流系统。随着物流系 统的集约化、一体化的发展，配送不仅仅是物流方式的一种优化，而且促进了流 通方式的巨大变革。配送充分满足客户的需求，有效解决了库存和资金占用上的 瓶颈，成为物流活动中的一个的关键环节。 。 物流配送是物流系统中的一个重要环节，它是指按客户( 包括零售商店、用 户等) 的订货要求( 包括在货物种类、数量和时间等方面的要求) ，在物流中心( 也 称物流基地、物流据点，包括配送中心、仓库、车站、港口等) 进行分货、配货 工作，并将配好的货物及时送交收货人的物流活动。配送是直接与消费者相连的 环节，是一个体现了服务质量和水平的关键环节。配送是对顾客服务的最后一环， 其地位十分突出，因此如何实现快速而准确的配送是企业在经营方面必须解决的 重要课题。 国内外实践证明，配送服务可促进商品流通的社会化、现代化与合理化，是 一种极具生命力的流通方式。由于长期以来，我国重生产轻流通，在现代化建设 中，流通严重滞后。所以，加快流通现代化的步伐非常重要。流通现代化包括流 通设施、技术装备现代化和流通管理现代化。而配送作为一种综合性的物流活动， 要求相应的生产手段，包括现代化的仓储、计量、分拣、加工、装卸搬运和运输 等技术装备；同时要求拥有高素质的配送人员，组织、运用先进的管理方法和手 段，特别是利用计算机进行信息处理和辅助管理。因此，对“配货”与“送货”两阶 段的服务时间进行分析，有利于决策者优化人员配置，确定敏感路段，规避高风 险路段。 合理组织货物存储装卸，优化配送车辆调度，提高物流企业的服务质量，减 少物流企业和客户的库存，降低经营成本、增加经济效益是十分必要的。因此， 减少配送的作业时间是物流公司首先要考虑的。具有时效性的产品能给物流公司 带来高利润。而快捷便利的物流配送服务能向物流需求方提供资金、产品等多方 面的优势，使物流公司更具有竞争力，从而成为物流产业的主要组成部分，具有 代表性的物流公司如联邦快递。快运需求的物流配送具有很大的研究价值，具有 快运需求的物流配送在物流产业中有很大的价值。 j 量塞交通太堂亟堂僮i 金塞 绪论 1 2 国内外关于快运需求物流配送的研究概述 配送包含备货、储存、分拣及配货、配装、配送运输、送达服务等六个基本 环节，有的还包含配送加工环节。从目前查阅文献来看，物流配送的研究主要集 中在配送车辆调度和货物存储两个方面。 1 2 1 车辆调度问题 自从车辆运输调度问题于1 9 5 9 年提出后，b o d i n 、g o l d e n 、l i n u s 和s a v e l s b e r g h 等许多学者对其从不同角度按不同标准进行了多种分类。按任务特征分，有纯装 问题和纯卸问题( p u r ep i c ku po rp u r ed e l i v e r y ，车辆在所有任务点装货或卸货， 即集货和卸货问题) 及装卸混和问题( c o m b i n e dp i c ku pa n dd e l i v e r y ，每个任务 有不同的装货点和卸货点，即集货、送货一体化问题) 。 我国对车辆路径问题的研究是在2 0 世纪9 0 年代以后才逐渐兴起，比国外滞后 3 0 余年，国内最早对车辆路径问题进行系统研究的是郭耀煌教授，并出版了国内 关于车辆路径问题研究领域的第一部专著车辆优化调度。李大卫等以t s p 的最 近距离启发式为基础，通过设置评价函数来处理时间约束，求解了简单的v r p 1 】； 张涛等人则是通过遗传算法来保证搜索的全局性，用o p t 算法来加强局部搜索能 力，得到针对v r p 的混合算法【2 j ；遗传算法对v r p 的求解取得了丰富的成果。蔡延 光等应用并行禁忌搜索算法而后模拟退火算法对满载问题进行了求解，但只针对 简单情形【3 】【4 】。张建勇等基于模糊可能性理论运用混合遗传算法研究了模糊需求车 辆路径问题【5 】；祝崇俊、刘民、吴澄冽等人以模糊可能性分布，建立了v r p 的基于 置信度的三下标流模型，并提出了基于可能性分布的o p t 算法【6 】；该算法已可解决 较大规模的问题( 大于2 0 0 个客户) 。谢秉磊等给出了第一篇关于动态车辆路径问 题的综述【7 】【8 1 【9 】【1 0 】【i l 】【1 2 】【1 3 】【1 4 】；刘云忠给出了车辆路径问题的模型及算法研究综述 0 s o 车辆调度问题在目标和范围方面有很大差别，主要是研究的目标和限定条件 不同。在研究目标方面有的是最短路线，有的是最短时间，有的是客户的方便程 度等等。在限定条件方面，有配送中心方面的区别，和有单配送中心的，有多配 送中心；有配送车辆的数量、种类方面的区别，如车辆数有限、无限、单一车型 和多种车型；在业务种类方面，有的是集货任务，有的是送货业务，有的是集送 一体化业务，有的是各种业务混合情况。 有时间窗的车辆调度问题是最为普通的问题，大部分人都是对这个问题进行 研究。r o b e r t oc r d o n c 等提出了一种新的算法a k r e d ( a l t e r n a t e 2 j 匕哀交通太堂亟堂僮i 金塞 绪论 k - - - - c x c h a n g e r e d u c t i o n ) 1 6 】，主要是解决单配送中心、单车型的v r p t w 问题，这 个算法是两阶段近似算法，这种算法与t a b us e a r c h ，g e n e t i ca l g o r i t h m s ，s i m u l a t e d a n n e a l i n g 最大的区别和优势是解决和避免局部最优，寻求全局最优时不需要改变 参数设置，而是通过设立第二个目标函数来解决。需要注意的是第二个目标函数 与主目标函数应该是部分独立的，而不是密切相关的。文中使用的主目标函数是 使用的车辆数最少，次目标函数是行车时间总和最短。文章最后还通过对 b e n c h m a r k 问题的测试与其他方法的对比，证明此算法具有良好的效果。y v e s c a s e a u 和f r a n c o i sl a b u r t h e 设计了一个启发式算法求解有时间窗条件下的大规模 ( 几千个客户几百辆配送车辆的情况) 车辆调度问题。算法的核心是把未来插入 算法( 1 0 0 k - a b e a di n s e r t i o na l g o r i t h m ) 、增强局部优化方案( i n c r e m e n t a ll o c a l o p t i m i z a t i o ns c h e m e ) 和约束解决方法结合起来求解旅行商问题。与传统的局部优 化算法相比，这种算法不但速度快，而且结果更好【1 7 】。有限配送车辆的调度可能 存在的问题是有不能服务的客户或者违反时间窗的限制两方面。h o o n gc h u i nl 肌 等研究了在有限车辆数量下有时间窗的车辆调度问题。作者采用的是两阶段启发 式算法【l 引。为了解决有限车辆问题，作者引进了保留客户( 1 i s t ) 和层次成本构造 ( h i e r a r c h i c a lc o s ts t r u c t u r e ) 的做法，同时搜索战略采用的是t a b u 搜索法。但是， 没有说明保留那些客户。在实际中可以对客户进行等级分类，先把等级最低的保 留，在计算过程中慢慢添加，或者不进行服务，或者不按时完成配送任务。 s u n g _ - c h u ih o n g 等人把总行驶时间和客户的等待时间作为双目标建立模型，两 者通过一个决策者可以改变确定的权重系数关联建立现行目标规划模型，求解 运用启发式算法【1 9 1 。整个启发式算法分两个阶段：并行插入法进行分组( p a r a l l e l i n s e r t i o nm e t h o df o rc l u s t e r i n g ) ：用顺序线性规划进行路线安排( s e q u e n t i a ll i n e a rg o a l p r o g r a m m i n gp r o c e d u r ef o rr o u t i n g ) 。客户的等待时间可以反映客户对服务满意程 度的一个标准。 7 1 2 2存储卸车管理 国内外关于这方面的研究的主要是以电子信息系统为手段，以管理为方法的 研究方向，具体的表现为装卸仓储管理信息系统w m s ( w a r e h o u s em a n a g e m e n t s y s t e m ) 。 由计算机控制的仓库管理系统的目的是独立实现仓储管理各种功能：收货、在 正确的地点存货、存货管理、定单处理、分拣和配送控制。仓储管理系统w m s 是仓储管理信息化的具体形式，它在我国的应用还处于起步阶段。下面从应用角 度对国内企业的w m s 概况做一个分析。 第一类是基于典型的配送中心业务的应用系统，在销售物流中如连锁超市的 配送中心，在供应物流中如生产企业的零配件配送中心，都能见到这样的案例。 第二类是以仓储作业技术的整合为主要目标的系统，解决各种自动化设备的 信息系统之间整合与优化的问题。 第三类是以仓储业的经营决策为重点的应用系统，其鲜明的特点是具有非常 灵活的计费系统、准确及时的核算系统和功能完善的客户管理系统，为仓储业经 营提供决策支持信息。 上述三类只是从应用角度来做的一个简单分类。第一类w m s 比较标准，但 是并非所有企业就能一下子用起来。第二类是企业内部物流发展进程中经常会用 到的，当生产企业或商贸企业在推进其信息化的时候，物流部分往往先从自动化 开始，然后与企业的其他信息系统整合起来。第三类则是传统仓储企业向现代物 流业过度的进程中经常会见到的情况。w m s 的这些分类反映了我国物流需求还不 很成熟的现状，所以各自有其用武之地。 1 3 论文的理论出发点 快运配送是配送诸多形式的一种，它是指在一定时间内运送更多的货物。在 时段一定的情况下，快运配送通过运送的货主数量来体现；在客户数量一定且作 业时段宽裕时，通过汽车的行驶里程来体现。 本文研究的是小批次货物的快递配送。这种配送具有货物批次小、货主每次 货物需求不确定、货主对货物的配送时间没有明确的时段性但具有时限性等特点。 在现实中，有很多这样的快递物流公司或者快递配送部门，比较典型的公司有e m s 包裹快递公司、u p s 快递包裹公司，为各公司提供货物配送的顺丰物流。本文问题 的研究，将有利于减少物流配送的耗费，争取最大的货源，保证最大的客户数量。 在理论上，快运物流配送的车辆调度的研究主要是集中在时间窗这一块。时 间窗是指按照客户的要求在某个时间点送到，分为软时间窗和硬时间窗。软时间 具有惩罚约束，硬时间窗则是过点就拒收，可以理解为惩罚约束无穷大。本文研 究的是在客户没有明确时限要求情况下的一定时段内物流配送的路径最小化和客 户数量最大化，客户数量的最大化权重高于路径的最小化。 时效性是物流配送的主要特点之一，但时效不等于快速。例如，定时运送和 带时间窗要求的配送就非常强调时效性，但对物流客户而言并不是货物越早到达 越好，货物提f i j i i n 达，不利于货主生产。 随着下订单时间的不同，每个客户所要配送的最低时间不同。物流服务商根 据各个订单的时限取公共集，以确定自己的配送作业时间段。因此，本文的快运 4 j 匕塞交通太堂亟堂位i 金塞 绪i 金 是指物流配送商从物流中心出发在一定时间段内尽量多的配送给客户、尽量多的 运送货物，通过提高物流配送服务商的作业量来体现快运。 1 4 本文研究内容 根据快运需求物流配送的研究现状，本文的研究内容包括： ( 1 ) 用系统理论的观点对物流配送进行整体剖析、设计，按照经济成本的 观点进行系统设计，以提炼出物流配送中能体现快运的因素。 ( 2 ) 有总时段限定的单向物流货物配送车辆调度的送到卸完模型。 ( 3 ) 限定时段内客户最大化单向货物配送车辆调度的送到模型。 ( 4 ) 设计求解算法，并以算例验证模型的有效性。 5 j 匕立交道太堂亟堂僮i 金塞迭运盂塞物逋配鲎丕统公蚯 2 快运需求物流配送系统分析 2 1配送的定义 配送是按照配送合理化的要求，在全面计划的基础上制定科学的、距离较短 的货运路线，选择经济、迅速、安全的运输方式和选用适宜的运输工具的运输方 式。 配送是一种特殊的、综合的活动形式，是商流与信息流紧密结合，包含了商 流活动和信息流洁动。 配送包括了所有的物流功能要素，是物流的一个缩影或在某小范围中物流全 部活动的体现。一般的配送集装卸、包装、保管、运输于一身，通过这一系列活 动完成将货物送达的目的。特殊的配送则还要以加工活动为支撑，所以包括的方 面更广。配送的主体活动是运输及分拣配货，分拣配货是配送的独特要求，也是 配送中有特点的活动，以送货为目的运输则是最后实现配送的主要手段，从这一 主要手段出发，常常将配送简化地看成运输中之一种。 概念一，从经济学资源配置的角度，对配送在社会再生产过程中的位置和配 送的本质行为予以表述： 配送是以现代送货形式实现资源的最终配置的经济活动。这个概念的内涵， 概括了四点： ( 1 ) 配送是资源配置的一部分，根据经济学家的理论认识，因而是经济体制 的一种形式。 ( 2 ) 配送的资源配置作用，是“最终配置”，因而是接近顾客的配置。接近 顾客是经营战略至关重要的内容。美国兰德公司对幸福杂志所列的5 0 0 家大 公司一项调查表明“经营战略和接近顾客至关重要”，证明了这种配置方式的重要 性。 ( 3 ) 配送在社会再生产过程中的位置，是处于接近用户的那一段流通领域， 因而有其局限性，配送是一种重要的方式，有其战略价值，但是它并不能解决流 通领域的所有问题。 概念二，从配送的实施形态角度，表述如下： 按用户定货要求，在配送中心或其它物流结点进行货物配备，并以最合理方 式送交用户。 这个概念的内容概括了五点： ( 1 ) 整个概念描述了接近用户资源配置的全过程。 6 j 丝哀交通太堂亟堂僮j 金塞 迭运盂壅物速醒送丕统盆抚 ( 2 ) 配送包含仓储和送货： 一般收送货可以是一种偶然的行为，而配送却是一种固定的形态，甚至是一 种有确定组织、确定渠道，有一套装备和管理力量、技术力量，有一套制度的体 制形式。 ( 3 ) 配送是一种“中转”形式。配送是除去主干运输的其他的作业环节。广义 上，许多人也将非中转型送货纳入配送范围，将配送外延从中转扩大到非中转。 ( 4 ) 配送以用户要求为出发点。在定义中强调“按用户的定货要求 明确了 用户的主导地位。配送是从用户利益出发、按用户要求进行的一种活动，因此， 在观念上必须明确“用户第一”、“质量第一 ，配送企业的地位是服务地位而不是 主导地位，因此不能从本企业利益出发而应从用户利益出发，在满足用户利益基， 础上取得本企业的利益。更重要的是，不能利用配送损伤或控制用户，不能利用 配送做为部门分割、行业分割、割据市场的手段。 ( 5 ) 概念中“以最合理方式”的提法是基于这样一种考虑：过分强调“按用 户要求”是不妥的，用户要求受用户本身的局限，有时实际会损失自我或双方的利 益。对于配送者讲，必须以“要求”为据，但是不能盲目，。应该追求合理性，进 而指导用户，实现共同受益的商业原则。这个问题近些年国外的研究著作也常提 到。 2 2配送的类型和形式 在不同的市场环境下，为适应不同的生产和消费需要，配送表现出多种形式。 这些配送形式各有优势，同时也有各自的适应条件。 1 按配送服务的范围划分 ( 1 ) 城市物流配送：即向城市范围内的众多用户提供服务的配送。其辐射距 离较短，多使用载货汽车配送，机动性强、供应快、调度灵活，能实现少批量、 多批次、多用户的“门到f - j 配送。 ( 2 ) 区域物流配送：是一种辐射能力较强、活动范围较大、可以跨市、省的 物流配送活动。它具有以下特征：经营规模较大，设施齐全，活动能力强；货物批量 较大而批次较少；区域配送中心是配送网络或配送体系的支柱。 2 按配送时间及数量划分 ( 1 ) 定时配送：指按规定时间或时间间隔进行配送。每次配送的品种及数量 可按计划进行，也可在配送前由供需双方商定。定时配送有以下几种具体形式： 一是小时配：即接到配送订货要求1 小时内将货物送达。适用于一般消费者 突发的个性化配送需求，也经常用做应急的配送方式。 7 j 匕立交遭太堂亟堂位论塞迭运盂塞物逾醒鲎丕统盆盘 二是日配：即接到订货要求2 4 小时之内将货物送达。日配是定时配送中较为 广泛采用的方式，可使用户获得在实际需要的前半天得到送货服务的保障，基本 上无须保持库存。 三是准时配送方式：即按照双方协议时间，准时将货物配送到用户的一种方 式。这种方式比日配方式更为精密，可实现零库存，适用于装配型、重复、大量 生产的企业用户，往往是一对一的配送。 四是快递方式：是一种在较短时间内实现货物的送达，但不明确送达的具体 时间的快速配送方式。一般而言其覆盖地区较为广泛，服务承诺期限按不同地域 会有所变化。快递配送面向整个社会企业型和个人型用户，如美国的联邦快递、 我国邮政系统的e m s 快递都是运作得非常成功的快递配送企业。 ( 2 ) 定量配送：即按事先协议规定的数量进行配送。这种方式货物数量固定， 备货工作有较强的计划性，容易管理。 ( 3 ) 定时定量配送：即按规定的配送时间和配送数量进行配送，兼有定时、 定量两种方式的优点，是一种精密的配送服务方式。 ( 4 ) 定时定路线配送：即在规定的运行路线上，按配送车辆运行时间表进行 配送，用户在指定时间到指定位置接货。 ( 5 ) 即时配送：即完全按用户突发的配送要求随即进行配送的应急方式，是 对各种配送服务的补充和完善，灵活但配送成本很高。 3 按配送品种和数量不同划分 ( 1 ) 单( 少) 品种大批量配送：配送的商品品种少、批量大，不需与其他商品 搭配即可使车辆满载。 ( 2 ) 多品种少批量配送：按用户要求将所需各种物资配备齐全，凑整装车后 由配送据点送达用户的一种配送方式。 ( 3 配套成套配送：按生产企业的需要，将生产每台产品所需的全部零部件 配齐，按生产节奏定时送到生产线装配产品。 4 按配送企业业务关系划分 ( 1 ) 综合配送：指配送商品种类较多，在一个配送网点中组织不同专业领域的 产品向用户配送的配送方式。 ( 2 ) 专业配送：指按产品性质、形状的不同适当划分专业领域的配送方式。 其重要优势在于可以根据专业的共同要求束优化配送设施，优选配送机械及配送 车辆，制定适用性强的工艺流程等，从而提高配送各环节的工作效率。 ( 3 ) 共同配送：是指为提高物流效率，由多个配送企业联合在一起共同进行 的配送方式。 5 按加工程度划分 8 ( 1 ) 加工配送：指在配送据点中设置流通加工环节，当社会上现成的产品不 能满足用户需要，或用户提出特殊的工艺要求时，可以经过加工后进行分拣、配 货再送货到户。流通加工与配送的结合，使流通加工更有针对性，可取得加工增 值收益。 ( 2 ) 集疏配送：是只改变产品数量组成形态而不改变产品本身的物理、化学 形态，与干线运输相配合的一种配送方式。比如大批量进货后小批量、多批次发 货，零星集货后以一定批量送货等。 6 按配送的方式划分 ( 1 ) 直送：指生产厂商或供应商根据订货要求，直接将商品运送到客户的配 送方式。特点是需求量大，每次订货往往大于或接近一整车，且品种类型单_ 。 这种配送线路往往是单程式有载往复行驶线路。即车辆在运送货物过程中回程不 载货。由于车辆利用率比较差，里程利用率不到5 0 ，只有利用装卸作业点之间 的最短路线，才能缓解车辆被利用的情况。 ( 2 ) 集取配送：即往复配送，指与用户建立稳定的协作关系，在将用户所需 的生产物资送到的同时，将该用户生产的产品用同一车运回。不仅充分利用了运 力，也降低了生产企业的库存。它包括两种情况，即回程部分有载往复式行驶线 路和双程有载往复式行驶线路。 回程部分有载往复式行驶是指回程货物只运到线路中间的某个结点。这种行 驶线路的车辆里程利用率在5 0 到1 0 0 之间。 双程有载往复式行驶线路是指回程( 从卸货点到装货点) 全部载有货物。车 辆在每一周转中同样完成了两个运次，空载行程接近于零。 ( 3 ) 交叉配送：指在配送据点将来自各个供应商的货物按客户订货的需求进 行分拣装车，并按客户规定的数量与时间要求进行送货。有利于减少库存、缩短 周期、节约成本。这种配送往往是环形式行驶线路。即车辆在由若干个物流结点 组成的封闭回程线路上连续单向运行的行驶线路。 ( 4 ) 会集式行驶线路：指车辆沿分布于运行线路上各物流结点依次完成相应 的装卸作业，且每次的货物装( 卸) 量均小于该车核定载货量，直到整个车辆装 满( 卸空) 后返回出发点的行驶线路。这种线路主要有三种方式即分送式、收集 式、分送收集式。 2 3配送最优化衡量 配送最优化是服务提供商的努力目标，也是服务需求商所要需要的，是服务 提供尚和需求商的最优结合点。但服务需求商和提供商对最优配送的实现途径确 9 j 匕塞銮通左堂亟堂僮i 金塞怯重盖盛趁速醒堂丕红盆垣 有各自表述。 ( 1 ) 从快捷服务需求商的角度来考虑，主要是配送服务的时效性和安全性、 经济性，可以称为“配送品质指标”。 服务需求商根据货物运送时间和货物的完整性为主要依据来判断快捷服务提 供商的品质，经济性其次；或者说安全性和时效性的权重大于经济性。具体权重 指标多少还需要通过大量市场调查来得出，在本文中不做太多考虑。 ( 2 ) 在快捷服务提供商的立场，主要是从经济成本上来考虑，即要经济成本 最小。以经济成本为出发点，引生出时间成本、物料成本、人力成本和其他成本。 或者说这些成本最终都汇聚为经济成本表现到快捷服务供应商那里。 时间成本( t ) 是通过单位时间的配送量表示出来的，它们成正比关系。单位 时间配送量越高，时间成本越高；单位配送量越低，时间成本越低。或者说时间 成本表示为在单位时间内能获得的最大收益或者是所能完成的最大工作量。 物料成本( m ) 表示为在正常情况下完成一单位所消耗的平均物质，如完成一 吨配送所消耗的汽油、电力、派送的汽车及各种物质的折旧。 人力成本( l ) 是指完成一单位货物配送所需要的人力或者说所需要支付的薪 金。 其他成本( o ) 是指不能单独列项的一些零项支出或非正常支出，如车辆的意 外碰撞导致的支出。 e经济成本) 时间成本( t ) 物料成本：人力成本、其他成本： 图2 - 1 经济成本构成图 f i g u r e2 - 1t h em a pa b o u te c o n o m i cc o s t 2 4制约快捷配送的主要因素 对服务需求商来说，在安全性可衡量、稳定的情况下，快捷最优配送的衡量 指标是时效性；对服务提供商来说，快捷最优配送的衡量指标是经济性，即对于 成本的考虑。因此，快捷配送最优问题可描述为在经济成本最小条件下的时效性 最大化或者是在时效性最大化条件下的经济成本最小化。 基于以上的要求，影响最优配送的因素包含在以下几个方面： ( 1 ) 仓库的选址或者物流中心的选址。仓库是货物中转、分拣、库存的场所。 l o j 匕塞交道太堂亟堂位j 金塞迭运盂盛物近醒堂丕统盆扳 仓库的选址决定着服务需求者、仓库、长途主干运输网络( 例如铁路车站、飞机 场) 三者之间的最短距离。 仓库类型影响着仓库的选址。如，仓库可以是分类仓库，也可以是主仓库和 卫星仓库。因此，应各主服务需求商的产品特性考虑仓的库选址和布局。 例如，同城不同地点多个服务需求商的货物能否实现最短位移进入( 主) 仓 库中转；各仓库与长途主干运输网络接入口的距离和最短，或者是主仓库与长途 主干运输网络接入口最短的条件下，各分仓库实现与长途主干运输网络接入口最 短距离。 ( 2 ) 车辆调度计划的制定。这个问题可以归结为在最短时间内用最少的车次 最小的物耗实现商品或者是中小件货物的移动。 在现实中，快捷服务提供商常常要从所在的仓库点向各自辐射区域排车队同 时为多个服务需求商服务的情况。此时，派车点首先要考虑各服务需求商的优先 权，以及收集小批次货物时车辆路径的合理安排。 当某服务需求商所需服务量特别大时，经常会出现跨区派车的情况。如图2 2 所示在同一服务需求商的情况下，从a 区调车去b 区向b 仓库运货；在a 区整体 繁忙的情况下，可适当扩大周边仓库的辐射区域，实现弹性辐射。 中转货物出仓后转到主干运输网络的问题。在车耗费用最小的条件下，各仓 库的小批量货物如何集结进入主干运输网络的问题。例如，是各仓库点派车送到 火车站或者飞机场还是只派遣一辆车收集各仓库的小批量货物然后在送入到火车 站或者飞机场。 图2 2 辐射区示意图 f i g u r e2 - 2t h em a pb o u tc a r g oa r e a ( 3 ) 在仓库点装卸等待时间。具体是指在装卸力量一定的条件下各辐射区的 货车接货回到服务区后仓库按照什么次序卸货以尽量减少各车卸车等待时间。 j 鳖塞銮道太堂亟堂僮途塞 怯运盂塞物近醒耋丕统盆逝 2 5货物配送网络的分类 按照生产的实际情况，配送网络可分为三种，分别是集中型配送网络、分散 型配送网络、多层次配送网络。 ( 1 ) 集中型网络配送网络。指在配送系统中只设一个配送中心，所有用户需 要的物品均由这个配送中心完成任务。 ( 2 ) 分散型配送网络( 单层次配送网络) 。指在配送系统中有多个配送中心， 而将用户按照一定的原则区分，归属某一个配送中心。 ( 3 ) 多层次配送网络。是指在系统中设有两层或者更多层次的物流中心和配 送中心，其中至少有一层是配送中心而且靠近用户。 2 6本章小结 本章对物流配送的定义、分类、最优配送的成本构造、制约配送的主要因素 进行了介绍；强调了车辆调度在快运配送中的重要地位，然后介绍了货物配送网 络的分类。 1 2 3 物流配送车辆调度问题概述 3 1物流配送车辆调度问题简介 v r p 问题作为一个n p 难题，随着客户数量的增加，可选的配送路径方案 数量将以指数速度急剧增长，即出现组合爆炸现象。v r p 问题作为一个约束性 多路径旅行商问题，与t s p 相比，不仅约束条件更为复杂，而且存在多条配送 路径，因此，其计算量会比t s p 大得多。一般的，只有在客户数量较少、运输 网络简单时，才能求得v r p 问题的精确最优解。根据研究重点的不同，v r p 问 题存在多种分类方式。 按已知信息的特征可分为确定性v r p 和不确定性v r p ；而其中不确定性 v r p 又可进一步分为随机v r p ( s v r p ) 和模糊v r p ( f v l 冲) ：按约束条件的 不同，可以分为c v r p ( 带能力约束) 、d v r p ( 带时间距离约束) 、v r v r p ( 带 时问窗) 。 一般的具体分类有以下几种： ( 1 ) 按配送中心的数目分，有单配送中心问题和多配送中心问题。 ( 2 ) 按客户对货物取( 送) 时间的要求分，有无时限问题( 客户对货物送 到的时间无具体要求) 和有时限问题( 客户要求将需求的货物在规定的时间窗 内送到，也称为有时问窗问题) 。有时限问题又可以分为硬时间窗问题( 客户要 求货物必须在规定的时间窗内送到，不能提前也不能拖后) 和软时间窗问题( 客 户要求将货物尽量在规定的时间窗内送到，但也可以提前或拖后，只不过在提 前或拖后时，要对配送企业实施一定的惩罚) 。 ( 3 ) 按车辆类型数分，有单车型问题( 所有配送车辆的载重量相同) 和多 车型问题( 配送车辆的载重量不完全相同) 。 ( 4 ) 按优化目标数分，有单目标问题( 仅考虑一个配送目标) 和多目标问 题( 同时考虑多个配送目标) 。 ( 5 ) 按配送中心的货物数量有无限制分，有容量无限的问题( 即假定配送 中心的货物数量充足，能够满足所有客户的要求) ，和容量有限的问题( 即配送 中心的货物数量是有限的) 。 3 2物流配送车辆调度问题的描述 l 匕塞交通厶堂亟堂位途塞物速配遂奎牺调廑闻题概述 v r p 问题定义为：设图g = ( e a ) 是一个连通的混合网络，其中肛f j ， 以，为节点集，表示城市( 或货栈) ，而点1 表示中心车站，彳为联弧集。对于每一 弧( i , a o 有一非负距离矩阵c = ( c ) ，c 可视为旅行费用或旅行时间；另外，假定 中心站有m 辆可用车，其中m 锄 l ，有一个非负重量( 或 需求) 4 与之相联系，车辆载重不能超过其最大能力，该类问题又称为c v r p s ； 每一径路上城市数( 或货栈) 限制，不允许超过某一常数； 总运行时间约束，路线的长度或车辆总运行时间( 线路运行时间+ 中间停车 时间) 不允许超过规定值工，该类问题又称为d v r p s ； 时间窗口约束：城市( 或货栈) f 只允许在给定的时间窗范围内访问； 优先关系：城市( 或货栈) i 必须先于城市( 或货栈) d 被访问。其他约束 包括车队数( 一个车队、多个车队) ，每个车队车辆数( 一辆，多于一辆) ，车 辆类型( 相同、不同) ，供求类型( 确定、不定) ，需求位置( 边、节点、混合 型) ，网络类型( 无向、有向、混合) ，其它时间规定( 有、无) ，费用函数( 固 定、随时间变化、模糊、随机) ，作业类型( 有倒装、无倒装) ，车队位置( 活 动、确定) ，送达程度( 全部、部分) 等。目标函数( 总里程最短、运费最小、 人因素、最少车辆数、缺货损失、停车损失等) 。 3 3物流配送车辆调度问题的数学模型 一般v r p 问题可描述为：用于送货的若干辆相同型号的车从配送中心出发， 到不同地理位置的客户那罩去送货，然后返回配送中心，要求每辆车只髓出发一 次，任何一个客户有且只能有一辆车访闯，并且所配送的货物不能超过车辆的载 重量，求一种配送方案使得配送总成本最少。 令g = ( ，e ) 为一无向图，其中肛( v , l i = o , 1 ，2 ，