任务4：共享单车调度方案

发布时间：2021-01-25，作者：阿水, 鱼遇雨欲语与余

## 学习目标

单车利用率计算
单车调度过程和衡量指标
单车调度算法

赛题任务：针对工作日早高峰厦门全岛附近停车和用车问题，自由进行数据分析和算法模型构建，以共享单车资源合理分配为目标，设计共享单车调度方案；
赛题数据：共享单车轨迹数据、共享单车停车点位（电子围栏）数据、共享单车订单数据、轨道站点进站客流数据、轨道站点出站客流数据和轨道站点闸机设备编码数据；

## 单车利用率

共享单车作为城市交通中重要的一环，可以方便市民便捷出行。但单车具体的位置随着群体波动，并且容易出现单车潮汐和分布不均衡的情况，最终导致单车利用率较低。

$$单车利用率 = \frac{每小时单车骑行秒}{3600秒}$$

首先我们可以统计不同品牌单车的利用率：

# 共享单车轨迹数据
bike_track = pd.concat([
    pd.read_csv(PATH + 'gxdc_gj20201221.csv'),
    pd.read_csv(PATH + 'gxdc_gj20201222.csv'),
    pd.read_csv(PATH + 'gxdc_gj20201223.csv'),
    pd.read_csv(PATH + 'gxdc_gj20201224.csv'),
    pd.read_csv(PATH + 'gxdc_gj20201225.csv')

])
bike_track = bike_track.sort_values(['BICYCLE_ID', 'LOCATING_TIME'])

bike_use_ratio = bike_track.groupby(['source','BICYCLE_ID', 'hour'])['date'].count() * 15.0 / 3615
bike_use_ratio = bike_use_ratio.reset_index()
bike_use_ratio.groupby(['source', 'hour'])['date'].mean()

统计结果：

source   hour
halou    6       0.157031
         7       0.221240
         8       0.315490
         9       0.223382
meituan  6       0.092250
         7       0.099389
         8       0.099104
         9       0.108867
qingju   6       0.054113
         7       0.161101
         8       0.195099
         9       0.120881
Name: date, dtype: float64

从统计结果我们可以看出哈喽单车的利用率是其中最高的，而且随着早高峰的到来变化也非常明显。其次是青桔单车，单车利用率也较高。表现最差的是美团单车，单车利用率较低，且在早高峰并没有充分利用。

## 调度衡量指标

对于共享单车利用率比较低的原因主要是单车调度不到位导致的，即在需要骑车的位置要有单车。这个过程就是单车调度的目标，在原始电单车分布的情况下对单车进行调度，让单车利用率变得更高。但是单车调度是存在成本的：

每次调度的单车是有限的；
每次调度的单车是存在时间成本；

调度具体的衡量因素包括：

调度之后的单车的使用率；
调度之后的停车点的潮汐情况；
调度过程中的调度成本：
- 调度单车个数；
- 调度单车次数；

因此单车调度方法的优化指标可以写为：

$$ \begin{align} 优化指标 &= min(1-全局单车使用率) + 调度成本 \\ &=min(1-全局单车使用率)+min(调度单车个数) + min(调度单车次数) + min(调度单车距离) \end{align} $$

## 单车调度算法

### 分析思路

对于单车调度可以考虑从订单数据和轨迹数据同时入手：

对于订单数据，我们可以参考算法分析题的思路，识别出具体的潮汐点。然后判断潮汐点和停车点的位置来完成具体的调度操作；
对于轨迹数据，我们从单车利用率的角度来分析不同公司单车的调度策略，并与之进行对比分析；

### 调度算法设计

调度的目的是希望增加单车单位时间内的骑行率，所以设计的调度原则可以为：

统计固定时间和经纬度下共享单车用车需求$Demand$；
统计固定时间和经纬度下共享单车的停入流量$Inflow$；
根据用车需求$Demand$和停入流量$Inflow$计算停车存量$Deposit$（如果为负数则为缺口量）；
- $Deposit > 0$，则需要调度进入单车；
- $Deposit < 0$，则需要调度出单车；

具体的调度策略可以为：

优先满足$Deposit$的需求，尽可能保证市民有单车可以骑乘；
尽量压缩单车调度的成本，最小化调度单车个数和调度单车距离；
在同等调度步骤情况下，调度步骤越少越好；

因此现有的数据可抽象为，在给定具体的潮汐点和停车点位置$V$组成的地图$Map_{bike}$的情况下，具体需要具体位置调度，如从位置$v_1$到$v_2$完成$w_{1-2}$的单车调度。

### 基于贪心思路的调度算法

思路：按照区域完成单车调度，匹配单车使用需求；

实现过程：

将厦门地区按照经纬度完成聚类，或直接使用厦门原始地区划分；
计算每个区域内部的停车点和潮汐点的停车存量$Deposit$；
对每个区域内按照$Deposit$缺口进行排序，从本区域内单车存量位置调度到缺口位置；

优缺点：

优点：计算简单，速度快；
缺点：只能完成局部计算，且不是全局最优的策略；

### 基于遗传算法的调度算法

思路：将每种调度算法视为个体，将单车位置$V$调度过程视为一个变量序列，使用遗传算法完成演化；