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


## 学习目标

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

  • 赛题任务:针对工作日早高峰厦门全岛附近停车和用车问题,自由进行数据分析和算法模型构建,以共享单车资源合理分配为目标,设计共享单车调度方案;

  • 赛题数据:共享单车轨迹数据、共享单车停车点位(电子围栏)数据、共享单车订单数据、轨道站点进站客流数据、轨道站点出站客流数据 和 轨道站点闸机设备编码数据;


## 单车利用率

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

$$单车利用率 = \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}$的单车调度。

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

思路:按照区域完成单车调度,匹配单车使用需求;

实现过程

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

优缺点:

  • 优点:计算简单,速度快;
  • 缺点:只能完成局部计算,且不是全局最优的策略;

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

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

实现过程

  • 步骤1:初始化初始种群,使用贪心思路生成$N$个个体,即$N$种调度策略;
  • 步骤2:选择合适种群,根据评价指标计算所有$N$种调度策略的目标代价,选择其中$K$种较优的调度策略;
  • 步骤3:对选择的$K$种调度策略完成交叉变异操作:
    • 交叉:对两种调度策略互换其中部分调度过程;
    • 变异:选择一种调度策略,对调度过程进行随机修改,如修改调度单车数量和调度路线;
  • 步骤4:使用步骤3又可以得到$N$种调度策略,goto步骤2继续演化;

优缺点:

  • 优点:是全局优化的策略,且有可能搜索到最优策略;
  • 缺点:运行时间较长,且演化过程中的交叉和变异,需要解决调度冲突的问题;

## 改进思路

  1. 从订单数据和轨迹数据中可以固定一个单车ID,去分析现有单车调度的策略;
  2. 对于单车调度尽量是考虑提高单车骑行率,还是需要完成潮汐分析;
  3. 对于单车调度可以量化调度成本,如调度步骤和调度距离;

## 参考文献



## 报告撰写建议

  1. 建议考察下现有单车调度建议,并进行对比分析;
  2. 可以选择一个位置,进行具体分析并给出具体建议,并对比优化前后对比;
  3. 数据使用+技术架构,可以先设计demo,撰写好文档;

赛题FAQ:https://shimo.im/docs/dpgWPXRcygjKg9GH/



© 2019-2021 coggle.club 版权所有     京ICP备20022947    京公网安备 11030102010643号