多受灾点救灾物资分配调度问题启发式算法  

Heuristics for Distribution and Scheduling of Relief Supplies among Multiple Disaster Sites

作　　者：杨勃[1] 杜冰[1] 李小林[1] 

机构地区：[1]中国科学技术大学管理学院,安徽合肥230026

出　　处：《系统工程》2012年第1期97-103,共7页Systems Engineering

基　　金：创新研究群体科学基金资助项目(70821001);博士点基金资助项目(200803580024)

摘　　要：救灾物资的分配调度问题是灾害应急救援工作面临的一项重要任务。合理的物资分配调度方案可以极大程度地缓解灾情,保障人民群众的生命财产安全。本文提出一类具有多个受灾点、多种救灾物资的分配调度问题,以满足所有受灾点物资需求时间最短为优化目标。证明了该问题是强NP难解的,给出了问题的一个下界以衡量近似算法的性能。此外,提出了求解该问题的若干启发式算法,并通过仿真实验对启发式算法的性能进行了比较。Distribution and scheduling of relief supplies is an important task in Emergency relief work.A reasonable plan to distribute and schedule relief resources is crucial to successful disaster mitigation efforts,and will be able to protect life and property of the people.A problem of distribution and scheduling of a variety of relief goods with multiple disaster sites was proposed in this paper.The objective of the problem is to minimize the maximum completion time of transportation of relief supplies.The problem was shown to be strongly NP-hard,thus a lower bound was presented to evaluate the performance of approximation algorithms.In addition,several efficient heuristics for the problem were also proposed,and their performances were evaluated through extensive computational experiments.

关 键 词：多受灾点 救灾物资分配调度 应急管理 组合优化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]