基于自行车共享系统静态再平衡问题的分支定界算法

摘要

自行车共享系统是一种交通系统,允许用户在分散在城市各处的众多自动租车点之一租用一辆自行车,使用它们进行短途旅行,并在任何站点返回.良好的服务质量是建立在再平衡操作基础上完成的,具体形式表现在将自行车从一些车站移走,并将它们转移到其他车站.为了提高服务质量,研究了静态情况下的再平衡车辆路径问题,即车辆在各车站之间进行往返,以将其返回到所期望的站点,而且每一个站只能访问一次.这个问题类似于有额外限制出行的推销员的问题.其目的是找到一种最优的车辆调度方法,使车站在不平衡状态下的总等待时间最小化.首先建立相关模型,提出使用下界和上界.这些边界用于分支定界算法进行计算,得出最优解.为了验证方法可行性,对大量实例进行了计算实验,得到的结果表明了该方法的有效性.