Abstract: Public bike sharing system has been developing rapidly in China, encouraging people to cycle and use this low-carbon transport mode to make trips. It is therefore important to strengthen the public bike repositioning optimization in order to increase the attractiveness of cycling in Chinese cities. Based on the analysis of the background of public bike, we introduce a multiple type bike repositioning Problem. According to the shortage or excess of public bicycle in real life, we formulate a mixed-integer linear programming Problem to minimize the total cost. A hybrid tabu search is proposed to solve this Problem. The numerical experiments are performed to analyze the characteristics of the Problem and performance of the hybrid tabu search. The results show that the unbalanced penalty coefficient determines the amount of loading and unloading of bikes, and has an effect on the vehicle routing, which is the key factor to the optimization of the multiple type bike repositioning. Substitution strategy makes transportation decision more flexible. The hybrid tabu search can solve much larger network and obtain better quality solutions compared with the exact method.

Key words: multiple type public bike, transportation optimization, hybrid tabu search, vehicle routing problem

摘要： 公共自行车是我国正大力发展的低碳交通出行模式,加强公共自行车调运优化是提升自行车出行吸引力的关键要素。通过对公共自行车调运背景分析,提出了一类多类型公共自行车的调运优化问题。针对现实生活中租赁站点内公共自行车不均衡的情况,建立了以总成本最小为目标的混合整数线性规划模型,并提出一种改进的混合禁忌搜索对问题进行求解。通过数值实验分析了问题特性并验证了算法性能。实验结果表明非均衡惩罚系数决定了租赁站点各类自行车的装卸载数量,并影响了调配车辆的运行路线,是实现多类型公共自行车均衡优化的关键因素。不同类型自行车的替代策略使得调运决策更加灵活。混合禁忌搜索可以求解更大规模的问题,并能在短时间内求得较好质量的解。

关键词: 多类型公共自行车, 调运优化, 混合禁忌搜索, 车辆路径问题