论文部分内容阅读
大规模突发灾害事件发生时,需要将大量受灾人员疏散至安全地点,若待疏散人数超过该区域内所有应急疏散车辆的总载客能力,即应急车辆紧缺,则所有待疏散人员不能一次性被运送完毕,此时需要通过对车辆进行分批次、多阶段的调度,来使其快速高效地完成运载所有受灾人员的任务。应急车辆的调度问题可视为拓展形式的车辆路径问题(Vehicle Routing Problem,VRP)。传统VRP要求各需求点需求量不大于单车容量、所有车辆只能行动一次、各需求点只能被单车单次访问。本文结合应急疏散实际,将应急车辆调度问题转化为多行程多时间窗需求可拆分的车辆路径问题(Vehicle Routing Problem with Multiple trips and Multiple Time Windows and Split Delivery,VRPMTMTWSD),即在应急疏散过程中,允许各车辆多次行动,允许各需求点的需求被拆分并由多车多次配送,同时保证伤势程度不同的受灾人员在其所须的时间窗内被疏散。基于此,本文以最小化应急疏散总完成时间、最小化灾民到达避难所的平均时间、最小化延误损失为目标,构建了多目标的VRPMTMTWSD数学模型。本文通过引入虚拟站点的方式,简化了延误损失计算过程,并基于此分析了数学模型最优解的特征。设计了改进的遗传算法对模型求解,在基因编码中,以灾民作为编码的基本单位并利用虚拟站点编号来代表灾民。结合该基因编码形式,利用最优解的特征提出了解的格式调整方法以提高算法的求解性能。此外,本文针对启发式算法的不足,设计了对最终解的再优化方法。最后,本文结合算例验证了模型的合理性和算法的可行性。结果表明:本文算法能够有效对多目标数学模型进行求解,且具有良好的稳定性,能够为应急车辆的多批次调度问题提供一定的决策指导和参考。