多受灾点应急救援车辆调度的优化遗传算法

在多个地区发生灾害后，迫切需要及时救援和物资的快速运输，从仓库调拨物资到受灾点，交通网络规模较大，运输货物类型多样，并且要满足各个受灾点的资源需求、实时路况、运抵时限要求等多个目标约束条件，车辆调度具有较大难度.为解决多重约束带来的困难，根据遗传算法的生物进化理论和群体遗传学机制，建立了车辆应急运输的多目标优化问题模型，设计合适的序列编码方式表示车辆行进路线及运输货物类型；建立了新的优化遗传算法，从编码方式的设计、适应度函数、选择、交叉和变异操作机制的设计三个方面做了创新改进，主动保持优良基因，根据阶段进展调节交叉和变异概率，有效提高好的新模式的产生几率，较好地克服了已有方法的早熟局部收敛所导致的结果偏差较大的不足.多个仿真实验结果表明，优化遗传算法比已有算法在满足送达时限以及送达时间的总长度等方面均有较大提高，对于复杂的调度任务，在保证运抵时限的前提下，可占用更少的车辆，花费更少的行进时间完成物资运输，从而满足多受灾点对物资的实时性需求.

Optimized Genetic Algorithm for Vehicle Scheduling Problem in Emergency Rescue of Multiple Disaster Areas

Disaster relief demands urgent need for rapid transport of supplies. Vehicle transportation scheduling is based on large-scaled and real-time traffic network with time limit constraints and various supplies for multiple destinations lay the difficult points. To attain the target, multi objective optimization model for vehicle emergency transportation is built, and an optimized genetic algorithm is put forward to solve the vehicle scheduling problem in emergency rescue with multiple constranins including road variation, arrival deadlines and multiple materials. Based on the theory of biological evolution and principles of population genetics, the optimized algorithm takes the multi spots and in-fact road conditions into consideration, makes focus on the multiple material demands and the precedence on the arrival time without delay, designed a new coding pattern which made new encoding mode design, adaptive function, new selection, crossover and variation operators, and new generation mechanism to produce more and better patterns in less time, so as to overcome the premature convergence of the classic genetic algorithm. Tests proved the better performance of the proposed algorithm in finding the global optimized solution than the traditional genetic algorithm in delivery time constrains and the total length of arrival time, with less vehicles involved and less solving time. The proposed method can improve the transportation efficiency of disaster relief and cut down the vehicle cost, and meet the demands of complex vehicle scheduling tasks.