A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems
A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems
复制标题
DOI：
10.1016/j.cie.2016.02.002
复制
发表时间：
2016-05-01
影响因子：
7.9
通讯作者：
Labadi, Karim
中科院分区：
文献类型：
--
作者：
Kadri, Ahmed Abdelmoumene;Kacem, Imed;Labadi, Karim
自行车共享系统是允许用户在分散在城市周围的许多自动租赁站之一租用自行车，使用它们进行短途旅行并在任何车站归还它们的交通系统。这种系统成功的一个关键因素是它能否确保向用户提供良好的服务质量。这意味着有自行车可供取车和免费归还自行车的地方。这是通过重新平衡操作来执行的，该操作包括使用专用车辆将自行车从一些站点移除并将其转移到其他站点。在本文中，我们研究的再平衡车辆路径问题，考虑静态的情况下。车辆在站点之间进行图尔斯游览，以使它们返回到预先已知的期望水平，并且每个站点必须由车辆恰好访问一次且仅访问一次。这个问题类似于附加约束的旅行商问题。其目的是找到一个最佳的车辆调度，最大限度地减少在不平衡状态下的车站的总等待时间。我们提出了几个下限和上限。这些定界过程用于分支定界算法。在大量实例上进行了计算实验，结果表明了该方法的有效性。(C)2016爱思唯尔有限公司版权所有
Bicycle sharing systems are transportation systems that allow the users to rent a bicycle at one of many automatic rental stations scattered around the city, use them for a short travel and return them at any station. A crucial factor for the success of such a system is its ability to ensure a good quality of service to users. It means the availability of bicycles for pick-up and free places to return them. This is performed by means of a rebalancing operation, which consists in removing bicycles from some stations and transferring them to other stations, using dedicated vehicles. In this paper, we study the rebalancing vehicles routing problem by considering the static case. Vehicles conduct tours between stations to return them to their desired levels, which are known in advance, and each station must be visited exactly once and only once by a vehicle. This problem is similar to the traveling salesman problem with additional constraints. The aim is to find an optimal scheduling of the vehicle that minimizes the total waiting time of the stations in disequilibrium states. We propose several lower and upper bounds. These bounding procedures are used in a branch-and-bound algorithm. Computational experiments are carried out on a large set of instances and the obtained results show the effectiveness of our method. (C) 2016 Elsevier Ltd. All rights reserved.