图5-2-1
5.3 求解分配方案的预估—校正算法
每个租赁点的单车数量可以以预估计算的方式经多次计算得出一个稳定解。即大部分租赁点的单车数量满足110%的要求，少部分租赁点单车数目远远超出需求量，还有少部分单车数目几乎为零（奇点）。最后，将计算所得的几个奇点分块，从自行车数量超出40或大量超出需求量的地点运送单车至奇点（用启发算式法计算运送路线及运送时间）。
5.4 求解调度方案的启发式算法
5.4.1算法简介
启发式算法是依据有限的知识在短时间内找到问题解决方案的一种技术。在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解。
在搜寻问题中，每个节点都有b个选择以及到达目标的深度d，一个毫无技巧的算法通常都要搜寻bd个节点才能找到答案。启发式算法借由使用某种切割机制降低了分叉率(branching factor)以改进搜寻效率，由b降到较低的b'。分叉率可以用来定义启发式算法的偏序关系，例如：若在一个n节点的搜寻树上，h1(n)
- 16 -
的分叉率较h2(n)低，则 h1(n) < h2(n)。启发式为每个要解决特定问题的搜寻树的每个节点提供了较低的分叉率，因此它们拥有较佳效率的计算能力。我们主要应用启发式算法的这个优点来解决本题的调度问题。
算法的流程图如下：
图5-4-3
5.4.2算法内容
以指定租赁店点为初始站点，对该租赁点的下一租赁点，搜索路径，搜索规则如下：
（1）查找与初始点距离最近的N个租赁点（N值按照题目适当确定），并且按照距离由小到大的规律排序；
（2）依次遍历排好序这N个租赁点，如果这个租赁点为需求点且需求量大于车上的剩余自行车（无法满足一次性完成调配），则删除该节点，并重新得到新的N个租赁点。
- 17 -
（3）计算每一层的自行车调度数量（取绝对值）和走过的距离，并求出两者的比值。
（4）以搜索到的满足条件的N个租赁点分别为初始点，重复第（1）-（3）步。搜索深度为N。
（5）求出每一次搜索路径自行车调度数量和走过距离的比值后，求和，选取比值之和最大的那条路径，则这条路径中初始节点对应的下一节点为调度方案的下一个调度点。
（6）以下一个点为起始点，重复第（1）-（5）步，直到所有的车辆都被搬运完毕。
算法如图所示：
。。。。。。
。。。。。。
起点 。。。。。。 。。。。。。
搜索至第N层后返回
图5-3-1
5.4.3约束条件
1、综合考虑租赁点的数目，搜索深度根据不同分组的站点数目N取3~5。 2、如果租赁点是调度需求点，则调度车上的自行车数目必须满足需求，一次性完成该租赁点的需求；如果该点是盈余点，则在不超过调度车最大负载的情况下，调度车要尽可能地多装；
- 18 -
3、调度的出发点选为某一个租赁点，从这一点出发完成调度后，需要返回原来的租赁点，但是返回租赁点的耗时不必计入总耗时； 4、两辆调运车不能同时到达一个租赁点。 5.4.4算法流程图 该算法的程序流程图如下：
图5-4-1
启发式算法能够解决在租赁点确定后的调度问题，在第一问、第三问中应用。
- 19 -
5.5租赁点位置
因为建立租赁点时应当考虑平均需求、最大需求两点，所以首先我们应当确定加权平均比例，我们认为，在两者比较中更加重要的是平均需求量，而最大需求量次之。我们经过查资料得知，有一些类似的问题多采用0.6与0.4的比例，但是我们认为此次问题的影响因素中平均值的价值不仅仅为0.6。经过我们的讨论，我们决定采用0.65与0.35的比例。
5.6计算结果
5.6.1第一问结果 启发式计算结果为：
早上A：26->27->7->8->9->28->10->24->22->6 早上B：5->20->18->11->12->13->14->3->4 中午A：9->10->24->22->4->17
中午B：26->7->30->8->21->20->18->12->11 晚上A；25->26->27->7->30->9->28->10->24->23->3 晚上B：19->5->20->21->18->11->12->14->2
图5-5-1
- 20 -
公共自行车调度问题-数学建模论文
