多行程多时间窗需求可拆分的应急疏散车辆调度
大规模突发灾害事件发生时,需要将大量受灾人员疏散至安全地点,若待疏散人数超过该区域内所有应急疏散车辆的总载客能力,即应急车辆紧缺,则所有待疏散人员不能一次性被运送完毕,此时需要通过对车辆进行分批次、多阶段的调度,来使其快速高效地完成运载所有受灾人员的任务。应急车辆的调度问题可视为拓展形式的车辆路径问题(Vehicle Routing Problem,VRP)。
传统VRP要求各需求点需求量不大于单车容量、所有车辆只能行动一次、各需求点只能被单车单次访问。本文结合应急疏散实际,将应急车辆调度问题转化为多行程多时间窗需求可拆分的车辆路径问题(Vehicle Routing Problem with Multiple trips and Multiple Time Windows and Split Delivery,VRPMTMTWSD),即在应急疏散过程中,允许各车辆多次行动,允许各需求点的需求被拆分并由多车多次配送,同时保证伤势程度不同的受灾人员在其所须的时间窗内被疏散。
基于此,本文以最小化应急疏散总完成时间、最小化灾民到达避难所的平均时间 ...