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

救灾物资的分配调度问题是灾害应急救援工作面临的一项重要任务。合理的物资分配调度方案可以极大程度地缓解灾情,保障人民群众的生命财产安全。本文提出一类具有多个受灾点、多种救灾物资的分配调度问题,以满足所有受灾点物资需求时间最短为优化目标。证明了该问题是强NP难解的,给出了问题的一个下界以衡量近似算法的性能。此外,提出了求解该问题的若干启发式算法,并通过仿真实验对启发式算法的性能进行了比较。

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

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.