电梯的模拟算法与优化调度方案(8)

第一步，画出与图7相似的动态规划图形。

第二步，计算出图形中每条线段的长度。如果线段是从楼层i到楼层j的，那么

j?iW?j?i,i?1?，W?j?i,i?1?表示分区的最低楼层为第i+1该线段长度取值为m3P?11nr?1rINTW?tp???xl?2Sr?1l?02求出的去该楼层，且该分区共有j-i层楼时，根据

层分区的乘客的平均逗留时间。

第三步，求解最短路径问题；这里采用Dijkstra算法，求得最短路径和对应的分区区间。

Dijkstra算法的C语言描述：

Void ShortestPath.DIJ(MGraph G , int v0 , PathMatrix &P, ShortPathTable &D){

∥用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权长度D[v]。

∥若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。 ∥final[v]为TRUE当且仅当v?S，即已经求得从v0到v的最短路径。 For(v=0;v

Final[v]=FALSE;D[v]=G.arcs[v0][v];

For(w=0;w

D[v0]=0;final[v0]=TRUE; ∥初始化，v0顶点属于S集 ∥开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 For(i=1;i

min=INFINITY; ∥当前所知离v0顶点的最近距离

for(w=0;w

if(!final[w]) ∥w顶点在V-S中 if(D[w]

final[v]=TRUE; ∥离v0顶点最近的v加入S集

24

for(w=0;w

if(!final[w]&&(min+G.arcs[v][w])){ ∥修改D[w]和P[w]，w?V?S D[w]=min+G.arcs[v][w];

P[w]=P[v];P[w][w]=TRUE; ∥ P[w]=P[v]+[w] }∥if }∥for

}∥ShortestPath.DIJ

第四章 模型的推广

①在当地一座有4部电梯的4到12层的居民楼，收集高峰时（如早高峰）乘客到达间隔（可能的话，还有到达楼层）的数据，并且根据数据（构造累积直方图）建立到达间隔和到达楼层的子模型。最后也可以得到附录表1那样的结果。

②对于大型商场，我们可以根据该算法，在多方采集数据的情况下，更好地设计调度方案。比如：我们可以连续二或三天进行调查，在全天的运营调查中，调查每位乘客的目的地楼层；调查节假日的客流情况。

第五章 模型的评价

25