沈奕奕-毕业论文 - 图文

宁波理工学院

毕业设计（论文）

题 目 公共自行车站点规划模型研究

姓 名 沈奕奕 学 号 3110411048 专业班级 11信息与计算科学112班 指导教师 范良忠 学 院 信息科学与工程学院 完成日期 2015年 5月 15日

摘 要

2013年9月，宁波在全市首推公共自行车服务系统。为了让公共自行车站点在尽可能多的时段内处于理想状态，提升市民的满意度，本文运用逐步遍历、TSP问题、普里姆算法和多次优化对宁波市的部分站点进行了建模分析。然后通过实例验证了所设计的模型和算法，并得到了预期效果。证明了所用算法符合模型的求解，且通过该模型所求得的规划方案是合理的。

关键词：逐步遍历；TSP问题；最小生成树；普里姆算法；多次优化

I

Abstract

In September 2013, The public bicycle system is used in Ningbo. In order to make this system more efficient and promote citizen's satisfaction, we utilizes the traversal, TSP, Prim algorithm and optimization to analysis some public bike stations in Ningbo. Finally the examples verify the result of model and algorithm and they have been reached the expected effect. It is approved that all of the algorithms are fit with models. Using the planning scheme which proved to fit the model is reasonable.

Keywords: Traversal；TSP；Prim algorithm；Optimization

II

目 录

摘 要 ............................................................ I ABSTRACT ......................................................... II 第1章 绪论 ........................................................ 1 1.1 研究背景 ....................................................... 1 1.2 研究现状分析 ................................................... 2 1.2.1 国外研究现状 ................................................ 2 1.2.2 国内研究现状 ................................................ 2 1.3 论文研究方法 ................................................... 3 1.4 论文研究内容 ................................................... 3 1.4.1 论文的技术路线 .............................................. 4 第2章 公共自行车站点规划分析 ....................................... 5 2.1 公共自行车站点规划的必要性 ..................................... 5 2.1.1 公共自行车系统在时间上的局限性 .............................. 5 2.1.2 公共自行车系统在空间上的局限性 .............................. 6 2.2 公共自行车站点信息的采集 ....................................... 6 2.2.1 公共自行车站点位置信息的采集 ................................ 6 2.2.2 公共自行车站点实时数据的采集 ................................ 6 2.3 站点规划所需算法简介 ........................................... 6 2.3.1 TSP问题研究 ................................................ 6 2.3.2 普里姆算法 .................................................. 7 第3章 公共自行车站点规划模型的构建 ................................. 9 3.1 公共自行车站点规划描述 ......................................... 9 3.2 站点规划模型的构建 ............................................ 10 3.2.1 模型假设 ................................................... 10 3.2.2 符号定义 ................................................... 10 3.2.3 站点规划模型 ............................................... 11

III

3.2.4 站点分类 ................................................... 12 3.2.5 站点规划路线模型 ........................................... 13 3.2.6 价值模型 ................................................... 14 第4章 实证分析 .................................................... 15 4.1 宁波市公共自行车现状 .......................................... 15 4.2 实例分析 ...................................................... 15 4.2.1 碧云天小区北站点规划方案 ................................... 16 4.2.2 规划路线的分析 ............................................. 17 4.2.3 计算每条路线所需时间 ....................................... 19 4.2.4 价值比较 ................................................... 20 4.2.5 结果分析 ................................................... 20 第5章 总结与展望 .................................................. 22 5.1 论文总结 ...................................................... 22 5.2 展望 .......................................................... 22 参考文献 .......................................................... 23 致 谢 ........................................................... 25

IV

第1章 绪论

1.1 研究背景

本文旨在研究公共自行车站点规划模型——调度优化方法，并将优化结果再进行人工性优化，通过比较得到最好的规划模型。

当今社会，人们的生活水平越来越高，环保、低碳的生活渐渐成为人们健康生活的目标。随着城市公共自行车的普及，一个个成功的案例展现在我们的眼前。公共自行车租赁系统不仅对节能减排、减少环境污染、建设可持续发展型社会有重大的意义，又在一定程度上缓解了城市交通的压力，城市公共自行车将会是未来城市发展的重要区域。

但是，在公共自行车系统也存在着很多不足，主要是在高峰期不能满足用户的需求，所以对公共自行站点进行再规划是非常重要的。这样不仅能够提升整个城市公共交通系统的服务质量，还能更大限度的满足用户上下班高峰期对公共自行车的需求量。其具体意义体现在：

（1）提高了公共自行车系统的服务，使公共自行车系统能更大的满足用户的需求，这样就会有更多的人选择公共自行出行。目前存在的问题是用户在上下班高峰期不能即使借还车，这样的情况会让用户对公共自行车失去兴趣，同时增加了其他交通工具的压力，给城市交通带来负担。因此，对公共自行车站点进行再规划不仅可以提高用户对公共自行车的满意度，而且对缓解城市交通压力有重要的意义。

（2）现在拥有私家车的家庭越来越多，汽车尾气排放造成环境的污染也越来越严重。这严重威胁到了我国市民的身体状况，而且不符合节约能源和可持续发展的趋势。而城市公共自行车即节约能源又保护环境，最重要的是能缓解交通压力。所以对现在公共自行车系统进行科学的规划很重要。如果一味的增加公共自行车站点点和自行车的数量，这样会浪费更多的人力、物理资源。因此，对公共自行车站点规划模型的研究，不仅可以节约城市资源，而且可以更好的满足用户需求，让更多人的选择公共自行车。这样又进一步节约了能源和保护了环境。

1

（3）为政府或者公共自行车的承包公司了解当前的公共自行车系统的不足，为他们提供指导和建议。

1.2 研究现状分析

国内外对公共自行车的现状和未来发展都很看好以及重视，许多学者在研究公共自行车系统方面有许多见解和想法。

1.2.1 国外研究现状

国外对公共自行车的研究有公共自行车网络、信息系统等各个方面。具体情况如下。

Pinaud,Antoine和SantosCanals,Mare在“Copenhagen:how bicycles can become an efficient means of public transportatio”(2006)中指出自行车与公共交通都是城市的重要元素,哥本哈根城市,将自行车交通与公共交通两者结合起来,创建一个新的系统[1]。

Krykewycz,Gregor R提出了采用GIS进行对公共自行车系统网络进行分析，从而确定公共自行车系统的主要服务区域，并采用公共自行车系统的监测数据推算出公共自行车路径的分流比率；最后，在前述研究的基础上估算各个自行车服务区域自行车路径的分流比率[2]。

Kaltenbrunner Andreas等通过分析巴塞罗那公共自行车系统的使用情况，计算出了各公共租赁站点需要提供的自行车数量，并采用预测方法提前预测了任意一个自行车租赁点的公共自行车数量[3]。

Maria Bordagaray,Angel Ibeas等为了实现公共自行车系统的有效管理，及其其可持续的流动性，提出了模拟系统中使用者所感知的质量标准，并针对改变单个属性的情况，文章将采用有序的概率模型来校对在整个服务质量感知的改变[4]。

1.2.2 国内研究现状

国内对公共自行车的研究方面有很多大致可以分为公共自行车租赁点方面、运行条件、机制和政策方面、信息系统方面、综合评价方面和公共自行车调度方面。

2

具体情况如下。

李黎辉等提出了公共自行车租赁点的布局思路，并将自行车租赁点划分为五种类型，分别为公共交通租赁点、大型居住区租赁点、公共基础设施租赁点、校园租赁点以及旅游观光租赁点[5]。

潘海啸等指出若要较好的引导城市PBS的发展，政府首先应制定一个条理清晰的发展目标，并制定相应的扶持政策，并充分利用企业的技术和成本的优势，鼓励引进私人企业投资建设和运营的模式[6]。

Rongliang Luo设计了基于谷歌地图的公共自行车系统。该系统可以实时显示租赁站点的位置和该租赁点的现状车辆数，以及租赁点处管理人员的状态。

Xingcai Liu等运用SWOT方法分析了城市公共自行车的未来发展趋势，并设计了基于群众满意度的指标体系[8]。

Meiqing Luo提出了政府或者企业需加强公共自行车调度的相关管理机制，并构建了调度信息的系统框架，同时，根据各个租赁点的供给和需求的改变来调整各个租赁点的公共自行车数量，最终实现公共自行车的供需平衡[9]。

[7]

1.3 论文研究方法

本文尝试对城市公共自行车站点再规划，使得城市公共自行车系统在运营成本和客户需求都达到最优。并以宁波某区域的公共自行车站点的信息数据作为研究数据。在开始研究之前必须要先了解公共自行车站点规划的必要性和目的。本文以宁波某区域的公共自行车站点为研究对象。首先借助宁波公共自行车系统，获取研究所需信息数据，通过学习TSP问题和普里姆算法，构建公共自行车站点规划模型，然后再利用所得数据进行实证分析，并对所建模型进行价值评价。

1.4 论文研究内容

（1）公共自行车站点规划分析

通过对公共自行车的发展以及现状的分析，提出公共自行车站点规划的必要

性，分析公共自行车站点规划所需要的信息数据以及对所需算法的学习。

（2）公共自行车站点规划模型的构建

通过所获取的站点信息先为每个站点设计一个最优规划方案，然后得到站点

3

之间的网状图，将规划模型拟化为TSP问题，并用普里姆算法解决该问题，最后对所得模型进行优化。

（3）实证分析

将宁波某区域的公共自行车站点作为算例进行分析，对文章中提出的模型和算法进行了验证。结果表明本论文建立的模型和所采用的算法是可行的，且达到了一定的预期效果。

1.4.1 论文的技术路线

本文对公共自行车系统的现状提出一套解决现存问题的公共自行车规划方案，具体的技术路线如下图所示。

结果与展望（第五章） 实证分析（第四章） 公共自行车站点规划模型的构建 （第三章） 公共自行车站点规划分析（第二章）

图1.1 技术路线图

4

第2章 公共自行车站点规划分析

2.1 公共自行车站点规划的必要性

公共自行车站点规划就是在运营成本尽可能小的情况下，对各个站点的公共自行车进行有效调配，最终使得整个城市公共自行车系统在时间和空间上达到均衡，使得各站点尽可能长的时间处于最佳状态（即可借可还状态）。

公共自行车系统是对个体自行车的升级，更方便，省心，又能有效的解决“最后一公里”的问题，公共自行车系统在缓解城市交通上有很重要的作用。由于公共自行车系统是静态的，所以我们需要解决公共自行车系统在时间和空间上的局限性。

2.1.1 公共自行车系统在时间上的局限性

公共自行车系统在时间上的局限性主要表现为时间的分布特性、潮汐性和在一定时间段内的停车特性。

（1）公共自行车系统的时间分布特性主要表现为早晚高峰和中午的两次小高峰。通过对宁波公共自行车使用情况的相关调查，发现宁波公共自行车使用的早高峰出现在7:00～9:00，中午主要集中在11:00～1:00，晚高峰主要集中在4:00～6:00。

（2）公共自行车系统的潮汐性主要表现为高峰期公共自行车的整体流向。在早高峰阶段，自行车大部分是从居民区流向公交站点或者是商务大厦，而晚高峰时期则是逆向流回，所以自行车的流向有很强的潮汐性[10]。

（3）公共自行车系统在一定时间段内的特车特性主要表现为在高峰期，短时间内会有大量自行车涌入某个站点，这样反而会加重该站点的交通压力，如果没有合理的规划，反而加深了交通压力。

5

2.1.2 公共自行车系统在空间上的局限性

公共自行车站点有较强的固定性且占地的局限性，每个公共自行车站点间有一定的距离，且由于可用地的限制，公共自行车站能容下的自行车数量有限，在高峰期会出现就近站点都是处于饱和或空缺状态，导致用户无法在短时间内借到或归还自行车。这类问题一方面降低了用户对公共自行车的满意度，另一方面反而加重了部分的确的交通压力。

2.2 公共自行车站点信息的采集

2.2.1 公共自行车站点位置信息的采集

本文需要对城市某区域内的所有公共自行车站点进行规划。通过宁波公共自行车系统网站，获取公共自行车的遍布位置，并将所取范围内的所有站点位置转换为坐标图。

2.2.2 公共自行车站点实时数据的采集

公共自行车站点实时数据的采集包括公共自行车站点当前车辆数、停车位数量等。通过长期记录的数据，计算得到的每个时间段每个公共自行车站点所需调配的自行车数量，统计每次调配所需的总数量和每个站点所需车辆，反馈给工作人员，方便工作人员快速准确的开展工作。目前，已征得宁波公共自行车所在公司的同意，获得了宁波某区域每个时间段公共自行车站点的实时数据。

2.3 站点规划所需算法简介

2.3.1 TSP问题研究

旅行商问题(T raveling Salesman Problem,简称TSP)是一个易于描述但难于解决的著名难题之一。TSP问题可描述为: 已知n个城市各城市间的距离,某一旅行商从某个城市出发访问每个城市一次且仅一次,最后回到出发城市,怎样安排才使

6

其所走路线最短[11]。

（1）TSP的数学模型 TSP 问题的数学模型如下[12] :

对于城市V={v1,?,vn}的一个访问顺序为T={t1,t2?,tn}, 其中

ti=V(i=1,?,n)，而且tn+1=t1,则问题mind∑ntiti+1T∈Ωi=1，其中Ω为这n个城市不重复

排列的所有可能回路。

（2）求解TSP 问题的常用算法（蚁群算法）

蚁群算法(Ant Colony Optimization,简称ACO)由意大利学者Dorigo M等在1996年首先提出。该算法通过模拟蚂蚁的觅食行为,蚂蚁觅食的时候会在所走过的路径上留下信息激素,同时信息激素会随时间而挥发。一条路径走过的蚂蚁越多,留下的信息激素越多；反过来,信息激素浓度高的路径上会吸引更多的蚂蚁。通过这种正向反馈,最终将找到一条最优路径。为了避免蚂蚁两次走上同一条路径( 非法路径),为每个蚂蚁设置一个禁忌表以记录它已走过的路径。其算法可描述如下

[13]

:

Step 1 初始每条路径上的信息激素浓度。

Step 2 把m只蚂蚁随机地放置在n个城市上,并把已访问的城市写入禁忌表。

Step 3 如果第k(k=1, 2, ?,m)只蚂蚁还有未访问的城市,则该只蚂蚁根据概率决策选择下一个城市(i是该蚂蚁当前所在城市,j < ( N - 禁忌表),pij是一个由城市i到城市j之间的路径长度和信息激素浓度构成的函数),把选择的城市j写入禁忌表, 直到所有的城市访问完。

Step 4 计算k(k=1, 2, ?,m)条路径的路径长度,选出本次最优路径。 Step 5 根据本次蚂蚁的访问情况更新每一条边上的信息激素浓度, 清空禁忌表。

Step 6 判断是否满足结束条件,如果不满足, 转到Step 2；否则结束。

2.3.2 普里姆算法

普里姆算法就是从一个最小的连通子网开始，逐步扩大到最小生成树。为了

7

具体描述这个生成步骤，暂时引入一些名称：上述的连通子网称为入选子网，它最初的顶点集只包含一个顶点，称为始点，边集是空集。入选子网以外的顶点组成候选集。对候选集中的一个顶点，我们把入选子网的顶点与该顶点的关联边称为特殊边，该顶点对应的最短的特殊边为候选边。每一个候选集的顶点都对应一条候选边，候选边的集合称为候选边集。在候选边集中选择一条最短的，把终点和边分别加到入选子网的顶点集和边集。入选子网扩大了，候选集缩小了，候选边集需要更新，然后再选出最短的，加到入选子网。依此类推，直到入选子网的顶点集等于连通网络的顶点集[14]。 普里姆算法的数学模型：

设 G=(V,E)是连通网络，V={v0,v1,?,vn}。不失一般性，设v0为起始点，U 是入选子网的顶点集，T 是入选子网的边集。

U ={v0};T =Φwhile(U ≠V ){ c( u', v')=min∪{min∪c(u,v)}v∈VUu∈U

T=T∪{(u', v')} U=U∪{v'}}

8

第3章 公共自行车站点规划模型的构建

3.1 公共自行车站点规划描述

2013年9月22日，宁波公共自行车系统正式开通运营，以缓解行路停车难、解决“最后一公里”交通问题。

公共自行车借车、还车环节需在公共自行车站点完成。然后公共自行车站点很多情况处于不理想状态。此时工作人员可通过上架或下架操作使该公共自行车点恢复理想状态。若站点满架，则下架部分自行车置于附近；若站点空架，则将部分置于附近的自行车上架。

虽然宁波公共自行车系统的有些站点设立了值守点，并采用了走动式服务管理等措施，但这样盲目的管理措施和随机设立的值守点在人力、物力和财力上造成了很大的浪费。因此需要通过构建模型获得一套更合理的公共自行车站点规划方案。

首先假设每个站点每个时间段的需求量是固定的。通过调查掌握每天每个整点公共自行车站点的实时数据，统计出每个站点在每个时间段的借车、还车数据。试给出工作人员到该站点的时间以及所需调整的自行车的数量，使得一天内需对该点进行管理的次数最少。假定一天内到该服务点的次数不超过两次，并使得服务点处于理想状态的时段尽可能长。然后选择宁波的某一区域，确定巡逻管理该区域的工作人员数量及规划方案，使该区域内的公共自行车站点尽可能保持 理想状态，并在高峰期能最大层度的满足用户的需求，且人力成本较小。

为了求得某公共自行站点的管理方案，先对数据分析，对各时刻的用车净需量累计，计算得到该站点各时刻的剩余车辆，找到所有不满足理想状态的不理想点。这些不理想的点肯定存在这某一时刻，对其撤下或增加N辆车后，能使得之后处于不理想状态的时段达到最小。用c++遍历所有不理想点，对其撤下或增加的车辆数N进行遍历，求得去一次的最优管理方案，模拟出管理后的数据，对其进行第二次遍历，求得去二次后的最优管理方案，且最终管理次数不超过两次。 得到每个站点的管理方案以及站点间的坐标图后，将问题拟化为TSP问题来

9

进行分析。首先结合实际情况对区域内各个点进行了分区，并给每个区域分配不同的时间段去管理。接下来通过普里姆算法来生成连通成环的最小生成树来求解最短路，通过此算法，对每块区域的进行了路线规划。通过规划后的结果，再对路线进行手工优化，并且计算出通过每条路线去管理各个站点的时间都能在所给时间段内完成。最后通过建立价值模型来分析手工优化前与优化后的路线价值。

3.2 站点规划模型的构建

3.2.1 模型假设

公共自行车系统有太多的不定的因素，若考虑全部因素，则会导致建立的数学模型非常复杂，且难以求解。通过公共自行车规划分析，针对宁波市鄞州区公共自行车进行了全方位考察，并结合实际情况，提出如下假设：

1、该区域内每天每个站点自行车使用量基本稳定

2、便于模型算法的设计，假设该区域内工作人员对公共自行车站点调配，都是从中心站出发且最终回到中心站。

3、在对每个站点调配公共自行车时，所花时间不超过两分钟，且对每条路线上的公共自行车站点规划一次所花时间不超过九十分钟，否则该规划路线视为不合理。

4、工作人员在对公共自行车站点规划时的行驶速度为50km/h。 5、假设每天每个站点需要调整的公共自行车数量固定不变。 6、每天每条路线的规划次数不超过两次。

7、在对站点进行规划时，每条路线上两个人一组开展工作。

以上假设均结合了公共自行车系统的实际情况，且为模型构建提供了方便。

3.2.2 符号定义

根据上诉分析，所需构建的模型主要分为两部分：第一得到每个站点的规划方案；第二构建整块区域的规划路线。

为了方便模型的构建，本文定义如下符号：

Xi：表示从零点开始第i个整点该站点的车辆剩余量

10

X：表示该站点的总容量

Pj,Pz：表示不理想状态点的位置

J：表示不理想状态的个数

nixzf：表示一个第i个J×24矩阵的第z行的第f列 xzf：表示z行Xi

count[i][z]：表示第i个矩阵中每行处于不满足状态的个数的最小值 Dab：表示ab两点间的近似实际最短距离

N：表示每条路线上的公共自行车站点个数

Hi：表示第i点的不健康度

Zi：表示第i点的实际可租自行车辆数 Zi：表示第i点的最佳可租自行车辆数 Vi：表示去第i服务点的价值

'3.2.3 站点规划模型

在上诉的条件下，以获取每个站点的管理方案为目的，构建第一个模型：

Step1：找到i从1遍历到24得到每个处于不理想状态的点的位置，储存数组

place中即：

如果Xi<1orXi>X，那么Pj=i （3.1）

Step2：从第一个不理想位置遍历到最后一个不理想位置，若第Pz个位置不理想状况是满车状态，那么就将该位置以后的数据全部减去1（表示拿掉一辆车），即

n1xzf=Xf-1 f∈(pz,24),z∈(0,J) （3.2）

若第pz个位置不理想状况是空车状态，那么就将该位置以后的数据全部加上1（表示加上一辆车），即

n1xzf=Xf+1 f∈(pz,24),z∈(0,J) （3.3）

在遍历后，再次遍历

如果n1xzf>X，那么 n1xzF=X-[n1xzF-(n1xzf-X)],F∈(f,24)；

11

如果n1xzf<0就记成n1xzf=X-[n1xzf+(0-n1xzF)],F∈(f,24)。（n1xzf只肯能是0~X之间的整数）。

Step3：循环Step2，令其减去或加上i（i∈(2,X)），且保存在数组nixzf中。 Step4：得到J个J×24的矩阵,每一行表示某时刻增加或减少i（i∈(1,X)）辆车后的情况。对这J×J组数据进行分析，将每组不再理想状态下的情况记录，即

[i][z]中i,z∈(0,J)在count中找对于 nixzf>Xornixzf<1的个数保存到count到一个最小的数，该最小值的位置就是i和z就是指i时刻调整z辆车。

3.2.4 站点分类

开始为工作人员规划工作路线之前先对各个点进行分区，因为在市区，小区附近和郊区的自行车租借情况都不大一样，所以需要对这些点进行分类。通过对整个宁波公共自行车系统的分析，得到以下结论：

1.工作区域：有许多人的上班的终点在这片区域，所以，上班时间段还车的人可能非常苦恼导致；相反在下班时间段，下班的人，会因为在这个区域内借不了而车感到困扰，所以在7点到10点和16点到19点，这两段时间对这部分区域的公共自行车服务点进行管理，从而使这些公共自行车服务点竟尽可能的满足需求。 2.小区区域：根据实际情况，早上年轻人因为工作原因，老年人可能也会去购物，所以，在早上的时间里小区附近的公共自行车服务点可能会比较缺车；而晚上恰恰相反，年轻人大都下班回家，所以这时小区附近的服务点可能会爆棚；所以在6点到9点和17点到20点，这两段时间对这部分区域的公共服务点进行管理。 3.平淡区域：因为地点特殊，自行车的还车和租借的需求量会相对比较小，为了和上面两个区域进行交错对各个点进行管理，所以选择在11点到15点，这段时间来对郊区的公共自行车服务点进行管理，从而尽量满足市民的需求。

综上所述，将所有站点分为三类，即将所选区域的站点分成三条路线，但因为有些站点会出现在其他规划路线上，所以还需要对所分类后的结果进行人工优化。

12

3.2.5 站点规划路线模型

站点分类后，得到整块区域所有站点的坐标图，将规划路线拟化为TSP问题，通过构建最小生成树TSP方案模型来确定整个区域的规划线路。

因为街道都是比较规整的，几乎都需要过一个直角才可到达，通过抽样计算，发现站点之间的最近路程大约在站点直线距离的际最短距离近似值为：

1+3倍，于是得到两点之间的实2Dab=(1+3)(xa-xb)2+(ya-yb)2 （3.4）

2因为需要节省人力成本，所以将为每个区域制定一套合理的路线方案，用最小生成树解决来解决不重复的环形TSP问题。

一棵生成树是连通图的一个极小连通子图，它含有连通图中的全部n个顶点，一个连通图的最小生成树，是此图所有生成树中代价和最小的一棵生成树。它与TSP问题所求路径有许多相同之处，它们都必须经过所有的n个顶点，n个顶点之间都是相互连通(但在TSP问题中，路径为回路)，并且路径长度为最短。因此，对于TSP问题的求解，可以借助于最小生成树的求解方法

[15]

。

本文决定用普里姆算法来求解最小生成树。算法的描述为：在含有n(n>1)个顶点的完全连通无向图中，任意选择一个顶点Vi作为起始点，在与顶点Vi相关联的n-1条边中，选择一条权值最小的边ei，此边可连接Vi及图中另一个顶点Vj，然后在与Vi或Vj相关联除ei以外的所有边中，选择权值最小的边ej，ej又可连接另外一个顶点(边的选则还要保证树中没有环的产生)。

按照此方法，选定起始点Vi（即公共自行车站点的中心站），然后形成一棵顶点完全连通的最小生成树，这棵树就是所需的规划路线。

由于不同类站点之间可能相距很近，所以得到规划路线后，需再对其二次优化，即人工优化。

通过上述方法得到每条规划路线后，计算每条路线所需时间，要求每条规划路线所花的时间能在规定时间内完成，即：

60Dab+2N<90 （3.5） 30000∑

13

3.2.6 价值模型

为了进一步的研究各个路线是否具有较大的价值，建立一个可以初略表示该站点的不健康度的模型。因为各个站点无论是不能归还状态还是不能借出状态都是不理想状态，所以将站点剩余车辆等于该站点总车辆数的一半的情况视作最健康状态，而距离这个状态越远，表示该站点越不健康。得到站点不健康度Hi的关系式：

'Hi=Zi-Zi （3.6）

然而这个不健康度就是来表示要去的需要管理的量，所以价值Vi就可以表示为：

Vi=HiLi （3.7）

（Li表示去i站点的距离）

而整个方案线路的总价值可以表示为：

V总H∑=L总

i （3.8）

14

第4章 实证分析

4.1 宁波市公共自行车现状

宁波公共自行车系统已经开通运营且，我们选取了宁波鄞州区内某区域的公共自行车站点作为研究对象，该区域内的站点分布情况如图4.1所示。

图4.1 宁波市鄞州区内某区域内公共自行车站点分布图

所选区域内，共有公共自行车站点68个，其最终目标是建立 1中心站，并将

这些站点划分为 3 类，构建3条规划路线，由工作人员按所得路线对该区域内的公共自行车站点的进行调整。

4.2 实例分析

根据上述分析的公共自行车规划模型，首先要确定每个站点的规划方案，由于一共有68个站点，所以仅以碧云天小区北站点为例。且每个站点都有各自的数字代号，碧云天小区北站点的数字代号为070。

15

4.2.1 碧云天小区北站点规划方案

通过调查统计，计算的得到一个月内得到碧云天小区北站点（070）每个时间段借车的净需求量的平均值(每一个小时表示一单位00:00-23:00)，如下图4.2所示。

图4.2 碧云天小区北站点每天借车净需求量

图中可以看出该小区借车的高峰期为早上7:00到9:00，还车的高峰期从18:00开始。通过对070站点一个月数据的统计，得到070站点每时刻剩余车辆Xi（(每一个小时表示一单位00:00-23:00），如下图4.2所示。

图4.3 碧云天小区北站点每时刻剩余车辆

从图4.3中可以得到从9:00开始，该站点处于不理想状态，对该站点进行第三章模型中的四步遍历，得到第一次为9:00去该站点，并增加5辆车，第二次为19:00去该站点，并撤下7辆车。

16

4.2.2 规划路线的分析

首先将所选区域的西南角（图4.4的左下角）作为坐标原点，将宁波公共自行车系统中给出的公共自行车站点在图中的位置坐标（用地图上的像素点表示）记录下来，新建一张坐标图，如图4.4所示。

图4.4 公共自行车站点坐标分布图

通过上述计算，获得每个点的规划方案并分类。如碧云天小区北站从地域和所得的最佳规划方案都可以看出该站点属于小区类。将所有站点按规划时间和站点的属性将这些站点分为3类，并选取四明三江超市站点（000）作为中心站。如图4.5所示

图4.5 公共自行车站点分类坐标分布图

17

图4.5中绿色的点表示平淡区域，这些站点的基本能自身保持借还平衡，所以每天只需去规划一次。紫色的点表示小区区域，红色的点表示工作区区域，这些站点每天需要规划两次，且时间都在早上和傍晚。

然后根据站点规划路线模型以及所获的的站点坐标图，利用MATLAB求解，得到各个区域的一个较优的回路方案，如图4.6所示。

平淡区：000→053→026→021→022→023→0164→084→081→002→066→009→045→039→094→056→034→143→142→114→051→087→088→000

工作区：000→089→027→085→086→028→009→008→075→025→024→161→163→162→017→077→106→083→076→012→013→015→014→000

小区：000→030→029→032→143→115→054→144→038→116→032→035→033→035→036→037→092→079→080→078→131→082→019→018→011→000

图4.6 公共自行车站点规划路线

上图中黄色线段连接而成的环形回路表示每次去管理工作区区域的站点路线，红色线段连接而成的环形回路表示每次去管理小区区域的站点路线，蓝色线段连接而成的环形回路表示每次去管理平淡区域的站点路线。

通过图4.6中的规划路线，可以看到每个方案的路线都会出现几个其他方案的坐标点，如果将某些坐标点纳入这个路线中，可以节省许多路程，于是对它们进行了再次优化，得到的结果如图4.7所示。

18

平淡区：000→053→026→021→022→023→164→084→081→131→002→066→009→045→039→034→143→142→114→051→087→088→000

工作区：000→030→029→089→027→085→086→028→009→008→075→025→024→161→163→162→073→106→013→015→014→000

小区：000→032→143→115→055→054→144→038→056→094→116→033→035→036→037→092→079→080→078→082→019→018→017→083→011→010→076→000

图4.7 优化后公共自行车站点规划路线

4.2.3 计算每条路线所需时间

(1+3)将各个路程上的站点带入公式Dab=(xa-xb)2+(ya-yb)2，计算得出

2（地图原图标量是125像素长度为500米）：

S平淡区=18435.93mS工作区=11010.94m S小区=16790.62m考虑到管理每个点的时候会需要时间，通过调查得知每个服务点的管理时间不会超过2分钟，所以将每个站点的管理时间记作2分钟。在市区内有部分公路限速50km/h，所以将管理者在各个服务点来回的速度记作50km/h。

19

18435.93×60+21×2=64.12min5000011010.94T工作区=×60+20×2=53.21min50000 16790.62T小区=×60+26×2=72.15min50000T平淡区=

上述结果可以看出每一个方案路线都可以在九十分钟以内完成所有工作，而有重复时段的区域只有繁华区域和小区区域，所以仅仅需要两组人员（四个人）就可以合理的管理所规划的区域了。

4.2.4 价值比较

利用得到的模型计算价值比较最后方案优化后与优化前的好坏。为了得到每个站点各个时刻的可租借量，抽取9月30日该区域的公共自行车站点的实时数据，通过获得的数据分别配合前面通过程序规划的路线和优化后的路线，带入价值模型中进行计算，最后比较两者值的大小（因为数据时候实时变化，将每条路线所经过的时间里不健康度最大的值来进行计算）。

74=0.00418435.93136.5+100.5V工作区==0.011 11010.94×295+75V小区==0.00516790.62×2V优化后=V平淡区+V工作区+V小区=0.020V平淡区=通过计算，优化前的价值

1'''V优化前=（V平淡区+V工作区+V小区）=0.017

3可以明显的看出优化后的线路比优化前的线路总价值更高，所以优化后的路线还是比较成功的。

4.2.5 结果分析

首先通过遍历的方法找到了每个点的规划方案，即去该点管理的时间，得到结果，且所得结果与公共自行车系统现状分析的管理时间吻合，所以该方法是可

20

行的。

然后通过站点分类，将问题拟化成TSP问题，用普里姆算法来生成连通成环的最小生成树来求解最短路，求得不同类别的站点的规划路线。并将所得路线再次优化。确定每条路线上的站点规划所需时间都能在指定时间内完成。最后通过价值模型，证明优化后的路线更佳。

总的来说，本文所设计的规划模型是成功的。通过最短规划路径来降低规划所需时间和运行成本，并使得该区公共自行车站点能最大程度的满足市民的需求。

21

第5章 总结与展望

5.1 论文总结

公共自行车系统在我国已经很普及，但是由于公共自行车系统在空间和时间上存在许多问题，导致公共自行车系统的价值不能更好的被展现。因此本论文研究公共自行车站点的规划问题。首先了解公共自行车系统的现状，以及所需解决的问题。然后确定解决问题的步骤，并确定建模所需的算法。然后开始建模和分析。最后采用实例，验证模型和算法的可行性。

5.2 展望

随着城市的发展，公共自行车系统将成为城市公共交通体系中重要的一部分。不但能缓解交通压力，而且绿色环保，又能节约能源，公共自行车系统逐渐成为交通规划和城市发展领域的重点研究对象。但由于每个城市的发展情况和交通情况的都不一样，所以公共自行车系统只能以城市或更小的地域范围进行研究。不过近年来，国内外在公共自行车系统研究方面已经取得一定的成果，当然仍然存在很多有待改善的方面。

纵观全球，公共自行车已经快有50年的发展历程了，公共自行车系统的确在慢慢的进步，慢慢的完善当中。现阶段对公共自行车租赁点选址规划的研究已经很丰富而且很完善了，但由于公共自行车的流动性很大，所以在空间上的分布上会出现不均衡导致在高峰期无法满足市民需求，由此，公共自行车调度应运而生。而对于公共自行车系统站点规划模型的研究即公共自行车的调度优化的研究还处于萌芽阶段。深化公共自行车站点选址规划和调度优化的方法，并创新公共自行车系统运营管理的体制和保障措施，可以更良好的促进公共自行车系统的发展以及城市公共交通的发展。

展望未来，公共自行车将会是更多人出行的选择，无论城市还是乡镇都会普及公共自行车，公共自行车系统会更加完善，公共自行车的调度优化方法以及管理模式会更加完美。

22

参考文献

[1] Pinand, Antoine&Santo Canals, Mare. CoPenhagen:how bicycles can become an efficient means of Public transportation[J]. Denmark:Roskilde University,2006:109-117. [2] Krykewycz Gregory R, Puchalsky Christopher M, Rocks Joshua. Defining a Primary Market and Estimating Demand for Major Bicycle-Sharing Program in Philadelphia,Pennsylvania[J]. Transportation Research Record. Octobe,2010:117-124. [3] Kalten brunner Andreas, Meza Rodrigo, Grivolla Jens. Urban cycles and mobility patterns: Exploring and predicting trends in a bicycle-based public transport system [J]. Pervasive and Mobile Computing,August,2010:455-466.

[4] Maria Bordagaray, Angel Ibeas, Luigi dell’Olio*. Modeling user perception of public bicycle services [J]. Procedia - Social and Behavioral Sciences, 2012:1308-1316. [5] 余敏,张秀英. 基于统计分析的公共自行车服务系统研究[J]. 郑州铁路职业技术学院学报,2014(3):14-19.

[6] 邱小勇. 广州市公共自行车发展探讨[J]. 城市交通. 2011(8):57-60.

[7] Rongliang Luo, Yunru Shen. The Design and Implementation of Public BikeInformation System Based on Google Maps[C]. Proceedings of the 2009 International Conference on Environmental Science and Information Application Technology,2009:156-159.

[8] Xingcai Liu, Rui Song, Li Zhen and Yang Sun. Thought of Bicycle Traffic Development under Low - Carbon Background[C]. Proceedings of the Third International Conference on Transportation Engineering,2011:3280-3285.

[9] Meiqing Luo, Shunying Zhu. Research on the Leasing Model and Efficiency Improvement of Public Bicycles in Wuhan[C]. Proceedings of the 1st International Conference on Transportation Information and Safety,2011: 957-963.

[10] 惠英,孙天宇,赵杰. 外围城区公共自行车系统使用特点和规划对策研究[J]. 建设科技, 2014(15): 22-24.

[11] 王剑文,戴光明,谢柏桥,张全元. 求解TSP问题算法[J]. 计算机工程与科学, 2008(30): 72-74.

[12] 喻菡. 遗传算法的求解TSP的研究: [硕士论文][D]. 成都:西南交通大学, 2006.

23

[13] 谷文祥,李向涛,王春颖,李国媛,殷明浩. 一种求解TSP问题的混合算法[J]. 东北师大学报:自然科学版, 2011,43(3):60 -64.

[14] 普里姆算法和迪克斯特拉算法的比较[J]. 计算机教育, 2008(21):53-96. [15] 姚建华,杨成涛. 用最小生成树解决TSP问题[J]. 湖北师范学院学报:自然科学版, 2004,24(4):52 -56.

24

致 谢

本论文在范良忠老师的悉心指导下得以顺利完成。从论文的选题、模型算法和主要内容的研究直至论文的最终完成，都受到了范老师耐心细致的指导，他总是细心地帮我检查论文，指导我修改论文，使我从中受益匪浅。大学四年里，范老师一直兢兢业业，对任何事情都是亲历亲为，认真负责。不仅传授我知识，还传授我们做人的道理。

同时，我还要感谢我们专业的所有老师。大学四年里，他们给我的无私帮助和教导我将终生难忘。然后我还要感谢我的大学同学，是你们陪伴我度过了轻松快乐且令人终生难忘的大学四年时光。最后感谢我的寝室室友，谢谢你们四年来带给我的帮助和欢笑、支持与鼓励。

25

本文来源：https://www.bwwdw.com/article/h13p.html