Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (8): 2444-2449.DOI: 10.11772/j.issn.1001-9081.2018122516

• Frontier & interdisciplinary applications • Previous Articles     Next Articles

Modeling and optimization of disaster relief vehicle routing problem considering urgency

ZHANG Yuzhou1,2, XU Tingzheng1,2, ZHENG Junshuai1,2, RAO Shun1,2   

  1. 1. School of Computer and Information, Anqing Normal University, Anqing Anhui 246133, China;
    2. Key Laboratory of Intelligent Perception and Computing in Anhui Province, Anqing Anhui 246011, China
  • Received:2018-12-21 Revised:2019-02-24 Online:2019-08-10 Published:2019-04-22
  • Supported by:
    This work is partially supported by the Anhui Provincial Natural Science Foundation (1808085MF173), the Natural ScienceKey Research Project for Higher Education Institutions of Anhui Province (KJ2016A438), the Key Projects of Provincial Quality Projects for Higher Education Institutions of Anhui Province (2017jyxm0302).

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

张玉州1,2, 徐廷政1,2, 郑军帅1,2, 饶舜1,2   

  1. 1. 安庆师范大学 计算机与信息学院, 安徽 安庆 246133;
    2. 安徽省高校智能感知与计算重点实验室, 安徽 安庆 246011
  • 通讯作者: 徐廷政
  • 作者简介:张玉州(1976-),男,安徽无为人,副教授,硕士,主要研究方向:智能交通、进化算法;徐廷政(1995-),男,安徽六安人,硕士研究生,主要研究方向:智能计算、车辆路径问题;郑军帅(1994-),男,安徽亳州人,硕士研究生,主要研究方向:智能计算;饶舜(1986-),男,安徽安庆人,硕士研究生,主要研究方向:智能交通、智能计算。
  • 基金资助:
    安徽省自然科学基金面上项目(1808085MF173);安徽省高校省级自然科学研究重点项目(KJ2016A438);安徽省高等学校省级质量工程重点项目(2017jyxm0302)。

Abstract: 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.

Key words: urgency, optimization, Vehicle Routing Problem (VRP), Genetic Algorithm (GA), local search

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

关键词: 紧急度, 优化, 车辆路径问题, 遗传算法, 局部搜索

CLC Number: