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

Bike rebalancing problem considering broken bike collection

作　　者：白雪[1,2,3] 周支立 钱桂生[3] 马宁[1,2] BAI Xue;ZHOU Zhili;CHIN Kwai-Sang;MA Ning(School of Management,Xi＇an Jiaotong University,Xi＇an 710049,China;State Key Laboratory for Manufacturing Systems Engineering,Xi＇an Jiaotong University,Xi＇an 710049,China;Department of Systems Engineering and Engineering Management,City University of Hong Kong,Hong Kong 999077,China)

机构地区：[1]西安交通大学管理学院,西安710049 [2]西安交通大学机械制造系统工程国家重点实验室,西安710049 [3]香港城市大学系统工程与工程管理系,香港999077

出　　处：《系统工程理论与实践》2018年第9期2326-2334,共9页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71390333);陕西省自然科学基金(2015JM7369)~~

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

关 键 词：公共自行车系统 自行车再分配调度 旅行商问题 动态规划 

分 类 号：U491.1[交通运输工程—交通运输规划与管理]