基于双层规划的应急救援车辆调度模型

Emergency rescue vehicle scheduling model based on bi-level programming

为了在有限时间域内最大化各灾区应急资源需求满足量、减少延迟成本,采用网络流理论及双层规划建模方法,构建了含时间窗的应急救援车辆多次、多阶段动态调度模型,并利用基于动态规划的两阶段启发式算法进行求解.算例结果表明,最优解形成了集覆盖调度方案,即从供应点1出发的车辆覆盖需求点(1,3,7,8),从供应点2出发的车辆覆盖需求点(2,4,6),从供应点3出发的车辆覆盖需求点(1,5).在最优调度方案下,总延迟成本为0.双层规划能降低求解维度,上下层合作关系保证了全局最优的实现.因此,应急管理部门应先行决策应急资源的战略配置以有效提高各阶段救援车辆调度效率.

To maximize the total satisfied demand of disaster areas and minimize the cost of delay within a limited time domain,a multi-time and multi-period model of emergency vehicle dynamic scheduling with time windows is constructed by using the network flow theory and bi-level program-ming modeling method.And a two-phase heuristic algorithm based on dynamic programming is put forward to solve this problem.The numerical results indicate that the optimal solution is a set-cover scheduling scheme.The vehicles from supply point 1 cover demand points （1,3,7,8）;the vehicles from supply point 2 cover demand points （2,4,6）;the vehicles from supply point 3 cover demand points （1 ,5 ）.The total cost of delay is 0 under the optimal solution.The bi-level programming can degrade the dimension of the solution,and the cooperation relationship between the upper level and the lower level guarantees the realization of global optimization.Therefore,the emergency manage-ment department should first make strategic decisions of emergency resource allocation to effectively enhance the efficiency of the vehicle scheduling during each period.