综合考量借还车需求与调度成本的公共自行车调度优化模型

An Optimization Model for Bike Repositioning in Bike-sharing Systems Considering Both Demands for Borrowing or Returning Bikes and Costs of Repositioning Operations

传统的公共自行车调度模型要求各自行车租赁站点的自行车取送需求已知并严格得到满足,这可能会为了少数车辆的平衡而大大增加调度成本(一些站点经调度后的自行车数量可能与目标数量只差几辆,对于满足的借、还车需求大小影响很小,而如果严格按照目标值进行调度的话卡车调度路线长度或时间会增加很多)。基于此,提出一个新的公共自行车调度模型,该模型并不需要所有的站点都严格按照事先给定的自行车配备数量进行调度,并综合考虑满足借还车需求最大化目标及调度成本最小化目标,分析调度约束及系统中借车与还车在时间上与空间上的动态演化过程,对卡车调度线路进行优化,得到各站点应配置的自行车数量及可满足的借还车需求大小。随后,对模型提出相应的遗传算法求解方法,设计适宜求解的编码与遗传算子,通过算例对该模型进行验证,并与传统的自行车调度模型的计算结果进行比较。研究结果表明:通过调整多目标之间的权重,并运用该模型进行优化可得到较好的既能最大程度满足借还车需求而调度成本又较省的调度卡车行驶路线方案;提出的模型在满足借还车需求减少比例很小的情况下使得调度时间明显下降;如果硬性要求每个自行车租赁站点的调配需求都严格满足的话,调度时间将会明显增加。研究成果可为公共自行车调度提供依据。

Traditional bike-rebalancing models in bike-sharing systems required that the number of bikes allocated at each bike station be known and that they meet the exact demand values,which may increase costs sharply for repositioning small numbers of bikes.(The number of bikes at some stations after repositioning considering both demand and operation costs may be just a few less than the exact demand,with little impact on the number of satisfied demands for borrowing or returning bikes,whereas the route length or time expense of truck scheduling may increase significantly if scheduled to meet the exact demand values).Therefore,this paper proposes a new bike-rebalancing model,which does not require a strict allocation in advance for a given number of bikes to all stations.The proposed model comprehensively considered both demands for borrowing and returning bikes and costs of repositioning operations.It also analyzed the constraints and dynamic evolution of bike-borrowing-and-returning in time and space.The model facilitated the optimization of the scheduled routes of trucks,and the determination of both the number of bikes allocated at each bike station and the number of satisfied demands.Genetic algorithms were developed for solving the proposed models,and the code and genetic operator were created to solve the models.A numerical example showed that,through the adjustment of weights amongst multiple goals in the proposed model,a truck routing scheme can be determined that can not only finely satisfy the demand for borrowing and returning bikes,but also save costs for repositioning operations.Results indicate that,in comparison with the traditional bike-repositioning model,the proposed model leads to a 30%reduction in scheduling time with an approximately 2%reduction in the satisfied demand for borrowing or returning bikes.The repositioning time will obviously increase if the number of bikes allocated to each bike station are required to meet demands strictly.This research provides a foundation for bike repositioning in bike-sharing systems.