考虑维修车辆的公共自行车系统再平衡问题

城市公共自行车系统由于不均匀的需求分布,需要进行自行车再分配调度,并且随着系统的使用,待维修自行车的收集和运返也成为日常运营的重要活动.本文研究考虑了自行车运返维护的静态自行车再分配问题,是一种包含正常自行车和待维修自行车的双货物路径规划问题.针对问题建立整数规划模型,提出了基于动态规划的精确算法,并根据问题特性引入两条加速规则.基于多组随机生成算例进行实验计算,并且与CPLEX进行对比,此外还针对维修车辆的数量进行了敏感性分析.计算结果验证了两条加速规则的有效性,所提动态规划算法可以有效地求解该问题.

Bike rebalancing problem considering broken bike collection

In public bicycle system, bike rebalancing is crucial to meet the fluctuating demand of bikes. With the use of system, broken bike collection and maintenance also become into important activities in daily operations. This paper studies the static bike rebalancing problem with broken bike collection, which is a two-commodity (normal bikes and broken bikes) routing problem. An integer programming model is formulated for the problem. A dynamic programming based algorithm is proposed to solve the model, which includes two speed rules based on attributes of the problem. We test the model and algorithm by several random instances, comparing with CPLEX. The results verify the effectiveness of two rules and indicate that the proposed algorithm can solve the problem efficiently.