基于图论的物流配送中心车辆调度系统设计与实现.doc

《基于图论的物流配送中心车辆调度系统设计与实现.doc》由会员分享，可在线阅读，更多相关《基于图论的物流配送中心车辆调度系统设计与实现.doc（52页珍藏版）》请在沃文网上搜索。

1、摘 要 摘 要停车位分配问题直接影响着配送中心的运作效率与发展，成为企业界和学术界关注的热点话题。本文通过分析配送中心停车场的运作情况，建立了停车场的顶点着色模型及其求解算法。通过构建配送车辆使用停车位的时间冲突集合，以“先到先服务”原则为基础，把停车位分配问题转化为顶点着色问题，并建立了相应模型。利用分解算法，停车位的利用效率得到改善。该算法的计算复杂度为。通过将该算法应用于一个算例，得到了最优解。最后应用Visual Basic程序语言设计了一个配送中心停车位分配系统，有助于配送中心实现停车场整体资源配置的最优化与现代化程度的提高。关键词： 配送中心，停车调度，图论，顶点着色，算法，Vis

2、ual Basic I目录- 7 -AbstractGate assignment make great effect on the logistics centers development, it has become the hot issue to which the enterprise and the academic circles pay attention.The operation of logistics centers parking lots was analyzed. Vertex coloring model and algorithm of gate assig

3、nment problem was proposed. By improving an algorithm of time conflict, the set of the time conflict of the scheduled car was constructed. Based on the “first in first out” principle, gate assignment problem was transferred to vertex-coloring problem, and corresponding model was constructed also. By

4、 utilizing decomposed algorithm, it is possible to improve the gates operation ability. The algorithms computational complexity is O ( ). An example was offered to demonstrate the application of the algorithm and the optimal solution was obtained. Finally，Visual Basic was used to fulfill design a ga

5、te assignment system of logistics centers. This algorithm is benefit to the overall optimization and improvement of the logistics centers in the level of modernization.Key words：logistics centers；gate assignment；graph theory ；vertex coloring；algorithm；Visual Basic目 录目录摘 要IAbstractII目录III第一章 前言- 1 -1

6、.1课题研究的背景意义- 1 -1.2停车位调度管理的研究现状- 2 -1.2.1国内研究现状- 2 -1.2.2 国外研究现状- 4 -1.3课题的研究方法- 5 -1.4本论文的主要思路和预期目标- 6 -1.5本文主要的研究工作- 6 -第二章 图的相关知识- 8 -2.1图的定义及性质- 8 -2.2图的基本性质- 9 -2.3着色问题- 10 -2.3.1 边着色- 10 -2.3.2 顶点着色- 10 -2.4算法复杂度的定义及其算法的效率度量- 10 -2.5本章小结- 11 -第三章 配送中心的相关知识- 12 -3.1配送中心的定义- 12 -3.2 配送中心的类型- 12

7、-3.3 配送中心的工作流程- 14 -3.4配送中心主要功能- 16 -3.5本章小结- 17 -第四章 停车调度的数学模型- 18 -4.1问题陈述- 18 -4.1.1停车位分配存在问题- 18 -4.1.2影响车位分配的其他因素- 19 -4.2配送中心停车位的顶点着色模型- 20 -4.2.1停车位分配分析- 20 -4.2.2停车位分配的顶点着色模型- 21 -4.3算法设计及分析- 21 -4.3.1车辆运行时间冲突判断的算法设计- 21 -4.3.2 停车位分配问题的算法设计- 22 -4.3.3 算法复杂度分析- 24 -4.4 本章小结- 25 -第五章 配送中心停车场停车

8、位分配算例- 26 -5.1配送中心停车位及车辆介绍- 26 -5.2 停车位的时间冲突算例- 28 -5.3 顶点着色的算例- 29 -5.4 本章小结- 30 -第六章 停车调度系统设计及其实现- 31 -6.1停车调度算法的程序设计- 31 -6.1.1 设计思路- 31 -6.1.2 程序设计- 31 -6.2本章小结- 35 -第七章 总结- 36 -7.1 工作总结- 36 -7.2 工作展望- 37 -参考文献- 38 -致 谢- 40 -附录- 41 -第一章 前言第一章 前言第一章 前言1.1课题研究的背景及意义随着经济全球化趋势的加强，现代信息技术、供应链管理技术的飞速发展

9、，被称为企业的“第三利润源泉”的物流作为一种实现经济高效运行、融合高新技术为一体的先进管理技术与组织方式，通过计划、实施、控制与协调等手段对运输、仓储、装卸、包装、配送、流通加工、信息各环节的系统整合，以最低的费用和最少的资金占用，安全、准时、高质量地为用户提供多功能、一体化的综合服务，在世界范围内受到了广泛的关注，发展十分迅速。配送是物流系统中的一个重要环节，它是指企业或物流代理企业在确认顾客的订购信息之后将商品从配送中心送到各个消费者手中的过程。在物流成本中，配送是成本消耗最大的物流活动之一，占物流总成本的二分之一到三分之二。因此，降低配送的成本，就能有效降低整个物流的成本。随着我国经济的

10、飞速发展，市场经济已经越来越激烈，尤其是进入21世纪后，企业间的核心竞争要素已经从价格和质量转变为服务和时间。对于配送中心也是这样。只有那些快速满足用户需求，具备及时快速的物流能力的企业才能在竞争中取胜。 配送中心的管理水平尤其反映一个企业的市场竞争能力。停车调度问题直接影响配送时间及服务质量。在配送中心的管理的工作中占了重要角色。配送中心的配车计划管理软件, 在美、日等国已商品化。它能大大缩短配车计划编制时间、提高车辆的利用率、减少闲置及等候时间、合理安排配送区域和路线等。在我国, 由于观念、制度和经济上的种种制约, 我国物流的发展非常缓慢, 物流企业电子化程度低, 只有少数物流企业在互联网

11、上提供了企业状况、业务范围、报价系统、运费支付、在途货物查询等功能，与市场的需求差距较大。所以, 我们亟需解决配送中心的规划与管理、仓储设施的现代化配置、配送运输工具的更新换代、物流管理模式和经营方式的优化等问题1。随着配送中心专业化程度的不断加深，停车位的分配问题开始占据越来越重要的位置，成为配送专业化的集中体现。若能对配送中心的停车位进行最优化分配，可极大地提高配送质量。在停车位分配问题中，停车场的管理处于重要地位。建立并优化停车位分配模型以及相应算法是计算机辅助调度停车场停车位的重要课题。由于车辆使用停车位大都集中在一个个的时间区间内进行，分配停车位的算法设计的关键是处理作业时间冲突的任

12、务安排问题1。现代大型物流配送中心的发展趋势要求配送中心停车场的管理要有高效率，而停车位的管理直接决定了停车场的高效率。对于现代大型物流配送中心来说，停车场调度工作的重要表现已越来越突出的反应出来，物流配送中心的功能也随之越来越突出，然而目前国内关于配送中心停车调度工作的研究不足，而我国运输业等的发展对物流配送中心提出了更高的要求，成为本课题研究的现实背景。1.2停车位调度管理的研究现状首先明确停车调度的含义。在交通行为中，停车调度是常用的一种调度控制手段。实施停车调度就是要决定车辆应如何行使，驶向哪些停车位，调度的目的是使整个运输系统费用最低。停车调度手段在公共交通的管理中应用较为广泛。目前

13、我国关于停车位分配的问题研究较少，而国外交通虽然机动化程度较高，但尚没有行之有效的方法解决停车位分配的效率问题。现有的停车调度模型及其求解算法或者不能求得最优解，或者只能达到局部最优化，而对于配送中心来说，停车场停车位分配的整体最优化才是企业期望的目标。因此，寻求一种解决停车位分配问题的有效方法，成为学术界和企业界关注的焦点问题之一。1.2.1国内研究现状梅振宇，项贻强，陈峻，王炜通过对停车选择的分析，提出了停车率诱导信息配置优化组合模型与算法2。该模型的研究从车辆率高和日常泊位饱和度大的热点停车场入手，考虑车辆停放者的选择行为，以总行程时间最小建立了目标函数，通过采用基于最优组合的可变信息板

14、(VMS)信息显示组合方式来发挥停车选择诱导作用，并对它设计遗传算法(GA)进行计算，从而获得目标函数最优化值。经实例验证，设置诱导后最小总行程时间可大大减少。陈峻、周智勇、王炜提出一种服务于驾驶员的优化模型3。该模型以驾驶员使用最便利，可达性最强,出行停放成本最低为目标,利用启发式算法计算了备选停车场车辆停放选择的备选解集。经实例验证,该模型可以得到多个满足约束条件的合理性停车方案,从而为驾驶员在出行前选择停车场提供了决策依据。该方法能求出多个停车方案解集，但不能确定最优解。他们还提出了基于排队论的出行车辆停放接受条件，为了提高停车场车辆停放的可达性,引入排队论原理和“生灭过程”状态方程表达

15、出行者车辆停放过程.将目的地停车场视作可互通的多服务通道损失制系统,采用服从泊松分布的车辆到达率和服从负指数分布的车辆平均停放时间,建立了出行过程中的车辆停放接受条件概率模型。应用美国道路局路阻函数计算车辆行程时间值并采用范围域表示,围绕驾车者行程初期和行程末期2个瞬时状态,进行停车接受条件分析,同时获得行程末期停车场服务能力和停放饱和度指标的计算结果。研究结果表明,当停车设施的服务能力N值在一定范围内保持稳定时,可满足车辆停放接受条件,而行程时间的波动幅度与停车接受条件R,N值和停车场停放饱和度值直接相关4。熊光华，王令其设计出了一种先进的停车方式和控制系统，即自动化立体车库和车库群监控系统

16、5。自动化立体车库技术可以有效地解决大城市的用地紧张和停车难的矛盾，在发达国家率先得到推广应用。立体车库的核心部分车库群的监控系统，通过网络对单元车库的作业进行动态监控管理，使整个车库具有很高的自动化程度和可靠性，并且集管理、调度与监控方式于一体，大大提高了立体车库的使用、管理与维护效率，也可用于其它交通系统的行车调度5。黎冬平，董瑞娟，陈峻通过对以商业区停车场短时车辆到达率和离去率的调查和分析，用BP神经网络算法对其进行短时预测，得到小区所有停车场车辆总到达率特性比单个停车场更为稳定和显著，而车辆离去率特性在两者之间的差异则不明显。本研究为中心区停车场的管理和停车诱导提供了理论依据6。1.2

17、.2 国外研究现状发达国家的机动车拥有量很大，公共机动车停车系统成为城市交通中很重要的问题。德国和法国关于停车系统的研究起步较早，在缓解城市交通压力，提高停车场利用效率方面取得了较为显著的效果，特别是对于停车位的管理方法较为先进，值得我们学习与借鉴。城市停车诱导信息系统(简称PGIS) 就是为了解决城市停车信息缺乏、停车无序、缓解交通而产生的。它通过信息诱导为司机提供实时、准确的停车信息,避免了司机盲目寻找停车空位,提高了停车场泊位利用率,缓解了城市交通的压力。国外对城市交通、停车诱导信息系统的研究起步较早, PGIS 最早出现在德国的亚琛市,随后在欧洲、日本以及美国等地得到了应用。目前,我国

18、城市的机动化程度不断提高,迫切需要解决停车难问题,PGIS 已经在北京、上海、广州、苏州等地有所应用7。PGIS 的停车位预定功能使得司机可以在某停车场内预约停车位,节约了司机寻找停车空位的时间,驾车出行变得更有计划性。PGIS 统一管理城市内停车场所,在适当位置为司机提供丰富的停车信息,引导司机快速而准确地寻找理想的停车场所,为城市交通作出了贡献,具有很高的实用和经济价值。就停车场具体情况而言，为避免车辆使用停车位时发生作业时间冲突，所以处理时间冲突问题就成为算法设计的关键。国外学者就此问题进行了研究，其研究结果可以分成两种：一种是专家系统法，通过将分配原则建立于知识库系统，并考虑较多的非量

19、化准则；另一种是数学规划，以仓库到停车位的距离最短为目标函数，利用0-1整数规划探讨分配的可行性及如何分配。前者往往由于受搜索范围的限制，忽视关键因素而导致分配结果不理想。后一种方法受目标函数的影响，常会出现把较多的车辆分配给较少的有吸引力的停车位，而且车辆行驶时间表微小变化都会很容易引起停车位分配的混乱和计算量的大增，并且当车辆数量较大时，由于计算时间太长往往得不到最优解或满意解16。早期的算法研究主要是诸如基于布尔代数运算的着色算法和基于深度优先搜索的回溯算法等经典方法，后来在用传统方法解决复杂及较大规模的问题出现困难时，一些近似算法或启发式算法陆续问世，近年来随着智能算法的发展，遗传算法

20、和模拟退火算法逐渐得到了人们的重视。但由于图着色问题是典型的NP难题，大部分早期的算法的时间复杂性是指数级的，而智能算法在图着色方面的应用还处于试探阶段，成果较少8。在应用启发式着色算法进行求解时，须指定一个顶点序列。该算法的着色过程是用标上号的颜色，按照给出的顶点排列顺序，逐次为每个顶点着尽可能少的颜色，对于图的每一种顶点的排列顺序，都可以用启发式算法得到一个确定的着色方案。该算法对于每一种顶点的排列顺序来说是最优的，但对于不同的排列顺序其得到的着色方案是不同的，因此要想得到最优解，就必须对图的n!种不同的顶点排列顺序均采用启发式着色算法进行着色，才可知道最优方案。当n较大时（如超过100个

21、顶点），用目前的计算机进行运算是不现实的8-10。此外，专家学者们在传统算法的基础上，创新了许多新的算法，例如混合顶点着色算法、启发式搜索蚂蚁算法、改进粘贴DNA算法、基于集合思想的着色算法等10，这些算法在不同的实际问题中都有良好的应用。Brelaz提出最大色度着色算法，其思路是尽早将度数高的的结点着色，因为在后面处理这些结点会很困难，同时，如果某结点有许多邻接点已着不同色，算法也应尽早处理该结点。在着色的同时，还要记录已使用颜色数，而且在图中删除已着色顶点及其关联边11。由于停车位分配工作的复杂性，国内这方面的研究主要针对公共停车场，而对配送中心的停车场研究较少，对于配送中心停车场的研究具

22、有重要意义。同时由于配送中心车辆使用的灵活性，造成停车位分配工作的复杂性。因此高效的精确算法可能性不大，启发式算法虽能快速解决问题，但对于解的质量无法保证，因此当前算法，均是求近似最优解。而本文在最大色度着色算法的基础上，设计出了顶点着色模型的着色算法，具有最逼近最优解的优点。1.3课题的研究方法本文主要通过对三个算法的设计，在着色理论以及图论的基础上，将停车位调度问题转化为一个着色问题，建立了停车位分配的顶点着色模型。解决了普通算法中解的质量不高从而造成停车场资源浪费的问题，求出了停车位调度问题的近似度很高的次最优解。1.4本论文的主要思路和预期目标本论文研究了配送中心停车场的停车位分配问题

23、。在配送车辆到达停车场的时间为已知的前提下，构建车辆使用停车位的时间冲突集合，以“先到先服务”为原则，将停车位分配问题转化为顶点着色问题，应用图论相关知识建立关于停车位分配的顶点着色模型。设计一种最大度优先算法确定适合某一时间段内每辆车的最佳停车位，使得配送车辆到达停车场时，能直接驶向最佳停车位，避免了选择车位的盲目性和滞后性。并应用Visual Basic 程序语言设计了一个配送中心停车调度系统，实现用最少的停车位满足配送中心停车场的停车需求。有助于配送中心现代化程度的提高和发展，从而提高物流企业的服务水平和市场竞争力。用该算法的目标是：进行车位分配时能充分利用停车场的资源，实现停车位的最佳

24、配置，达到系统整体最优化。本课题所采用的技术方法主要有：图的数学建模及着色算法、VB程序设计语言等计算机技术。1.5本文主要的研究工作第一章前言部分主要介绍了该课题提出的背景及意义、课题所用知识的研究现状，研究方法以及本课题的研究对象、目标和方法。第二章主要介绍图的基本概念及性质、图着色、图的存储结构、图的数学模型以及图的算法，是求解配送中心停车场的停车位分配问题的理论基础。 第三章旨在说明配送中心的基本概念，包括配送中心的定义、分类、配送中心的工作流程及主要功能。 第四章指出停车位分配存在的问题，建立和求解顶点着色模型所需要的三种算法：时间冲突算法、分解算法、着色算法。为第五章算例的求解提供

25、理论根据。 第五章算例，用配送中心停车场停车位的算例，证明算法的有效性，以及证明可以使用最少的停车位满足停车需求。第六章停车调度的程序设计。设计具体的程序以及界面来实现停车场配送系统的功能。第七章回顾全文，总结了为本论文所做的工作，并指出了待改进之处。第二章 图的相关知识- 48 -第二章 图的相关知识第二章 图的相关知识2.1图的定义及性质 定义1： 一个图定义为一个有序对。其中(1) 是一个非空集合，称为顶点集，其元素称为顶点或点；(2) 是由中的点组成的无序点对构成的集合，称为边集，其元素称为边， 且同一点对在中可出现多次。定义2： 一个图是一个三元组,，其中是一个非空的结点集合，是边集

26、合，是从边集合到结点集合上的函数。一个图可以用一个图形表示。若把图中的边看作总是与两个结点关联，那么一个图亦可简记为=,其中是非空结点集，是连接结点的边集。在一个图中，若两个结点由一条有向边或一条无向边关联，则这两个结点称为是邻接点。类似于邻接点的概念，关于同一结点的两条边称为邻接边。定义3： 在图中中，与结点关联的边数，称作该结点的度数，记作。由此我们知道，结点度数的总和等于边数的两倍。一个图由一个图形表示，由于图形的结点位置和连线长度都可以任意选择，故一个图的图形表示并不是唯一的。定义4：在有向图中，射入一个结点的边数称为结点的入度，由一个结点射出的边数称为该结点的出度。结点的入度与出度之

27、和就是该结点的度数。由此我们知道，在任何有向图中，所有结点的入度之和等于所有结点的出度之和。因为每一条有向边必对应一个入度和一个出度，若一个结点具有一个入度或出度，则必关联一条有向边。定义5：含有平行边的任何一个图称为多重图。不含平行边和环的图称为简单图。定义6：简单图中，若每一对结点间都有边相连，则称该图为完全图。有个结点的无向完全图记做。2.2图的基本性质图论是研究二元关系的一门学问,是计算机科学的理论基础,顶点和边是图的两个基本要素,一定的量反映一定质,顶点数和边数以及它们之间的数量关系在一定程度上决定了图的基本性质。 定理1 ：在任意一个图中，结点度数的总和等于边数的两倍,也即。证明：

28、因为每条边必关联两个结点，而一条边给予关联的每个结点的度数是1.因此在一个图中，结点度数的总和等于边数的2倍。定理2：在任何图中，度数为奇数的结点必定是偶数个。证明：设和分别是中奇数度数和偶数度数的结点集，则由定理1，有： 。由于是偶数之和，必为偶数；而是偶数，所以，是偶数，即是偶数。定理3：在任意有向图中，所有结点的入度之和等于所有结点的出度之和。证明：因为每一条有向边必对应一个入度和一个出度，若一个结点具有一个入度或出度，则必关联一条有向边，所以，有向图中各结点入度之和等于边数，各结点出度之和也等于边数，因此，任何有向图中，入度之和等于出度之和。定理4 个结点的无向完全图的边数为。证明：在

29、中，任意两点间都有边相连，个结点中任意取两个点的组合数为：，故的边数为。如果在中，对每条边任意确定一个方向，就该称该图为个结点的有向完全图。显然，它的边数也是。给定任意一个含有结点的图，总可以把它补成一个具有同样结点的完全图，方法是把那些没有连上的边添加上去。2.3 着色问题着色是指对二元图中的元素（顶点、边等）进行着色，即在满足一定的条件下，使得任意两个相邻的相同性质的元素的颜色不相同，并且使得所用颜色数最少（即在现实生活中所用资源最少）。2.3.1 边着色图的边着色，是种色在上的一种匹配，即是的一个-划分。的边色数是使为边可着色的最小的，记为。当时，称为边色的。2.3.2 顶点着色一般而言

30、，对图的顶点着色有如下定义：如果使用种颜色把图的每个顶点皆分配一种颜色，且使其邻顶点异色，则称此为对的顶点正常着色，图的顶点的正常着色中所需要颜色数的最小值称为的顶色数，简称色数,记之为。色数为的图称为色图。2.4算法复杂度的定义及其算法的效率度量无论是求解一个图的色数的算法，还是对一个给定的进行正常顶点着色算法、正常边着色算法以及正常全着色算法，都是NP完全问题。数较大时，用常规的方法很难得到图的正常k顶点着色、正常k边着色以及正常k全着色。于是，人们设想寻求更多简便的途径求得这些问题的算法。不管是从事数学研究的图论学者，还是从事电路与系统等工程技术方面研究的图论学者，或是其他领域内的科学家

31、，对图的着色问题都表示了极大的兴趣与关注。算法的复杂度是指执行算法所需的时间和空间的量。关于算法的复杂度主要有如下定义：定义1：令f和g为从整数集合或实数集合到实数集合的函数，如果存在常数c和k，使得只要xk，就有，则称是=,，记作 =。定理1：令=，其中， 为实数,则=.定理2：设, ,则.定理3：设，,则 大符号常用于估计一个特定的计算机过程或算法解题的操作步骤.做这些估计时常用的函数包括:。算法的效率度量有两种方式，一种是计算机按照算法解题所花费的时间，称为时间复杂性；另一种是计算机实现这一算法需要多大的内存，称为空间复杂性，空间复杂性与实现算法时使用的特定数据结构相关，故通常选择时间复

32、杂性度量算法效率。按匈牙利权威数学家Edmonds的定义，当一个判定问题给定之后，若存在一个多项式，使得对于的任何输入长为的实例，可以在的时间内对这个实例给出答案，则称这种解答算法时间复杂度是合理的，称这 种算法为好算法或有效算法；否则（例如时间为）称相应的算法的时间复杂度式不可容忍的，称这种算法为无效算法或坏算法。2.5本章小结本部分主要介绍了该课题所用到的图论的基础知识，包括图的定义、图的性质、算法的复杂度的定义等，为解决停车场的停车位分配问题做好了铺垫。第三章 配送中心的相关知识第三章 配送中心的相关知识3.1配送中心的定义中华人民共和国国家标准-物流术语12将配送定义为:“在经济合理区

33、域范围内，根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动”。配送是物流中一种特殊的、综合的活动形式，它把商流与物流紧密结合，是包含了物流中若干功能要素的一种物流活动。它不是消极地送货式的发货，而是把“配”和“送”有机地结合起来，按用户对商品种类、规格、货品种搭配、数量、时间、送货地点等各项要求，在物流据点有效地利用分拣、配、集装、合装整车、车辆调度、路线安排的优化等一系列工作，使送货达到一定的规模，以利用规模优势取得较低的成本。王之泰在现代物流学13中定义：“配送中心是从事货物配备(集货、加工、分货、拣选、配货)和组织对用户的送货，以高水平实现销售或供

34、应的现代流通设施”。配送中心是以组织配送性销售或供应，执行实物配送为主要职能的流通型物流据点。配送中心是专业从事货物配送的物流场所和经济组织，它集加工、理货、送货等多种职能于一体，是集货中心、分货中心、加工中心、运输中心等功能的结合。因此，配送中心既具有一般物流中心的基本功能，又具有自己的独特功能。具体来讲，配送中心有五种主要功能:信息交换和处理功能；储存保管功能；分拣配货功能；货物集散功能和配送加工功能。现代配送中心是市场经济条件下，以加速商品流通和创造规模效益为核心，以商品代理和配送为主要功能，集商流、物流、信息流于一体的现代综合流通机构。3.2 配送中心的类型配送中心是基于物流合理化和发

35、展市场两个需要发展起来的，是以组织配送式销售和供应，执行实物配送为主要功能的流通型物流结点。它很好的解决了用户小批量多样化需求和厂商大批量专业化生产的矛盾，因此，逐渐成为现代化物流的标志。随着经济的发展，配送模式日益盛行，商品的流转速度逐渐加快，流通规模扩大，使得对配送中心的需求不断增加，社会上出现了各种功能和形式的配送中心，总结国内外配送中心的建设与运营情况，按照不同的分类标准，其类型大体如下：（1）按配送中心的隶属关系分：a 自有型配送中心，其设施归一家企业或企业集团所有，成为企业物流组织体系和物流系统的构成部分，为企业自己或集团内部服务，很少对外提供服务,如美国沃尔玛的配送中心即是公司独

36、资建立，专门为本公司所属的连锁店提供商品配送服务的自有型配送中心；b 公共型配送中心，面向社会或某个行业所有用户服务，由若干家企业共同投资、持股和管理。（2）按营运主体分类：a 以制造商为主的配送中心，是制造商为了降低商品出售的流通费用和提高售后服务质量而建立的配送体系，如海尔物流配送中心；b 以批发商为主的配送中心，顾名思义，这是由批发商或代理商建立的配送中心；c 以零售商为主的配送中心，以零售商为主建立，面向终端用户或门店，如华联超市股份有限公司；d 以专业物流企业和公共物流站场为主的专业配送中心，是以第三方物流企业（包括传统的仓储企业和运输企业）为主体的配送中心，这种配送中心只提供仓储管

37、理和运输配送服务，现代化程度往往较高。（3）按配送中心的功能划分：a 储存型配送中心，在发挥储存作用的基础上组织配送活动；b 流通型配送中心；c 加工型配送中心。（4）按配送中心的层次和范围划分：a 中央配送中心，主要位于制造商的生产基地，辐射范围广，面向下游的区域配送中心或直接面向客户服务；b 区域配送中心，主要接收上游厂商或中央配送中心送来的货物，然后转运到下游的城市配送中心、仓库或直接配送给客户；c 城市配送中心，向城市范围内的用户提供门到门的配送服务。（5)按配送物品种类划分：如日用品配送中心、食品配送中心、生鲜品配送中心、化妆品配送中心、医药品配送中心、图书配送中心、服饰配送中心等1

38、4。本文所研究的配送中心是公共型以专业物流企业和公共物流站场为主的专业配送中心，提供城市之间的配送服务。3.3 配送中心的工作流程不同模式的配送中心作业内容有所不同，一般来说配送中心执行如下作业流程：进货-进货验收-入库存放-标示包装-分类-出货检查-装货-送货。归纳而言，配送中心的作业管理主要有进货入库作业管理、在库保管作业管理、加工作业管理、理货作业管理和配货作业管理。1)进货入库作业进货入库作业主要包括收货、检验和入库三个流程。收货是指连锁店总部的进货指令向供货厂商发出后，配送中心对运送的货物进行接收。收货检验工作一定要慎之又慎，因为一旦商品入库，配送中心就要担负起商品完整的责任。2)在

39、库保管作业商品在库保管的主要目的是加强商品养护，确保商品质量安全。同时还要加强储位合理化工作和储存商品的数量管理工作。商品储位可根据商品属性、周转率、理货单位等因素来确定。储存商品的数量管理则需依靠健全的商品账务制度和盘点制度。商品储位合理与否、商品数量管理精确与否将直接影响商品配送作业效率。 3)加工作业主要是指对即将配送的产品或半成品按销售要求进行再加工，包括：分割加工，如对大尺寸产品按不同用途进行切割；分装加工，如将散装或大包装的产品按零售要求进行重新包装；分选加工，如对农副产品按质量、规格进行分选，并分别包装；促销包装，如促销赠品搭配；贴标加工，如粘贴价格标签，打制条形码。加工作业完成

40、后，商品即进入可配送状态。4)理货作业理货作业是配货作业最主要的前置工作。即配送中心接到配送指示后，及时组织理货作业人员，按照出货优先顺序、储位区域别、配送车辆趟次别、门店号、先进先出等方法和原则，把配货商品整理出来，经复核人员确认无误后，放置到暂存区，准备装货上车。理货作业主要有两种方式，一是“播种方式”，二是“摘果方式”。 所谓播种方式，是把所要配送的同一品种货物集中搬运到理货场所，然后按每一货位(按门店区分)所需的数量分别放置，直到配货完毕。在保管的货物较易移动、门店数量多且需要量较大时，可采用此种方法。所谓摘果方式(又称挑选方式)，就是搬运车辆巡回于保管场所，按理货要求取出货物，然后将

41、配好的货物放置到配货场所指定的位置，或直接发货。在保管的商品不易移动、门店数量较少且要货比较分散的情况下，常采用此种方法。在实际工作中，可根据具体情况来确定采用哪一种方法，有时两种方法亦可同时运用。 5)配货作业配货作业过程包括计划、实施、评价三个阶段。(1)制定配送计划 配送计划是根据配送的要求，事先做好全局筹划并对有关职能部门的任务进行安排和布置，从而决定配送时间，选定配送车辆，规定装车货物的比例和最佳配送路线、配送频率。(2)配送计划的实施 配送计划制定后，需要进一步组织落实，完成配送任务。首先应做好准备工作。配送计划确定后，将到货时间、到货品种、规格、数量以及车辆型号通知各门店做好接车

42、准备；同时向各职能部门，如仓储、分货包装、运输及财务等部门下达配送任务，各部门做好配送准备。然后组织配送发运。理货部门按要求将各门店所需的各种货物进行分货及配货，然后进行适当的包装并详细标明门店名称、地址、送达时间以及货物明细。按计划将各门店货物组合、装车，运输部门按指定的路线运送各门店，完成配送工作。如果门店有退货、调货的要求，则应将退、调商品随车带回，并完成有关单证手续。3.4配送中心主要功能配送中心的功能可以从经济和服务两个方面来考察。配送中心在物流系统中的价值体现在它对整个系统的贡献，即配送中心建立在成本-效益的基础上。如果配送中心的使用可以降低连锁企业的物流的总成本，那么配送中心就产

43、生了经济利益，也说明了配送中心存在的合理性。配送中心对物流总成本的贡献是通过效益互换体现出来。例如，在物流系统增加配送中心会能使运输总成本下降，且其下降的幅度大于配送中心的固定成本和变动成本，那么总成本就会降低。配送中心基本的经济方面的功能主要有四个：集中、整理分类、加工和储存。（1）集中功能 配送中心的集中功能指原来供应商分别将商品送至目标门店，现在通过配送中心接收供应商送到某一特定门店的商品，然后把它们整合成单一的一次运输，其好处就是能减少运输费，同时减少门店收货时的拥挤现象。（2）整理分类功能 多数供应商是对多个门店送货，这些门店可以同属于一个企业，也可以属于不同企业。在没有配送中心的情

44、况下，供应商只能小批量装载分别将商品运至指定门店。如果有配送中心，就可以在这里将商品分类 整理成个别的订货，并安排当地的运输部门负责递送至门店由于长途运输转移的是大批量的装运，供应商的运输成本相对较低，连锁商商品的进价也可以降低，同时对于大量运输的跟踪也不太困难。（3）加工功能 一方面，配送中心通过对商品的加工，能够扩大经营范围和提高配送水平，满足广大消费者的需要；另一方面，通过加工，可以提高商品的价值，从而提高连锁超市的经济效益。（4）储存功能 有些商品的品种有限或商品的生产具有季节性，所以对商品储存是很重要的。例如，玩具是全年生产的，但主要在儿童节和圣诞节期间内进行销售，为了防止缺货，常常

45、在节日之间就要开始储备。与此相反，农产品在特定的时间里收获，但却在全年消费。所以一定的储存提供了存货缓冲，使配送活动在受到采购和顾客需求的限制条件下提高效率15。3.5本章小结本章介绍了配送中心的相关知识包括配送中心的概念，配送中心的分类及工作流程和主要功能。从而为配送中心停车调度系统的研究提供现实的依据，使配送中心停车调度的研究具有实用性的特性。第四章 停车调度的数学模型第四章 停车调度的数学模型第四章 停车调度的数学模型4.1问题陈述4.1.1停车位分配存在问题在停车场车辆运营管理中，基本信息为包含车次开始使用停车位和离开停车位的时间、车型、任务性质的车次计划信息表，但要自动生成通用的车位

46、分配表是困难的，原因有:(l)停车场业务量大，根据统计国内车场排名前三位的停车场，在停车的高峰时期业务量相当之大，因此要求算法有较好的时间和空间性能。(2)一个车次有多个可行的车位分配方案，且作计划时，信息不全，只给出理论最佳方案。(3)停车位多，各停车场有不同的车位分配规定。(4)车次有不同的出行任务，如正班、加班、补班等。有不同的行车线性质，如国内长途、国际长途和短途运输。(5)存在各种意外情况，如意外因素造成时间延误等。(6)存在冲突的分配目标，如优化旅客服务和减少运营成本、增加停车场收益。(7)安全性要求高，由于关系到企业利益和生命财产的安全，稍有疏忽将可能引起很大的经济损失，和恶劣的

47、社会、政治影响，因此驾驶员应有娴熟的专业技术和高度的责任感。(8)实时性，要求能够快速进行资源分配。进入停车场马上根据指示找到自己的停车位，而不在停车场内反复寻找，影响其他待停放的车辆。停车场的停车位是车场运营的重要资源，给进出停车场的每个车次分配一个合适的停车位，是停车位分配工作的主要任务。对配送中心管理者来讲，使用最小的代价来获得停车场方面最多的资源，是停车位分配的重要目标。从这个角度看，能否做好车场资源管理工作，尤其是停车位资源的分配工作，令所有停放在车场的司机满意，是停车场提供给停车者服务的主要指标。而对于配送中心来说，停车位选择的优劣性则与整个运作系统的经济效益息息相关。从表面上看，停车位分配就是给即将停放的车辆安排一个空的停车位，这似乎是很简单的事情，但实际上，如何分配好停车位，还要考虑很多因素。首先是停车位的分配必须适合车位的物理特性。这种适合体现在两个方面：一个是必须适合车位的容量特性，车场的不同停车位可以容纳的车辆型号是不同的，这就是车位的容量特性；另一个是在长时段内减少车位冲突。