发布时间 : 星期一 文章基于图论的物流配送中心车辆调度系统设计与实现更新完毕开始阅读57171e1afad6195f312ba6ed
SHANDONGＵＮＩＶＥＲＳＩＴＹ ＯＦ ＴＥＣＨＮＯＬＯＧＹ
毕业设计
基于图论的物流配送中心车辆调度系统
设计与实现
学 院： 院
专 业： 学生姓名：
学 号：
指导教师：
2012年 05月
摘 要
摘 要
停车位分配问题直接影响着配送中心的运作效率与发展，成为企业界和学术界关注的热点话题。
本文通过分析配送中心停车场的运作情况，建立了停车场的顶点着色模型及其求解算法。通过构建配送车辆使用停车位的时间冲突集合，以“先到先服务”原则为基础，把停车位分配问题转化为顶点着色问题，并建立了相应模型。利用分解算法，停车位的利用效率得到改善。该算法的计算复杂度为O(n2)。通过将该算法应用于一个算例，得到了最优解。最后应用Visual Basic程序语言设计了一个配送中心停车位分配系统，有助于配送中心实现停车场整体资源配置的最优化与现代化程度的提高。
关键词： 配送中心，停车调度，图论，顶点着色，算法，Visual Basic
I
Abstract
Abstract
Gate 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 assignment 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 utilizing decomposed algorithm, it is possible to improve the gates? operation ability. The algorithm?s computational complexity is O ( n2). 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 gate 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
II
目 录
目录
摘 要 ........................................................................................................................... I Abstract ...................................................................................................................... II 目录 ............................................................................................................................ III 第一章 前言 ............................................................................................................ - 1 -
1.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 - 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 -
III