地铁中心站周边公共自行车调度问题

地铁中心站周边公共自行车调度问题

摘要

本文针对在地铁时代上下班高峰时期，早高峰公共自行车在地铁站大量集中无处停放，而在居民区内却没车可借；晚高峰地铁站无车可借，而居民区车子停满没法还车的问题，建立一系列的数学模型，设计不同问题下公共自行车的调度问题。

针对问题一，首先讨论只有一辆搬运车的情况：开始利用AutoCAD 画出道路以及自行车停靠点的位置坐标图。然后利用启发式搜索的思想，用启发式搜索A*算法，得到启发式搜索中的估计函数，对自行车停靠点进行评估，得到最佳公交车行车路线为公交总站→1→5→22→24→1→3→9→10→11→6→2→29→28→23→21→7→28→3→18→6→公交总站，所用的总时间为181.4分钟。其次讨论只有两辆搬运车的情况：首先将此问题视为多个售货员的的最佳旅行售货员回路问题，将地铁站区自行车租赁点进行大致的分组，然后根据路程的长短和搬运量的大小考虑三组的均衡性，进行均衡度的计算，找出最合理的分组，最后根据只有一辆搬运车时所用的启发式搜索A*算法，得到启发式搜索中的估计函数，对自行车停靠点进行评估，得到最佳公交车行车路线为. 车辆一：公交总站→30→29→28→23→21→9→5→3→28→7→22→24→公交总站，所用总时间为99.15分钟; 车辆二：公交总站→1→4→5→10→11→7→1→3→18→6→公交总站，所用总时间为99.99分钟。

针对问题二，首先通过对题意的理解，利用启发式搜索的A*算法，得到启发式搜索中的估计函数，对自行车停靠点进行评估，得到最佳公交车路线为1→7→23→21→6→1→10→11→22→24→1→5→9→1→16→18→6→1。所用时间为164.61分钟。在5号，9号，18号自行车租赁点放25辆，7号自行车租赁点放13辆，其余7个自行车租赁点放16辆。

针对问题三，首先通过对题中表格所给的数据分析得出，将自行车租赁点分为两组即自行车的调入与调出。其次对问题以及数据分析，继续利用启发式搜索的思想，将此问题分为两个子问题：第一个问题是对自行车租赁点桩内和桩外自行车数数据分析，然后对需要调动的自行车租赁点进行分组，我们利用扫描法将其可分为三组，说明需要三辆车来调度自行车。第二个问题是继续利用启发式搜索方法的A*算法，对搬运路线进行优化。综合以上两个问题找出调度的最佳方案，对自行车进行调动。得到的调度路线为：A 车路线：公交总站→1→3→5→9→10→22→24→25→1→公交总站（总路程所用的时间为23min ）；B 车路线：公交总站→30→29→28→27→23→21→7→31→32→34→30→公交总站（总路长所用时间为20min ）；C 车路线：公交总站→8→33→6→4→2→30→29→28→27→23→21→19→12→7→8→公交总站（总路程所用的时间为24min ）。

关键字 启发式搜索 A*算法 均衡度 扫描法

一、问题的重述

地铁时代的来临将给杭州公共自行车带来更为突出的上下班高峰潮汐现象，即早晨7：00左右至8：30左右大量市民骑车到地铁站换乘地铁上班，造成地铁交通圈内集中大量的公共自行车，如不及时处理将会造成地铁站附近公共自行车无处停放，而居民住宅区附近则没有车可借用的情况；下午17:00至18：30左右则地铁站周围无车可借，而居住区内却因车子停满没法还车。本题讨论地铁武林广场站以西约1.5公里的地铁辐射范围的公共自行车调度问题。目前，杭州公交集团一般用拆掉座位的公交车运送自行车到各个自行车租赁点，每辆公交车可装50辆自行车。设高峰时段公交车行驶时速为30公里/小时，减速停靠路边所需时间1分钟，每送出或取回一辆自行车往返所需时间0.3分钟（设搬运车辆从L5路东侧的公交总站出发，完成搬运自行车任务后返回公交总站，公交总站具体位置见表1）。为了简单起见，假设每个十字路口或三叉路口公交车直行等待绿灯所需时间为1分钟，左拐等待绿灯时间为1.5分钟，右拐等待绿灯时间为0.5分钟。考察以下问题：

问题一：分别针对一辆搬运车和两辆搬运车的情况找出从地铁2号站地铁交通圈自行车租赁点将多余自行车送到居住区各个租赁点的最佳公交车行车路线（注意行车规则，图中马路都是双向道，不考虑穿马路搬车，路口和马路中间不允许公交车掉头）。

问题二：如果1号自行车租赁点积聚了200辆多余的自行车，居住区虚线框内11个租赁点都是空的，问一辆公交车应该以怎样的顺序向这些租赁点搬运自行车？请列出行车路线以及具体的搬运顺序与数量，并计算出所需时间(公共自行车租赁点一般要求停车桩内自行车数不少于停车桩总数的20%，不多于停车桩总数的80%，多余车辆要移到停车桩外) 。

问题三：天气因素、各种体育与商业活动影响着人们的出行方式，使自行车需求发生随机变化。科学、快速的应急调度是自行车租赁管理的一个重要手段。表2是某天上午7：50各自行车点的自行车数，请提出具体的快速调度方案。

二、符号说明

n —表示自行车租赁点

f(n)—表示该启发式搜索中估价函数

g(n)—表示从起点到任意自行车租赁点n 的实际所需时间

h(n)—表示任意自行车租赁点n 到下一个目标租赁点的估计所用时间 x —表示总站到各任意目标租赁点n 的坐标距离 v —表示公交车行驶时速 t 0—减速停靠路边所需时间

t 1—每送出或取回一辆自行车往返所需时间 t 2—直行等待绿灯所需时间 t 3—左拐等待绿灯时间 t 4—右拐等待绿灯时间 z —表示减速停靠路边次数 p —直行等待次数 q —左拐等待次数

r —右拐等待次数

m —需要装卸自行车的数量

α0—分组的均衡度

ωi —表示分组路线的长度

三、模型的假设

⑴假设每个十字路口或三叉路口公交车都要等待绿灯（只用于问题一和问题二中）；

⑵假设公交总站在L5路y 轴的东侧；

⑶假设30站在L6路与H1路交界东30m ；

⑷将图中所示的路没有尽头时，均视为可调头；

⑸针对问题三，在有人值守的自行车租赁点假设可以停车。

四、模型的分析

4.1问题一中对一辆搬运车模型分析

通过对问题的分析，本题我们利用启发式搜索方法的思想，即从公交总站出发，对居民区和地铁站区每个自行车停靠点的位置进行评估，得到最后的停靠点位置，再从这个位置进行搜索直到车子运送完，公交车回到公交总站。然后根据启发式搜索方法的A*算法，根据题中的条件写出启发式搜索中的估计函数，根据估计函数搜索最优的自行车停靠点，找出搬运自行车的最佳路线。在解答此问题时，我们对地铁站区和居民区自行车租赁点停车桩数的分析得，我们总共需要搬运的车辆为165辆，但居民区有空缺的自行车租赁点总共可以放的自行车数量为227辆，为了均衡居民区每个自行车租赁点自行车停放数量，我们通过计算得出，居民区每个自行车租赁点停放自行车的数量在14 ~16辆（满足公共自行车租赁点一般要求停车桩内自行车数不少于停车桩总数的20%，不多于停车桩总数的80%）。 4.2问题一中对两辆搬运车模型的分析

对两辆车在居民区所走的路线通过的自行车租赁点进行分组[4]

在此问题中我们利用求解多个售货员的最佳旅行售货员回路问题的思想辆搬运车所走的路线通过的自行车租赁点进行分组，我们分组时所遵循的准则如下：

准则一：尽量使每条路线上搬运车所搬运的自行车数量均衡 准则二：应使每条路线所走的距离最短。

准则三：尽量使每条路所走的路程的长度均衡。

根据4.1中对一辆搬运车的最佳路线的算法，即利用启发式算法的A*算法，找出不同分组中每辆车所要经过的自行车租赁点的评估函数，根据函数分别计算出两辆搬运车不同路线中，从起点到每个目标点在调度自行车时所用的时间，求出两辆搬运车的最佳行驶路线。 4.3问题二模型的分析

在此问题中，通过对题意的分析知，此题是固定的从1号自行车租赁点出发，将多余的自行车搬运到居民区的11个自行车租赁点。因此我们继续

利用启发式搜索的思想，从固定的1号自行车租赁点出发，对地铁站的每个自行车停靠点的位置进行评估，得到最佳的停靠点位置，再从这个位置进行搜索直到此次搬运车上车子送完又回到1号自行车租赁点，进行下一次的搜索，直到所有车子都运送完找出搬运的路径。而且我们对居民区11个自行车租赁点的位置分析，得到7号租赁点比较偏，因此对7号租赁点我们只考虑满足停车桩内自行车数不少于停车桩总数的20%这个条件。因为题中1号自行车租赁点多出200辆车，对居民区11个自行车租赁点的分析发现，如果只满足公共自行车租赁点一般要求停车桩内自行车数不少于停车桩总数的20%，不多于停车桩总数的80%这个条件，居民区自行车租赁点车子无法放下200两车，所以我们根据问题中表2的条件，将有人看守的自行车租赁点每个租赁点放25辆，其余每个租赁点放16辆。 4.4问题三的模型建立

首先我们通过对题中表格所给的数据分析得出，我们可以将所有自行车租赁点进行划分，具体分为两类即自行车的调入与调出。然后我们根据对题目数据的分析，我们继续利用启发式搜索的思想，在此问题中我们用启发式搜索的分解法，将此问题分成两个子问题进行模型建立 4.4.1对自行车租赁点进行调入和调出的基本划分

首先我们通过对题中表格所给的数据分析得出，需要搬出的车辆共计

734辆，总计桩内空缺为791辆，由于二者不平衡，所以我们可以将所有自行车租赁点进行划分，具体分为两类即自行车的调入与调出。我们的具体划分方案如下：调入点的划分特点为，首先靠近居民区，且各自行车租赁点内的自行车数量未达到停车桩数的80%，最后我们把是否有人看守作为参考，来决定调入车辆的数目；调出点的划分特点为，首先靠近地体区，且各自行车租赁点内的自行车数目较多。除此之外，我们还有几个调动性比较强的点要做具体说明，例如2，3，28，29这四个自行车租赁点既有大量的调入又有大量的调出，因此庄内停车位数只需达到停车总桩数的20%，即5这四个自行车租赁点每个点放5辆。并且其中序号为11，13，15，16，17，18自行车站由于桩内车未达到该站停车桩个数上限且桩外有人值守，所以不考虑调度。

其次我们通过对自行车桩内桩外自行车数的数据分析，找出需要调动的自行车租赁点，对这些需要调动的自行车租赁点进行分组，分组的个数即为调度所需公交车的数量。

4.4.2对需要调动的自行车租赁点进行分组，确定调度所需公交车的数量

分组的依据：首先考虑各个自行车租赁点在道路旁的方向；其次考虑各个自行车租赁点所需存放自行车的数量与搬运车上现有的自行车的数量。 4.4.3搬运路径的优化

依旧使用启发式搜索A*算法，进行最佳路线的选择。

五、模型的建立与求解

5.1利用AutoCAD 画出道路以及自行车停靠点的位置坐标图， 如下所示:

图1

在图1中，蓝线表示坐标系；红线表示地铁线；绿线所圈区域分别为居

民区（左）与地铁区（右）；黑色数字表示自行车租赁点编号；紫色数字表示所在路线长度(m)。

5.1.1对问题一中一辆搬运车的模型的建立与求解： 启发式搜索方法

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标[1]。基本思想是确定一个评价函数f 对当前的搜索状态进行评估，找出一个最有希望的节点来扩展[3]。此题中就是找出这个评价函数f （n ），从公交总站出发，对任意一个自行车停靠点进行评估，找出最有希望的自行车停靠点。 5.1.2启发式搜索方法的A*算法[2]

根据上面的启发式搜索方法的思想，我们利用A*算法进行计算，A*算法的具体解法如下：

A*搜寻算法，俗称A 星算法。这是一种在图形平面上，有许多节点的路径，求出最低通过成本的算法。在此算法中，g(n)表示从起点到任意顶点n 的实际距离，h(n)表示任意顶点n 到目标顶点的估算距离。

A*算法的公式: f(n)=g(n)+h(n)

在本题中，f(n)表示该启发式搜索中估价函数，g(n)在本题中表示从起点到任意自行车租赁点n 所需时间，h(n)在本题中表示任意自行车租赁点n 到下一个目标租赁点的估计所用时间，选择时间较少的自行车租赁点为下一个目标点。

回路中所用的所有时间如下表1

公交总站→

1（放29辆，剩31辆）→5→22→24→1（将剩余的31辆放完）→3（放14辆，剩余7辆）→9→10→11→6（放下5辆）→2→29→28（放8个，剩13个）→23→21→7→28→3→18→6→公交总站。（其余未标注的地方都是将租赁点放满）

5.2问题一中对两辆搬运车模型的建立与求解

5.2.1对两辆车在居民区所走的路线通过的自行车租赁点进行分组

在此问题中我们利用求解多个售货员的最佳旅行售货员回路问题的思想辆搬运车所走的路线通过的自行车租赁点进行分组，我们分组时所遵循的准则如下：

准则一：尽量使每条路线上搬运车所搬运的自行车数量均衡 准则二：应使每条路线所走的距离最短。

准则三：尽量使每条路所走的路程的长度均衡。

对于准则二，我们根据距离算出的均衡度进行比较，选出均衡性较优的一组。其中均衡度的计算公式如下:

其中，α0表示分组的均衡度，ωi 所分的组中每条路线的长度

由此均衡度的计算可得第二组的均衡度最小，我们选第二组为我们的最

优分组。

5.2.2我们根据模型建立中所用到的启发式搜索的A*算法得到的两辆搬运车回路中所用的所有时间如下表3：

车辆一：公交总站→30→29→28→23→21→9→5→3→28→7→22→24→公交总站

车辆二：公交总站→1→4→5→10→11→7→1→3→18→6→公交总站 5.3问题二模型的建立与求解 5.3.1启发式搜索方法

在此题中启发式搜索方法就是从1号站点作为出发点，找出满足此题的评估函数，然后根据此函数对居民区的11个自行车租赁点进行评估，找出搬运路径中的下一个最佳的自行车租赁点，然后从此租赁点出发在找下一

个，直到此次搬运车上自行车放完，回到1号站又找下一个租赁点直到所有自行车搬运完毕。

5.3.2启发式搜索方法的A*算法

A*算法的公式: f(n)=g(n)+h(n) 此题中，g(n)表示从1号自行车租赁点出发到居民区任意一个自行车租赁点所需要的时间。h(n)表示任意自行车租赁点n 到下一个目标租赁点的估计所用时间。

得到的具体结果如下表：

表4.1

→23（放16辆）→21（放16辆）→6（放5辆）→1（装50辆）→10（放2辆）→11（放16辆）→22（放16辆）→24（放16辆）→1（装50辆）→5（放25辆）→9（放25辆）1（装50辆）→10（放14辆）→18（放25辆）→6（放11辆）→1（车辆运完回到1号租赁点），所用的总时间为164.61分钟。

得到的每个租赁点停放车辆的数目，如下表：

其次我们通过对自行车桩内桩外自行车数的数据分析，找出需要调动的自行车租赁点，对这些需要调动的自行车租赁点进行分组，分组的个数即为调度所需公交车的数量。

5.4.1对需要调动的自行车租赁点进行分组，确定调度所需公交车的数量

Ⅰ. 分组的依据：首先考虑各个自行车租赁点在道路旁的方向；其次考 虑各个自行车租赁点所需存放自行车的数量与搬运车上现有的自行车的数量。

Ⅱ. 分组的算法：扫描法 ⑴扫描法的定义

此方法属于先分组再排路线的方式。该方法采用极坐标来表示各需求

点的区位，然后任取一需求点为起始点，定其角度为零度，以顺时钟或逆时钟方向，以车容量为限制条件进行服务区域之分割，再借由Lin 与Kernighan 的交换法进行需求点的排序，建构车辆排程路线。此方法也可以用来求解车辆数目。

扫描法的操作步骤：①以起始点v 0作为极坐标的原点，并以连通图的任意一自行车租赁点和原点的连线定义为角度零，建立极坐标，然后对所有的自行车租赁点所在的位置进行坐标系的变换，全部都转化为极坐标系。

②分组。从最小角度的自行车租赁点开始，建立一个组，按

逆（顺）时针方向，将顾客逐个加入到组中，直到自行车租赁点的需求总量超出了负载限制，然后建立一个新的组，继续按照逆（顺）时针方向，将自行车租赁点继续加入到组中。

③重复②的过程，直到所有的自行车租赁点都被分到某个组

为止。

根据此分组来确定调度所需公交车的数量，对自行车租赁点进行调入和调出的基本分类，具体结果如下：

其中序号为11，13，15，16，17，18自行车站由于桩内车未达到该站停车桩个数上限且桩外有人值守，所以不考虑调度。

5.4.2利用扫描法对需要调动的自行车租赁点进行分组

根据以上表6的数据分析我们发现，1号，8号，30号自行车的调度比较集中，所以我们以1号自行车租赁点，8号自行车租赁点，30号自行车租赁点为极坐标的起点，根据扫描法进行分组：

⑴以自行车1号租赁点为起点的极坐标图示表示如下：

图2（以自行车租赁点1号为坐标原点顺时针扫描图） ⑵以自行车30号租赁点为起点的极坐标图示表示如下：

图3（以自行车租赁点30号为极坐标原点逆时针扫描图） ⑶以自行车8号租赁点为起点的极坐标图示表示如下：

图3（以自行车租赁点8号为极坐标原点顺时针扫描图）

由于第三组自行车租赁点比较分散，因此扫描结果如上图，对剩余未扫描到的2，4，30，33由于对工作量的考虑编入第三组。 5.4.3搬运路径的优化

依旧使用启发式搜索A*算法，进行最佳路线的选择。 综上所述，最后对自行车租赁点的分组结果如下：

利用均衡度进行模型三的检验： 三组车辆工作的均衡度

六、模型的评价推广与改进

6.1对模型的评价

在模型一和模型二中，我们对交通图利用CAD 软件进行改造，对后面模型中路径的计算带来了很大的方便。我们利用启发式搜索的思想，达到减少搜索范围，降低问题复杂度的目的，然后便于问题的求解。总的来说，在求解小规模的车辆调度时，启发式算法与精确算法相比在精度上不占优势，但是在求解大规模的车辆调度问题时，启发式算法总可以在有限时间内找到满意的次优解。因此，在实际应用中，启发式算法用的更广泛些。在具体计算中，由于L5路具体位置不确定，因此在实际中结果可能与其略有偏差。模型三的优越性在于模型操作性强，应用方便，在实际应用中灵活度大，更便于贴近实际情况，推广性强。缺点在于，由于已知数据较少，可能在个别细节方面与现实有所出入，另外本题数据处理分析方法较为繁琐，可改进为更为简便的算法，三辆车工作的均衡度还有优化的空间。 6.2 对模型的推广与改进

由于模型的灵活度较大，因此更便于应用于现实情况，推广性强，可推广至校园或景区的便携交通工具的调度、公交车的调度等类似的最短路径问题。本题在数据处理方面方法较为繁琐，就此一点，可采用更简便的数据处理算法，以减少模型的计算时间。若将数据处理方法简便化，就可在运算中考虑更多的原始数据，得到更优的最终处理方案。

参考文献：

1. 《启发式搜索》——百度百科2012年8月24号； 2. 《A*搜寻算法》——维基百科；

3. 启发式图搜索.http://www.doc88.com/p-[1**********].htm；

4. 西北工业大学数学建模指导委员会 编. 数学建模简明教程. 高等教育出版

社.2008.9；

附录：

地铁站与公共自行车租赁点的简化图（图中已标注出每段路的长度）