摘 要

在当今的移动互联网时代，共享经济已经深入人心，尤其是在共享单车火爆以后，众多的公司加入到这个行列中。但是随着自行车共享公司迅速加入，数以万计的，五颜六色的共享自行车出现在城市的各个地方。这样就出现了在城市中，有的地方自行车投放量过剩，有的地方投放量过少的问题。

该毕业设计主要研究方向就是处理上述问题。第一，就是要满足一定区域内的所有民众的自行车使用需求；第二，就是在满足民众使用需求的前提下，尽量少的投放车辆，以达到减少社会资源的浪费以及降低投入成本。本毕业设计的主要难点就是抽象出相应的模型，然后利用组合结构的相关知识设计出不同的算法去附和上述的两个目标，最终通过比较，得出一种相对而言更优的算法。在完成对设计出来的几种算法进行测试比较后，结果表明能够有效的改善共享单车的投放策略。

关键词：共享单车；组合算法；贪心策略；方案优化；优化成本。

Abstract

In the era of this mobile-internet, the sharing economy model has been popular among the people all over the world especially, after the booming of “Sharing Bike” startups.  As a result, thousands of colorful bikes of a noticeable amount of companies have appeared everywhere in cities. But for those bikes, the infrastructure and related rules and regulations of the city are not well constructed, and we do not know how to deal with the influx of these huge numbers of bikes. And this has led to the problem of oversupply of bicycles in some big as well as small cities.

The significant purpose of the project is to research the problems. Firstly, it is important to satisfy the needs of all citizens for using bicycles within a certain area. Secondly, to keep as few vehicles as possible near to the respected place of people in order to reduce the wasting of social resources and also reduce the unexpected costs. The main difficulty in the design of this project is to abstract the corresponding model then imply the gained knowledge of the combined structure to design different algorithms for the above goals. After lots of researchers and comparing situations, a relatively better algorithm was obtained. After testing and comparing the design of algorithms, the result shows that the availability of shared bicycles can be reduced to a logical number.

Keywords：Shared bicycle; Combinatorial algorithm; Greedy strategy ; Scheme optimization; Optimizing cost.

目录

摘要 1

Abstract 2

第一章 绪论 4

1.1 研究背景与意义 4

1.2 共享单车概述 4

1.3 国内外研究现状 6

1.4 主要研究内容 6

1.5 论文结构安排 7

第二章 共享单车投放模型分析与解决方案 8

2.1 前提假设 8

2.2 共享单车投放模型建立 9

2.3 共享单车投放模型分析 10

2.3.1 所有圆都不相交 10

2.3.2 两个圆相交或相切 10

2.3.3三个圆相交 11

2.3.4 n个圆相交 12

2.4 组合结构算法 12

2.4.1 方案一：就近比较策略 12

2.4.2方案二：中心点策略 13

2.4.3 方案三：贪心策略 14

第三章 共享单车投放策略实现 15

3.1 策略实现前提 16

3.2 就近比较策略实现 16

3.2.1 就近比较策略实现 16

3.2.2就近比较策略实现结果图 16

3.3 中心点策略实现 16

3.3.1 中心点策略实现 17

3.3.2中心点策略实现结果图 17

3.4 贪心策略实现 18

3.4.1 贪心策略实现 18

3.4.2 贪心策略实现结果图 18

第四章 结果验证与分析 19

4.1 验证前提 19

4.2 获取验证数值 19

4.2.1 人口密集点获取 19

4.2.2具体化区域大小A 20

4.2.3具体化取车半径r₀ 21

4.2.4具体化投车数量m₀ 21

4.3 验证结果对比 22

4.4 优化程度对比 23

第五章 总结与展望 25

5.1 总结 25

5.2 未来展望 25

参考文献 26

致谢 27

第一章 绪论

1.1 研究背景与意义

自从共享经济的想法在人们心中深化之后，共享单车在2015年年底以十分迅猛的态势进入了人们的平时生活。共享单车在给人民群众带来了生活上的便利，大大改善了人民群众近距离出行十分麻烦的难题，而且提倡了一种更加健康环保的生活。其中，以ofo小黄车、摩拜单车领头的共享单车公司得到了许多投资家的热衷，在国内的很多大城市的大学校内、地铁出口、公交站台、写字楼、产业园区等都可以看到各式各样，各种颜色的自行车。但是，用户在享受共享单车带来了便利的同时，也有许多不文明的现象，比如乱停乱放，侵占盲道、人行道甚至机动车停车位的现象随处可见。随意停放不仅影响市容，更导致公共空间的无序占用，甚至存在因为违章停放被管理部门拖走的情况。这不仅与民众的素质有关，也与共享单车企业对自行车投放管理不科学有关。因此，企业需要一种合理的，科学的自行车投放策略，在满足民众正常出行需求的同时，以最少的单车数量满足民众的日常需求，让每辆共享单车能发挥最大的运营能力，减少对社会的负面影响。

面对共享单车有的地方泛滥成灾，有的地方却无法满足民众日常需求的问题。科学合理的共享单车投放策略，对用户而言，可以有效解决民众出行最后一公里的问题。对企业而言，可以减少投放量，节约成本，节约管理费用。对社会而言，有利于建设一个低成本，高效率的社会。同时也倡导一种健康环保的生活方式。总的来说，合理科学的共享单车投放策略是十分有必要而且有意义的。

1.2 共享单车概述

共享单车是一种新类型的环保共享经济，指企业在地铁站，校园内部，公交站台，居民小区，商业区域，公共场所等提供自行车的共享服务，主要模式是分时租赁。从2016年底之后，国内的共享单车就一下子火爆了起来。一张手机截图瞬间蹿红网络，24个共享单车应用，足以说明共享单车的竞争激烈。共享单车能迅速的火爆起来，主要有以下几个优点：第一、共享单车能够一定提高城市的效率。第二、共享单车提升了人们生活和工作的效率。第三、共享单车是一种低碳环保的出行方式，也是一种更加健康的生活方式。第四、共享单车牵连了物联网的发展。第五、共享单车也会促进城市内部交通设施的完善。然而，共享单车带来便利的同时，也给城市带来了巨大的压力。

图 1.1

图1.2

然而，在城市的街头边，共享单车几乎已经到了“泛滥”的地步了。各大城市的街边排满了五颜六色的共享单车。正是因为共享单车随用随停的方便性，骑手们将单车随意停放在任何地方，甚至丢弃自行车，导致单车堆积如山，给曾是的街道和道路带来了巨大的压力。拒不完全统计，我国的共享单车投放累计数量已经超过了1600万辆，其中一线城市北京，上海，广州，深圳就占了大约500万辆。过度投放的共享单车因为乱停乱放，已经严重超出了城市的承载能力，这使得许多城市都纷纷叫停了共享单车新增投放，其中包括北上广深，宁波等共12个城市。

1.3 国内外研究现状

对国外而言，共享单车在国外的市场才刚刚开启，虽然共享单车在国外受到了大家的热烈欢迎，但是主要的两个厂家ofo和摩拜单车每次仅仅只拿出一两千辆自行车出来，跟国内的城市动不动就几十万的画风相差甚远。没有出现国内共享单车管理不当的问题。所以在共享单车投放方面的问题还不是很深刻。但是，国外有类似于摄像头分布，传感器分布的安置问题，但是摄像头，传感器等都是静态的分布问题，而共享单车随着人们的使用，是一个动态的分布，所以需要更进一步的深入研究。本毕业设计主要研究的也是初始投放策略，所以简单的参考国外传感器分布的相关研究，并加以完善。

在国内而言，共享单车投放的研究也不多见，大多数都是停留在共享单车流量分布，使用时间，空间分布等表面问题。而当前的研究问题是如何使空间分布更加契合用户的使用情况。可以使用之前国内对共享单车时间空间分布的研究结论应用于本研究中。

1.4 主要研究内容

在国家提倡低碳出行，共享经济发展迅猛的社会环境下，共享单车具有方便，快速，缓解交通拥堵等优点，走进人们生活。但是，也存在使用率低，投放不科学合理的情况。因此，需要寻找一种科学并且合理的共享单车投放方案，拟定用户可使用的车辆数量以及车辆的覆盖面积，应用组合数学中的结构模型，模拟用最少的车辆，覆盖周围区域所有民众的出行需求。

目标：分析设计在保证完整覆盖的基础上，满足车辆总数的最低投放量，并加以实现应用。也就是，每个地区都覆盖了共享单车，并且对于每个民众而言，他们所能使用的共享单车的数量相同。以达到投放共享单车数量最少的目的。最重要的目标就是满足用户的需求，并且投放车辆总数最少。

如今共享单车的品牌种类十分丰富，但是大致的功能点都近乎相同，服务的对象也一致，这里作者主要就提两个具有代表性的共享单车企业：ofo小黄车和摩拜单车。

ofo单车可谓是共享单车的先驱了，在2014年，ofo共享单车的创始人戴威兼CEO就提出了将共享经济与智能硬件相结合的理念，解决民众出行最后一公里的理问题，于是创立了国内第一家以平台共享的形式运营大学校内自行车的互联网科技公司。Ofo小黄车提倡用户将自己的车共享出去，达到以1换N的模式，提供了更加快捷，有效的出行体验。这种共享模式可以让闲置的车辆的利用率大大提高，也能减少对环境的污染，缓解交通压力。还有一个最大的特点，也是首创的无桩共享单车。ofo共享计划一经推出，就在北京大学获得了2000辆自行车，并且得到了Pr0e-A轮融资。之后，在2016年1月以及同年8月完成了A轮融资以及A 轮融资，在2016年9月，完成了数千万美元的B轮融资，在十月，ofo项目宣布完成了1.3亿美元的C轮融资。在资本的催化下，ofo发展迅猛，在2016年6月突破了五百万订单，三个月之后突破一千万订单。如今，ofo已经覆盖了全国一百多个城市，日订单超过三百万。

摩拜单车是同ofo小黄车一起领跑共享单车的第一梯队。摩拜单车成立于2015年，在2016年4月22日在上海推出，是北京摩拜科技有限公司研发的一种解决出行的智能自行车。创始人胡玮炜格外关注科技对生活的带来的改变，同王晓峰，刘禹，夏一平等人共同创立了Mobike，并且自主研发了智能锁，其中集成了全球定位系统和通讯模块，能够通过手机软件让用户定位使用周边的车辆。摩拜单车的诞生同样也得到了很多资本家的青睐，在2017年6月份，摩拜单车完成了一笔超过6亿美元的融资，这一数字是共享单车行业内有史以来单笔最高融资。目前为止，摩拜单车已经先后进入了九个国家，180多个城市，有超过700万辆摩拜单车，用户突破2亿，每日的订单量超过3000万，是世界上最大的共享单车平台以及移动物联网平台。

1.5 论文结构安排

本毕业毕业设计总共分为五章，每一章的内容如下：

第一章是绪论。主要是引出问题,分析毕业设计的背景与意义，探讨国内外的研究现状以及目前仍有的问题,阐述本文的主要内容。

第二章是问题分析与解决方案。对问题提出符合实际情况的假设，建立起数学模型，便于利用组合结构相关的数学知识解决问题。其中包括对提出来的问题进行大概分析，给出几种不同的解决方案。

第三章是编码实现与验证。包括用程序模拟出上述的模型，用代码实现解决问题，对输出的结果进行验证，检查代码的正确可靠性。

第四章是验证结果分析。分别对第三章提出的三种方案进行分析，分析出现这种结果的原因，比较每种方案的优确定，得出相对而言更优的方案。

第五章是总结和期望。主要是阐述了本文所有的工作内容,并提出了下一阶段面临的问题，最后对共享单车的投放策略进行了展望。

第二章 共享单车投放模型分析与解决方案

本章主要内容是设定一定的假设，所有的假设都是基于现实情况，然后根据设定的内容建立数学模型。建立模型可以通过抽象，简易的刻画出实际问题，使之可以纯粹的使用数学知识解决问题。

2.1 前提假设

假设一：若半径为R₀的区域内，人口数量每超过n₀，就称该区域为人口密集区域，同时在区域内设定一个人口密集点P1（x1，y1）。如图2.1所示

图2.1

同理，若在半径为R₀的区域内的总人数为nx。则在区域内的点的数量为：

f（i）=[nx/n₀] (取商运算) nx为区域内总人数，n₀为取点界值。

这样就可以得到点集合P ，{P1，P2……Pn}，其目的就是将一定区域内的人口集中化处理，将其抽象为一个点，现实生活中人口集中区域也可以模拟成一个点，这样可以便于后面模型的建立。

假设二：假设人容忍行走取车的距离为r₀。

当所有的人口密集点确定之后，也是相当于所有的人口都集中在集合P中。在现实生活中，如果使用者的身边没有车辆，人们会愿意行走一小段距离取车，然后前往目的地，在这里，我就将这段距离具体化，减少变量。也就是在以P_i为圆心，以r₀为半径的范围内的车辆都是可以供P_i的人群使用的。

假设三：假设所有的人口密集点，都是通过人口密度分布图给定的，以下的所有研究都是基于给定了人口密集点集合P，当然，集合P内的元素是随机的，相当于在给定范围的区域内随机产生的人口密集点。

接下的工作就是如何确定投放车辆的点集合Q，以及每个点投放车辆的数量m，最后总和所有的车辆：

Min{ S_i=∑mQ_i }

该模型也只是将具体的情况进行抽象处理得到的，现实生活中的情况要比这复杂的多，在这里，只是简单的模型化处理。

2.2 共享单车投放模型建立

当给定了人口密度分布图或人口分布表格之后，可以通过假设一，得到人口密度分布点的集合。如何获取人口密集点不是本文重点研究的内容，上述内容也只是给与了一种获取人口密集点的方法。为了后期的测试环节（第五章）的简便性，本课题采取随机产生人口密集点的方式进行模拟。在得到人口密集分布点之后，可以建立直角坐标系，为了便于研究，不妨假设所有的点都落在在第一象限，而且每个点的坐标的范围都可以调节，坐标的范围代表这区域的大小，可调节的大小可以更好的模拟不同地区的大小。每一个人口密集分布点P_i和固定的半径r₀就会在坐标轴上形成同等数量大小相同的圆，而每个圆内都应该有可使用车辆，让该区域的人群使用。于是问题可以演变为：在圆P_i内部投放车辆，确定投放车辆的点Q_i，使得每个区域内都存在可用车辆。同时，尽可能少的确定投放车辆的点Q_i，也就是尽量少的投放共享单车数量。

模型建立之后得到流程图如下：

开始

输入数据

圆P内是否存在Q点

在圆pi内是否存在其他点p

结束

本章主要内容是模型分析与解决方案。在上一章节完成数学模型建立之后，就需要对问题进行详细分析，然后得到相对来说比较合理的解决方案。问题分析主要分为概要分析以及具体分析。而解决方案，本文主要列出了三种解决方案。

2.3 模型分析

由于每个人口密集点结合取车半径r₀可以确定一个圆，为了表述方便进行模型分析，以下所有的点半径结合用圆来表示。

2.3.1 所有的圆都不相交

假如所有的人口密集点P_i以及半径为r0形成的圆都不相交，则简单的在每个不同的圆内都投放车辆，随机确定点Q，即可满足条件。如图3.1所示。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：