（计算机软件与理论专业论文）基于deds派送调度问题的研究.pdf

太原理_ l 大学硕士研究生学位论文 基于d e d $ 派送调度问题的研究 摘要 派送调度问题是物流管理领域中一个重要的课题，是大型 超市集团、大型零售连锁店、物流派送中心及工业生产企业共 同存在的问题。随着跨地区、跨地域的经济活动日益加强，迫 切要求解决物资流通当中合理调度运输工具的问题来有效实现 企业生产计划、减少物资库存，从而提高工商企业的生产效率。 目前对于派送调度问题的研究主要集中在对运输工具的配置和 静态调度领域，这些研究工作已经取得了丰富的成果，并且研 。 究结果也主要应用于决策和管理方面。但是对于运输工具运行 情况变化和派送任务动态产生和调整关注较少，同时，在线派 送调度的计算机系统产品也较少。针对这一情况，文章运用 d e d s ( d i s c r e t ee v e n td y n a m i c s y s t e m s ) 理论对派送 过程中对运输工具动态调度进行了分析和研究，同时也给出了 一个简单的计算机在线派送调度系统的系统结构。 文章在描述派送调度问题的基础上，分析问题的性质并给 出了派送调度问题的数学定义，详细讨论了派送调度问题的两 i 太原理上大学硕士研究生学位论文 个主要特征：动态性和离散性。为了精确表示派送调度问题和 实现对派送任务进行连续调度和动态调度，文章分别建立了派 送调度问题的静态模型和系统模型；并且，提出用闭环覆盖来 确定车辆运行过程中行驶的方向及运输成本，详细讨论了闭环 覆盖与派送调度问题之间的关系；最后，给出派送调度问题的 求解算法以及简单的系统模拟结果。 在实际应用中文章解决了在固定地域范围内对运输工具的 连续调度和动态调度问题。通过对系统的简单模拟验证了文章 提出的理论和方法的可行性。 最后，文章给出用以上理论和算法解决派送调度问题的结 论与展望。 文章设计派送调度系统的系统架构以及用图论工具对车辆 运输方式的表示可以方便地对固定地域范围内派送调度问题进 行描述，从而有利于用计算机程序处理派送调度问题。通过对 派送调度问题的详细研究，文章为设计派送调度系统提供一定 的理论准备和设计指导。 关键字：派送，调度，闭环覆盖，d e d s ，物流管理 i i 太原理工大学硕士研究生学位论文 t h er e s e a r c ho fa p p o i n tj o b s c h e d u l i n gp r o b l e mb a s e d0 n d i s c r e t ee v e n td y n a m i cs y s t e m s a b s t r a c t t h e a p p o i n tj o bs c h e d u l i n gp r o b l e mi sa ni m p o r t a n tt a s ko f t h ef l o w s h o ps c h e d u l i n gp r o b l e m i te x i s t si nt h e g r e a t s u p e r m a r k e t s 、t h eg r e a tr e t a i lm u l t i p l es h o p sa n dt h ec e n t e r so f f l o w s h o p - w i t he n h a n c i n go ft h ee c o n o m i ca c t i v e s p a n n i n g d i f f e r e n td o m a i n i n c r e a s i n g l y w ep r e s sf o r s e t t l i n gs c h e d u l i n g p r o b l e m st oc a r r yo u tp r o d u c ts c h e m ea n dr e d u c es t o r a g e ，t h e r e b y w ec a ni n c r e a s ee n t e r p r i s e s e f f i c i e n c y b u ta tp r e s e n tr e s e a r c ho n t h ea p p o i n tj o bs c h e d u l i n gp r o b l e mf o c u s e s i nt h ed o m a i n so f c o n f i g u r et r a f f i ct o o l s a n ds t a t i cs c h e d u l i n g t h e s er e s e a r c h e sh a v e a l r e a d yg a i n e dg r e a tf r u i t a n dt h e i rr e s u l t s h a v eb e e nu s e di n i t t 太原理三盔堂堡主婴窒竺堂堡笙塾 一 d e c i s i 。n - m a l ( i 睁a n da d m i n i s t e r d o m a i nm 。s t i y b u t t h e r ei 8al i t t l e 批n t i o n t oc h 狮g eo f t r a f f i cr u n n i n gc o n d i t i o na n d t a 8 k 8d y n 锄1 0 c r c a t i n ga n d t h e r ea r ef e w o n l i n ea p p o i n t j o bs c h e d u l i n g 。o m p u t e r s y s t e m sp r o d u c t s t o t h i sp r o b l e m ，t r a f f i ct o o l sd y n a m i c s c h 。d u l i r i g i s a l l a l y z e d a n ds t u d i e du s i n gd e d s ( d i s c r e t e e v e n td y n a 叫c s v s t e m ) t h e o r ya n d as i m p l es y s t e mf r a m e w o r k o fo n l i n ea p p o i n t j o bs c h e d u l i n gc o m p u t e rs y s t e m i sp r o v i d e di nt h i sa r t i c l e t h i sa r t i c l ea n a l y s e st h ea p p o i n tj o bs c h e d u l i n g p r o b l e m p r o p e r t i e s a n dp r o v i d e st h em a t h e m a t i c d e f i n i t i o nb a s e do nt h e d e s c r i p t i o no f t h ea p p o i n t j o bs c h e d u l i n g p r o b l e m t h ea r t i c l e6 n d m a tt h ea p p o i n tj o bs c h e d u l i n g p r o b l e mh a st w om a i na t t r i b u t i o n ： d v n 锄i ca n dd i s c r e t e i no r d e r t oe x p r e s st h ep r o b l e mc o m p l e t e l y a n dc a r r y o u ts c h e d u l i n gd y n a m i c a n dc o n t i n u a l l y t h i sa r t i c l e e s t a b l i s ha p p o i n ts c h e d u l i n gp r o b l e m s s t a t i cm o d e la n ds y s t 。m m o d es e p 础l y a n d t h ec l o s e dl o o pi sp r o v i d e di nt h ea r t i c l e ，i t i su s e dt 0c 【e c i d e t h er u n n i n gd i r e c t i o na n dt r a n s p o r t c o s to ft h e v e h i c l e sw h e n t h e ya r et a k i n g o nt h ea p p o i n tt a s k s a n d t h i sa r t i c l e i i s c u s s e st h er e l a t i o nb e t w e e n t h ea p p o i n tj o bs c h e d u l i n g p r o b l e m l n d t h ec 1 0 s e dl o o pp a r t i c u l a r l y a t l a s tt h i s a r t i c l e p r o v i d e d i v 太原理工人学硕十研究生学位论文 s c h e d u l i n ga l g o r i t h m sa n ds y s t e m ss i m u l a t i o nr e s u l t s o n p r a c t i c ea s p e c t ，t h i sa r t i c l es o l v e st h ep r o b l e mo ft r a f f i c t o o l s r u n n i n g a n d d y n a m i cs c h e d u l i n gp r o b l e m i n i m m o b i l i t y d o m a i na n dv a l i d a t e sf e a s i b i l i t yo ft h et h e o r ya n dm e t h o d p r o v i d e d i nt h ea r t i c l e a tt h ee n do ft h i sa r t i c l es o m eu s e f u lc o n c l u s i o n sa n do t h e r e x p e c t su s i n gt h e s et h e o r ya n da l g o r i t h mt os o l v e a p p o i n tj o b s c h e d u l i n g p r o b l e ma r e g i v e n t h ef r a m e w o r ko f a p p o i n tj o bs c h e d u l i n gc o m p u t e rs y s t e m s i nt h i sa r t i c l ea n dt h ee x p r e s so fm a n n e ro fv e h i c l e r t m n i n gc a n d e s c r i b ea p p o i n tj o bs c h e d u l i n gp r o b l e m si n i m m o b i l i t yd o m a i n e a s i l y , s ot h a tw ec a ns e t t l ea p p o i n tj o bs c h e d u l i n gp r o b l e m sb y p r o g r a m s a f t e rr e s e a r c h i n go na p p o i n tj o bs c h e d u l i n gp r o b l e m s t h i sa r t i c l e p r o v i d e st h e o r y b a s ea n dg u i d a n c eo f s y s t e m sd e s i g n k e yw o r d s ：a p p o i n tj o b ，s c h e d u l i n g ，t h ec l o s el o o p ，d e d s ， f l o w s h o ps c h e d u l i n g v 太原理工大学硕士研究生学位论文 第一章绪论 1 1 派送调度问题概述 1 1 1 派送调度问题的概念 派送调度问题就是在一定地域内多个派送网点在物资流通过程中合 理调度和安排运输工具的运行方式来达到某一个企业或客户感兴趣的目 标( 如：运输成本最小、运输时间最短等) 。解决问题目的是为了合理地 利用交通运输工具、提高企业的经济效益。 派送调度问题实际上是属于物流调度问题( f l o ws h o p s c h e d u l i n g p r o b l e m ，f s p ) ，它是具有更严格条件的作业调度问题( j o bs h o ps c h e d u l i n g p r o b l e m ，j s p ) 的一个特例【1 l 。派送调度问题是大型超市集团、大型零售 连锁店、物流中心及工业生产企业共同存在的问题，它与企业的库存管理 系统紧密联系，是工商企业管理领域中研究的重要课题。 1 1 2 派送调度问题的发展 对于派送问题的提出可以追溯到第二次世界大战时美军对其后勤补 给线问题的研究。经济活动的加强增大了地区之间及地区内部物资流通的 数量和规模，为了降低运输成本、有效完成企业的生产计划、减少物资的 库存积压派送问题在物流管理系统中逐渐被提出并且为人们所重视。其涉 及的内容也从原来的资源配置( 如：运输工具的数量、仓库的选址、物 资库存数量) 延伸到对运输工具的运行方式合理安排和调度以及在无人车 太原理工大学硕士研究生学位论文 间里安排和调度工件的加工工序等方面。1 。在实际应用方面在应用方面国 外有代表性的系统是波音公司的物资流通管理系统、国内是浙江大学用遗 传算法开发的f m s ( f l e x i b l em a n u f a c t u r i n gs y s t e m s ) 及8 6 3 计划c i m s 主题课题项目，等等。1 。 1 1 3 派送问题研究的内容及方法 研究派送问题一般来讲要考虑两个方面的内容：一方面在满足运输 任务的要求条件下使得运输工具的配置更加合理：另一方面是在给定运输 工具配置的条件下，如何有效调度运输工具的运行方式来提高运输工具的 利用率，或者提高货物的运输量、缩短货物的运输时间等。这两个方面的 内容既相联系有相区别，运输工具的合理配置是有效调度的前提和基础， 只有运输工具的合理配置才可能对运输工具进行有效调度；而只有有效调 度才能体现运输工具的合理配置。 运输工具的合理或最佳配置受到多方面因素的影响，如：货物的地 域分布、运输货物量的多少、货物种类及不同种类货物的单位运输成本等 因素。运输工具配置要达到的目标也可能是多方面的，如：运输成本最 小、货物的运输响应时间最小、最大的运输能力等单个目标或多个目标的 组合。因此，运输工具的配置问题实际上是在一系列约束条件下的一个单、 多目标规划问题。对于单、多目标规划问题的主要研究与解决方法是单纯 形法。当然，还有其他方法，如：7 0 年代前苏联数学家哈奇杨提出的椭 球算法、贝尔实验室印度人卡玛卡提出的投影算法嘲。一般来讲，单、多 目标规划问题的解是多条曲线、曲面、体的交点或交面。 因此，运输工具的配置问题实际上属于一种策略问题，它与我们常常 提到的库存管理系统的库存量相类似。对于鳃决运输工具配置问题的一般 方法是：首先，根据实际要求写出表示问题的目标函数，并在分析实际限 2 太原理工大学硕士研究生学位论文 制条件基础上写出目标函数的约束条件；其次，对目标函数的约束条件进 行化简；最后，在化简的约束条件下求目标函数的解。一般来讲，对于单 目标规划问题，是求目标函数的最大或最小值，而对于多目标规划问题， 要在多个目标函数的最值之间寻求一个平衡8 。9 1 。 运输工具的调度问题是运输工具有一定的配置数量的条件下如何有 效地使用运输工具。根据运输工具当前的运行情况和当前派送任务的要求 和数量，合理地调度运输工具的运行方式使运输工具的运行在完成运输任 务前提条件下达到某一或多个目标。由此我们可以看出运输工具的调度问 题也属于一个规划问题。但是，这种规划问题要体现运输工具运行状况和 派送任务的动态特征，要根据当前运输工具的运输状态和派送任务的要求 及派送任务的变化合理地、动态地调度运输工具的运行方式，并且这类规 划问题的目标函数和约束条件的取值是整数，如：运输工具的数量、派送 任务的数量等等【4 1 0 。1 引。 运输工具调度问题的解实际上是派送任务在各运输工具之间的分配 和排列。因此，对问题的求解过程是在一个解集合里搜索可行解或最优解 的过程。 由于运输工具的运输规则是根据实际需求人为地规定出来，加之运输 工具的运行状态和派送任务随时问的推移而发生变化，因此，从系统的角 度来看运输工具的调度问题又属于离散事件动态系统( d i s c r e t ee v e n t d y n a m i cs y s t e m s ，简称d e d s ) 3 1 。关于离散事件动态系统我们将在以后 的章节旱进一步进行讨论。 对于与派送问题有关的两个方面的内容，文章只研究问题的第二个方 面。我们假定对运输工具己经进行了合理配置的前提条件下，如何根据当 前运输工具的运行状态和派送任务的变化来合理地分配任务及调度运输 工具运行，使得完成派送任务的整个运输过程达到某一个既定的目标。 3 太原理工大学硕士研究生学位论文 1 1 4 问题的研究动态 派送调度问题的研究难度较大，这不仅是因为问题本身是一个n p 问 题，而且因为派送调度问题又有离散性、动态性、多机性。因此，派送调 度问题又属于离散事件动态系统( d i s c r e t e e v e n td y n a m i c s y s t e m ， d e d s) 的范畴2 4 】。对于派送调度问题的研究将会对n p 问题的研究和 d e d s 的应用领域产生一定的影响 2 “ 研究f s p 或j s p 的派别较多。尽管此类问题的研究难度较大，但是对 他们的研究不断深入，同时也产生了一些学术流派。如果我们按学者们研 究所遵循的准则来分类，则可分为三类：一类是相对派别，一类是绝对 派别，另一类是相容派别口“】。相对派别的研究准则是：既然此类问题 是np 问题，所以，不求问题的最优解而是求问题的次优解或相对最优解。 此类研究常常是将问题的求解限制在一个给定的时空范围里或一个给定 的条件下，人为控制或解除问题的复杂性。其典型代表是启发式算法，如 清华大学、南开大学提出一些jsp 启发式算法。绝对派别的研究准则是： 既然此类问题是一个np 问题就不能用传统的方法去解决，要想解决此类 问题就要求打破传统的表示方法建立新的时空模型来对问题进行求解。这 种研究试图打破传统的思维方法来研究任务调度问题。显然，这种研究的 目标是求得问题的最优解。如清华大学提出的状态空间表示法。但是，这 种研究还停留在概念，未进入实质性研究。相容派别的研究准则是：在模 型上延用传统的表示模式，在方法上采用现代先进的计算手段，来求得问 题的最优解。这一派别研究的实质是借助现代先进的计算手段来消除问题 的复杂度。典型代表有基于神经网络的j s p 和基于遗传算法的j s p 。如北 京航空航天大学提出的“神经网络作业调度”、浙江大学的纪树新等开发 的基于遗传算法的车间作业调度系统。 4 太原理t 大学硕士研究生学位论文 而对于派送问题的研究主要集中在管理学的领域里，应用运筹学的方 法和工具来解决物流系统资源合理配置和资源的有效使用问题。在资源的 合理配置方面运用数学规划的方法和手段，资源的有效使用方面主要是对 资源的运行进行静态调度。假设在资源合理配置的情况下，派送的调度问 题在本质上属于一类特殊的作业调度问题。因此，用传统的方法将资源的 调度问题规约经典的图论问题( 如：旅行商问题，t s p ) ，这样就不能反 映问题的一些特征：动态性、离散性等。 要反映派送调度问题的动态性、离散性等特性就要求用新的方法和手 段对问题进行表示，建立新的系统模型来反映这些特性。通过分析派送调 度问题的特性，我们可以看出派送调度系统本质上属于离散事件动态系统 的范畴。 1 2d e d s 概述 1 2 1d e d $ 概念 严格地讲，对于离散事件动态系统，至今还没有一个具有概括性和普 遍适应性并以至被认同的定义。大致来讲，d e d s 是由离散事件驱动，并 由离散事件按照一定的运行规则互相作用，导致状态演化的一类动态系 统。这个定义显示出d e d s 具有两个特点：第一，d e d s 的系统属性表 现为由离散事件驱动，而这正是其取名为离散事件动态系统的原因所在； 第二，d e d s 人造属性表现为基于人为的运行规则，因此，d e d s 覆盖了 一大批高技术的人造系统3 5 。 1 2 2d e d s 研究背景 5 太原理工大学硕士研究生学位论文 对离散事件动态系统的研究追溯到对排队现象和排队网络的研究。从 现今的观点来看，排队理论、网络分析、计划评审等方法所面对的研究对 象都可归入d e d s 的范畴。近年来d e d s 受到人们的充分重视，并被认为是 系统与控制理论领域的一个前沿方向，一个重要的原因是当今一大批高新 技术发展和推动的结果。 现今对离散事件动态系统研究的兴起出现在2 0 世纪8 0 年代，那个 时期，随着信息处理技术、计算机技术和机器人技术的发展和完善和广泛 的应用，在通信、制造、交通管理、军事指挥等领域相继出现了一批反映 技术发展方向的人造系统，其典型的例子如柔性生产线或装配线、大规模 计算机和通信网络、空中或机场管理系统、军事指挥系统的c “等。 从理论方面讲对d e d s 研究的主要方向有：性能层次的建模与分析方 法排队网络方法( 包括j a c k s o n 排队网络f o r k j o i n 网络等) 、代 数层次的建模与分析极大代数方法、逻辑层次的建模与分析方法 佩特里网方法和自动机形式语言方法。”。j “ 对于d e d s 系统的调度问题主要的解决方法主要有分支界定法、模拟 退火法、特别是遗传算法理论的成熟使得解决d e d s 系统的调度问题有一 个更加强有力的工具。 1 3 文章的研究目的与意义 随着社会的进步与经济的繁荣，物资的流通数量与规模逐日增加。降 低物资的运输成本、缩短物资的流通周期对于工商企业提高企业的经济效 益有着重要的作用。同时随着电子商务深入发展和广泛应用，人们对物资 派送请求的数量和派送的地域范围不断增长和扩大。如何根据物资派送请 6 太原理工大学硕士研究生学位论文 求的实时数量、范围和运输工具的实际运行情况来动态地安排派送任务执 行将影响工业企业的生产效率或商业企业的商品的销售数量。 为了满足物流管理中对运输任务的合理调度及物资派送请求的动态 产生，文章在详细分析派送调度问题的基础上设计出一个在线派送调度计 算机系统的系统结构，并且讨论了系统的工作流程从而实现对派送任务的 动态调度。同时，文章也对系统进行了简单的系统模拟。为了满足实现动 态调度的要求文章对派送问题的特征进行了较详细的分析与讨论，并且为 调度算法提；出了一些理论准备及与派送调度问题之间的转化。为此文章 做了以下工作： 第二章对派送调度问题进行了一般性的描述，在此基础上给出了派 送调度问题的数学定义并且在分析派送调度问题特征的基础上，建立了派 送调度问题的系统模型。派送调度问题的系统模型主要体现了问题的动态 性和离散性的特征。通过缓冲由静态调度算法产生的调度结果，系统可以 对派送任务实现连续调度和动态调度。 第三章根据问题的定义为派送调度问题建立一个静态的数学表达， 使得对派送调度问题的研究有在一个精确的依据。 第四章中提出了闭环覆盖概念作为调度算法的理论准备。作为调度算 法的理论准备，闭环覆盖用图论的工具对派送调度问题中车辆为完成派送 任务的运行方式进行描述。 第五章是关于调度算法的选择和实现，在分析分支定界算法和贪婪算 法的特征和算法的适用范围的基础上，文章采用分支定界算法和贪婪算法 实现对派送任务的调度。 最后，通过对系统的模拟，文章说明基于d e d s 的原理对派送调度问 题进行建模和闭环覆盖在解决派送调度问题是可行的。 综上所述，文章为派送调度问题分别建立了静态模型和系统动态模型 7 太原理上大学硕士研究生学位论文 以及用图论工具对车辆运输方式的表示可以方便地对固定地域范围内派 送调度问题进行描述，从而有利于用计算机程序处理派送调度问题。通过 对派送调度问题的详细研究，文章为设计派送调度系统提供一定的理论准 备和设计指导。 8 太原理t 大学硕士研究生学位论文 第二章问题的系统模型 随着电子商务在人们只常生活和企业之间商务活动广泛应用，社会上 的物资流通数量和流通范围不断扩大，并且对于物资的派送请求更加呈现 不确定性和随机性。为了赢得更多的客户定单，企业必须提高派送任务的 执行效率，劳且根据派送请求的实时情况改变物资派送方案。物资流通规 模和数量的不断增长要求对派送任务的执行提出更加有效管理方法和管 理手段。为此，在分析派送调度问题性质的基础上本章将重点讨论如何搭 建一套在线派送调度计算机系统，并且分析其工作流程和系统的体系结 构。 2 1 派送调度问题的定义 首先，我们对派送问题进行一般描述并给出问题的定义。 2 1 1 派送调度问题的一般描述 假设在一个给定的地域里有n 1 个网点( 其中n 1 兰2 ) ，在n ，个网点中 任意两点i ，j 之间存在通路，即这n 。个网点组成一个全连通图。各网点 之间都可能随机产生货物运输的要求，并且货物运输要求可以是双向的， 即可以从i 点到j 点运货也可以从j 点到i 点运货。各网点之间的权代表 诸如：运输成本、行驶路程、需要的运输时间等。 货物运输量可假设为k ( k 兰1 ) 单位，在不失一般性的情况下可设每 9 太原理工大学硕士研究生学位论文 个单位是运输工具载重量。如：网点i 向网点j 运输m 单位的货物，则 表示运输工具需要承担m 次的运输任务。 在n 1 个网点以外，有一点a 为车队的位置。其中，a 点与n 1 各个网 点也组成一个全连通图，即从a 点出发可以到达n 1 个网点中的任意一点。 对于车队位置a 点，没有货物的输出也没有货物的输入，即a 点到i 点 ( i e n l ) 的运输量k = 0 、或i 点( i e n l ) 到a 点的运输量k = 0 。 车队有n 台车辆，假设它们的载重量相等并且为1 个运输单位。车队 的各个车辆从车队位置出发，在完成运输任务后最终要回到车队的位置。 派送调度问题是在各个网点随机地产生运输量为k 的派送要求时，如 何将这些派送要求在各个车辆之间分配，并且，安排每个车辆的运输次序， 使得整个运输过程达到某一目标，如运输成本最小、最短的运输响应时间 等。由此，我们可以看出派送的一次调度可演化为旅行商问题( t s p ) 或 中国邮政问题( c p p ) 。 2 1 2 派送调度问题的定义 定义1 - 1 派送就是利用运输工具对货物在原点和目的点的运输过 程。 从以上对派送的定义我们可以看到派送具有动态性的特点，派送任务 通过创建申请运输工具、通过执行获取运输工具、通过睡眠等待运输工具、 通过消亡释放运输工具。 派送请求与派送是两个不同的概念，派送请求可以用一个三元组( 0 【， p ，m ) 来表示，其中a ，p 分别表示请求的源点和目的点，m 表示货物 的量。派送请求是一个静态的概念，而派送是一个动态的概念，表示为满 足一系列派送请求进行的货物运输过程。 定义1 - 2 派送调度就是对派送任务在各运输工具之间合理的分配和 1 0 太原理t 大学硕士研究生学位论文 有效的排序使得某一个目标函数最小。 从派送调度的定义，我们可以看出派送调度具有极值性的，派送任务 不是简单的在各个运输工具之间的分配与排序，而是解的目标值最小化。 定义1 3 派送调度的基本限制条件 一次派送只能由一辆运输工具单独完成，即一次派送任务 不可由多个运输工具合作完成。 派送任务必须一次性完成，也就是：当某一派送任务开始 执行后，该任务不重新参加调度。承担该派送任务的运输工具在 未到达目的地时不再承担其它派送任务。 在同一时刻一辆运输工具只承担k 项派送任务，其中k 小于等于1 除了派送调度的基本限制条件以外，派送调度还有其他限制条件。派 送调度限制条件的数目和内容随派送的需求及运输工具特性的不同而不 同，如：运输工具可承担的派送任务、道路状况等，都会对派送调度的 限制条件产生影响。不论派送调度的限制条件在数量和内容上如何变化， 上述基本限制条件都必须满足。派送调度的基本限制条件是我们进行调度 理论研究的主要约束条件。满足这三个基本限制条件是派送调度成功的一 个重要标志。能否有效地解决这三个限制条件是研究派送调度问题成功的 关键。 2 1 3 研究派送调度问题的意义 派送调度问题是大型超市集团、大型零售连锁店、物流派送中心及工 业生产企业共同存在的问题，它与企业的库存管理系统紧密联系，是工商 企业管理领域中研究的重要课题。对它的研究可追溯到解决二战期间美军 的后勤运输问题。半个世纪以来，它的应用范围日益扩大，几乎遍及商业 1 1 太原理工人学硕士研究生学位论文 活动、工业生产的一切经济领域，甚至关系到许多军事行动。随着，跨地 区、跨地域的经济活动的日益加强，对派送调度问题的研究也r 益激烈， 那么对派送调度问题的研究到底有什么意义? 派送调度问题是物流管理成功的一个重要因素 工业企业或商业企业的物流管理一般包括：生产调度子系统或商品 销售子系统、库存管理子系统、交通运输管理子系统。对于交通运输子系 统来讲，必须在有限运输工具的条件下合理安排运输工具的运行，使车辆 既能满足物资流通的原则，又达到最佳运行效益的目标。而实现交通“运 输管理子系统”的功能的关键是派送调度的成功实现。这是因为： 1 交通运输管理子系统”必须在运输能力均衡的前提下完成运输任 务，而运输能力的均衡必须成功解决派送调度问题的基础上实现； 2 “交通运输管理子系统”根据运输能力提出运输计划，而计划的前 提是有效解决派送调度问题； 3 “交通运输管理予系统”要在运输工具、派送请求变化时迅速调整 派送任务的分配，而这也要求成功解决派送调度问题： 因此，我们可以认为成功解决派送调度问题是物流管理成功的一个重 要因素。 派送调度问题是n p 问题的一个代表 现实世界里存在许多n p 问题，这些n p 问题的解决具有重大的现实 意义。如：多任务多处理机的分配问题是一个n p 问题，它的解决必然推 1 2 太原理上人学硕士研究生学位论文 动并行技术的发展：车间作业调度问题是一个n p 问题，它的解决将推动 计算机集成制造系统( c i m s ) 的发展与广泛应用；我们讨论的派送调度 问题也属于一个n p 问题，它实质上是运输路径的选择和完成派送任务次 序相结合的一个问题。派送调度问题属于n p 问题，这一点我们将在第四 节进行讨论。因此，对派送调度问题的解决将对解决n p 问题有一定参考 意义，并且为n p 问题的研究提供一个有实际应用价值的内容。【6 1 4 】 综上所述，对派送调度问题的研究不仅有现实意义，而且有理论价值。 2 1 4 派送调度问题的特征 要建立一个完整、通用的派送调度问题的系统模型，就必须对该问题 的特征进行分析。根据派送调度问题的特征建立起来的系统模型才能保证 模型的准确性和完整性。下面我们来讨论派送调度问题的特征： 特征之一：离散性 从派送调度问题的描述当中，我们可以看到确定派送任务的因素有货 物派送的起始地点、货物的目的地点、需要运输货物的数量、货物到达目 的地点的时间、车辆在执行派送任务时行驶的路线、货物流通的地域等。 这些因素都呈现出离散性的特征。 派送请求产生、货物的运输过程也呈现出非连续性特征。既然派送调 度问题呈现出离散性特征，所以，单纯运用连续理论来解决派送调度问题 是行不通的。运用离散控制理论来研究调度问题目前已经取得定的成 果，如：浙江大学纪树新等人开发的基于遗传算法的车间作业调度系统。 在我们看来，运用离散控制理论解决派送调度问题的关键是在问题原来的 表示模型上创建一个更加合适的表示模型，及能否将原来的表示模型与其 1 3 太原理工大学硕士研究生学位论文 他方法结合起来3 孔。 特征之二：动态性 从派送调度问题的定义我们可以看到派送调度系统的操作对象是派 送任务。由于执行派送任务的动态性特征，既派送任务有创建、执行、完 成的生命周期，也就是派送调度过程的状态是离散变化的。 客户通过电话、网络等其他方式随时可能向企业提出货物派送要求， 同时企业之间也根据实际的销售情况和生产计划动态也动态地提出货物 的派送要求。因此，派送调度问题呈现出动态性特征。 2 2 静态派送调度向动态派送调度的转化 根据派送调度问题的定义和对其特征的分析结果来看，一个派送调度 计算机系统需要根据派送要求的实际情况和运输工具的运行状况来实时 地安排派送任务的执行也就是该系统要实现在线或动态调度。但是，需要 指出的是派送调度问题的动态性特征和动态调度是有着本质上的区别，它 们是完全不同的两个概念。 问题的动态性特征是问题本身固有的特性与系统解决派送调度问题 的方式无关。但是问题的这一特征决定或要求系统在实施派送调度时采取 的方法。而系统为了强调派送调度的实时性可以采用相应的调度方式。 在系统实施派送调度时，可以根据实施调度时机的不同将派送调度划 分为静态派送调度和动态派送调度。所谓静态派送调度，就是在运输工具 执行派送任务前执行派送调度，静态调度也称为离线调度。动态调度是在 1 4 太原理t 大学硕士研究生学位论文 运输工具执行派送任务的过程中根据任务的执行情况实施派送调度，动态 调度也称为在线调度。静念调度和动态调度的根本区别在于派送调度的执 行效率上，动态调度有较高的实时性。然而，在事实上静态调度和动态调 度算法基本上一致。因此，二者有密切的联系。方面：一个消减计算复 杂性的静态调度算法同样可适用于动态派送调度。另一方面：运用静态派 送调度来削减动态派送调度的计算复杂程度，使得动态派送调度满足实时 性的要求。 对于静态派送调度和动态派送调度之间转化，我们可以在动态调度和 静态调度之间设置一个调度结果缓冲池，将静态调度的结果暂存在缓冲池 里，并且根据派送任务的执行情况动态地对静态调度结果进行修正。 图2 - l 就是静态派送调度用于动态调度的一个行之有效的缓冲池模 型。静态派送调度研究是动态派送调度研究的前提和基础，如果成功地解 决静态派送调度，那么动态派送调度就迎刃而解。因此，我们对于派送调 度问题研究的出发点也主要是解决静态派送调度问题。 图2 - i 静态派送调度和动态派送调度缓冲池模型 p i c t u r e2 - 1s t a t i ca p p o i n tj o b s c h e d u l i n g a n d d y n a m i cb u f f e rm o d e l 1 5 太原理工人学硕士研究生学位论文 根据以上对派送调度问题两点特征的讨论，毫无疑问，派送调度问题 属于离散事件动态系统( d i s c r e t e e v e n td y n a m i cs y s t e m s ，简称d e d s ) 。因 此，我们将对离散事件动态系统进行简单的介绍。 2 3 离散事件动态系统简介 在传统的系统与控制理论领域里，主要研究对象是一类本质上属于物 理时间范畴的连续变量动态系统，简称为c v d s 。c v d s 的动态过程服从 于物理学定理( 如：电学的、力学的、热学的定理等) 或广义的物理学 定理( 经济学规律、人口学规律、生态学规律、社会学规律) 的约束。其 数学模型可表示为传统意义下的微分方程。借助于数学理论所提供的对问 题描述和求解方法，使得这类问题的建模、分析、控制和优化的研究已经 达到相当成熟和完善的境界，并在实际应用中显示它的有效性。 本节介绍的离散事件动态系统是区别于c v d s 的另一类系统，离散 事件动态系统简称d e d s 。d e d s 本质上届于人造系统的范畴，不管系 统的运行规则还是系统研究的方法，都与c v d s 有着重要的区别。这一节 我们简单介绍d e d s 的基本概念和一般研究方法。 2 3 ，1 离散事件 构成离散事件动态系统的基本要素是离散事件。d e d s 行为随时间的 演化过程就是离散事件复杂交互影响的结果。大致来讲，离散事件是指 d e d s 中发生在离散时刻的事件，所谓事件则是使d e d s 状态发生变化的 一个行动或事情。 在不同的学科里，对事件的限定范围和重要程度的规定是不同的。在 1 6 太原理工大学硕士研究生学位论文 社会科学里，事件的通常是指历史上或社会上发生的重大或不寻常事情， 限定为对历史进程和社会变革产生重大影响的事情。除此之外的事情都不 可称为事件。工程科学如计算机科学里，凡是一种情况或一种活动的发生 都可称为一个事件，与第一个定义相比较，这一个定义在限制范围上明显 要宽广的多。对于d e d s 来讲，其对事件的定义比较接近后一种定义。 和离散时间连续变量系统不同，d e d s 中离散事件的发生时刻通常是 异步的，离散事件发生的时刻，取决于这一事件前系统行为的演化过程。 派送系统中的“货物开始运输”和“货物运输完成”，通信网络中的“信 号到达网络”和“信息处理完毕”，就是离散事件的一些典型例子。在d e d s 中，一个离散事件的发生，在驱动系统状态发生变化的同时，还回按照系 统的运行规则在系统其他部分触发新的离散事件的产生，从而形成在离散 事件驱动下系统状态的演化过程。派送调度系统中车辆继续承担下一个运 输任务，通信网络中信息沿传输设各和继续传递和变换过程，就是离散事 件复杂交互影响下所形成的d e d s 状态演化的例子。 归纳以上对d e d s 离散事件的分析，d e d s 中的离散事件有以下三个 基本特征： 离散事件是导致d e d s 状态发生变化和触发新的离散事件的 唯一因素，也即离散事件是驱动系统状态演化的基本因素。 离散事件的发生时刻是异步的和非约定的，即事件的发生时刻 由并且只能由系统的演化过程决定。 离散事件是研究d e d s 的主体，对d e d s 的分析归结为确定 离散事件交互影响所导致的系统演化过程，对d e d s 系统的控制归结 为禁止不期望的事件发生或使事件按期望的时序发生。 2 3 2 离散事件动态系统 1 7 太原理工大学硕士研究生学位论文 严格地讲，对于离散事件动态系统，至今还没有一个具有概括性和普 遍适应性并以至被认同的定义。大致来讲，d e d s 是由离散事件驱动，并 由离散事件按照一定的运行规则互相作用，导致状态演化的一类动态系 统。这个定义显示出d e d s 具有两个特点：第一，d e d s 的系统属性表 现为由离散事件驱动，而这正是其取名为离散事件动态系统的原因所在； 第二，d e d s 人造属性表现为基于人为的运行规则，因此，d e d s 覆盖了 一大批高技术的人造系统。 在d e d s 中，系统的状态由一批号码和离散变量所表示，并且只能在 离散事件驱动下和在异步离散时间内发生跳跃式变化。对于派送调度，系 统的状态由等待在派送网点的派送任务、运输工具的忙闲状况和运输开始 时刻的所表示。d e d s 的动态性一方面体现为“离散事件的发生驱动系统 状态的跃变”，另一方面体现为“系统状态的跃变触发新的离散事件的发 生”，由此形成复杂的相互作用。对于实际的d e d s ，系统参数的微小变 化，都可能引发离散事件发生时序的变化，从而导致不同的系统演化模式。 对于确定的d e d s ，在确定的运行规则和系统参数的情况下，由离散事件 驱动的系统状态演化模式也是确定的。 与连续变量动态系统( c v d s ) 相比较，离散事件动态系统( d e d s ) 有以下一些特点1 3 0 1 ： 不同于c v d s ，d e d s 的状态只能在离散时间点上发生跳 跃。在d e d s 中，状态的演化是由离散事件驱动的，因此，只在 事件发生的瞬间，系统的状态才能发生变化，在其他时刻系统的 状态保持不变。这是一种固有的不连续属性。与c v d s 中的时间 离散化有着本质上的区别。c v d s 中时间离散化是依靠引入采样 装置而人为加以实现的，不管采用何种方式进行离散化，变量的 变化时刻总是可以知道的。就物理本质而言，时间离散化后的 1 8 太原理工大学硕士研究生学位论文 c v d s 仍具有连续属性。 d e d s 的状态变化具有异步性和并发性。在d e d s 中， 系统状态由系统固有的离散性决定，演化过程中的状态跳跃时刻 呈现异步性。另外，一个离散事件的发生，可能使系统变化呈现 并发性，也就是同时导致一些或全部状态变量发生跳跃。 实际d e d s 的状态变化常常出现不确定性。在d e d s 中， 离散事件同时受到系统内部和系统外部的因素影响，这些因素在 一定程度上包含某种不确定性，因此导致系统状态变化出现不确 定性。 d e d s 服从的是人为的规则，而不是物理学定律及其衍生 物，这就决定了d e d s 通常不能采用传统的方法来描述。 2 3 3 离散事件动态系统的研究背景 对离散事件动态系统的研究最早可追溯到对排队现象和排队网络的 研究，排队论、网络分析、计划评审和调度排序的方法所面临的对象都可 归如d e d s 的范畴。但是，近年来d e d s 所以倍受人们的重视，并被认 为是系统与控制领域的一个前沿方向，一个重要的原因是当今一大批高技 术发展的需要和推动的结果。 现今，对离散事件动态系统研究的兴起出