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

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

单位：西安交通大学管理学院; 西安710049; 西安交通大学机械制造系统工程国家重点实验室; 西安710049; 香港城市大学系统工程与工程管理系; 香港999077