XX市公共自行车租赁点间自行车调度方案研究.doc

摘要：本论文主要是研究徐州市公共自行车运输调度问题，如何制定出一套切实可行的运输调度方案，实现在公共自行车使用高峰期过后，对各个租赁点的公共自行车进行有效调度，以此满足市民对于公共自行车的实际需求。我们通过区域划分，将某一区域分配给制定的调度员，让调度员驾驶一辆运输车在该区域内的各个站点之间收集并分配公共自行车，完成调度任务。而在此过程中的重点就是如何合理地制定运输车的行进路线，遍历各个站点，才能有效的完成收集工作，并以此将运输车所装载的公共自行车分配到需求点处。

在分析了运输环境后，我们就将实际问题简化成为一个单目标非线性规划模型。在此数学模型中寻找到一条最短的行进路线，而此行进路线必须要满足诸多的实际约束条件。这个模型类似于问题，属于难问题，我们不易得出其真正的最优解，因此本文采用启发式搜索方法来求该问题的近似最优解，使得能得出切实可行的实际运输方案，以满足徐州市公共自行车运输调度问题的需要。

针对某一区域进行分析，结合运输车的负荷量、各个站点的位置，各站点间的距离及公共自行车数量，利用Floyd算法可以得到任两个站点之间的最短路径，然后采用启发式搜索方法得出该区域的行进路线的一个近似最优解，也就是：自站点30出发，经站点30、15收集自行车，依次于站点14、3、21分配，再经站点23、16、15收集自行车，于站点4、17分配，经站点28、27收集，于站点29、19、18分配，经站点15收集，于站点11、9分配，经站点7、6收集，于站点8分配，经站点1收集，于站点10、5分配，经站点22收集，于站点26分配，经站点2收集，于站点13、12分配，经站点20收集，于站点24分配，最后回到出发点30。

关键词：自行车运输调度；单目标非线性规划模型；启发式搜索；Floyd算法；近似最优解

目录

摘要

Abstract

1 绪论-1

1.1 研究的背景与意义-1

1.1.1 研究背景-1

1.1.2 研究的目的和意义-1

1.2 相关研究方法-2

1.3 本文研究内容-3

1.4 本文结构安排-3

2 运输问题解法的相关理论-5

2.1 相关概念-5

2.1.1 运输问题-5

2.2 运输问题分类-5

2.2.1 一般运输问题-5

2.2.2 网络运输问题-5

2.2.3 最大流量问题-5

2.2.4 最短路径问题-6

2.2.5 任务分配问题-6

2.2.6 生产计划问题-6

2.3 运输问题的相关解法-7

2.3.1 图上作业法-7

2.3.2 表上作业法-7

2.3.3 启发式算法-7

2.3.4 贪婪算法-8

2.3.5 蚁群算法-8

3 徐州市公共自行车运输环境分析-9

3.1 徐州市公共自行车配备状况描述-9

3.1.1 徐州市公共自行车站点配备特点-9

3.1.2 徐州市公共自行车站点分布情况-10

3.2 徐州市公共自行车调度方式分析-11

3.2.1 徐州市公共自行车站点运输方式-11

3.2.2 徐州市公共自行车站点运输路线-11

3.2.3 徐州市公共自行车站点运输时间-11

4 徐州市公共自行车调度问题分析-13

4.1 问题分析-13

4.1.1 问题重述-13

4.1.2 问题分析-13

4.2 数学模型分析-14

4.2.1 模型准备-14

4.2.2 模型相关问题的基本假设-15

4.2.3 模型的建立-15

4.3 数学模型的求解-18

4.3.1 启发式搜索方法-18

4.3.2 启发式搜索方法求运输问题的过程-21

5 调度问题方案的优化分析-32

5.1 算法优化分析-32

5.2 算法优化方法-32

6 结论与不足-34

6.1 结论-34 

6.2 本文的不足之处-35

参考文献-36

附录-37