（产业经济学专业论文）货运物流配送决策系统研究与设计.pdf

i 摘 要 摘 要 随着世界经济的一体化，中国的企业面临着国内外的考验，商业竞争越来越 激烈，如何在保持利润基础上寻找新的利润增长点，成为企业必须考虑的问题。 很多企业在提高客户满意度和减少运营成本等方面做文章。对于物流行业来说， 配送系统是物流系统的重要组成部分，它肩负着在正确的时间把正确的货物送到 正确的人手上，配送系统的好坏直接关系到物流系统的效率和整体物流成本。因 此设计符合企业需求的高效的物流配送系统对提高企业服务水准和信息化程度， 降低企业运营成本有着重要的意义。因此本文对该问题展开研究，主要研究工作 如下： 第一，针对物流配送的业务进行研究，分析影响物流配送效率的因素，提出 物流配送系统的优化目标，建立物流配送的多目标优化函数，引入时间窗约束， 把优化目标转化为带时间窗约束的物流配送车辆路径优化问题。 第二，对带时间窗约束的物流配送车辆路径优化问题建立单配送中心多用户 的多目标规划问题的数学模型， 该模型综合考虑了运输费用、 惩罚成本二种因素， 模型中可以根据企业对两个因素的重视程度给每个目标辅以不同的权重值。对原 始的节约算法进行修正，并考虑时间约束，在对节约算法改进的基础上对所建的 多目标数学模型求解。 第三， 以大众物流信息平台项目为背景， 开发了其中的物流配送决策子系统， 分析了系统的主要功能模块、设计了系统的主要工作流程和数据库、部分实现了 核心模块。论文最后以一个单配送中心的配送实例，完成物流配送路径方案的生 成，指导企业的实际配送业务。实例证明，该配送系统的路径优化模型节约了运 输成本，减少了运输时间，可以提高了整个企业的生产率。 关键词：物流配送、车辆路径问题、节约式算法 ii abstract with the integration of the world economy, chinas enterprises faced with the test at home and abroad, business competition has become fiercer, how to maintain profits on the basis of looking for new profit growth, as enterprises must consider. many enterprises in improving customer satisfaction and reduce operating costs, such as making an issue of respect. for the logistics industry, logistics distribution system is an important component of the system, which should at the right time to put the right goods to the hands of the right people, the distribution system will have a direct bearing on the efficiency of the logistics system and the overall logistics cost. therefore the design to meet your business needs efficient logistics and distribution system to enhance their standard of service and the degree of information, reduce the cost of enterprise operations is of important significance. so this study of the issue, the main research work are as follows： first, for logistics and distribution business research, analysis of the impact on the efficiency of logistics and distribution, set up the logistics and distribution systems to optimize goal, the establishment of logistics and distribution of multi-objective optimization function, the introduction of time window constraints, to optimize the target zone into a window of time constraints to the logistics and distribution vehicle routing optimization problem. second, window of time constraints with the logistics and distribution vehicle routing optimization single distribution center set up multi-user multi-objective planning of the mathematical model, the model considered the transport costs and punishment cost factors, model based on two factors enterprises degree of attention to each goal supported by the weight of different values. the conservation of the original saving algorithm that and consider the time constraints, the algorithm to improve conservation on the basis built by the mathematical model for multi-target. third, the logistics to the public information platform for the project background, the development of the logistics and distribution of these decision-making system, iii analysis of the systems main function modules, the system design of the major work processes and databases, to achieve some of the core module. the final papers to a single distribution center distribution example, logistics and distribution path to complete the formation of the programming, guiding the actual distribution business, examples show that the distribution system optimization model the path of the transport cost savings, reducing the transit time, can improve the whole the productivity of enterprises. keywords：logistic distribution system, vehicle routing problem, saving method 学位论文原创性声明学位论文原创性声明 本人郑重声明： 所呈交的学位论文， 是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容 外，本论文不含任何其他个人或集体已经发表或撰写过的作品成 果。对本文所涉及的研究工作做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律责任由本 人承担。 本人郑重声明： 所呈交的学位论文， 是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容 外，本论文不含任何其他个人或集体已经发表或撰写过的作品成 果。对本文所涉及的研究工作做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律责任由本 人承担。 特此声明特此声明 学位论文作者签名：学位论文作者签名： 年年 月月 日日 学位论文版权使用授权书学位论文版权使用授权书 本人完全了解对外经济贸易大学关于收集、保存、使用学位 论文的规定，同意如下各项内容：按照学校要求提交学位论文的 印刷本和电子版本；学校有权保存学位论文的印刷本和电子版， 并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有 权提供目录检索以及提供本学位论文全文或部分的阅览服务；学 校有权按照有关规定向国家有关部门或者机构送交论文；在以不 以赢利为目的的前提下，学校可以适当复制论文的部分或全部内 容用于学术活动。保密的学位论文在解密后遵守此规定。 本人完全了解对外经济贸易大学关于收集、保存、使用学位 论文的规定，同意如下各项内容：按照学校要求提交学位论文的 印刷本和电子版本；学校有权保存学位论文的印刷本和电子版， 并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有 权提供目录检索以及提供本学位论文全文或部分的阅览服务；学 校有权按照有关规定向国家有关部门或者机构送交论文；在以不 以赢利为目的的前提下，学校可以适当复制论文的部分或全部内 容用于学术活动。保密的学位论文在解密后遵守此规定。 学位论文作者签名：学位论文作者签名： 年年 月月 日日 导师签名：导师签名： 年年 月月 日日 1 第第 1 章章 引言引言 1.1. 课题研究的背景 1.1.1. 物流信息平台现状 货物运输方式主要有航空运输、铁路运输、轮船运输、汽车运输等方式，其 中航空、铁路和轮船运输主要用于较远距离的运输任务，汽车运输主要用于较短 距离的货物运输。航空运输时间最短但是运输费用最高且单件货物体积不能太 大，铁路运输可运送体积大且不易损耗的货物，轮船运输时间较长但是运输费用 较低且可运输较大体积的货物，汽车运输时间也较短运输费用相对也较低是日常 运输中最常用的运输方式1。随着城市公路的发展，公路交通路线日益复杂,汽车 运输的运输路线并不是唯一的，为货物的汽车运输选择合适的运输路线成为运输 优化中的一个重要课题。目前我国物流服务行业存在较多问题，国内物流信息服 务模式存在很多弊端： 目前物流公共信息平台依然采用“寻呼中心+传呼终端接受器”的短波传输 技术，面向会员企业和个人提供广播式的信息服务模式。这种广播式的信息服务 模式存在诸多弊端： 一、 配货站接收到的信息有效性差和大量的冗余信息的存在。 物流企业和配货站只能在接受信息之后按照车（货）源的始发地和到达地进行简 单的筛选处理，但是这样不能保证配货站即时地获取到他们当前需要的物流信 息，因此，配货站只能安排专人不间断的注视着信息筛选结果以期待获取自己需 要的信息，这样就会增加了配货站的人员成本。二、广播式的信息服务模式容易 引起“信息纷争” 。如果某个配货站在公共信息服务平台上发布一条货源信息， 该信息通过公共信息服务平台广播传输模式发布到每个配货站点，采用的是短波 传输技术的信息服务模式，信息服务的有效范围小只有一定范围的物流公 司、配货站能在该公共信息平台上实现物流信息共享，形成以城市为界限的“信 息孤岛” ，信息量有限、信息共享程度低、信息服务范围小，造成物流企业获取 有效信息成本高、难度大。 物流运输过程中“回空”现象严重，公共信息服务平台服务对象仅仅为固定 地域内的物流公司、配货站，并没有直接服务于车主、货主。车主由于不能在路 2 上及时获取需要的有效信息，导致物流运输过程中“回空”现象严重。 配货站一般规模较小，这些配货机构一是接触的车、货信息有限，造成交易 成功的偶然性很大，许多车辆常常放空；二是无法对车主进行调查，当出现货物 遗失等情况时难以处理和追踪，信用度极低。甚至出现恶意“套货” 、 “骗车”现 象，扰乱物流市场的秩序，增加政府部门对物流配送市场管理的难度。 因此，建立面向地区物流公司、配货站、车主提供精准匹配物流信息的物流 信息平台，构建企业的物流配送决策系统是必要的。物流配送决策系统将在一定 程度上扩大共享信息源、提高物流交易成功率、缩短物流交易时间、降低物流交 易成本，这是作者研究本课题的出发点。 1.1.2. 大众物流信息服务平台项目 大众物流信息服务平台项目包括城市配送平台、流通货运平台、行业协同平 台、公共物流资源平台，建成面向区域配送、城间运输、企业供应链管理以及业 务协作的、具有广泛适用性的综合性 asp(application service provider)服务平台。 在这一平台上，可以为城域中小企业提供包括业务流程处理在内的整体信息化解 决方案；接入大型货运企业，构成物流服务基地；为城市配送企业提供配送解决 方案，帮助流通行业企业通过平台应用和业务对接，实现以物流企业为核心的供 应链管理， 实现上下游之间及同行业企业之间的业务协作和流程接续； 实现货源、 车辆、仓库、库存、位置、流量、需求等信息的实时发布和查询；提供门户网站， 政府各相关部门利用本平台进行政务信息发布、行业指导，根据平台提供的数据 进行行业数据统计分析，为行业管理及宏观调控提供依据；为流通企业和相关使 用者提供数据分析、流程优化、库存控制、业务咨询、资源匹配等增值服务。 本课题以大众物流信息服务平台项目为背景，研究设计其核心部分物流配送 决策子系统，通过对物流配送的车辆路径优化达到物流配送系统的优化，完成对 配送决策理论研究和系统的分析、设计和部分实现。 1.2. 本文研究的目的和意义 美国物流专家 robert v delancy 提出物流总成本由运输成本、存货持有成本 和物流行政管理成本构成，即物流总成本=运输成本存货持有成本物流行政 管理成本2。 图 1.1 是中国 1992 年到 2002 年的物流成本组成占 gdp 的比例。 从表中不难 3 看出物流成本中，运输成本占的比重之大。因此在物流配送中，如何合理、有效 的分配配送资源、安排配送线路，不仅关系到配送效率，而且直接影响运输成本。 合理的配送决策、配送车辆的合理安排和车辆路径的合理调度等对于降低配送费 用、提高用户满意度、提高企业经济效益都有着重要的意义。 图 1.1 19982002 年的我国物流成本统计 （资料来源：本研究整理） 本文的研究目的就是对物流配送的业务进行研究和分析，分析影响物流配送 效率的因素，建立物流配送的优化模型，并设计一个物流配送决策系统，解决企 业的配送业务，提高配送效率，降低物流配送成本，提高订单的相应度和客户满 意度，增加企业效益。 为了实现最终研究目的，本文先对物流配送流程进行研究和分析，找出物流 配送流程中影响配送成本的因素。在此基础上，对配送车辆路径问题(vrp)进行 的理论研究，建立基于混合时间窗的物流配送数学模型，并采用节约式算法对所 见模型进行求解，得出合理的配送策略。最后本文以大众物流信息平台为背景， 分析和设计并部分实现配送决策子系统，并配送车辆路径优化进行实例验证。 1.3. 本文的研究内容 本文的具体研究内容包括以下二个部分： 1) 配送车辆路径优化 本文通过对现有配送业务的描述，分析影响配送业务流程中的各项因素。对 于单配送中心多用户的配送车辆优化问题进行理论研究，对同类运输方式的货物 订单进行优化组合，根据货物的运输路径和吨位，建立一个基于混合时间窗的车 辆调度优化模型，并采用节约法计算最优车辆配送路径。 0 5000 10000 15000 20000 25000 19981999200020012002 物流成本占gdp的比例(%)运输成本占gdp的比例(%) 4 路径选择有很多的处理方法，如精确优化方法、启发式算法、模拟方法、人 工智能方法等等。本文采用节约法为工具来生成配送决策，并对模型进行验证。 给定起始城市、所经过的城市以及需运输到该城市的货物吨位，系统自动计算最 优路径以及所需的最小成本。 2) 配送决策子系统的分析、设计 本文采用面向对象的信息系统建模思想，以某物流公司综合物流信息平台为 背景，分析和设计配送决策子系统，对配送决策系统的业务流程抽取出不同的功 能模块，对各个模块进行分析和设计。 系统最后以实际数据验证模型，由配送 决策系统生成车辆配送路径。围绕本课题研究内容，为了达到研究目标本文按图 1.2顺序组织安排： 第一部分是引言部分， 首先介绍论文的研究背景， 在介绍研究背景的基础上， 引出本课题的研究目的和意义，最后介绍论文的研究内容和结构安排。 第二部分包括两章， 第二章先介绍物流、 物流配送的概念和物流配送的流程， 以及物流信息系统的概念，再介绍物流配送车辆路径优化理论研究的现状和我国 物流配送现状和发展趋势。第三章是货运物流配送模型研究，主要是车辆路径优 化问题（vrp）的理论研究，本文以五路运输成本最小和时间惩罚成本最少为目 标，建立单配送中心多用户的车辆配送的目标函数，为了降低研究难度和研究方 便选取线性函数作为时间惩罚函数，建立数学模型，用节约法对模型求解，并用 参考文献的经典数据解释节约法。 第三部分是物流配送子系统的分析与设计，由于时间有限，本文对物流系统 的配送子系统进行分析、设计和部分实现，最后用实际数据验证论文所建的基于 混合时间窗的车辆路径优化模型。 5 第一章引言 第五章 货运物流配送实例 第四章 物流配送决 策系统分析与设计 第三章 货运物 流配送模型研究 第二章 物流配送概述 第三部分：货运物流 配送系统分析与设计 第一部分：引言 第二部分：货运物流 配送模型 货 运 物 流 配 送 决 策 系 统 研 究 与 设 计 图 1.2 本文的结构和内容安排 1.4. 本章小结 本章主要阐述论文的研究背景和物流配送决策系统研究的重要意义，描述中 体现本文的研究方法，最后介绍本文的研究内容和论文结构安排。 6 第第2章 物流配送概述章 物流配送概述 配送是物流中一种特殊的、综合的活动形式，是商流和物流的紧密结合。配 送几乎包括了所有的物流功能要素，是物流的一个缩影或在某小范围内全部物流 活动完成将货物送达的目的。下面本文将介绍一下物流配送相关概念、我国物流 配送现状和发展趋势，以及本文理论研究部分车辆路径优化问题的研究现状。 2.1. 物流配送的概念 2.1.1. 物流配送的概念 物流配送业主要涉及的是对物流的管理，人们对物流存在不同的看法。按照 目前被普遍认同的美国物流管理协会在 1985 年所下的定义： “物流是以满足客户 的需求为目的的，为提高原料、在制品、制成品以及相关信息从供应到消费的流 动和储存的效率和效益而对其进行的计划、 执行的计划、 执行和控制的过程” 3。 相应的物流功能性活动则包括：需求预测、订单处理、客户服务、分销配送、物 料采购、存货控制、交通运输、仓库管理、工业包装、物资搬运、工厂和仓库或 配送中心的选址、零配件和技术服务支持、退货处理、废弃物和废弃商品的回收 处理等。 从企业的角度来看，物流是一个过程，这个过程是存货的流动和储存 的过程，是若干功能协调运作的过程，是提高企业运营效益的过程，因此物流也 是一个规划、管理和控制的过程，包括物流、信息流和现金流的过程。 配送的本义是运送、输送和交货。是指根据一定的用户需求，在物流据点内 进行分拣、配货等工作，并将配好的货物及时交给收货人的一个过程。2001年4 月，中国国家标准物流术语将配送定义为:“在经济合理区域范围内，根据 用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定 地点的物流活动”4。配送一方面在向客户送货的过程中有确定的组织和比较明 确的供货渠道，以及相关的约束制度；另一方面送货建立在备货和配货的基础之 上， 按照用户的要求进行组织和安排。 配送不是一种先进的物流方式和物流机制， 从物流功能或物流要素的角度来看， 配送是多项目、 多环节物流活动的有机结合， 既有货物运输，同时也包括集货、存储、分货、拣选、配装等活动。 7 2.1.2. 物流配送意义 配送是分货、配货、送货等活动的有机结合体，完善了输送及整个物流系统， 降低物流成本，提高经济效益。 1) 完善物流系统 采用配送方式从范围来说，将支线运输和小搬运统一起来，使整个物流输送 过程的运力得到合理运用， 优化和完善了整个物流系统， 进一步降低了物流成本。 2) 提高物流效益 采用配送方式，通过增加经济批量经济进货，又通过将各种商品用户集中一 起进行一次发货。同时用户只需向一处订货或者和一个进货单位联系就可以订购 到以往需要去很多地方才能够订到的货物，只需要组织对一个配送单位的接货便 可以代替现有的高频率接货，因而大大减少了客户的工作量和负担，提高物流经 济效益。 3) 通过集中库存使企业实现低库存或零库存 一方面，实现了高水平的物流配送之后，尤其是采取准时（just in time）配 送方式之后，生产企业完全依靠配送中心的准时配送而不需保持自己的库存，或 者， 只需保持少量保险储备而不必留有经常储备， 可以从库存的包袱中解脱出来， 同时解放出大量储备资金，从而改善财务状况；另一方面，实行集中库存，可以 利用规模经济的优势，使单位存货成本下降，同时总量远低于不实行集中库存时 各企业分散库存之总量，提高了社会经济效益。 4) 提高供应保证程度 生产企业自己保持库存，维持生产，供应保证程度很难提高(受库存费用的 制约)，采取配送方式，配送中心可以比任何单位企业的储备量更大，相对缩小 了中断供应、影响生产的风险，可以免去用户的货物短缺之忧。 2.1.3. 物流配送流程 对订单数据加以处理并经过拣货、出货的手续后便要着手进行配送的工作， 实际配送工作的进行完全仰赖事前排车计划的拟定，通常排车计划的拟定需在接 单后开始计划，所需的信息除了包含订单上的客户信息、货物信息、配送信息外 还需配送公司的人员、车辆等相关信息来进行配合排车计划的拟定，排车计划的 内容包括必须排定哪些订单可以同车配送、配送车辆的吨数(车型)等，再指派司 8 机进行配送的工作，一般而言在配送时主要所需决定的工作内容包括了以下几 项:(1)配送区域划分，(2)车辆安排，(3)每辆车负责的客户，(4)配送路径选择， (5)配送顺序决定，(6)车辆装载方式。在配送分区上目前的作法有定点定线、分 区、与不分区等作业方式，定点定线方式是先规划好固定的路线及配送顺序，而 分区的性质则是将配送区域划分但路线未固定，同车尽量不跨区配送，不分区则 是完全不限制区域排车纯粹以效益为考虑。在完成了车辆类型的安排与分区选择 的工作后，接着就是要进行车辆路径的指派与指派的顺序，配送计划中，车辆配 送路线安排的恰当与否，将直接影响运输的成本及服务的效率。运输配送主要以 下流程： 1) 物流配送中心根据客户的发货指令视库存情况做相应的配送处理。 2) 根据配送计划系统将自动地进行车辆、人员、 调配的出库处理。 3) 根据选好的因素由专人负责货物的调配处理，可分自动配货和人工配货， 目的是为了更高效的利用物流公司手头的资源。 4) 根据系统的安排结果按实际情况进行人工调整。 5) 在安排好后，系统将根据货物所放地点（库位）情况按物流公司自己设 定的优化原则打印出拣货清单。 6) 承运人凭拣货清单到仓库提货，仓库那头做相应的出库处理。 7) 装车完毕后，根据所送客户数打印出相应的送货单。 8) 车辆运输途中可通过gps车辆定位系统随时监控，并做到信息及时沟通。 9) 在货物到达目的地后，经受货方确认后，凭回单向物流配送中心确认。 10) 产生所有需要的统计分析数据和财务结算，并产生应收款与应付款。 图2.1 物流配送业务流程 （资料来源：本研究整理） 企 业企 业 配 送 中 心配 送 中 心 消 费 客 户消 费 客 户 订单订单 配 送 计 划 物 流 企 业 配 送 计 划 物 流 企 业 出货出货配送决策配送决策 卸货卸货 运 输运 输 装 货装 货 9 2.2. 物流信息系统 物流信息系统是指一个由人、计算机等组成的对物流信息进行收集、存储、 分析、处理、传递和使用的系统，是物流系统的组成部分之一，其作用是实现物 流过程中各环节的有机衔接与合作，实现物流活动的目标。物流信息系统就是为 了缩短从接受订货到发货的时间、提高搬运作业效率、提高运输效率、提高订单 处理的精度、防止发货，配送出现差错、调整需求和供给、要使接受订货和发出 订货更为省力，提高对客户的服务水平和降低总成本。物流合理化是物流管理追 求的总目标。物流合理化，它是对物流设备配置和物流活动组织进行调整改进， 实现物流系统整体优化的过程。它使物流设备配置和一切物流活动趋于合理，合 理具体表现为以尽可能的物流成本，获得尽可能高的服务水平。 物流信息系统的发展大致可以分为四个阶段： 1) 物流信息系统的雏形阶段 早期的物流信息系统只是一些简单的库存管理或运输管理，因此只能算是一 个雏形。 数据大量依靠人工输入， 速度慢， 准确率低， 决策分析理论也比较简单 。 2) 自动化设备的应用阶段 随着自动化设备的开发应用，使得物流信息系统的速度与准确率有了很大的 提高。引进了一些简易的决策支持系统，计算机系统对物流管理中的事务性工作 有了一定的智能决策能力，物流信息系统在物流管理中正式崭露头角。 3) 与其它信息系统的结合阶段 这一阶段的物流信息系统开始与其它信息系统结合，物流管理融入到了企业 甚至是全行业的管理中去。在生产型企业中，物流信息系统先后融入到了mrp、 mrpii、erp等系统中。在商业流通中，物流信息系统包含了pos、eos等系统。 这一阶段的物流信息系统发展较快，也确实给企业与社会带来了巨大的收益。 4) 电子商务下的物流信息系统 因特网技术的成熟为企业信息管理系统增加与客户或供应商实现信息共享 和直接的数据交换的能力，从而强化了企业间的联系，形成共同发展的生存链， 体现企业为达到生存竞争的供应链管理思想。 2.3. 配送车辆路径问题研究现状 车辆路径问题(vehicle routing problem，vrp)也有学者称之为车辆调度问题 (vehicle scheduling problem，vsp)。一般认为，不考虑时间要求，仅根据空间位 10 置安排线路时称为车辆路径问题，即vrp。考虑时间要求，安排线路时称车辆调 度问题，即vsp。有时间要求的车辆调度问题称为(vehicle routing problem with time window，vrptw)。由于国内外文献习惯采用vrp表述车辆路径与调度问 题，对vrp和vsp,本文也一律称之为vrp。 vrp最早是由dantzig和ramser于1959年提出的，提出后很快引起运筹学、应 用数学、组合数学、图论和网络分析、物流科技、计算机应用学科专家与运输计 划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿和研究热点问 题， 各学科的专家对该问题进行了大量的理论研究及试验分析， 取得了很大进展。 1962年，ballnski等人首提出了vrp的集分割，直接考虑可行解集合，在此基础上 进行优化，建立最简单的vrp模型。1964年clarke和wright提出一种对dantzig和 ramser方法进行改进的较有效的启发式算法clarke-wright节约算法。1991年， gendereau等人将禁忌搜索方法应用于vrp。该算法求解过程中的邻域，是通过 gem过程得到的。它针对vrp比较好的启发式算法，可以成功地应用于许多经典 的vrp。1996年，j.lawrence将遗传算法用于vrp的研究，并可有效求解带时间 窗口的vrp5。 m.l fisher于1995年对车辆路径问题作了总结，他把车辆路径问题的研究方 法归结为三个阶段6。20世纪60年代到70年代是第一个阶段，这个阶段主要是应 用一些简单的启发式方法来研究车辆路径问题，研究的重点主要局限于局部搜索 和交换技术；第二个阶段是20世纪70年代到80年代基于启发式方法的设计阶段， 这个阶段主要是利用不同于一般启发式方法的近似优化算法来求解车辆路径问 题。从实验的结果分析，这个阶段的求解效果明显优于第一阶段的简单启发式方 法；到了第三阶段，即20世纪80年代至今，研究的重点主要放在精确的优化算法 和新兴的人工智能算法，包括模拟退火算法、禁忌搜索算法、遗传算法和人工神 经元网络方法、蚁群算法、粒子群算法等。 国内对vrp的研究相对较少， 有关车辆路径问题的研究是在20世纪90年代 以后才逐渐兴起的。目前，国内对于复杂的车辆路径问题研究尚处于起步状态， 最近几年才陆续有一些相关的研究成果发表，如李军和郭耀煌用传统启发式算法 解决了一些相对简单的vrp问题， 如送货点比较少的容量约束、 时间窗约束vrp； 蔡延光用遗传算法、模拟退货算法等研究重载vrp，取得了一些成绩；谢秉磊、 郎茂祥等用遗传算法在容量约束和时间窗约束的vrp上做了一些工作。近年来， 我国理论界逐渐开始关注车辆路径问题的研究， 并已取得初步成果， 总体来说， 11 目前我国对车辆路径问题的理论仍需要进一步研究。 2.4. 我国物流配送现状和发展趋势 经过二十年的改革开放和经济的持续快速发展，我国目前己初步具备了发展 物流管理和配送技术的经济环境和市场条件。在中央和地方各级政府对物流发展 的大力推动和各类相关物流企业的不懈努力下，国内物流和配送服务得到了迅猛 发展，物流配送己经成为许多企业降低成本，提高竞争能力的重要手段。尽管目 前我国社会物流需求持续高速增长, 物流业增加值稳步上升, 物流服务在我国 仍占主导地位,但物流发展的总体水平还比较低, 问题比较突出, 主要体现在以 下几方面7: 1) 物流基础设施的“瓶颈”现象 2004年,测算的社会物流总额增长率如剔除价格因素，需要运输的实物量增 长20%左右。而实际完成的货运总量只增长了10.6%，与需求增幅之间至少存在9 个百分点的差距，而这又集中体现在铁路运力偏紧和沿海水路运力偏紧两个方 面。我国铁路总营业里程居世界第三，完成工作量居世界第二，每公里完成的货 运量居世界第一，但仍然不能满足社会物流需求。全国各地每天向铁路部门申请 车皮15万16万辆, 实际只能满足9万多辆的要求。同年, 煤炭、石油、焦炭、 金属矿石、钢铁及有色金属、水泥等大宗基础原材料资源总量高达52亿吨, 增幅 高达44.5%, 这些产品通过铁路运输不到16亿吨，只增长10.1%。其他部分只能通 过公路、水路运输解决。既增大了物流费用。也由于运输批量小、速度慢。加剧 了运力紧张的局面, 同时也造成产品滞压、库存增长的现象。港口接卸进口铁矿 石2亿吨，同比增长38%，由于疏运能力不配套形成了压库压港, 2004年7月份全 国主要港口铁矿石港存达到3400万吨，同比增长了146%，年末仍高达2400万吨。 2) 物流模式粗放, 供需不平衡依然存在。 企业物流运作模式受“大而全”、“小而全”的思想影响，习惯于自成体系、 自我服务，大量潜在的物流需求还不能转化为有效的市场需求；同时物流企业规 模小、实力弱、功能单一，服务质量和效率难以满足社会化物流的需要。这几年， 我国第三方物流发展很快，但真正能够提供一体化服务的企业还不多。物流社会 化、专业化、组织化程度低, 造成物流效率低下, 现有资源利用不足, 社会物流 依然粗放。我国物流粗放也明显地表现在物流市场不成熟。我国物流外包业务绝 大多数还只是集中在传统的运输、仓储业务, 一些新兴的物流业务外包比重很 低。物流企业一哄而上, 而且绝大多数都涌向运输领域, 造成我国运输能力, 特 12 别是公路运输能力极为分散, 恶性竞争, 导致运价过低, 超载超限现象严重。 3) 物流整合协调能力受到宏观环境的制约。 我国物流总体水平落后,存在物流技术与装备水平和物流综合协调能力这两 方面的约束。在科技进步和管理技术创新的驱动下, 物流产业经历了从量变到质 变的过程, 这种质的飞跃说明全球物流已经进入供应链时代, 包括美国、日本在 内的物流产业发达国家, 都寻找到了物流趋势的路径, 而精细物流、闭环物流, 对中国物流产业的发展产生了直接的影响。全球经济将进一步增长, 尤其是发展 中国家的优胜劣汰将不可抑制, 伴随着经济增长的全球物流将会得到极大发展, 发展中国家物流将迎来更大的发展机遇。根据国内外物流发展情况, 可以将21世 纪物流的发展趋向归纳为信息化、网络化、柔性化、标准化、社会化等。专家认 为: 面对世界物流发展趋势,中国物流应该把握供应链, 提升核心竞争力。供应 链是物流管理在深度和广度方面的扩展； 制造业企业、 物流企业都应重视供应链, 供应链取代物流, 不仅是理论的发展, 更是时代的变革。从而使物流速度加快, 准确率提高, 库存减少, 成本降低, 以此延伸和放大传统物流的功能, 为用户 提供多功能、一体化的综合性服务。在信息化时代，随着网络技术，电子商务、 交通运输、物流管理的现代化，现代物流企业配送系统也将不断的实现现代化管 理模式，从而出现了系统化、自动化、信息化、智能化的趋势。 2.5. 本章小结 本章在阐述物流配送概念、意义、流程和物流信息系统相关概念的基础上， 分析影响物流配送的因素，详细地介绍了物流配送路径问题的国内外研究现状， 最后指出了我国物流配送存在的主要问题，讨论了物流配送系统的最新发展趋 势。 13 第第3章 物流配送系统中的优化模型章 物流配送系统中的优化模型 在本论文所讨论的问题中，研究和设计物流配送决策支持系统，以实现运输 费用最小化， 其核心就是对货运运输的路线进行优化组合， 以达到运输路径最短， 总的运输时间最短，从而节省运输成本，降低运输费用。这实际上就是要对发往 确定地点的货物选择合适的车辆及运输路线，也就是物流配送中典型的车辆路径 问题。在解决实际问题时，我们将配送系统建成车辆路线问题的数学模型，然后 利用节约法得到满足约束条件的最优解。 3.1. 物流配送系统的优化目标 物流配送决策系统是对分散的客户需求进行整合，在满足客户需求的前提下 达到配送成本低，效益高。配送系统目标可概括为“三高一低一短”如图3.1。 图3.1 配送系统目标 1) 高配送效率 以最少的投入获得更多更好的产出是每个企业追求的目标。只有提高配送的 效率,才能提高配送系统的经济效益。所谓配送系统的效率是指“配送系统的产 出与投入之比”。配送系统的产出是配送服务,产出的多少可以用配送量来衡量 与评价；配送系统的投入是为提高配送能力所消耗的活劳动与物化劳动,体现为 配送成本。以最低的配送成本达到可以接受的服务水平,或以可以接受的配送成 本达到最高的服务水平,这都是企业所追求的目标。 2) 高客户服务水平 指在规定的时间内完好无损地把货物送到客户手中，做好各种服务工作，如 保质!保量为客户及时送货，为客户提供信息支持、技术咨询、技术支持和售后 服务等，因而需要做好配送工作的每个环节。 配送质量 配送成本 配送效率客户服务水平 高高 低 高高高 低 高 运输时间 短短 14 2 1 1,0,1, 2 . ii i wwi = = = 3) 高配送质量 配送质量与配送企业的管理水平和配送设施设备等密切相关，配送质量的高 低直接代表企业的形象和信誉，对一企业的市场占有率有很大影响。 4) 低配送成本 低配送成本是指配送的总成本最省。配送的各个环节都会发生配送费用，配 送环节所发生的配送费用的总和即这个配送系统的总费用。配送的总成本最省即 配送系统的总费用最小，从而要求整个配送系统优化，各个单元优化，并尽量利 用各种优化技术，充分利用和节约资源，提高工作效率，降低配送成本。 5) 运输时间最短 既要满足即时配送，即以某天的任务为目标，在充分掌握了这一天客户的需 求量、种类及要求到达时间的前提下，及时安排最优的配送路线并安排相应的配 送车辆实行配送，又要在最短的时间内完成任务并返回。 综合考虑以上五个目标，本文主要通过配送线路优化即车辆路径优化问题 (vrp)来实现低配送成本和缩短运输时间的目标。车辆路径问题(vehicle routing problem，vrp）一般定义为：对一系列装货点和（或）卸货点，组织适当的行车 线路，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、 交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标 （如里程最短、费用最少、时间尽量少、使用车辆数尽量少等）8。 本文目标是为了达到低配送成本和运输时间最短，这就构成了一个多目标问 题，对于多目标规划问题，本文将两个目标汇总成一个目标，只要在每个目标前 按配送中心和客户对各目标的重视程度加上不同的权重就可以实现，据此列出下 面的目标函数： 1122min()zw zw z=+ (3.1) 其中： ，1z:运输路径最短，2z：运输时间 最少，1w和2w分别表示两个目标的权值。若其中某一项的权重为1，另一项的 权重为0，则问题就转化为单目标规划问题，应该说，单目标规划问题是多目标 规划问题的特例。 15 3.2. 惩罚函数的确定 3.2.1. 时间窗概念 本论文讨论的物流配送决策系统优化目标之一是使运输时间最少，就是在车 辆路径问题加上时间窗约束，这是传统的车辆路径问题加上时间窗约束即 vrptw问题，因此在建立数学模型时对于违反时间约束的实施相应的惩罚函数。 时间窗约束可分为硬时间窗、软时间窗与混合型时间窗，三者分述如下: 1) 硬时间窗（hard time windows）: 配送车辆必须在客户指定的时间内（如图3.2（et，lt）时间段)将货物送到， 如果配送货物在客户要求的时间段以外，无论早到还是晚到，惩罚函数 ( )iitp 就会 是一个无穷大的正数。 2) 软时间窗(soft time windows) : 配送车辆无法在客户指定的时间内（如图3.3（et，lt）段）将货物送到， 根据客户早到和晚到的时间与客户要求的时间差距，给予一定罚金或其它惩罚来 补偿客户的损失。惩罚成本函数 ( )iitp的设定一般以配送中心与客户的商议确定， 以维护双方的利益。 图3.2 硬时间窗 图3.3 软时间窗 （资料来源：本研究整理） （资料来源：本研究整理） 3) 混合型时间窗(mixed time windows): 在实际情况许多情况下，物流配送多采用硬时间窗或软时间窗的结合。如图 3.4所示，如果货物在客户指定的时间段et，lt内送到，则不需惩罚，如果在a， et或lt，b内送达则要接受一定的惩罚成本 ( )iitp ，货物在其他时间段送到，视 为客户拒绝接受。 et lt t p(t) et lt t m p(t) 16 图3.4 混合时间窗 （资料来源：本研究整理） 3.2.2. 惩罚函数 带时间窗约束的车辆路径的优化，降低配送车辆的行驶距离，就是降低车辆 的行驶成本，同时降低时间窗约束的惩罚成本，从而降低物流配送的成本。配送 中心应该和客户商榷惩罚成本的计算方法，确定一个双方都愿意接受的较为合理 的规定，使配送中心不至于为了节省路线成本而降低服务品质，以提高配送中心 对订单的反应速度和客户的满意度。在本论文中对惩罚成本以函数方式表示，并 作如下假设: 1) 当车辆在顾客时闻窗内服务，配送中心不须支付任何惩罚成本. 2) 时间窗宽度越窄者，其惩罚成本的边际效应越高，突出时间的重要性。 3) 不论早到或晚到，只要违反时间窗就有惩罚成本值，随着违反程度增加， 惩罚成本呈线性增加，惩罚成本系数c1，c2是不为零的正常数。 4) 当超出一定的限制后，惩罚成本就是一个无穷大的正数，客户和配送中 心的信任关系将会动摇。 本论文参考实际情况，按顾客对物流中心违反时间窗约束规定时的接受程 度，决定采用混合型时间窗模型,理由如下: 1) 软时间窗的模型比硬时间窗的模型更符合实际作业的情况，顾客对于配 送车辆到达时间的期待及满意度可通过惩罚函数来表达。例如，当违反 时间窗约束程度越大，其惩罚值也相对越大，当配送车辆运达时间超过 顾客所能容忍的范围时，顾客将拒收货品或施以重罚，上述情形都可以 用适当的惩罚函数来表示。 2) 在实际情况中，物流中心的运输成本不只是实际距离上的成本，还包括 a et lt b t m p(t) 17 因提早到达，但顾客的卸货区容量有限或正被使用中，而必须等待的成 本。 3) 在物流配送中以硬时间窗模型设计车辆配送路线时，若顾客时间窗宽度 很窄，车队的规模又不大时，则可能无法得到可行解.此时，如果能使用 混合型时间窗模型，则至少可以获得一个可行解，据此用来指派配送车 辆，然后再做局部的调整。 4) 混合型时间窗模型可以提供额外的信息帮助决策者分析。例如，到底哪 些顾客无法在时间窗内完成服务，并进而寻