电梯优化策略

架构

UML类图

• 采用架构为三类线程、分配器与控制器分离

请求处理流程

优化策略

强测结果

请求拆分策略

策略概述

• 拆分与分配独立，无需在拆分时考虑电梯的实时状态

• 使用静态Floyed预处理求最短路

• 无向图中边的定义为：

  $\forall F_i \forall F_j \quad R(F_i, F_j)\leadsto g(F_i,F_j)=|F_i-F_j|$∀Fi​∀Fj​R(Fi​,Fj​)⇝g(Fi​,Fj​)=∣Fi​−Fj​∣

  $\forall F_i \forall F_j \quad !R(F_i, F_j) \leadsto g(F_i,F_j)=INF$∀Fi​∀Fj​!R(Fi​,Fj​)⇝g(Fi​,Fj​)=INF

  其中$R$R为三类电梯总的可达性矩阵，且$R(F_i,F_j)=R_A(F_i,F_j)|R_B(F_i,F_j)|R_C(F_i,F_j)$R(Fi​,Fj​)=RA​(Fi​,Fj​)∣RB​(Fi​,Fj​)∣RC​(Fi​,Fj​)

• 换乘的花费定义：

  $dp(F_i, F_j) \sim dp(F_i, F_k)+g(F_k, F_j)+1$dp(Fi​,Fj​)∼dp(Fi​,Fk​)+g(Fk​,Fj​)+1

  即定义换乘花费为$1$1

• 与以不同电梯花费相关的值作为边权不同，主要考虑点在于拆分器与分配器的行为匹配

  如果拆分器认为应该把任务M给A电梯处理，但分配器进行分配时发现A电梯已经满载或距离起始楼层太远，而将任务M分配给了另外的电梯，这样反而相对最好的情况相差太大

  上述定义的拆分策略不是最优，但相对来说平均性能较好

• 静态在于针对A，B，C三类电梯建图，新增电梯不需要修改

实现细节

• 中间点k的循环一定要在最外层！

• 否则dist(i,j)的确定不会因为更多的路径更新而更新，即以i->j->k的顺序枚举时，最后一次更新dist(i,j)后的值不是最优的

• 通过trace跟踪当前dist(i,j)最短路上的上一个节点来获取路径，即拆分后的任务，简洁一点可以用递归找

• 存储数据结构采用单链表，构建HashMap以personID作为key，每个人一个单链表，任务节点定义如下

  

• 查找较为方便高效

控制器策略

策略概述

• 注意到对于每一个电梯的每个时刻可能的决策空间只有向上与向下两种，这对枚举策略很友好

• 借鉴启发式搜索中的估价函数，贪心地选取估价函数中最优的策略

• 最重要的是如何选取估价函数h*(state)，需要保证估价函数与真实情况十分相近，其中最优的真实情况h(state)是估价函数的下界，即$h(state)\le h^*(state)$h(state)≤h∗(state)

• 但h(state)无法通过较短时间获取，需要暴力搜索，不可取

• 估价函数$h^*(state)$h∗(state)一种可能的定义为

  当前状态的电梯使用LOOK策略到电梯运行结束还需要的耗时（针对第一次作业）

实现细节

• 定义模拟器类，调用Simulator.simulate(…)根据当前状态获得LOOK运行至结束的花费，作为估价函数

• 需要注意模拟器的修改需要clone一下，避免对原电梯状态进行改变

分配器策略

策略概述

• 对于多个电梯，控制器仅仅解决了单个电梯给定任务集后的最佳调度

• 同样采取枚举策略，尝试将当前待分配任务分别加入到每个电梯进行枚举，将所有电梯运行时间的最大值作为估计函数（针对第二次作业），即

  ​ $h^*(state) = max(runtimeCost(E_i))$h∗(state)=max(runtimeCost(Ei​))

  其中，$E_i$Ei​定义为按照state规定的加入当前任务后的电梯

• 最后将$argmin(h^*(state))$argmin(h∗(state))作为最终决策应用到实际电梯中进行分配

• 对于第三次作业的评价指标加入了等待时间之和，只需要按照指导书性能值的配比修改估价函数的计算方式就行了，其他不需要改变

• 由于$\sum_{stage}(T_1+T_2)\ne \sum_{stage}T_1+\sum_{stage}T_2$∑stage​(T1​+T2​)​=∑stage​T1​+∑stage​T2​，所以估价函数应在最终决策时确定，模拟器返回一个runtimeCost与waitingCost的Pair

  ​ $h^*(state)=max(runtimeCost_{E_i})+\sum waitingCost_{E_i}$h∗(state)=max(runtimeCostEi​​)+∑waitingCostEi​​

实现细节

• 其中初始值的设定使用了INT_MAX是为了防止使用LONG_MAX进行加法的意外溢出

其他优化

• 拆分后的任务如果第一阶段已经完成了才通知分配第二阶段，会造成电梯等待的浪费，即电梯等待楼层与接客楼层太远

• 分配第一阶段任务后，新增一个操作，选一个电梯的等待楼层设置为第二阶段的起始位置

• 用循环链表管理当前分配到哪个电梯，继续寻找下一题个Waiting状态的电梯进行等待楼层设置

• 如果遍历一圈了都没空，就设置当前这个电梯等待楼层为第二阶段起点

• 平均下来等待楼层能够较为分散，且每个电梯任务量较平均

• 当前分配到哪个电梯，继续寻找下一题个Waiting状态的电梯进行等待楼层设置

• 如果遍历一圈了都没空，就设置当前这个电梯等待楼层为第二阶段起点

• 平均下来等待楼层能够较为分散，且每个电梯任务量较平均