考虑紧急度的救灾车辆路径问题建模与优化

Modeling and optimization of disaster relief vehicle routing problem considering urgency

为了减少救灾物资配送的延误时间和救灾车辆的总运输时间,引入紧急度的概念,建立了基于紧急度的救灾物资车辆路径问题模型,并设计了一种改进遗传算法对该模型进行求解。首先,采用多种策略生成初始种群;然后,提出一种基于紧急度的任务再分配算法作为局部搜索算子,该算法依据紧急度为延误安置点重新安排配送车辆或调整配送顺序从而减少延误时间,对无延误的车辆优化其路线从而减少总运输时间,以达到延误时间和总运输时间两者最优。在17个数据集上与先来先服务(FCFS)算法、按紧急度排序(URGS)算法和遗传算法(GA)三种算法进行了对比。实验结果表明,具有基于紧急度的任务再分配策略的遗传算法(TRUD-GA)与GA相比,平均延误时间减少25.0%,平均运输时间减少1.9%,与FCFS、URGS算法相比改进则更加明显。

In order to reduce the delay time of disaster relief materials distribution and the total transportation time of disaster relief vehicles,the concept of urgency was introduced to establish a vehicle routing problem model of disaster relief vehicles based on urgency,and an improved Genetic Algorithm (GA) was designed to solve the model.Firstly,multiple strategies were used to generate the initial population.Then,an urgency-based task redistribution algorithm was proposed as local search operator.The proposed algorithm achieved the optimal delay time and total transportation time based on urgency.The delay time was reduced by rescheduling the vehicle or adjusting the delivery sequence for delay placements.The routes of the vehicles without delay were optimized to reduce the total transportation time.In the experiments,the proposed algorithm was compared with First-Come-First-Served (FCFS) algorithm,Sort by URGency (URGS) and GA on 17 datasets.Results show that the Genetic Algorithm with Task Redistribution strategy based on Urgency Degree (TRUD-GA) reduces the average delay time by 25.0% and decreases the average transportation time by 1.9% compared with GA,and has more obvious improvement compared with FCFS and URGS algorithms.