基于贪心算法的共享单车的优化调度模型

卢泗化 李倩文

摘要：在经济、科技发展都如此迅速的信息时代，共享经济逐渐发展壮大，共享单车成为新的四大发明之一，它改变了人们短途出行方式，随之而来的共享单车分配成为业界的关注焦点。本文主要考虑城市内某些单车投放点供求关系不平衡需要进行调度服务，使各单车投放点的数量保持动态平衡，根据已知数据利用贪心算法在一定的约束范围内，制定出共享单车的调度方案，同时满足人们对共享单车的需求及调度成本最小，希望有助于共享单车的优化调度。

关键词：调度模型 供求不平衡 动态平衡 贪心算法

一、引言

随着共享经济的发展，在各大公交站台，地铁出入口以及商场、小区等地区均有共享单车的投放点，共享单车是一种分时租赁模式，由企业自主经营，由于其价格低廉，绿色低碳且短途出行十分方便，受到广大人民群众的欢迎。每一辆共享单车都有GPS定位，手机下载APP能够随时观测到共享单车的位置，并且某些共享单车企业会雇佣员工对车辆进行移位、维护等服务，使各个单车投放点均有一定数量单车满足顾客需求且摆放整齐，这对共享单车投放、调度起到十分重要的作用。

二、模型的假设

仅考虑成都市五大主城區之间的共享单车调度，且五大主城区内的共享单车总量不变。

不考虑共享单车损毁、故障的情况。

车辆调度均考虑在凌晨0点到6点之内。

每个投放点既为出发点又为到达点。

仅考虑车辆每天早上6点时的初始状态及凌晨12点的末状态。

不考虑车辆回到原区域的情况。

共享单车分配点的数量始终不会为负数。

三、各区域共享单车调度状态的确定

各区域共享单车的分配量即为各区域共享单车数量的初始状态，经过一天的时间，早上6点到凌晨12点。各区域的共享单车数量会有所变化，则需要对各区域的共享单车进行调度。共享单车的调度状态分为两种，第一种为一天内，人对单车的需求量大于单车的数量。第二种为一天内，人对单车的需求量小于单车的数量。根据各区域所处的调度状态来制定调度方案。

首先确定各区域单车末状态的数量：

由上表可得出如下结论：

到单车数量末状态时，1、2、3区域的单车数量多于初始状态量，而4、5区域的单车数量少于初始状态量，故需要将1、2、3区域的单车调度到4、5区域。

约束条件：

由之前问题分析可知需要将1、2、3区域的单车调度到4、5区域。

1.从1、2、3区域调度出来的单车数量为车辆末状态与初始状态的差值。

2.从1、2、3区域调度出来到达4、5区域的单车数量为4、5区域车辆初状态与末状态的差值。

3.从1、2、3区域调度出来的单车数量与4、5区域补充的单车数量一致。

4.从1、2、3区域出发仅能选择一个目的地。

5.回到4、5区域的单车的来源是1、2、3区域调度的单车。

五、模型求解

经过贪心算法得出最佳调度方案为：先将区域3的单车调运4.6万辆到区域4，然后再将区域2的单车调运1.5万辆到区域4；将区域3的单车调运1.5万辆到区域5，最后将区域1的单车调运2.3万辆到区域5。

六、结语

在大多数情况下，单车投放点供求不平衡的情况是十分常见的，所以对单车进行合理地分配与调度十分重要，这不仅能提高单车的使用效率而且能提高顾客的满意度，如果方案合理的话还能达到成本最小化。所以在现实生活中，对各个单车投放点进行定期地调度是十分，必要的，此模型仅提供一定借鉴作用，希望能起到一定的帮助。