资源布局和调度.pdf

应急资源布局与调度问题研究应急资源布局与调度问题研究应急资源布局与调度问题研究应急资源布局与调度问题研究 回顾与展望回顾与展望回顾与展望回顾与展望 报告人报告人 许建国许建国报告人报告人 许建国许建国 应急资源管理应急资源管理 突发事件发生以后的应急响应包括几突发事件发生以后的应急响应包括几 个关键环节个关键环节 确定所需应急资源确定所需应急资源 从相从相个关键环节个关键环节 确定所需应急资源确定所需应急资源 从相从相 关单位调配该应急资源 资源到位后规关单位调配该应急资源 资源到位后规 划急救活动划急救活动 在应急响应的过程中所需在应急响应的过程中所需划急救活动划急救活动 在应急响应的过程中所需在应急响应的过程中所需 要的应急资源种类与数量的预测将决定要的应急资源种类与数量的预测将决定 其后应急服务的质量其后应急服务的质量 要实现资源的合要实现资源的合其后应急服务的质量其后应急服务的质量 要实现资源的合要实现资源的合 理利用 需要对资源进行布局 调度和理利用 需要对资源进行布局 调度和 配送配送 配送配送 汇报主要内容汇报主要内容 应急资源布局问题应急资源布局问题 应急资源调度问题应急资源调度问题 资源布局问题资源布局问题 应急管理中的资源布局问题包括应急资源的选址 和配置两个部分 布局的目标是将应急资源的地 应急管理中的资源布局问题包括应急资源的选址 和配置两个部分 布局的目标是将应急资源的地 址合理规划 在每一个地址上配置适量的资源 在应急管理中使得资源的供应量达到最大或者最 址合理规划 在每一个地址上配置适量的资源 在应急管理中使得资源的供应量达到最大或者最 优优 一般来说一般来说 选址问题和配置问题是相关联的选址问题和配置问题是相关联的 优优 一般来说一般来说 选址问题和配置问题是相关联的选址问题和配置问题是相关联的 选址问题需要考虑到以后的资源配置问题 而资选址问题需要考虑到以后的资源配置问题 而资 源配置问题也需要综合考察选址情况进行配置源配置问题也需要综合考察选址情况进行配置 源配置问题也需要综合考察选址情况进行配置源配置问题也需要综合考察选址情况进行配置 对于某些地址已经确定的问题 资源配置作为一 个独立的问题来考虑 对于某些地址已经确定的问题 资源配置作为一 个独立的问题来考虑 资源布局问题相关的数学模型资源布局问题相关的数学模型 确定性模型确定性模型 P P centercenter问题问题 P P centercenter问题问题 P median问题P median问题 集覆盖选址模型集覆盖选址模型 集覆盖选址模型集覆盖选址模型 the location set covering problem LSCP the location set covering problem LSCP 最大覆盖选址模型最大覆盖选址模型 最大覆盖选址模型最大覆盖选址模型 the maximal covering location problem MCLP the maximal covering location problem MCLP 备份覆盖模型备份覆盖模型备份覆盖模型备份覆盖模型 BACOP1 Backup Coverage Problem1 BACOP2 Backup Coverage Problem2 BACOP1 Backup Coverage Problem1 BACOP2 Backup Coverage Problem2 P center问题P center问题 集合P到顶点的距离定义为 集合P到顶点的距离定义为 寻求一最优的集合P 使其中每一个候选地址点到其需求寻求一最优的集合P 使其中每一个候选地址点到其需求 点点 顶点顶点 的距离达到最小的距离达到最小 即即点点 顶点顶点 的距离达到最小的距离达到最小 即即 中心问题中心问题 the center problemthe center problem 最早由最早由Sylvester 1857 Sylvester 1857 中心问题中心问题 thethe centercenter problemproblem 最早由最早由Sylvester 1857 Sylvester 1857 提出 P center model 是一个最大最小 minmax 模型 模提出 P center model 是一个最大最小 minmax 模型 模 型目标最小化需求点与其最近设施点之间距离的最大值型目标最小化需求点与其最近设施点之间距离的最大值 也也型目标最小化需求点与其最近设施点之间距离的最大值型目标最小化需求点与其最近设施点之间距离的最大值 也也 就是使最糟糕的情况尽量的好 相比系统平均性能这个模型 更重视公平性 就是使最糟糕的情况尽量的好 相比系统平均性能这个模型 更重视公平性 P median问题P median问题 Hakimi 1964 提出了P median问题 建立了P median model Hakimi 1964 提出了P median问题 建立了P median model 确定设施的建造地址确定设施的建造地址 使需求点与设施之间的平均距离最小化使需求点与设施之间的平均距离最小化 确定设施的建造地址确定设施的建造地址 使需求点与设施之间的平均距离最小化使需求点与设施之间的平均距离最小化 集覆盖选址模型集覆盖选址模型 the location set covering problem LSCPthe location set covering problem LSCP thethe locationlocation setset coveringcovering problem problem LSCPLSCP ToregasToregas 19711971 等发表的集覆盖选址模型等发表的集覆盖选址模型 LSCPLSCP 是是ToregasToregas 19711971 等发表的集覆盖选址模型等发表的集覆盖选址模型 LSCPLSCP 是是 在覆盖所有需求点的前提下使车辆数最小 在这个模型中 需求点被覆盖当且仅当至少有一辆车在一定的时间标准下到 在覆盖所有需求点的前提下使车辆数最小 在这个模型中 需求点被覆盖当且仅当至少有一辆车在一定的时间标准下到 达需求点 达需求点 最大覆盖选址模型最大覆盖选址模型 the maximal covering location problem MCLPthe maximal covering location problem MCLP thethe maximalmaximal coveringcovering locationlocation problem problem MCLPMCLP ReVelle 1974 ReVelle 1974 发表的最大覆盖选址模型发表的最大覆盖选址模型 MCLPMCLP 是在给定一定数量是在给定一定数量ReVelleReVelle 1974 1974 发表的最大覆盖选址模型发表的最大覆盖选址模型 MCLPMCLP 是在给定一定数量是在给定一定数量 的车辆 使需求点的覆盖率达到最大 LSCP模型可以确定满足一定的需求 量需要的车辆数 而MCLP模型可以解决在资源紧缺时如何配置资源使需求 的车辆 使需求点的覆盖率达到最大 LSCP模型可以确定满足一定的需求 量需要的车辆数 而MCLP模型可以解决在资源紧缺时如何配置资源使需求 点的被覆盖率最大化点的被覆盖率最大化 这两个模型从需求这两个模型从需求 覆盖率尽可能大覆盖率尽可能大 和供给和供给 车车点的被覆盖率最大化点的被覆盖率最大化 这两个模型从需求这两个模型从需求 覆盖率尽可能大覆盖率尽可能大 和供给和供给 车车 辆数尽可能少 两个不同的角度对选址问题作了描述 辆数尽可能少 两个不同的角度对选址问题作了描述 备份覆盖模型备份覆盖模型 BACOP1 Backup Coverage Problem1 BACOP1 Backup Coverage Problem1 HoganHogan和和ReVelleReVelle提出了两个备份覆盖模型提出了两个备份覆盖模型 BACOP1BACOP1考虑考虑HoganHogan和和ReVelleReVelle提出了两个备份覆盖模型提出了两个备份覆盖模型 BACOP1BACOP1考虑考虑 的是在所有需求点都被一次覆盖的条件下 使需求点被二次 覆盖的需求量最大化 的是在所有需求点都被一次覆盖的条件下 使需求点被二次 覆盖的需求量最大化 备份覆盖模型备份覆盖模型备份覆盖模型备份覆盖模型 BACOP2 Backup Coverage Problem2 BACOP2 Backup Coverage Problem2 BACOP2最大化需求点被一次覆盖和二次覆盖的需求量加权值 BACOP2最大化需求点被一次覆盖和二次覆盖的需求量加权值 资源布局问题相关的数学模型资源布局问题相关的数学模型 随机性模型随机性模型 最大期望覆盖模型最大期望覆盖模型最大期望覆盖模型最大期望覆盖模型 the maximum expected covering location problem formulation MEXCLP the maximum expected covering location problem formulation MEXCLP 最大可利用选址问题最大可利用选址问题 the maximum availability location problem MALP the maximum availability location problem MALP 随机集覆盖选址模型随机集覆盖选址模型 随机集覆盖选址模型随机集覆盖选址模型 the probabilistic location set covering problem the probabilistic location set covering problem PLSCP PLSCP PLSCP PLSCP 最大期望覆盖模型最大期望覆盖模型 the maximum expected covering location problem formulation MEXCLP the maximum expected covering location problem formulation MEXCLP Daskin 1983 提出了最大期望覆盖模型 在此模型中 假定Daskin 1983 提出了最大期望覆盖模型 在此模型中 假定 所有救护车忙的概率都是相同的所有救护车忙的概率都是相同的 此概率记为此概率记为q q 即每辆救护车都有即每辆救护车都有所有救护车忙的概率都是相同的所有救护车忙的概率都是相同的 此概率记为此概率记为q q 即每辆救护车都有即每辆救护车都有 的概率无法回应需求点的求救电话 在模型目标中考虑了这种不确定 性 的概率无法回应需求点的求救电话 在模型目标中考虑了这种不确定 性 最大可利用选址问题最大可利用选址问题 the maximum availability location problem MALP the maximum availability location problem MALP ReVelle和Hogan 1989 提出了最大可利用选址问题 给定一定的概 率水平 最大化需求点被覆盖率 而这个概率水平 表示的是对于能覆盖 ReVelle和Hogan 1989 提出了最大可利用选址问题 给定一定的概 率水平 最大化需求点被覆盖率 而这个概率水平 表示的是对于能覆盖 需求点需求点 的候选地址的车辆中至少有一辆车是可利用的概率要大于的候选地址的车辆中至少有一辆车是可利用的概率要大于 此模此模需求点需求点 的候选地址的车辆中至少有一辆车是可利用的概率要大于的候选地址的车辆中至少有一辆车是可利用的概率要大于 此模此模 型的假设与MEXCLP中一样 都假设所有救护车忙的概率都是相同的 通过 二项式分布把这个概率约束化简为确定的不等式约束 型的假设与MEXCLP中一样 都假设所有救护车忙的概率都是相同的 通过 二项式分布把这个概率约束化简为确定的不等式约束 随机集覆盖选址模型随机集覆盖选址模型 the probabilistic location set covering problem PLSCP the probabilistic location set covering problem PLSCP ReVelle和Hogan的随机集覆盖选址模型 在保证一ReVelle和Hogan的随机集覆盖选址模型 在保证一 定覆盖率的前提下最小化服务设施的数目定覆盖率的前提下最小化服务设施的数目 定覆盖率的前提下最小化服务设施的数目定覆盖率的前提下最小化服务设施的数目 资源调度问题资源调度问题 资源调度是指当突发事件发生的时候 根据有关部门资源调度是指当突发事件发生的时候 根据有关部门 的指挥调度的指挥调度 根据现有的资源配置情况和生产需求根据现有的资源配置情况和生产需求 调动调动的指挥调度的指挥调度 根据现有的资源配置情况和生产需求根据现有的资源配置情况和生产需求 调动调动 库存资源来满足灾难主体的需求 在应急管理中 除了要 考虑能否满足利润最大原则外 还需要结合突发事件的特 库存资源来满足灾难主体的需求 在应急管理中 除了要 考虑能否满足利润最大原则外 还需要结合突发事件的特 点进行考虑点进行考虑 点进行考虑点进行考虑 时效性或紧迫性 应急管理中的资源调度应该以反应时间最小为 时效性或紧迫性 应急管理中的资源调度应该以反应时间最小为 首要原则首要原则 这是由突发事件本身的特点所决定的这是由突发事件本身的特点所决定的 时间的紧迫性是应时间的紧迫性是应首要原则首要原则 这是由突发事件本身的特点所决定的这是由突发事件本身的特点所决定的 时间的紧迫性是应时间的紧迫性是应 急问题最显著的特点 突发事件发生以后 应该以最快的速度进行救 助 尽量将损失减少到最小程度 时间效益高于经济效益 急问题最显著的特点 突发事件发生以后 应该以最快的速度进行救 助 尽量将损失减少到最小程度 时间效益高于经济效益 动态性动态性 突发事件发生时突发事件发生时 状况是不断变化的状况是不断变化的 这与一般的资源这与一般的资源 动态性动态性 突发事件发生时突发事件发生时 状况是不断变化的状况是不断变化的 这与一般的资源这与一般的资源 调度的需求任务有很大不同 救助工作不是单一阶段的工作 而是根 据救援的情况和灾害的发展情况进行动态的多阶段的资源调度 调度的需求任务有很大不同 救助工作不是单一阶段的工作 而是根 据救援的情况和灾害的发展情况进行动态的多阶段的资源调度 应急资源调度的特点应急资源调度的特点 应急资源调度并不十分侧重于经济性 属于同时追求应急资源调度并不十分侧重于经济性 属于同时追求 货物运输时间最小化与费用最小化的多目标规划问题货物运输时间最小化与费用最小化的多目标规划问题 货物运输时间最小化与费用最小化的多目标规划问题货物运输时间最小化与费用最小化的多目标规划问题 由于自然灾害与公共突发事件的随机性 规模种类的 不确定性 导致所需救援物资的种类繁多 并且随着时 由于自然灾害与公共突发事件的随机性 规模种类的 不确定性 导致所需救援物资的种类繁多 并且随着时 间的变化间的变化 需求量可能会发生变化需求量可能会发生变化 从而使得应急资源从而使得应急资源间的变化间的变化 需求量可能会发生变化需求量可能会发生变化 从而使得应急资源从而使得应急资源 调度更加困难和复杂 调度更加困难和复杂 应急资源调度是由政府组织的活动应急资源调度是由政府组织的活动 其所需要的车辆其所需要的车辆 一般是由政府按照应急预案临时征用的社会团体或个人一般是由政府按照应急预案临时征用的社会团体或个人 应急资源调度是由政府组织的活动应急资源调度是由政府组织的活动 其所需要的车辆其所需要的车辆 一般是由政府按照应急预案临时征用的社会团体或个人一般是由政府按照应急预案临时征用的社会团体或个人 的车辆 的车辆 应急资源调度使用公路应急资源调度使用公路 铁路铁路 航空等多种运输方式航空等多种运输方式 应急资源调度使用公路应急资源调度使用公路 铁路铁路 航空等多种运输方式航空等多种运输方式 而且会在不同的运输方式中进行转换 而且会在不同的运输方式中进行转换 资源调度模型的分类资源调度模型的分类 按照优化目标可以划分为三种模型按照优化目标可以划分为三种模型 最小化运输费用的数学模型最小化运输费用的数学模型最小化运输费用的数学模型最小化运输费用的数学模型 最小化运输时间的数学模型最小化运输时间的数学模型 最小化运输费用与运输时间的双目标数学模型最小化运输费用与运输时间的双目标数学模型 按照隶属不同数学模型可以划分为以下四种类型按照隶属不同数学模型可以划分为以下四种类型 点点间的最短路问题点点间的最短路问题 TSPTSP Traveling Salesman ProblemTraveling Salesman Problem 旅行商问题旅行商问题 TSPTSP TravelingTraveling SalesmanSalesman ProblemProblem 旅行商问题旅行商问题 多救援点多救灾点的运输方案分配问题多救援点多救灾点的运输方案分配问题 VRPVRP Vehicle Routing ProblemVehicle Routing Problem 多回路运输问题多回路运输问题 VRPVRP VehicleVehicle RoutingRouting ProblemProblem 多回路运输问题多回路运输问题 VRP问题VRP问题 Vehicle Routing ProblemVehicle Routing Problem VehicleVehicle RoutingRouting ProblemProblem 最早由最早由DantzigDantzig和和RamserlRamserl于于19591959年首次提年首次提最早由最早由DantzigDantzig和和RamserlRamserl于于19591959年首次提年首次提 出 VRP问题一般指的是 对一系列发货点和 收货点 调用一定的车辆 组织适当的行车 出 VRP问题一般指的是 对一系列发货点和 收货点 调用一定的车辆 组织适当的行车 路线路线 使车辆有序地通过它们使车辆有序地通过它们 在满足指定在满足指定路线路线 使车辆有序地通过它们使车辆有序地通过它们 在满足指定在满足指定 的约束条件下 例如 货物的需求量与发货量 的约束条件下 例如 货物的需求量与发货量 交发货时间交发货时间 车辆可载量限制车辆可载量限制 行驶里程限行驶里程限交发货时间交发货时间 车辆可载量限制车辆可载量限制 行驶里程限行驶里程限 制 行驶时间限制等 力争实现一定的目标 如车辆空驶里程最短 运输总费用最低 车 制 行驶时间限制等 力争实现一定的目标 如车辆空驶里程最短 运输总费用最低 车 辆按一定时间到达辆按一定时间到达 使用的车辆数最小等使用的车辆数最小等 辆按一定时间到达辆按一定时间到达 使用的车辆数最小等使用的车辆数最小等 VRPVRP模型的类别模型的类别VRPVRP模型的类别模型的类别 多多供货点问题供货点问题 Multiple Depot VRP Multiple Depot VRP MDVRP MDVRP 多个供货点可以同多个供货点可以同多多供货点问题供货点问题 Multiple Multiple DepotDepot VRPVRP MDVRP MDVRP 多个供货点可以同多个供货点可以同 时对客户进行供货 该类问题的研究涉及到供货点如何选择 时对客户进行供货 该类问题的研究涉及到供货点如何选择 带有时间窗的问题 VRP with Time Windows VRPTW 每个客户带有时间窗的问题 VRP with Time Windows VRPTW 每个客户 对车辆的最早到达时问对车辆的最早到达时问 最迟到达时间及服务时间均有一定的要最迟到达时间及服务时间均有一定的要对车辆的最早到达时问对车辆的最早到达时问 最迟到达时间及服务时间均有一定的要最迟到达时间及服务时间均有一定的要 求 求 随机问题随机问题 Stochastic Stochastic VRPVRP SVRP SVRP 问题涉及的某类元素具有随问题涉及的某类元素具有随随机问题随机问题 Stochastic VRP Stochastic VRP SVRP SVRP 问题涉及的某类元素具有随问题涉及的某类元素具有随 机性 比如需求的到达 服务时间等等 也有研究者将该类问题 定义为动态车辆路径问题 Dynamic VRP DVRP 机性 比如需求的到达 服务时间等等 也有研究者将该类问题 定义为动态车辆路径问题 Dynamic VRP DVRP 分批交货问题分批交货问题 Split Delivery VRP Split Delivery VRP SDVRP SDVRP 相当于满载问相当于满载问 分批交货问题分批交货问题 Split Split DeliveryDelivery VRPVRP SDVRP SDVRP 相当于满载问相当于满载问 题 一个客户的需求需要多个车来满足 题 一个客户的需求需要多个车来满足 回程时集货的问题 VRP with Backhauls VRPB 该类型的问题回