晚上B：16->15->50->2->32->33->23->21
晚上C：18->43->25->41->53->52->45->46->47->49 早上：t=6.3253e+003 s=105.4min<150min 中午：t=8.5675e+003 s=142.8min<150min 中午：t=8.7849e+003 s=146.4min<150min 平均：t=131.5min<150min
六、模型检验
1. 问题一中求解最短路径采用Floyd-Warshall算法，以动态规划为手段，解决任意两点间的最短路径，并通过Matlab求解；
2. 问题一求解最短调度时间采用启发式算法，通过C++程序设计穷举算法，并搜索最佳调度方案，由于上述结果是通过穷举得到的，必然全局最优； 3. 问题二引入方便因数，全面综合各方面因素，所以得到的站点分配为最优解。 4. 问题三的方法与问题一和问题二相似，故所求调度方案为最佳调度方案。
七、模型优缺点以及改进
在确定自行车的分配方案和调度方案时，这个问题是在已知节点具体的位置的条件下求解两个问题。我们对两个问题分开求解，即先确定最分配方案，再根据最优分配方案确定对应的最优调度方案。然而根据数学模型和实际情况得这两者并不是相互独立的，即问题最优解并非简单地两者最优解的结合。因此，我们的最优结果可能和实际情况存在偏差。
为了方便问题的求解，我们做出了一些假设，比如假设每辆调度车从固定的某租赁点出发，最后又回到原来的点，而实际情况中会更局具体情况选择车辆停靠点。这些假设方便了求解，但实际上简化了问题的复杂度。
- 26 -
7.1分配方案的优点
租赁点自行车分配中，我们采用了一种创新的分配方案，在分配中不仅考虑了需求量对分配的影响，而且还按照动态的目光，先给出合理的分配初值，然后让其按照自行车的骑行规律（即在某个租赁点还车的概率与租车点和还车点的距离成反比）自动分配若干次，每一次得出一个新的分配方案后和原来的方案比较，然后做出调整，最终得出最优的分配方案。这个分配方案的优点是突出的，主要体现在以下几点：
1、首先考虑了需求量对分配方案的影响，使之从一开始就是合理的，兼顾重要因素。
2、由于即在某个租赁点还车的概率是一个常数，所以常数因子对分配方案的影响可以通过一次优化最终补偿，最终的结果是形成的调度方案是满足骑行规律的最优解。
3、这个模型还有一个优点是，在校正后，能够使得需要调度的自行车数目达到最小，从而在计算调度量时，为最优解提供保证。
7.2调度方案的缺优点
调度方案的优点是在租赁点不大的情况下，按照启发式算法一次性可以把相对来说最优的调度方案解出来，建模简单，求解也相对比较容易。
调度方案的缺点重要体现在算法的局限性上。而启发式算法则试图一次提供全部目标。例如通常能发现很不错的解，但是也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。总的来说，启发式算法有一定的不稳定性。可以用性能更好的遗传算法或者退火算法解决。
7.3新增节点模型的优缺点
在求解新增节点时，我们巧妙地引入了一个“方便因数”，用来衡量新增的租赁点的合理程度，用求解最优解的思路来求解新增的租赁点和分配的自行车数目，模型简单明了，容易用现成的算法实现。
- 27 -
但是方便因数并没有将影响新增租赁点的所有的因素都考虑进去，仅仅考虑了分配值、节点数、和邻近该租赁点的其他租赁点的数目。其他因素如是否能达到调配量最小等因素没有考虑，其次定义的一些量如Pi、Si不尽合理，原因是只考虑了新增加的单个节点所收到的影响，不没有考虑新增的节点间的相互影响，因此所得的结果有可能和最优解有一定的差距。
7.4模型和算法的改进
7.4.1算法的改进
由于启发式算法的局限性，可以采用收敛速度更快的遗传算法（Genetic Algorithm，简称GA）和退火算法（Stimulated Annealing，简称SA）。与启发式算法相比较其优点有：计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。在本题中，由于数据量相对较小，启发式算法还能够满足要求，为了使结果更加稳定，可以考虑退火算法和遗传算法。 7.4.2模型的改进
我们可以把调度问题看成一个赋有权值的图G，先要求出图G的最小生成树，使树上各边的总权和达到最小。然后基于最早生成树生成一个可行的最短行车路径。
对上述30个租赁点重新编号，依次为1-30，用集合R表示。
我们用0-1变量xij来表示公交车是否从租赁点i到租赁点j,即
?1,公交车从租赁点i到租赁点jxij???0,否则（i，j?R)
目标函数为寻找一条从起始点开始到各个节点生成的最优树，要求各条线路的权值和最小，即
min?i?R?j?Rxijtij
约束方程为：
- 28 -
?n??xij?11?i?n? s.t??xij?1?i?1ui?uj?n?xij?(n?1)??uj?0?求解最小生成树的方法有破圈法、避圈法、Dijkstra算法等。这里我们
用避圈法求解，避圈法是指将图G中的边按照权数大小逐条考察，按不构成圈的原则加入到T（树）中，直到q(T)?p(G)?1为止，即T的边数=G的顶点数-1为止。
避圈法的算法是：
1. 把G的边按权的大小整理成
w(e1)?w(e2)??w(em).
令T0?(V,?),i?1,j?0.
2.若Tj?ei含圈，则转3，否则转4.
3．令i?i?1，若i?m则转2；否则停止，G不存在最小生成树。 4.令Tj?1?Tj?ei，j?j?1。
5.若j?n?1，结束，Tj是最小生成树；否则转3.
根据避圈法的算法，编写Matlab程序求得结果，得到最小生成树，结果列表如下：
表7-4-1 求最小生成树结果
注：图中打√处表示两个租赁点连通。
采用最小数算法算出的搜索路径比较原模型结果比较稳定，这是一个突出优点。
- 29 -
八、参考文献
[1] Clarke G and Wright J. Scheduling vehicles from a central depot to number of
delivery points[J]. Operations research, 1964, 12(4): 12-18
[2] 刘登涛, 方文道, 章坚民, 等. 公共自行车交通系统调度算法[J]. 计算机系统应用, 2011, 20(9): 112-116.
[3] 崔宏志, 龚加安. 带时间窗车辆路径问题的改进节约算法[J]. 纯粹数学与应用数学, 2011, 27(5): 688-693..
[4] 柳祖鹏, 丁卫东, 程逸旻. 公共自行车系统站间调度优化研究[J]. 城市公共交通, 2011 (1): 39-42.
[5]肖华勇.实用数学建模与软件应用.西安：西北工业大学出版社 2008.11
附录
1距离计算： ○
distance=zeros(53); for i=1:1:53 k=1; for j=1:1:53 if i~=j
distance(i,k)=abs(x1(i,1)-x1(j,1))+abs(x1(i,2)-x1(j,2)); end k=k+1; end end
2概率系数计算： ○
K=[]； for i=1:1:53
- 30 -
公共自行车调度问题-数学建模论文
