摘要
自行车共享系统是一种交通系统,允许用户在分散在城市各处的众多自动租车点之一租用一辆自行车,使用它们进行短途旅行,并在任何站点返回。良好的服务质量是建立在再平衡操作基础上完成的,具体形式表现在将自行车从一些车站移走,并将它们转移到其他车站。为了提高服务质量,研究了静态情况下的再平衡车辆路径问题,即车辆在各车站之间进行往返,以将其返回到所期望的站点,而且每一个站只能访问一次。这个问题类似于有额外限制出行的推销员的问题。其目的是找到一种最优的车辆调度方法,使车站在不平衡状态下的总等待时间最小化。首先建立相关模型,提出使用下界和上界。这些边界用于分支定界算法进行计算,得出最优解。为了验证方法可行性,对大量实例进行了计算实验,得到的结果表明了该方法的有效性。
The bicycle sharing system is a transportation one that allows users to rent a bicycle at one of the automatic rental points scattered throughout the city, use them for excursions, and return them at any site. Good service quality was built on the basis of rebalancing operation. The specific form is to remove the bicycles from some stations and transfer them to other stations. In order to improve the quality of service, the problem of rebalancing vehicle path is researched under the static condition, which refers to when the vehicles are used between stations, they can be returned to the expected site. Meanwhile, each station can only be accessed once. This kind of issue is similar to the problem of travel salesmen with additional restrictions. The purpose is to find an optimal vehicle scheduling method which minimizes the total waiting time of the station in an unbalanced state. First, establish a related model, and then propose the using of lower and upper bounds. These boundaries are used for branching and bounding algorithms for calculation, so as to get the optimal solution. To verify the feasibility of the method, we did plenty of computational experiments on a large number of instances. The results obtained has shown the effectiveness of the method.
作者
王天宇
韩印
夏晓梅
WANG Tianyu;HAN Yin;XIA Xiaomei(Management School,University of Shanghai for Science and Technology,Shanghai 200093,China)
出处
《物流科技》
2018年第11期73-77,共5页
Logistics Sci-Tech
基金
国家自然科学基金项目(51608324)
上海理工大学人文社科项目(SK18YB14)
关键词
自行车共享系统
车辆调度
等待时间
下界和上界
分支定界算法
bicycle sharing system
vehicle scheduling
waiting time
the lower bound and upper bound
the branch and bound algorithm
