《公共自行车系统自然租赁需求预测与多目标调度方法_吴满金.docx》由会员分享，可在线阅读，更多相关《公共自行车系统自然租赁需求预测与多目标调度方法_吴满金.docx（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、硕士学位论文 论文题目： 公共自行车系统自然租赁需求预测与 _ 多目标调度方法 _ 作者姓名 _ 吴满金 _ 指导教师 董红召教授 学科专业 _ 机械工程 _ 所在学院 机械工程学院 提交日期 2015年 4月 浙江工业大学硕士学位论文 公共自行车系统自然租赁需求预测与多目标调度方法 作者姓名：吴满金 指导教师：董红召教授 浙江工业大学机械工程学院 2015年 4月 Dissertation Submitted to Zhejiang University of Technology for the Degree of Master EVALUATION ON NATURAL RIDE DEM
2、AND AND DYNAMIC MODEL WITH MULTI-OBJECT FOR PUBLIC BICYCLE REBALANCING PROBLEM Candidate: Wu Manjin Advisor: Dong Hongzhao College of Mechanical Engineering Zhejiang University of Technology April 2015 作者签名 : 导师签名 : 浙江工业大学 学位论文原创性声明 本人郑重声明 ： 所提交的学位论文是本人在导师的指导下，独立进行研宄工 作所取得的研宄成果。除文中己经加以标注引用的内容外，本论文不包
3、含其它个 人或集体己经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育 机构的学位证书而使用过的材料。对本文的研宄作出重要贡献的个人和集体，均 已在文中以明确方式标明。本人承担本声明的法律责任。 作者签名：日期 : 年 W月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1. _ 保密 ， # 年解密后适用本授权书
4、。 2. 不保密 K。 (请在以上相应方框内打 “ V” ） 曰曰A 月月 A- 年 rrx 期期 Bn rK苛 浙江工业大学硕士学位论文 公共自行车系统自然租赁需求预测与多目标调度方法 摘 要 公共自行车系统作为破解公共交通 “ 最后一公里 ” 难题的交通方式，能有效提升城 市公共交通整体服务水平，但公共自行车系统在迅速发展的同时，也存在着经常出现的 “ 无车可借 ”与 “ 无法还车 ” 问题。因此，为解决出行者租 /还车难问题，需要获取公共 自行车系统服务点的实时状态信息及调度需求信息，设计合理的调度计划，均衡分配各 服务点的公共自行车数量。本论文以浙江省科技计划项目一一公共自行车运行数据
5、的空 间分析及其调度系统的研究与开发(2013C33047)为依托，研究了公共自行车系统的自然 租赁需求与调度模型及求解算法。 首先提出了公共自行车系统自然租赁需求的概念，并且给出了这种租赁需求的预测 方 法。通过 Multi-logit改进模型估算公共自行车在客运总量中的分担率，利用模型估算 所得分担率与调查统计所得到分担率的相关性，结合服务点历史租赁数据，实现公共自 行车系统自助服务点自然租赁需求的预测。服务点自然租赁需求是公共自行车系统调度 的前提，决定了服务点提供租还服务的能力和服务点的调度需求类型及调度需求量，对 提高公共自行车系统的调度计划质量起着非常重要的作用。 其次，从不同角度
6、对公共自行车系统调度问题进行了分析，将公共自行车调度问题 界定为公共自行车自流动与机动车调度相叠加的复杂动态车辆调度问题 。通过对公共自 行车系统服务点调度优先级、调度需求量、服务时间窗约束等特性进行的研究，建立了 统筹用户满意度与企业调度成本的公共自行车系统多目标动态调度模型。同时，设计了 禁忌搜索算法与遗传算法相结合的混合算法对所建立的调度模型进行求解，得到公共自 行车最优调度方案。 最后，通过 C#语言 、 Sql Sever 2008数据库，开发了基于客户端 /服务器 （ C/S)架 构的公共自行车系统调度软件，并验证了本文所提出的公共自行车系统多目标调度方 法。结果表明，调度方法在平
7、衡各服务点公共自行车数量方面具有预期效果，能够达到 缓解租 /还车难问题的目的。 I 关键词：公共自行车系统，自然租赁需求，多目标调度模型，调度软件系统 浙江工业大学硕士学位论文 EVALUATION ON NATURAL RIDE DEMAND AND DYNAMIC MODEL WITH MULTI-OBJECT FOR PUBLIC BICYCLE REBALANCING PROBLEM ABSTRACT Public bicycle system as a way to break the last mile” problem of bus transportation, can ef
8、fectively improve the city public transportation service level. Although the public bicycle system developing rapidly, the phenomenon no bike to borrow and cant return the bike often appears at the same time. In order to solve the problem renting or returning bike difficult for traveler, we need to
9、obtain the real-time information and scheduling requirements of public bicycle service point, and design reasonable schedule to distribute the public bicycle. This paper based on the science and technology project of zhejiang province: Analysis on historical running data and research on vehicle sche
10、duling for public bicycle system(2013C33047), the natural ride demand and rebalancing model of public bicycle system are studied. Firstly, the concept of natural ride demand containing the limited ride demand and the potential ride demand is proposed, meanwhile, the forecasting method of natural rid
11、e demand is proposed to solve such a issue. According to the improved.Multi-logit model for discrete choice, the public bicycle sharing rate among the total passenger amount is estimated. The correlation coefficient between the estimated sharing rate and the statistical sharing rate is calculated. C
12、ombined with the large historical data, the natural ride demand of public bicycle self-service station is evaluated ultimately. The natural ride demand is the basis of public bicycle scheduling, which decides the rental ability and scheduling requirements of service point. It is very important to im
13、prove the quality of public bicycle redistribution. Through analyzing the public bicycle scheduling problem in different angle, the bicycle scheduling problem was defined as a complex dynamic scheduling problem combining public bicycle flow and vehicle scheduling. According to the study about reposi
14、tioning priority, dynamic ride demand and time window of the self-service station in redistribution process, a dynamic public bicycle repositioning model with multi-object including user satisfaction and m ABSTRACT transportation cost was established. And a tabu genetic hybrid algorithm for solving
15、dynamic redistribution model was designed. Finally, through the C# , Sql Sever 2008 database, the public bicycle system scheduling software was developed based on the C/S architecture, and the multi-object scheduling method proposed in this paper was verified. The result shows the scheduling method
16、in rebalancing the public bicycle service can achieve expected effect and relieve the problem renting or returning bike difficult. Key words: public bicycle system, natural ride demand, rebalancing model with multi-object, rebalancing software system IV 浙江工业大学硕士学位论文 目 录 触 . I ABSTRACT . Ill 第 1 章 绪
17、论 . 1 1. 1课题的研究背景及意义 . 1 1.2研究现状 . 3 1. 2. 1公共自行车租赁需求预测现状 . 3 1. 2. 2调度理论研究现状 . 4 1.3目前公共自行车调度研究中存在的问题 . 7 1 4研究内容及组织结构 . 7 第 2章公共自行车系统自然租赁需求预测 . 10 2. 1引言 . 10 2.2自然租赁需求的提出 . 10 2.3自然租赁需求与调度需求量的关系 . 10 2.4公共自行车自然租赁需求的预测 . 11 2. 4. 1 Multi-logit预测模型的确定 . 11 2.4.2模型的改进 . 12 2. 4.3出行选择效用函数的建立 . 2. 4.
18、4特性系数标定 . 2. 4. 5公共自行车自然租赁需求预测 . 2.5实验分析与结果验证 . 2.6 本章小结 . 19 第 3章公共自行车系统多目标动态调度建模 . 20 3. 1引言 . 20 3.2公共自行车系统调度问题特性总结 . 20 3.3多目标动态调度模型的建立 . 21 3.3.1 调度问题的描述 . 21 3. 3. 2服务点调度请求 . 22 3. 3. 3服务点调度需求量的确定 . 23 3. 3. 4服务点调度时间窗的确定 . 23 3. 3. 5调度车辆初始装载量的确定 . 24 3.3.6目标函数的确定 . 25 V _ _ 3.4 本章小结 . 27 第 4章公
19、共自行车调度模型求解算法 . 28 4. 1 引目 . 28 4.2滚动时域法 . 28 4.3公共自行车调度问题求解 . 29 4. 3. 1求解算法简介 . 29 4. 3. 2禁忌遗传混合算法关键步骤设计 . 30 4.4实验与分析 . 34 4. 4. 1实验方案与资料 . 34 4. 4. 2结果分析 . 36 4. 5 本章小结 . 37 第 5章公共自行车调度系统的实现 . 38 5. 1引言 . 38 5. 2公共自行车调度软件功能需求分析 . 38 5.3公共自行车调度系统架构 . 39 5. 3. 1软件框架设计39 5. 3. 2 系统结构设计 . 40 5. 3. 3数
20、据库设计 . 41 5.4公共自行车调度系统的实现 . 42 5.4.1 可视化调度 . 42 5. 4. 2服务点调度管理 . 43 5. 4. 3调度信息生成 . 44 5.5 本章小结 . 45 第 6章结论与展望 . 46 6. 1 结论 . 46 6. 2 展望 . 47 附录 . 48 #敎南犬 . 52 至夂 i射 . 55 攻读学位期间参加的科研项目与成果 . 56 VI 浙江工业大学硕士学位论文 第 1 草绪 论 1.1课题的研究背景及意义 随着小型客车保有量的迅速增长，城市道路交通事故日益频繁，交通拥堵程度日益 增大，废气与噪声污染问题日益突出。大力推行公共交通出行方式，构
21、建绿色的交通系 统，作为解决城市交通拥挤问题的重要手段已经得到了国内外的广泛认同，但是由于公 交覆盖率较低，公交站点间距离长，发车频率不确定，换乘不方便等问题给人们的出行 造成了困扰，降低了公共交通出行的吸引力。为解决公交系统存在的上述问题，延伸公 交服务（最后一公里），吸引更多的自驾车出行者改变出行方式，公共自行车与公共交 通换乘的模式得到了广泛推行。公共自行车系统作为城 市公共交通的组成部分承担着重 要的交通任务，其提供的绿色、低碳 1出行方式有效地弥补了公共汽车存在的缺陷，极 大地方便了市民出行。近年来，英、法、美等一些发达国家都在积极推广自行车方式出 行，这些国家在自行车出行分担率方面
22、占有较大比重 2，比例最高的荷兰达 27%。当前， 巴黎、里昂、墨尔本、哥本哈根等大城市相继建立了公共自行车系统（ PBS)，杭州、 武汉、上海等近百个国内城市也推出了 PBS， 掀起了一股 PBS的建设热潮。下图为公 共自行车系统在全球的发展状况 5。 图 1-1公共自行车系统全球发展状况 1 _ 第 1 章绪论 _ 我国目前公共自行车数量约为 42.99万辆，超过了全球其它国家总和，仅杭州市自 2008年率先在国内推出公共自行车系统以来，现今己达 3113处服务点， 7.8万辆公共自 行车的规模，日均租借量突破 31.2万人次，日最高租借量达 41.68万人次。随着公共自 行车系统规模的逐
23、渐增大、使用频次的逐渐增加，给公共自行车系统的正常运行也带来 了一系列问题，尤其是普遍存在的 “ 租 /还车难 ” 问题。某些服务点所有锁桩成呈空位 状态，用户借不到车；而某些服务点所有锁粧呈满位状态，用户无法还车；居民区、办 公区及部分商业区都存在明显的早晚高峰和方向不均衡现象，导致了公共自行车使用率 的降低。 图 1-2是对公共 自行车用户普遍反映的问题进行调研统计的结果 6，充分反映了公 共自行车 “ 租 /还车难 ” 问题己成为用户使用公共自行车出行过程中的突出问题。由此 可见，公共自行车系统在使用及调度管理过程中仍然存在着较大的问题。 首选服务点无车可借 首选服务点无空车位 次选服务
24、点无法借还车 首选租还车地点未设服务点 图 1-2公共自行车使用状况 这些问题除了与服务点布局方式有关，另一个主要原因是公共自行车调度方法有待 改进。现有的公共自行车系统主要通过服务点监控的方式来了解各个服务点的自行车租 赁情况，并凭借人工经验对部分固定的服务点进行调度，这种方法存在着明显缺陷： 车辆调度方法以人工经验为主，无法确定最佳调度路线，缺乏科学性且效率低； 调度 计划单一，现场调度人员与调度管理中心缺乏必要联系； 公共自行车系统规模很大， 仅凭借人工经验对一些固定的服务点进行调度，难以解决其它服务点长时间出现无车可 借及无空车位可还的问题。 2 浙江工业大学硕士学位论文 图 l-3b
25、无车可租的服务点 图 l-3a无法还车的服务点 综上所述，本课题以浙江省科技计划项目一一公共自行车运行数据的空间分析及其 调度系统的研宄与开发 (2013C33047)为依托，拟研宄适合公共自行车系统的自然租赁需 求预测方法与调度模型及求解算法，及时均衡公共自行车在时空上的分布，缓解 “ 租 / 还车难 ” 现状，提升公共自行车系统整体服务水平，吸引更多出行者使用绿色的公共自 行车方式出行。 1.2研究现状 公共自行车系统的调度问题作为一种特殊的车辆调度问题，可描述为：对于一系列 有调度需求（运入或运出自行车 ） 的公共自行车系统服务点，派遣若干调度车辆沿合适 的调度路线依次对这些服务点进行运
26、入或运出自行车，并达到一定的目标，如使用的调 度车数量最少、行驶距离最短、综合费用最低等。此外，还需要满足一定的约束条件， 如调度车辆所能够装载公共自行车的数量、调度服务时间的限制等。因此，公共自行车 系统的调度需要在租赁需求预测的基础上，构建调度模型及求解算法。下面将对公共自 行车系统的租赁需求预测、调度建模及算法研究现状进 行介绍。 1.2.1公共自行车租赁需求预测现状 公共自行车租赁需求决定了公共自行车调度过程中服务点的调度需求类型及调度 需求量。因此，在租赁需求信息随时间动态变化的调度过程中，服务点租赁需求量的预 测对提高调度计划具有重要意义。 Kaltenbrunnerm(2010)
27、和 Borgnatra(2011)等人通过数据挖掘，从时间特性上分别分析 了里昂、巴塞罗那公共自行车系统的动态特征，并建立了预测租借量的统计模型。 Vogel9(2011)等人通过不同的聚类算法对维也纳公共自行车系统两年来的运营数据 3 _ 第 1 章绪论 _ 进行了挖掘，寻求系统租还规律。 何流等 1G(2013)在考虑用户等待、转移和消退三者概率的基础上建立了公共自行车 需求估算模型。 吴瑶 M等 (2013)通过 logit模型，计算得到公共自行车的出行分担率，结合居民出行 0D数据来进行公共自行车租借需求的预测。 顶 12等 (2013)建立了一个带比例约束的网络流模型，用于预测网络中
28、的公共自行车 流量，从而确定服务点公共自行车的初始分配数量。 温惠英 13等 (2014)依据公共自行车租还历史资料 ，结合居住人口和建筑面积等参数 , 建立了迭代回归模型预测公共自行车投放量。 时 14等 (2014)针对公共自行车用户的出行次数，出行距离长度和出行时间三个关键 参数进行了仿真实验，对租赁需求量及系统服务能力进行了模拟。 上述相关研宄所预测的公共自行车租赁需求量，尚未包括潜在用户量。因此，本文 将提出自然租赁需求的概念，即当前租赁需求量与潜在租赁需求量之和，自然租赁需求 的预测，对设计未来规划方案，合理安排调度方案，缓解出行者租 /还车难现状将具有 重大意义。 1.2.2调度
29、理论研究现状 目前，国内外很多城市已经建立了公共自行车系统，且针对公共自行车系统调度问 题进行了一定的研究。根据公共自行车系统的调度特点，公共自行车调度问题可归结为 一种特殊的车辆调度问题，国内外学者主要围绕着调度建模与求解算法两个重要因素进 行了大量研究。 1.2.2.1调度模型的研究现状 公共自行车调度模型研究主要根据优化目标及约束条件的不同而展开。优化目标主 要包含调度成本最低（所用调度车辆数目最少、调运距离最短、调度所用时间最短等） 及用户满意度等方面；而约束条件根据优化目标的不同，主要有服务时间窗，调度中心 数目，调度前信息是否已知，调度需求数量及类型等。 Parkin J等 15(
30、2008)通过调查所得的公共自行车租用量数据，建立了公共自行车调度 需求量计算模型。 董红召等 16(2009)在考虑调度模糊时间窗约束条件下，建立了以公共自行车用户满 4 _ 浙江工业大学硕士学位论文 _ 意度为优化目标的调度模型。 Benchimol1(2011)和 Chemla等 (2011)假设公共自行车系统服务点的租赁需求量 给定，即在调度需求量已知情况下，以调度成本最低为优化目标，建立了调度模型。 柳祖鹏等 19(2012)在考虑公共自行车调度车辆的满载量及下一受调度服务点需求的 情况下，建立了公共自行车系统调度模型。 Fant(2013)提出一种随机网络优化模型，模型基于服务点实
31、际需求变化，进行随机 动态优化分配。 Raviv等 21(2013)结合公共自行车系统租赁需求特性，建立了用户不满意函数，并 通过历史数据估算所得的转移概率来确定服务点合理的公共自行车配置数量。 Mauro等 22(2013)将公共自行车调度 问题看作装卸相结合的车辆调度问题，并以综 合调度成本最低为目标建立了调度模型。 张建国 23(2013)建立了区域调度模型，通过划分若干子调度区域，将调度问题由全 局最优问题转化为局部最优。 Kl imullnerM(2014)等提出了寻求整体公共自行车调度数量最少的调度优化模型， 并对模型可行性进行了验证。 Pfrommer25(2014)等通过对公共
32、自行车服务点设定动态变化的租车价格建立了再 平衡调度模型。 上述研究虽然在公共自行车调度方面取得了一定进展，但考虑的约束条件较少，而 实际调度过程中，由于自行车在服务点间不断流动，会导致需求量随机动态变化，直接 采用上述模型进行调度会给调度车辆带来很大的扰动。同时，公共自行车的调度往往涉 及到用户满意度、企业调度成本等诸多影响因素，需要进行多目标优化。 1.2.2.2调度算法的研究现状 车辆调度问题的求解算法主要包括精确算法、传统启发式算法以及智能优化算法 等。 1、精确算法 精确算法的思想是根据建立的数学模型进行精确求解，主要有分支定界法 (Branch and bound)、 切平面法 (
33、Cutting planes)、 动态规划法 26_27。虽然精确算法可以用于求解 最优化问题，但存在一个弊端，计算量随着所需要解决问题的规模增大呈指数倍增长。 因此，适应能力较差，仅适用于规模较小的寻优问题或对实时性要求不高的问题，实际 5 _ 第 1 章绪论 _ 应用较少。 2、 传统启发式算法 传统启发式算法主要有节约法 (Saving Method)、 数学规划法、两阶段法、扫描法 等 28_29，它不同于精确算法，追求的并非是问题的最优解，而是在可以接受范围内的满 意解，是一种用直观、经验构造出来的算法，对于较大规模的车辆调度问题，能够较快 获得问题的满意解 3()。 3、 智能优化
34、算法 传统启发式算法虽然比精确算法有了一定的进步，但缺乏统一、完整的理论体系， 且无法保证解的全局最优性；而智能优化算法具有全局最优性能以及严密的理论依据， 同时能够短时间内获取车辆调度问题的最优解，是众多国内外专家和学者研宄的热点。 智能优化算法主要包括禁忌搜索算法 31_33、遗传算法 34_37、蚁群算法 38_39和模拟退火算 法 4 _42等。表 1-1为智能优化算法的优 缺点。 表 1-1智能优化算法的优缺点对照 方法 优点 缺点 禁忌搜索算法 可通过 “ 记忆 ” 规则提高搜索效率， 爬山性能好 对初始解的依赖程度较大 遗传算法 并发搜索，全局搜索能力强，易与其 它算法相结合 易
35、出现早熟收敛，后期搜索效 率较低 模拟退火算法 能避免陷入局部最优，具有较强的鲁 棒性 结果不能保证最优，效率一般 蚁群算法 初始解的要求不高，具有较强的发现 较优解的能力 需要不断调整，搜索时间长，易 停滞 以上演算法单独使用时，都存在自己的局限性，因此，很多学者采用了混合算法以 弥补单个算法本身的缺陷。大部分学者采用两种智能算法的结合 43_45 ，也有将启发式算 法与智能算法相结合 46_47。 虽然许多学者对车辆调度尤其是公共自行车调度问题进行了深入的研究并取得了 丰硕的成果，但仍存在着一定的缺陷。现有的公共自行车调度问题大都是在需求量己知 的前提下进行的，只有部分文献提出需求量随机的
36、情况，并且是在假设需求量符合某种 分布的情况下进行求解的，而公共自行车调度实际上是一个时间和需求量都会随机变化 的问题。 6 浙江工业大学硕士学位论 文 1.3目前公共自行车调度研究中存在的问题 通过上节分析，目前公共自行车系统及其调度研究中主要存在着以下问题： (1) 公共自行车租赁需求数据对公共自行车系统调度问题的优化决策具有重要应用 价值。然而，系统历史运行数据受限于自助服务点 “ 租还车难 ” 的现实条件，仅反映了 该限条件下的租赁需求，尚未包含潜在的那部分用户的需求量。本文提出了自然租赁需 求的概念，即当前租赁需求量与潜在用户租赁需求量之和。目前，绝大多数的相关研究 都仅针当前受限公
37、共自行车租赁需求进行预测及规模分析，鲜有文献对自然租赁需求进 行深入剖析。 (2) 目前大多数公共自行车调度问题的研究是在假设调度需求量已知的条件下进行 的，而在实际调度过程中，公共自行车的自流动性会使服务点调度需求量在机动车对其 调度过程中发生动态变化。因此，在获取服务点实时租赁需求量的同时，测算潜在用户 需求量，并通过一定的标准去判断服务点的调度请求是否被允许，在此基础上才能对公 共自行车系统进行调度。 (3) 公共自行车调度是一个复杂的非确定性问题，在实际调度过程中受到的约束 比较多，而现有模型一般只考虑了其中少量几个约束，且都仅对单目标进行优化。公共 自行车作为一项公益服务事业，在考虑
38、企业 调度成本的同时，应使调度所带来的社会效 益最大化。因此，需要综合考虑公共自行车系统各方面的特性，建立以用户满意度最大、 企业调度成本最低为优化目标的调度模型非常有必要。 (4) 调度求解算法过于简单，存在一定缺陷，公共自行车系统调度问题的规模很 大，对算法的实时性要求相对较高。因此，设计快速、高效的求解算法对公共自行车系 统调度十分重要。且调度系统功能较为单一，许多学者仅针对公共自行车调度问题展开 研究，很少涉及到调度软件系统开发。现有的调度软件系统基本只能实现服务点租赁状 态显示及视频监控功能；或者仅能够生成调度 路线，但缺少 GIS的匹配，无法可视化地 图上显示生成调度路径 48。 鉴于上述存在的问题，本文将对公共自行车系统服务