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

王天宇，韩 印，夏晓梅

（上海理工大学 管理学院，上海 200093）

0 引言

随着全球油价的上涨、交通拥挤和噪音、空气等污染，世界上许多城市鼓励使用公共交通代替私家车出行[1]。最有趣的解决方案之一是自行车共享系统（BSS），它是一个日益流行的系统。一位顾客使用自行车从一个车站到另一个车站。只要有一个空的上锁泊位，一辆自行车可以从任何一个车站取出，并可在任何时候返回任何站点。BSS需要的不仅仅是自行车和站点，各种其他设备和系统（例如：自行车车队，停车和锁定机制，用户界面和结账退出协议和站点网络），以及需要维护和管理需求（例如：车队和站点维修、状态信息系统和自行车再分配系统）来维持自行车和站点功能保持在足够的服务水平。

大多数有关自行车共享系统的研究都集中在其历史和发展上[1]，促销政策和安全问题[2]。在过去的几年中，很多科学文章正在研究这些系统中的各种问题，包括战略和运营设计。现有的关于公共自行车的研究主要集中在宏观层面分析其发展所遇到的政策性问题[3]、立法监管[4]、共享经济发展[5]以及共享单车调度优化[6]等问题。总体而言，较为成熟的研究方向可以归纳为两类：战略设计和运营设计。

在战略设计层面，一些工程研究BSS的战略规划，如选址、网络设计和战略规划目标的站点的能力等。国内相关专家，例如吴瑶、龚翔等，都是选取我国某一个城市，将理论研究投入到设计案例中，进行分析解剖，根据公共自行车分担率和居民出行需求测算出公共自行车的租借需求规模，再结合自行车和停车桩的周转率预测公共自行车的总需求和停车桩的总规模大小，提出为强化不同的分区内公共自行车的特色功能，各区站点布局应各有所侧重，有所不同，做到了针对性的研究和设计[7-8]。而国外专家研究则与国内略有不同，例如Vogel等，提出了一个合适的模型来测试动态定位策略对系统性能的影响，但是模型对于战略规划来说是有效的，对于平衡运营却没有足够的细节来支持[9]。

此外，在运营设计层面而言，系统的运营必须确保至少具有最低服务质量，以满足用户的最大需求并降低运营成本。国外专家，Dell'Olio等调查了站点的选址问题，并为自行车共享系统的设计和实现开发了一种方法。核心是基于对一个给定时期的需求的估算，考虑到站点和租金的价格[10]。而Kadri,et al[11-13]，则是预测用户未来的需求、自行车的可用性。我国学者则指出存在公共自行车系统不兼容、站点分布不合理、站点自行车保护措施欠佳等问题，认为要促进公共自行车的发展，不仅要解决以上问题，还应寻求长期可靠的资金来源以维持系统的可持续发展[14]。

综上所述，系统平衡已经成为一个重要的研究方向了，平衡运营可以在不同的模式下进行，有些操作人员使用静态平衡，有些则使用动态平衡，也可以通过考虑这两种平衡模式来实现[15-16]。在现有文献中，静态平衡问题（SBP）比动态平衡问题有更多的解决办法。大多数研究采用混合整数规划（MIP）技术。然而，对这些工作的比较是比较困难的，因为大多数文献都考虑了不同的问题特征[17-19]。

针对这类问题的不足，本文将重点放在单一车辆路径问题上，目标是在不平衡状态下最小化站点的总等待时间，以达到最大程度使用现有资源的目的。本文结构如下：在第1节中，本文提出问题并对问题进行建模。在第2节中，本文描述了所提出的分支定界方法以及相关的下界和上界。在第3节中，本文案例仿真并讨论了实验结果。最后，以一些评论和总结来结束全文。

1 问题描述和数学建模

图1 各区间示意图

本文的问题可以正式定义如下。问题的输入是一组站点，用一个指定的仓库，每个站（i）的当前状态（Ei），一个已知的阈值水平和）表示对于每个车站（i）所需的最小和最大的自行车数量，最后，在车站之间的时间扩展矩阵（dij）表示从站点i到站点j的在分配车辆的位移时间。平衡车辆的路线是由一个给定的序列表示在访问顺序上的站点。其目的是将在不平衡状态下等待时间总和的加权目标最小化，直到车辆到达。一个站点（i）的不平衡（w）表示在平衡操作前的（i）车站的自行车数量（E）和之前那个站的自行车［R,R］的ii信用等级之间的差距。因此，目标函数值取决于站点的不平衡和车辆的到达站点的时间（ti）。各区间示意图如图1所示：

1.1 问题描述

问题是找到再平衡车辆的一个最优调度，使其加权时间Σiwi（ti- t0）的总和最小，这里 （ti- t0）是站点仍留在站点（i）的不平衡（wi）的时间。符合条件的问题解决方案的数量，即使是小的也相当可观，因为结构类似于出行商的问题。因此，可行的Hamiltonian circuits（哈密顿回路） 的数量是平常的（n-1）!，这里n是站点的数量）。在多项式时间里精确地解决这个问题太难了。问题的复杂性变得越来越重要，尤其是当n很大时。这一问题属于强烈的NP—困难问题。

1.2 模型建立

在这一节中，本文提出SBP的数学公式。为了解决这个问题，首先引入以下符号、变量和参数。

符号：

n——站点的总数；

N——表示网络站点的节点的集合，i=1,2,…,n；

N0——节点集合，包括站点和仓库（0表示），i=0,1,…,n；

Ei——在重新定位操作开始之前，在节点i的自行车的当前数量；

Ci——站点i的容量（i=1,2,…,n）；

di,j——从站点i到j的出行时间；

ti——到达站点i的时间，i=1,2,…,n；

wi——站点i的权重，表示Ei和Ri的自信水平之间的差；

决策变量：xi,j——二元变量，如果站点i在j之前被访问就为1，否则为0，i=0,1,…,n;j=1,…,n且i≠j。

SBP问题可以由以下模型计算：

目标函数式（1）使加权次数的总和最小。约束式（2）迫使从仓库离开的车辆。约束式（3）表示车辆从仓库出发的时间。约束式（4） 确保从（i）到（j）站的车辆的位移所需的最少时间。约束条件式（5） （或式（6）） 是车辆的流量守恒方程（即一个车站只能一次被一辆车访问）。最后，式（7）是二元约束。

2 分支定界方法

由于问题的复杂性和分支定界（B&B）方法的搜索策略，本文开发了这种类型的算法来解决问题。这种方法的目的是通过减少搜索空间找到一个最优解。该方法基于不同的工具（下界、支配规则、上界）。在此部分，给出了建议分支和定界过程的特征。

搜索树最初由一个根节点组成，在过程中以动态的方式开发。上界由最佳可行解的值初始化，这是由一个或多个元启发式算法预先计算的。选择的方法是，通过使用选择策略，从对应于未开发的可行子问题的活节点组中选择一个节点探究。选择基本上是基于节点下界的值，它代表了车辆的部分调度。

分支方案包括在部分调度之后分配一个新任务。然后研究选定的节点，并构造节点的子节点（序列中未调度的站点）。这样，子空间就被分成了其他子空间。然后，为每个子空间计算一个下界。如果这样一个下界的值等于或大于上界，则会消除子问题（因此，子问题的可行解不可能比最优解更好）。使用深度优先和最佳优先策略来探索搜索空间，它允许在可能的情况下快速更新上界，因此当它们的下界值等于或大于上界时，就会消除节点。

2.1 下 界

边界函数是B&B算法效率的主要组成部分，不能被节点选择和分支的应用策略所抵消。在最好的情况下，给定子问题的边界函数的值应该等于最优解的值，然而，在大多数情况下，实现这样的目标是NP—困难的。

由于目标的目的是使函数最小化，因此有必要开发低边界的良好质量。一般来说，计算下界包括放松一些约束，然后解决一个更简单的问题。

这个从模型SBP的约束式（5）和式（6）放松的下界结果和加权最短处理时间的应用规则（WSPT和被称为史密斯的规则） 是最优的单机调度问题 （1｜ Σ wjCj），目的在于加权总完成时间的最小化。这个规则包括排序工作，以增加它们的比率pj/wj（pj表示工作j的持续时间，wj表示那项工作的相关权重，wj≥0，pj＞0）。

在构建路径（序列）时，放松授权重新使用相同的弧。下界的值是基于到达节点j的最小的出行时间di,j，对于给定的节点，本文分两步来计算这个下界：

（1）对于已执行的调度，本文将累积次数的总和加上相应的值wi。

（2）对于未执行的（未调度的）作业，本文将关联人工调度问题1｜ΣwjCj，其中x（x是未执行作业之一）的处理时间是到达相关节点的最短运行时间，并且权重等于wi。人工问题由史密斯的规则解决，加权完成时间被添加到步骤（1）中发现的值中。

2.2 上界

利用上界的质量是提高B&B算法效率的关键因素。基于这个原因，本文利用遗传算法来定义上界。

（1）解决方法编码。使用遗传算法解决问题的编码过程通常是最困难的方面。将它们应用于特定的问题时，通常很难找到解决方案的适当表示，从而易于执行交叉过程。SBP解决方案的良好编码必须确定被访问站点的顺序。一个合适的表示是一个染色体组成的站点的路线。应该按照它们在染色体中出现的顺序来访问每个站点。图2给出了一个9站点的网络表示的例子。

（2）交叉。主要的遗传算子是交叉，它模拟了两个个体（或者同卵）之间的繁殖。 这是通过从父母的其中一个基因的某些部分和另一人的其他部分进行的，并且在同一个孩子中进行。

（3）停止条件。在遗传算法中使用的停止条件是给定的迭代次数。即使本文没有找到局部或全局最优，也不可能收敛，但在给定的时间之后，程序就停止了。停止遗传算法的其他标准也可以使用（例如，如果在固定的迭代次数下没有改进最好的记录解决方案）。

3 案例仿真与分析

在本节中，本文将进行数值实验，以评估和比较算法。在区间［0,+10］内选取代表各站不平衡的权重值。对于n=｛10,20 ｝，本文定义了8组实例，具体结果见表1和表2。对于n=30，本文简单定义了5个组，具体结果见表3。因为B&B算法的时间要求更大。本文注意到所有的CPU时间都是秒。为了评估B&B的性能，计算实验是在相同的实例上进行的，用于评估下界和上界。计算时间限制在7 200s。B&B的性能表现在下面两张表中，本文使用“BB-NxGy”这个符号，其中x是n的值，y表示组号。报告的参数如下：

图2 9站点网络示意图

OPT——最优值的平均值；

UB*——最好上界值的平均值；

CPU——在几秒内分支定界计算时间的平均值；

Nbr——探索节点的平均数量；

Nd——消除节点的平均数量；

Np——在初步消除过程中消除节点的平均数量；

Gap（%）——最优上限与最优值之间的平均差值。

表1 10个站点实验结果汇总

表2 20个站点实验结果汇总

由上表可以得到以下几点结论：

B&B能够解决多达30个站点的实例；

（1）当n更大的时候，初步排除是更有效的，因为通过消除一个节点包含x剩余任务（x＜n）本文避免x!可能性和结果本文减少了B&B的计算时间；

（2）当n较大时，所探索的节点的计算时间和平均数量都较高。这是由于搜索空间的增加引起的。因此，搜索树越大，问题就越难解决。

表3 30个站点实验结果汇总

得到的结果表明，在合理的时间内可以计算出（n≤30）的最优解。此外，开发的B&B算法可以转化为一种贪婪的搜索算法，它能够在非常短的计算时间内提供良好的解决方案。

4 结束语

本文研究了考虑静态模式的自行车共享系统中的单个车辆调度问题。本文定义并制定了一个数学模型，它的动机是需要将不平衡状态下的车站等待时间降到最低。在分支定界的算法中，提出并使用了下界和上界。为了评估和比较本文的算法，在大量的实例上进行了数值实验。结果表明，B&B算法可以解决多达30个节点的实例。但是，此方法在短计算时间内解决更大数量问题仍然有些力不从心。

在未来的工作中，本文的目标是在其他类型的放松的基础上开发新的下界，以及一个分支切割的方法来加速本文的算法。此外，新的元启发式算法和表示方法的研究似乎很有趣，以提高上界质量，从而提高B&B的性能。