（应用数学专业论文）物流配送的优化模型.pdf

摘要 摘要 现代物流的理念和运作对众多物流企业产生了深远的影响，如何将物流、 信息流和资金流进行全面的整合与有效的控制，从而提升企业的竞争能力，实 现产品供应链的价值和运作的最优化，是第三方物流企业面临的重要任务。本 研究通过某第三方物流企业的信息管理系统的分析和规划，从中提出了该企业 运作的四阶段优化控制方法，这对于第三方物流企业的信息化建设具有一定的 使用价值。 我们在本研究中所讨论的物流企业主要是进行散装液体的物流，为环渤海 地区的一些企业提供相应的产品。这些液体一般属于危险品( 如化学品等) ，而 且对温度有严格要求，并且在保存和运输时间上均有一定的限制。为了保证准 时、安全、有效的优质物流服务和贸易咨询服务，该公司在已有的商品信息平 台基础上，准备构建高效、优化的电子商务信息管理系统。本研究主要关注该 信息管理系统中的决策控制策略与优化方法。 该公司的主要物流业务流程可以划分为四个阶段：阶段i 是订货运输，阶段 i i 是入库加工，阶段i i i 是配送加工，阶段是配送运输。阶段i 的结束时间是 阶段i i 的开始时间，产品的仓库储存时间，根据常规可以视为一个常数c ，于 是阶段i i 的结束时间加上c 就是阶段i i i 的开始时间，而阶段的开始时间是 阶段i i i 的结束时间。时间的控制来自于客户( 生产企业) 的需求计划的综合处 理。如何有效地控制各个阶段的开始时间与结束时间是保证准时( 最早时间) 供货，降低库存成本( 库存周期) ，以及尽早收取供货款和延迟支付订货款( 最 迟订货) 的重要问题。由于阶段i 和均属于运输控制问题，因而在本研究的 第二章我们将运用a o n 网络技术来讨论。阶段i i 和阶段i i i 是加工处理时间最 小化问题，所以我们将在第三章运用f l o w s h o p 调度论方法加以讨论。 关键词： 物流配送a o n 网络调度f l o w s h o p a b s t r a c t t h et h e o r ya n do p e r a t i o no fm o d e r nl o g i s t i c sh a v ee x e r t e dad e e pa n db o a r d i n f l u e n c eo nm o s to ft h el o g i s t i c s e n t e r p r i s e s h o wt oe f f e c t i v e l yi n t e g r a t et h e p h y s i c a l m a t e r i a l f l o w , i n f o r m a t i o nf l o w , a n dc a p i t a lf l o wt oe n h a n c et h e i r c o m p e t e n c ec a p a c i t ya n do p t i m i z et h e i rs u p p l yc h a i nh a sb e c o m em o r ea n dm o r e i m p o r t a n tf o rt h et h i r d - p a r t yl o g i s t i c se n t e r p r i s e s b ya n a l y z i n gat h i r d p a r t yl o g i s t i c s f i r m si n f o r m a t i o nm a n a g e m e n ts y s t e m ，t h i sp a p e rs u g g e s t saf o u r - s t a g e o p t i m a l c o n t r o lo ft h ef i r m s o p e r a t i o n ，w h i c hm u s th a ss o m ep r a c t i c a lv a l u ef o rs o m e t h i r d - p a r t yl o g i s t i c sf i r m si n f o r m a t i o n i z a t i o n t h ef i l mw et a l ka b o u ti nt h i sp a p e ri s m a i n l ye n g a g e di nl i q u i dc h e m i c a l m a t e r i a ld i s t r i b u t i o n ，w h i c hi sv e r yd a n g e r o u s ，a n dn e e ds t r i c tt e m p e r a t u r ec o n t r o l ， p r o p e rp r e s e r v a t i o n ，t i m e l yt r a n s p o r t a t i o n ，e t c i no r d e rt og u a r a n t e et i m e l y , s a f e ，a n d e f f e c t i v ed i s t r i b u t i o ns e r v i c ea n dt r a d ec o u n s e l i n g , b a s e do ni t sc u r r e n ti n f o r m a t i o n p l a t f o r m ，t h ef i r mi sp r e p a r i n gf o rc o n s t r u c t i n gan e we l e c t r i c a lb u s i n e s si n f o 加a t i o n m a n a g e m e n ts y s t e m t h i sp a p e rf o c u s e so nt h ed e c i s i o nc o n t r o l s t r a t e g ya n d o p t i m i z a t i o no ft h en e ws y s t e m t h ef i r m sm a i no p e r a t i o nc a nb ec l a s s i f i e di n t o4 s t a g e s ：s t a g eio r d e r i n g t r a n s p o r t a t i o n , s t a g e1 1w a r e h o u s ep r o c e s s i n g , s t a g ei i id i s t r i b u t i o np r o c e s s i n g , a n d s t a g ei vd i s t r i b u t i o nt r a n s p o r t a t i o n t h ec l o s et i m eo fs t a g eii st h es t a r tt i m eo f s t a g e i i ；a st h es t o r a g et i m ec a nb es e e na sac o n s t a n tb yc u s t o m ，t h es t a r tt i m eo fs t a g ei i i e q u a lt ot h ec l o s et i m eo fs t a g ei ip l u sc ；t h ec l o s et i m es t a g ei i ii sa ss a m ea ss t a g e i v ss t a r t t h et i m ec o n t r o lp r o b l e ma l ld e p e n d so nc l i e n t sd e m a n d p l a n i ti sv e r y i m p o r t a n tt oe f f e c t i v e l yc o n t r o lt h es t a r tt i m ea n dc l o s et i m eo fe v e r ys t a g ef o rt h e a s s u r a n c eo ft i m e l ys u p p l y , d e c r e a s i n gs t o r a g ec o s t s ，a n dg e t t i n gb a c kp a y m e n to f g o o d s t h es t a g eia n di vc a nb ea t t r i b u t e dt ot r a n s p o r t a t i o nc o n t r o lp r o b l e m s ow e d i s c u s st h e mw i t ha o n t h e o r yi nc h a p t e r2 t h es t a g ei ia n di i ib e l o n gt ot h ep r o b l e m o f p r o c e s s i n gt i m em i n i m i z a t i o n ，s ow ea n a l y z et h e mw i t hf l o w s h o ps c h e d u l et h e o r y i nc h a p t e r3 i i a b s t r c a t k e yw o r d s ：p h ) r s i c a ld i s t r i b u t i o n a o n s c h e d u l i n gf l o w - s h o p i i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的s s 届, j 本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：杠贿 姗年j 1 月7 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下： i 内部5 年( 最长5 年，可少于5 年) 秘密 k l o 年( 最长1 0 年，可少于1 0 年) 机密 k 2 0 年( 最长2 0 年，可少丁2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：社捅 矽孑年7 旧刁日 第一章物流配送理论 第一章物流配送理论 现代物流的理念和运作对众多物流企业产生了深远的影响，如何将物流、 信息流和资金流进行全面的整合与有效的控制，从而提升企业的竞争能力，实 现产品供应链的价值和运作的最优化，是第三方物流企业面临的重要任务。本 研究通过某第三方物流企业的信息管理系统的分析和规划，从中提出了该企业 运作的四阶段优化控制方法，这对于第三方物流企业的信息化建设具有一定的 使用价值。在本章中，我们首先介绍物流配送的一些基本理论，然后讨论该第 三方物流企业配送运输活动的特殊性及其处理方法。 1 1 1 配送的基本概念 第一节概述 在现代物流活动中，配送是其中一种较特殊的综合的活动形式，几乎包括 所有的物流功能要素，是物流的一个缩影或在某小范围内物流全部活动的体现。 一般的配送集装卸、包装、保管、配送运输于一身，通过一系列活动完成将货 物送达的目的。特殊的配送还要以加工活动为支撑，所以包括方面更广。配送 的主体活动是末端或支线运输及分拣配货，其中分拣配货是配送的独特要求， 也是配送中有特点的活动，以送货为目的的末端或支线运输则是最后实现配送 的主要手段。【l j 按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语，配 送的基本含义是在经济合理区域范围内，根据用户的要求，对物品进行拣选、 加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。配送的目 的在于最大限度地压缩流通时间、降低流通费用，提高客户服务水平，降低社 会的总成本，实现资源的最优配置。 配送起源于“送货上门 。2 0 世纪6 0 年代初期，生产企业或中转仓库根据 客户的要求，将货物准备地运送到客户手中这就是配送的“普通送货 。随 着客户对产品多样化的要求，在客户需要什么就送什么的前提下，原始的普通 送货开始转向分拣、配货、送货一体化，因此产生了配送。2 0 世纪8 0 年代后， 第一章物流配送理论 配送手段日益先进，配送区域进一步扩大，配送方式日趋多样化，配送开始追 求信息化、网络化、系统化、规模化和社会化。 1 1 2 配送的目标、特点和意义 配送作业的总体目标可以简单地概括为7 个适当，即在适当的时间、地点 和适当的条件下，将适当的产品以适当的成本和方式提供给适当的客户。配送 功能的七要素为货物、客户、运输工具、人员、路线、目的地和时间。 从配送的标准定义看出，配送的实质性活动不是一般的送货，而是高水平 的送货。所谓高水平的送货，即除了送货，还包括拣选、分货、包装、分割、 组配和配货等工作。备货、理货和送货是组成配送的三个基本环节。配送还是 一种专业化的分工方式。【2 】 配送作为一种新型的物流手段，伴随着生产的不断发展而日趋成熟。因此 无论企业还是社会都从这种新型的物流手段中获益： 配送完善和优化了物流系统； 配送提高了末端物流效益； 配送通过集中库存使企业实现低库存或零库存； 配送简化事务，方便客户； 配送提高了供应保证程度。 1 1 3 配送中心 在实际生活中，配送和其他经济活动一样，通常是由配送中心进行安排和 操作的。按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语 ， 配送中心是指从事配送业务的物流场所或组织，应基本符合下列要求： 主要为特定的客户服务； 配送功能完善； 完善的信息网络； 辐射范围小； 多品种、小批量； 以配送为主、储存为辅。 配送中心的主要包括以下七大功能： 2 第一章物流配送理论 备货功能； 储存功能； 配组功能： 分拣功能； 集散功能； 加工服务功能； 送货功能。 配送中心作业流程是指配送中心活动过程在运动时所形成的基本工作顺 序。配送中心的作业路程一般包括：进货专验收斗入库专存放专拣取专包装 专分类专出货j 检查专装货等活动。在这些企业活动执行过程中还会产生一 系列表单及信息，每一类作业活动都必须纳入相应的管理系统。 1 1 4 配送合理化 配送合理化与否是配送决策系统的重要内容。总体上说，判断配送合理化 要看是否有利于物流合理化，因为配送是物流的一个功能要素，是物流系统的 一个组成部分。所谓物流合理化，就是配送必须有利于物流合理。物流合理化 表现在：降低物流费用；减少物流损失；加快物流速度；发挥各种物流方式的 最优效果；有效衔接干线运输和末端；减少实际的物流中转次数。具体的判断 指标主要包括以下六个： 总库存指标； 资金占用指标； 供应保障能力指标； 资本和效益指标； 社会运力节约指标； 用户满意指标。 配送合理化可采取的做法包括以下几种： 推行一定综合程度的专业化配送； 推行加工配送； 推行共同配送； 实行送取结合： 第一章物流配送理论 推行准时配送系统； 推行即时配送； 推行配送中心的现代化管理。 配送需求计划简称为d r p 。d r p 是决定企业产品库存的要求水平、保证企 业产品的供应来满足客户需求的管理程序。它是流通领域中的一种物流技术， 主要解决分销物料的供应计划和调度问题，目的是使企业对订单和供货具有快 速反应和持续补充库存的能力。系统依托于因特网，将制造商与代理商有机地 联系在一起，可以自动处理制造商及其普遍全国各地的代理商的仓储管理、销 售管理和订购管理，达到既保证有效地满足市场需要，又使得配置费用最省的 目的。d r p 的应用是立足于企业的产品配送中心，满足配送中心的作业需要和 经济效益需要。配送中心运用d r p 后，根据客户订单需求情况按时送货，同时 根据企业产成品的库存情况组织成品的入库。【3 】 1 1 5 配送成本管理 配送成本是指企业的配送中心在进行分货、配货、送货过程中所发生的各 项费用总和，包括包装费用、装卸费用及有关工作人员的工资等。数学表达式 为： c = c l + g + c 3 其中，c l 表示分货成本，指货物分拣、储存与集货过程发生的成本；g 表示配 货成本，指货物分割、组配、搬运、包装、分类、集中过程发生的成本；g 表 示送货成本，指货物线路、短途运输、送货信息反馈等过程发生的成本。为了 控制配送成本，应从以下几个方面进行： 加强配送的计划性； 确定合理的配送路线、配车计划管理及车辆运行管理； 进行合理的车辆配载以提高装载率； 量力而行，建立计算机管理系统； 建立物流信息系统。 4 第一章物流配送理论 1 1 6 配送运营 配送是一项服务，而且是越来越被广泛接受的服务。配送服务是按用户的 要求，编制最佳的配送作业计划，运用合理的捡货策略，选择最优化的配送线 路，以合理的方式送交客户，实现商品最终配置的经济活动。7 个恰当是配送的 服务质量和客户的满意度，降低配送成本，还要建立具体指标，如快捷相应、 最低库存、整合运输、安全经济等。 进行配送服务之初，首先要分析配送对象的性质、状态及配送流程、工艺 特点、管理方法等，设计选择不同的配送模式。确定不同配送模式的特点是进 行配送服务的基础。 具体来说，一项完整的配送服务包括下面的三个步骤： ( 1 ) 选择配送模式 小件杂货配送： 金属材料配送； 燃料煤配送； 水泥配送； 燃料油配送； 木材配送； 平板玻璃配送； 化工产品配送； 食品配送； 家具及家庭用具配送。 ( 2 ) 制定配送表 ( 3 ) 优化配送路线 1 1 7 配送质量管理 配送质量是指反映配送活动中满足客户明确和隐含需要的能力的特性综 合。配送的功能表现在在正确的地方得到正确的商品，保证质量和准时。配送 活动有极强的服务性质，整个配送过程的质量目标，就是其服务质量。配送服 务质量的具体衡量目标是时间、成本、数量和质量。 配送服务质量管理的内容包括：交货时间、配送力 t - r _ 、紧急配送、夜间配 5 第一章物流配送理论 送及假日配送、司机服务态度、咨询提供服务等。 基于质量的“三性 广义性、时效性、相对性，配送服务质量管理的 基本管理的基本工作主要包括以下几方面。 加强配送服务全体职工的质量意识和质量管理水平，建立必要管理组织 和制度； 搞好配送服务质量管理的信息工作； 做好实施质量管理的基础工作； 并发差错预防体系。 配送服务质量因不同客户而要求各异，但持续改进是提高质量的唯一途径。 第二节配送与运输方案设计 1 2 1 配送运输的概念 配送运输是指需配送的货物使用汽车或其他运输工具从供应点送至顾客手 中的活动。其间可能是从工厂等生产地仓库直接送至客户，也可能通过批发商、 经销商或由配送中心、物流中心转送至客户手中。配送运输通常是一种短距离、 小批量、高频率的运输形式。如果单从运输的角度看，它是对干线运输的一种 补充和完善，属于末端运输、支线运输，以高质量的服务为目标，以尽可能满 足客户要求。从日本配送运输的实践来看，配送的有效距离最好在5 0 公里半径 以内，国内配送中心、物流中心，其配送经济里程大约在3 0 公里以内。 配送是物流中一种特殊的、综合的活动形式，是商流和物流的紧密结合。 配送几乎包括了所有的物流功能要素，是物流活动的一个缩影。特殊的配送还 要进行物流加工活动。配送目标是安全、准确、优质服务和较低的配送费用。 配送不是单纯的运输或送货，而是运输与其他活动的组合，除了各种运、送活 动外，还要从事大量的集货、分货、配货、配装等工作，是配与送的结合。 配送的线路类型主要有以下几种： 往复式行驶路线； 环形式行驶路线； 汇集式行驶路线。 依据现代物流发展的需要，结合我国配送运输发展的现状，主要有以下几 6 第一章物流配送理论 种配送模式： 自营配送模式； 合作配送模式； 市场配送模式 综合配送模式。 1 2 2 配送线路的优化计算 1 、配送线路优化的意义及原则 进行配送线路优化时，必须有明确的目标，遵循基本的原则。配送线路方 案目标的选择可以从以下几个方面来考虑： 配送效益最高或配送成本最低； 配送历程最短； 配送服务水准最优； 配送劳动的消耗最小。 2 、配送线路的优化计算 如上所述，在从货物的配送中心输送到货物配送目的地的过程中，由于配 送中心的数量和客户收获地点的数量不同，配送线路的优化计算方法也不同。 ( 1 ) 一对一配送 一对一配送就是有一个供应点到一个客户的配送，在这种配送运输模式中， 要求选择最短的配送线路，实现高效率的配送，达到快速、经济配送的经营目 的。因此，在这种情况下，问题就归结为“最短路问题”。 ( 2 ) 一对多配送 一对多配送是指有一个供应配送点往多个客户货物接受点的配送。这个配 送运输模式要求，同一线路上所有客户的需求量总和不大于一辆车的额定载重 量。其基本思路是：由一辆车载所有客户的货物，沿一条优选的线路，依次逐 一将货物送到各个客户的货物接收点，既保证客户按时送货又节约里程，节省 运输费用。解决这种模式的优化设计问题可以采用节约里程法。 近年来，由于小批量、多批次的及时配送方式的发展，运输费用正在逐年 提升，许多企业的运输已经超越了库存费用。选择有效的配送路线，已称为控 制物流成本的主要措施。现代企业已经普遍接受了这一观点，即有效的配送路 7 第一章物流配送理论 线实际上是在保证商品准时到达客户指定点的前提下，尽可能地减少运输的车 次和运输的总路程。在这种思想的指导下，节约算法已成为选择配送路线的主 要方法，并受到国内外物流界的青睐。 节约算法有两种基本途径可以实现，一种叫并行方式，另外一种叫串行方 式。【4 】这两种方式在初始化时是相同的，它们的区别在于如何处理回路的合并问 题。下面分别对两种方式的具体应用步骤进行介绍。 a 、并行方式 并行方式分三步完成： 第一步：形成一个初始解。 形成初始解时，需要满足所有顾客的需求，而且所有的约束条件，例如容 量的限制、车辆总量的限制等也得满足。初始解可以由具有运载限制的最近邻 点法求得。形成初始解之后，可以得到每个车辆的一个初始的运输方案， 瓦= o ，f ，0 ) ，k = 1 ，2 ，m ) ，f ， p i p n ，p 咒 ak 表示车辆的标号，f ，j 表示顾客的标号。 第二步：进行节约度计算。 如下图所示，假设p 为配送中心，a 和b 为客户接货点，各点相互的道路 距离分别用a 、b 和c 表示。比较两种运输路线方案：一是派两辆车分别为客户 往a 、b 点送货，总的运输里程为2 ( a + 6 ) ；二是将a 、b 两地的货物装在同一 辆车上，采用巡回配送的方式，总的运输里程为a + 6 + c 。若不考虑道路特殊情 况等因素的影响，第二种方式与第一种方式的路程差为2 ( a + b ) - ( a + b + c ) ，按 照三角原理可以看出，第二种方式比第一种方式节约的里程数为a + 6 一c 。节约 法就是按照以上原理对配送网络的运输路线进行优化计算的。在本例中，两种 方案相比，可得节约度为c 么= + 一。对于一般情况而言，节约度的 计算公式为：c ：f = c o + g 厂c ：f ，f ，_ ，= 1 ，2 ，z ，且f ，然后我们需要对计算结 果进行升序排列。 第一章物流配送理论 p a b b 图1 2 1 第三步：进行回路的合并。在并行方式中，采用的合并策略是最可行合并 原则。从升序排列的节约度序列中的最上面的值开始，执行下面步骤。对于一 个已知的g ，判断这两个关系到f ，歹的回路是否存在合并的可能性，如果一个 回路以( o ，j ) 开始，一个回路以( f ，0 ) 结束，则该回路可以合并，并进行下面的合 并操作：删除两个回路中的部分路径( o ，歹) 和( f ，0 ) ，然后引入新的连接( f ，j ) ，得 到新的回路( o ，f ，j f ，0 ) 。 b 、串行方式 串行方式的节约算法同样也由三个步骤完成。 第一步：形成一个初始解。 形成初始解时，在考虑了顾客的需求和约束条件都得到满足之后，就可以 得到相应的初始解。初始解也可以由具有运载限制的最近邻点法求解。形成初 始解后，同样得到每个车辆的一个初始运输方案，互= o ，f ，j ，0 ) ， k - 1 ，2 ，m ，f ，je p p e n ，p ，l 。尼表示车辆的标号，f ，j 表示顾客的标号。 第二步：进行节约度的计算。计算所有点对的节约度e ，： g = c o + g 厂c ：f ，i ，j = 1 ，2 ，刀，且f j 。 然后对计算结果进行升序排列。 第三步：这里的合并策略不再是前面并行方式的节约算法那样两个部分的 对接，而是将一个回路中的某一部分替代，实现总运输距离的下降。具体的处 理方法为：按顺序对每一个回路( o ，i _ ，0 ) 进行考虑，找到第一个节约度的 9 第一章物流配送理论 点g 或c ，并将另一个以( 后，o ) 结尾或者( o ，) 开始的一段路径合并到当前回 路中。把当前考虑的回路不断地进行上面的合并操作，直到所得可行的合并操 作都完成为止。此时，就得到用串行方式的节约算法计算的近似最优解。 节约法须考虑的因素和注意的事项包括： 适用于顾客需求稳定的配送中心； 各配送路线的负荷要尽量均衡； 要充分考虑道路运输状况； 预测需求的变化及发展趋势； 考虑交通的状况； 利用计算机软件求解优化。 ( 3 ) 多对多配送 多对多配送是指由多个供应点向多个客户的配送运输。在这种配送运输模 式中根据供与销是否平衡又分为以下两种： 供销平衡模式； 供销不平衡模式。 第三节特殊物流企业的配送与运输 我们在本研究中所讨论的物流企业主要是进行散装液体的物流，为环渤海地 区的一些企业提供相应的产品。这些液体一般属于危险品( 如化学品等) ，而且 对温度有严格要求，并且在保存和运输时间上均有一定的限制。为了保证准时、 安全、有效的优质物流服务和贸易咨询服务，该公司在已有的商品信息平台基 础上，准备构建高效、优化的电子商务信息管理系统。【5 】本研究下面主要关注该 信息管理系统中的决策控制策略与优化方法。 该公司的主要物流业务流程可以划分为四个阶段：阶段i 是订货运输，阶段 i i 是入库加工，阶段i i i 是配送加工，阶段是配送运输。阶段i 的结束时间是 阶段i i 的开始时间，产品的仓库储存时间，根据常规可以视为一个常数c ，于 是阶段i i 的结束时间加上c 就是阶段i i i 的开始时间，而阶段的开始时间是 阶段i i i 的结束时间。时间的控制来自于客户( 生产企业) 的需求计划的综合处 理。如何有效地控制各个阶段的开始时间与结束时间是保证准时( 最早时间) 1 0 第一章物流配送理论 供货，降低库存成本( 库存周期) ，以及尽早收取供货款和延迟支付订货款( 最 迟订货) 的重要问题。 由于阶段i 和均属于运输控制问题，因而本研究的下一章我们将运用a o n 网络技术来讨论。阶段i i 和阶段i i i 是加工处理时间最小化问题，所以我们在最 后一章将运用f l o w - s h o p 调度论方法加以讨论。 第二章配送运输与订货运输的优化模型 第二章配送运输与订货运输的优化模型 综合全部客户的需求信息，向客户提供准时( 最早时间) 的，安全的送达 服务，这样不仅满足了客户的需求而且可以尽早收到客户支付的货款。向供货 商订货的时间是阶段的开始时间( 由最早完成时间确定的) ，在根据阶段i i i 、 i i 和储存时间c ，从而得到阶段i i 的开始时间，该时间作为阶段i 的工期，在阶 段i 采用最迟完成时间调度，目的是降低库存周期，延迟支付订货款，从而降低 物流成本。 由于经营产品的特殊性，因而生产场所的分布和供应商的供货地点等都与 通常的运输问题大不相同。因此，运用a o n ( 工程) 网络技术建立配送运输的 最早时间调度模型和订货运输的最迟时间调度模型。在物流系统中，由于技术 过程的要求和实际问题的要求，我们可以假定活动在处理中不可中断，它的处 理时间是已知的。 研究工程在给定时间内完成活动，常常给定的是时间窗口，在这里不讨论 资源需求。首先，讨论活动时间的最大最小时间间隔( t i m el a g s ) ，这种约束来 自技术或组织上的要求。其次，考虑工程的节点活动网络( a c t i v i t y o n n o d e n e t w o r k ) 的设计，讨论时间约束问题。第三，处理时间工程调度( t e m p o r a lp r o j e c t s c h e d u l i n g ) ，包括求最短工程时间，活动的开始完成时间和工程的关键活动。 第一节最大最小时差 时间窗口，即 码，0 ( 即为最早和最晚开始时间) 或 墨+ 矿，s + 矿 区间长度为时差。 设工程有n 1 项实际活动，活动的执行不可中断，除此之外，引入虚活动o 和n + 1 ，他们表示工程的开始和结束。 设只为活动f 的处理时间( d u r a t i o n o rp r o c e s s i n gt i m e ) ，其中，e 0 = + 1 = 0 ， 只n ，进而，ks , 0 为活动i 的开始时间，其中s o ：= o ，足+ l 为工程周期( s t a r t t i m eo f a c t i v i t yf ) 。 1 2 第二章配送运输与订货运输的优化模型 通常用s s ( s t a r t t o s t a r t ) 关系定义活动间优先关系。已给定最小时差 矿乞来定义f ，的关系： s - s , 矿 ( 1 ) 即活动_ ，不能在f 开始矿个单位f 前处理。 活动f 活动 - _ 一号一 卜e 一 d ? n l 毛， 图2 1 1 若_ ，可以在f 刚完成便开始，则瑶。_ 只，矿= 霉，式( 1 ) 表示一个先后 约束；若j 可以在f 完成之前开始，则f ，j 可以交错开始；有0 。： 邑一s d 7 ( 2 ) 这里指开始不能迟于f 开始矿时间单位。 r e m a d k 2 在实际中，名，矿，矿通常假定为整数，时间度量以分，小时，天等 等。然而，所有讨论的内容可以由实数来代替而无困难。 假定最小最大时差为非负数并不失一般性。若有矿 o 。根据( 1 ) ， s i s j 曼d ， 这表示对于_ ，i 有正的最大时差( 比较( 2 ) ) 。同理，负的最大时差可以由 正的最小时差代替。 假设已经给出矿和矿矿，则对于f 于s 开始后，开始的时间窗口为 置+ 矿，s + 矿 ，其窗口长度为矿一矿o 。 若t 一墨o ，于是墨一舅o ，即f 不能在后开始。因此，矿：= o 或 1 4 第二章配送运输与订货运输的优化模型 矿：= o k 立。 若几个活动同时开始，如毛= & = = & ， 之 曰) 时间开始，则掮：= 墨。 r e m a r k s3 在实际中的时间约束问题可以借助最小、最大时差来表示，例如： f ，先后执行，没有延迟，即s 厂s = 弓，这个约束的保证可以引入 蝴r a i n _ 号，而且d 严：= 曰，若f ，j 同时开始，则令矿：= 矿：= o ； 若f 恰在乏。时开始，则令铲：= 伊- ，同理可以引入严格在某时 终止( 帮“= 伊= 一忍) ； 若f 最早在乏。开始，则最迟在r 乏。开始，则令啦：- 彳，伊：= r 。 由于时差是关联着两个活动的开始时间，因而称为s t a r t t o s t a r t 时差，类似 地，可以引入c o m p l e t i o n - t o - s t a r t ，s t a r t t o c o m p l e t i o n ，c o m p l e t i o n t o - c o m p l e t i o n 时差。这几种时差，可以容易地相互转换。作为一个例子，我们下面将c s 时差 转换为s s 时差，反过来也一样。 设船雩“和”矿为原来的时差s s ，而相对应的。矿和嚣矿为c s 的时差a 设c ：f s + 只为的完成时间。于是( 假定处理不可中断) ： 。d 尹s j c i s 。d 尹。 由于 8 d 尹s s j s 。”d 尹， 第二章配送运输与订货运输的优化模型 两边及中间减去只有下式： 。d 尹一ess j s i 一只s & d 一只， 即 & d 尹一e s j c j s & d 尹一只， 所以( 假定最小时差、最大时差是唯一的) ： i8 矿= 嚣矿一只 【嚣矿= ”矿一只 正如下文所示，s s 时差对应于工程网络中的弧的权，可以从权的符号容易 的得知对应的是最小还是最大时差：正弧权表示最小时差，负弧权表示最大时 荠。 第二节a o n 工程网络( 节点活动网络) 及时间工程调度的时间计算 我们在本节阐述如伺通过时差来为已给工程构造节点活动网络，简称a o n 网络，进而讨论网络的一些性质。 活动0 ，1 ，力+ 1 用网络节点0 ，1 ，咒+ 1 表示。这样，y ：= o 1 ，n + l ， 其中i 是工程中的活动，又是网络中的节点，因而y 不仅是活动集又是网络的节 点集。 对于f _ ，和已给时间窗口 o ，矿一矿 ，其中矿= n 穹“) ， 矿= 叩 矿 则可以引入弧 - 6 ，s s 一如j 墨一s 矿) 。 非负开始时间s i ( ie 矿) 可以看做a o n 网络节点的权。映射s ：v - 恐。满足 ( 3 ) 也称为网络上的势( p o t e n t i a l ) ( 墨为节点f 的势) 。 下面来看a o n 网络的些性质。从上述构造可知，a o n 网络是由工程唯一 确定的。通常正弧权对应最小时差，负弧权对应最大时差，零弧权对应最小或 最大时差。 a o n 网络一般含有回路，至少一条弧在回路中对应于最大时差( 3 - 期) ，然 而也有最大时差在回路之外。( 有的i 具有只= 碱+ 。时) 若， 0 ，在f ! l j j 的路径长为，上诱导一个最小时差矿：= ，；若， e e 、) 墨o ( i v ) s o = 0 ( 4 ) 称模型( 4 ) 为时间约束工程调度模型，该模型必有最优解s = ( & ，s ，最+ 。) ， 其中墨乞，i = o 1 ，刀+ 1 。 1 7 第二章配送运输与订货运输的优化模型 实际上，该模型的可行域品表示为一个凸多面体。对于v f 0 ，s o 可以 由s o 和r e m a r k s l 中推出。( i 的最小时差d 0 7 已知) 。即使不写出s o = 0 ， 对于调度s = ( s ) 训，若是时间可行，也认为s o = o 。由2 1 可知，时间通常在 实际中为整数，于是可以设f 乏。，视为时间区间【f ，t + l 】，这对应时间段f + 1 。 这样，用s 乏。替代墨0 ，问题( 4 ) 就化为整数线性规划f 哼p ，t + 0 ，f z ， 即( o ，1 2 ，刀+ 1 ) 对应 o ，l l w 1 ，2 u u 【，l + 1 ，n + 2 】_ 【o ，n + 2 】。 设品a ，由于活动工期，最小和最大时差是整数，因此所有弧的权 岛( y ) 都是整数，故总存在整数值时间最优调度s ( 在( 4 ) 中) ，在这 种情况下，纵然问题( 4 ) 的约束s 0 ( i v ) 也是可以用墨乞来代替的。 若s t 矽，则有如下定理： 定理3 2 2 工程有时间可行调度的充分必要条件是工程的a o n 网络不含 正长度回路。 证明可见b a r t u s c h ( 1 9 8 8 ) 。注意，在2 2 已验证正长度回路表示与时间约 束( 3 ) 相矛盾，即时间可行调度中排除正长度回路。在下文总假定a o n 网络问 题中不含正长度回路。 由于在配送规划中，活动的最早最迟开始时间是非常重要的，在此介绍这 些概念。设磷和墨为最早最迟开始时间，e c ：f 和e 为最早最迟完成时间， e s = ( 麟，硒，圾+ 。) 成为最早调度，即对v s s t ，磷s i ( i 矿) ，e s s t 。 当然砜= o 和哦+ 。为最短工程工期。在实际中，最大整数工程工期孑碱+ 。必 应满足，于是： 省舡期 l s s r 为最迟调度，其中+ l l s , s i ( i v ) 对所有s s r 成立。 第二章配送运输与订货运输的优化模型 由工程网络增加背向弧 ，具有权瓯“o = 一最+ l ，而得到时间调 度网络+ 。 构成工程开始为0 完成在刀+ l 间的最大时差碟l = 碱+ 。， 可以由最大工期碱+ ；隐含给出。e + = e u ) ，n + 是时间调度网络，而 e + 是+ 的弧集，在+ 中用略表示从f 到歹的最长路径长度或距离，其中当f = 时办= o 。 最长距离办( f ，歹y ) 是满足下式的最小值： d o 岛( o ，则在f ，开始之间有最小时差办( 可以诱导) ：若略 o ，则有一个最 大时差( 诱导) - d o ，( 根据2 1 中r e m a r k s l ，v i e v ，有从0 到f 和从f 到刀+ 1 的路径) 。因此，在网络+ 中任两个f ，- ，y 都有连接的路径。由于假定( + ) 不 含任何正长回路， 因而对所有f ，y 都有办三最+ 。， 另外， 三邑+ 。= 肿。d o ，+ 略+ 嘭卅l ，其中如，乃卅l o 。 显然，最早调度e s 是如下规划( 惟一) 最优解： n + l m i n 了s i r 一 f _ o 豇s ，- s , 岛( f ，p e + ) s o = 0 ( 7 ) 约束墨o ( i v ) 没出现是由于自动满足。类似地，最迟调度l s 是下面问题 1 9 第二章配送运输与订货运输的优化模型 的最优解： n + l m a x s i = 0 础s s 岛( e e + ) s o = 0 ( 8 ) 最早开始时间鼹，即从工程到活动f 开始的最小时差，等于+ 中0 到f 矿 的最长路径长( 从而可以保证其间所有活动可以完成) 。类似地最迟开始时间， 即为- d o 。，是从f 到。最长的路径的负值。( 负数最大值) ( 喀。 0 ，从各反向路 径中选择负数最大，从而保证工期，即最迟时间) 对( 7 ) 略加修改而得到的对偶问题是最长路径问题，先将式( 7 ) 化为： 肿1、 幽i = 0 1 州肼1 |( 9 )k y ， 旺l - 邑一1 s 岛( e + ) j 与( 7 ) 相比较，省略s o = 0 和用墨一瓯替代s ，于是( 9 ) 的对偶问题是： m a x 岛呜 珐h 。p r e d ( i ，一。p 斗l - i 赢n ；等 )批m ( f ) t l j ，一u 吼o ( f ，p 矿) ( 1 0 ) 其中p r e d ( i ) 和s u c c ( i ) 是n + 中i 的直接前继和直接后继集。设盯) f + 是 、 v ， e 上 最优的基本可行解。于是基本变量 ，( e e rc e + ) 对应于+ 的一个生成 ( 支撑) 树( 严格地讲，具有根为0 ，节点集y 和弧集e r ) ，该树含从根0 到i v 位于+ 中恰一条最长路只，i o 。 ，可以解释为弧 位于丁上，这样的r 是 不同路径的数目。对应于( 9 ) 的最优解( e s i ) 彬，最优化条件 第二章配送运输与订货运输的优化模型 鹤一毯= 岛( ee 7 ) 成立。从这些方程和e s o = o 可以得出 巩= 磊，h e y ，磊o 。 由于时间调度网络+ 不含有正长度回路，因而模型( 9 ) 和( 1 0 ) 的最优 解也是网络中节点0 至n + l 的最长路径，因此为了求出e s , 和l s , ( v i v ) 均 可运用修正标号算法( 1 a b e l c o r r e c t i n ga l g o r i t h m ) ，