应急救援物资紧缺的配送车辆路径选择研究

针对应急救援物资总量紧缺不能全部满足各点需求量的实际情形,以单个需求点最大缺货量最小为目标,建立基于单个配送中心、车辆数目有限和带时间窗的应急救援物资配送车辆路径选择模型,并讨论了三种不同缺货情形下模型的求解。对于车辆按最短路径行驶也无法在救援时间内到达导致需求点缺货的情形,删除这些需求点的需求量后,如果剩余需求点的需求量不大于物资总量且车辆足够多,可转化为车辆最短路径问题求解;对于物资紧缺无法满足所有需求且车辆足够多的情形,设计时间复杂性为O(mn²)的精确算法A^*求解,其中m和n分别为车辆数和需求点数;对于物资紧缺且车辆数目不足无法把全部物资送达需求点的情形,设计时间复杂性为O(n²)的近似算法GA^*求解,并分析了算法GA^*的近似比。最后结合云南彝良县地震灾区局部路网进行实例分析,验证模型和算法的有效性。

Research on Vehicle Routing for Scarce Emergency Relief Supply Dispatching in a Emergency

For the practical case that the total amount of emergency relief supplies is scarce and can not meet the demand of all points, minimum the maximum shortage of each demand point, a emergency relief supply dispatching vehicle routing model based on one distribution center, limited amount of vehicles and time windows is established, and analyze the solutions of the model for three different cases of shortages. For the case that shortages result in vehicles can not reach demand points within rescue time requirement even go along the shortest path, after deleting the demand of this kind of demand points, if the total demand of remaining demand points is not bigger than the amount of emergency relief supplies, and with enough vehicles, this problem can be transformed into shortest path problem and solved. For the case that shortages result in the total amount of emergency relief supplies is scarce and can not meet the demand of all points even with enough vehicles, exact algorithm A^* is designed, and show that the time complexity is, where m and n denote the number of vehicles and demand points, respectively. For the case that shortages result in the total amount of emergency relief supplies is scarce and the amount of vehicles is inadequate that can not dispatch all the supplies to demand points, approximation algorithm GA* is designed, show that the time complexity is, and analyze the approximation ratio of algorithm GA^*. Take the local network of Yiliang earthquake disaster area in Yunnan as an example, confirm the model and algorithms are effective.