发布时间 : 星期一 文章基于图论的物流配送中心车辆调度系统设计与实现更新完毕开始阅读57171e1afad6195f312ba6ed
第一章 前言
1.2.2 国外研究现状
发达国家的机动车拥有量很大，公共机动车停车系统成为城市交通中很重要的问题。德国和法国关于停车系统的研究起步较早，在缓解城市交通压力，提高停车场利用效率方面取得了较为显著的效果，特别是对于停车位的管理方法较为先进，值得我们学习与借鉴。
城市停车诱导信息系统(简称PGIS) 就是为了解决城市停车信息缺乏、停车无序、缓解交通而产生的。它通过信息诱导为司机提供实时、准确的停车信息,避免了司机盲目寻找停车空位,提高了停车场泊位利用率,缓解了城市交通的压力。国外对城市交通、停车诱导信息系统的研究起步较早, PGIS 最早出现在德国的亚琛市,随后在欧洲、日本以及美国等地得到了应用。目前,我国城市的机动化程度不断提高,迫切需要解决停车难问题,PGIS 已经在北京、上海、广州、苏州等地有所应用[7]。
PGIS 的停车位预定功能使得司机可以在某停车场内预约停车位,节约了司机寻找停车空位的时间,驾车出行变得更有计划性。PGIS 统一管理城市内停车场所,在适当位置为司机提供丰富的停车信息,引导司机快速而准确地寻找理想的停车场所,为城市交通作出了贡献,具有很高的实用和经济价值。
就停车场具体情况而言，为避免车辆使用停车位时发生作业时间冲突，所以处理时间冲突问题就成为算法设计的关键。国外学者就此问题进行了研究，其研究结果可以分成两种：一种是专家系统法，通过将分配原则建立于知识库系统，并考虑较多的非量化准则；另一种是数学规划，以仓库到停车位的距离最短为目标函数，利用0-1整数规划探讨分配的可行性及如何分配。前者往往由于受搜索范围的限制，忽视关键因素而导致分配结果不理想。后一种方法受目标函数的影响，常会出现把较多的车辆分配给较少的有吸引力的停车位，而且车辆行驶时间表微小变化都会很容易引起停车位分配的混乱和计算量的大增，并且当车辆数量较大时，由于计算时间太长往往得不到最优解或满意解[16]。
早期的算法研究主要是诸如基于布尔代数运算的着色算法和基于深度优先搜索的回溯算法等经典方法，后来在用传统方法解决复杂及较大规模的问题出现困难时，一些近似算法或启发式算法陆续问世，近年来随着智能算法的发展，
- 4 -
第一章 前言
遗传算法和模拟退火算法逐渐得到了人们的重视。但由于图着色问题是典型的NP难题，大部分早期的算法的时间复杂性是指数级的，而智能算法在图着色方面的应用还处于试探阶段，成果较少[8]。
在应用启发式着色算法进行求解时，须指定一个顶点序列。该算法的着色过程是用标上号的颜色，按照给出的顶点排列顺序，逐次为每个顶点着尽可能少的颜色，对于图的每一种顶点的排列顺序，都可以用启发式算法得到一个确定的着色方案。该算法对于每一种顶点的排列顺序来说是最优的，但对于不同的排列顺序其得到的着色方案是不同的，因此要想得到最优解，就必须对图的n!种不同的顶点排列顺序均采用启发式着色算法进行着色，才可知道最优方案。当n较大时（如超过100个顶点），用目前的计算机进行运算是不现实的[8-10]。
此外，专家学者们在传统算法的基础上，创新了许多新的算法，例如混合顶点着色算法、启发式搜索蚂蚁算法、改进粘贴DNA算法、基于集合思想的着色算法等[10]，这些算法在不同的实际问题中都有良好的应用。Brelaz提出最大色度着色算法，其思路是尽早将度数高的的结点着色，因为在后面处理这些结点会很困难，同时，如果某结点有许多邻接点已着不同色，算法也应尽早处理该结点。在着色的同时，还要记录已使用颜色数，而且在图中删除已着色顶点及其关联边[11]。
由于停车位分配工作的复杂性，国内这方面的研究主要针对公共停车场，而对配送中心的停车场研究较少，对于配送中心停车场的研究具有重要意义。同时由于配送中心车辆使用的灵活性，造成停车位分配工作的复杂性。因此高效的精确算法可能性不大，启发式算法虽能快速解决问题，但对于解的质量无法保证，因此当前算法，均是求近似最优解。而本文在最大色度着色算法的基础上，设计出了顶点着色模型的着色算法，具有最逼近最优解的优点。
1.3课题的研究方法
本文主要通过对三个算法的设计，在着色理论以及图论的基础上，将停车位调度问题转化为一个着色问题，建立了停车位分配的顶点着色模型。解决了普通算法中解的质量不高从而造成停车场资源浪费的问题，求出了停车位调度问题的近似度很高的次最优解。
- 5 -
第一章 前言
1.4本论文的主要思路和预期目标
本论文研究了配送中心停车场的停车位分配问题。在配送车辆到达停车场的时间为已知的前提下，构建车辆使用停车位的时间冲突集合，以“先到先服务”为原则，将停车位分配问题转化为顶点着色问题，应用图论相关知识建立关于停车位分配的顶点着色模型。设计一种最大度优先算法确定适合某一时间段内每辆车的最佳停车位，使得配送车辆到达停车场时，能直接驶向最佳停车位，避免了选择车位的盲目性和滞后性。
并应用Visual Basic 程序语言设计了一个配送中心停车调度系统，实现用最少的停车位满足配送中心停车场的停车需求。有助于配送中心现代化程度的提高和发展，从而提高物流企业的服务水平和市场竞争力。
用该算法的目标是：进行车位分配时能充分利用停车场的资源，实现停车位的最佳配置，达到系统整体最优化。
本课题所采用的技术方法主要有：图的数学建模及着色算法、VB程序设计语言等计算机技术。
1.5本文主要的研究工作
第一章前言部分主要介绍了该课题提出的背景及意义、课题所用知识的研究现状，研究方法以及本课题的研究对象、目标和方法。
第二章主要介绍图的基本概念及性质、图着色、图的存储结构、图的数学模型以及图的算法，是求解配送中心停车场的停车位分配问题的理论基础。
第三章旨在说明配送中心的基本概念，包括配送中心的定义、分类、配送中心的工作流程及主要功能。
第四章指出停车位分配存在的问题，建立和求解顶点着色模型所需要的三种算法：时间冲突算法、分解算法、着色算法。为第五章算例的求解提供理论
根据。
第五章算例，用配送中心停车场停车位的算例，证明算法的有效性，以及证明可以使用最少的停车位满足停车需求。
- 6 -
第一章 前言
第六章停车调度的程序设计。设计具体的程序以及界面来实现停车场配送系统的功能。
第七章回顾全文，总结了为本论文所做的工作，并指出了待改进之处。
- 7 -