基于遗传算法的应急物资分层调度研究

胡飞虎，田朝晖，李 威，韩 鑫

（西安交通大学电气工程学院工业自动化系，西安 710049）

基于遗传算法的应急物资分层调度研究

胡飞虎，田朝晖，李 威，韩 鑫

（西安交通大学电气工程学院工业自动化系，西安 710049）

针对多车型、多物资特征的应急物资调度问题，设计分层调度方案，同时给出由两层物资调度系统组成的调度算例，并将该算例转化为2个相关的单层物资调度问题。以最小化系统调度任务完成时间为目标函数，利用遗传算法对一级和二级调度方案进行求解，得出系统中每种车型依次将何种货物从何地运往何处的具体方案。通过车辆各自运输任务的运货量计算和仓库点物资的实时统计结果表明，该分层调度方案符合各仓库出货量不超过现存量且各灾害点物资需求得到满足的供求条件，求解步骤简单且运行速度快。

应急物资调度；分层调度；车辆调度；遗传算法；目标函数

1 概述

启发式优化算法［1］被广泛用于解决应急物资配送的车辆调度［2-4］问题。在物资调度问题的求解方面：文献［5］应用蚁群算法对调度问题进行优化，将原始物资分配分为2个阶段，车辆路线分配和多种物资分配，从而解决应急物资运输问题。文献［6］在多种商品、多配送情况下，以系统总成本最小为目标，建立两阶段混合整数规划模型解决物资调度问题。文献［7］提出一种混合模糊聚类算法，得出关联两路网下物资调度问题的求解方案。文献［8］给出供应与需求不平衡情况下两阶段的多种运输方式、多物资运输模型。文献［9］提出两阶段随机规划方法解决调度问题。文献［10］针对应急物资调度问题，建立情景响应式两阶段随机规划模型。文献［11］研究了供应链中传统的车辆路径问题以及多

物资网络流问题，并且在交通工具、物资变化等情况下，提出解决动态调度问题的算法。分层是指路网调度具有层次，如省级路网、地方路网以及各种路网上适用的运输工具，本文提出对此类调度问题进行求解的思路。每层的需求点为下层的仓库点，各层的运输工具仅需完成各自所在层的仓库到需求点的物资调度任务，这样即可依次对各层调度问题进行独立求解，从而简化问题，便于求解计算。物资两层调度问题是此问题的典型特例，在实际问题中由二级调度（市县级地方仓库至灾害点）和一级调度（国家、省级仓库至市县级地方仓库）组合成的两层调度问题。因此，本文提出物资两层调度问题的数学模型，以任务耗时最短为目标，利用遗传算法［12-14］和分层求解方法给出最优调度方案。

2 两层应急物资调度问题的数学模型

已知各仓库点的物资储量和灾害点的物资需求量。

（1）假设条件

1）各层调度系统的运输工具只负责完成各自所在层的物资调度任务。

2）一级仓库点和二级仓库点各物资的总存储量一定能满足灾害点对各物资的总需求量，且二级仓库有一定储量，保证不会中途空仓，导致二级车辆在该二级仓库等待。

3）不考虑各运输工具的装卸货时间。

4）各运输工具的初始停放地点可为仓库点，也可为灾害点，且在执行完某单次任务后不必回到初始出发地点。

5）各运输工具均满载某单一物资正常运行，不考虑物资的混合装载且一旦开始执行某次运输任务，不能中途退出。

（2）模型参数

W：应急物资集合，即W=｛w1，w2，…，wP｝。

B：一级仓库点集合，即B=｛b1，b2，…，bm｝。

C：二级仓库点集合，即C=｛c1，c2，…，ca｝。

E：灾害点集合，即E=｛e1，e2，…，eq｝。

BW：一级物资储备中心（一级仓库）物资信息集合，即BW=｛bw1，bw2，…，bwm｝。

CW：二级物资储备中心（二级仓库）物资信息集合，即CW=｛cw1，cw2，…，cwn｝。

EW：灾害救援中心（灾害点）物资信息集合，即EW=｛ew1，ew2，…，ewa｝，ewk（k=1，2，…，a）表示某个灾害点的物资信息，包括需要的物资类型（wf）（f=1，2，…，P）及相应的需求量（γkf），即 ewk=｛（w1，γk1），（w2，γk2），…，（wP，γkP）｝。

R：一级运输工具信息集合，即 R=｛r1，r2，…，rg｝。rk（k=1，2，…，g）表示一级运输工具信息，包含载货量（dk）、速度（sk）、数量信息（nk），即 rk=｛dk，sk，nk｝。N=｛n1，n2，…，ng｝，nk（k=1，2，…，g）表示一级某种类型的运输工具的数量。

V：二级运输工具信息集合，即 V=｛ν1，ν2，…，νh｝，νk（h=1，2，…，y）表示二级运输工具信息，包含载货量（dk）、速度（sk）、数量信息（nk），即 νk=｛dk，sk，nk｝，N=｛n1，n2，…，nh｝，nk（k=1，2，…，h）表示二级序列某种类型的运输工具的数量。

q为一级仓库点和二级仓库点间路径距离矩阵：

l为二级仓库点和灾害点之间的路径距离矩阵：

μ：一级车辆的一次完整运载任务，即 μ=（bi，wf，cj）（i=1，2，…，m；f=1，2，…，P；j=1，2，…，n）。一级车辆的一次完整运载任务包括出发一级仓库点、运载的物资种类、抵达二级仓库点。

τ：二级车辆一次完整的运载任务，即 τ=（ci，wf，ej）（i=1，2，…，n；f=1，2，…，P；j=1，2，…，a）。二级车辆一次完整的运载任务为τ，它包括出发二级仓库点、运载物资种类、抵达灾害点。

Φ：一级序列完整的调度方案信息，即 Φ=｛φ1，φ2，…，φP｝，其中，φg（g=1，2，…，P）表示一级序列中第g个运输工具的调度方案信息，包括一系列运载任务序列和该运输工具的信息，φg=｛μ1，μ2，…，μχ；rk｝，即第g个运输工具的调度方案信息为 φg，车辆信息为rk，有χ次运载任务序列。

Ω：二级调度方案，即 Ω=｛ω1，ω2，…，ωq｝，其中，ωg（h=1，2，…，q）表示二级序列中第 h个运输工具的调度方案信息，包括一系列运载任务序列和该运输工具的信息；ωh=｛τ1，τ2，…，τy；νf｝，即第 h个运输工具的调度方案信息为 ωh，车辆信息为 νf，有y次运载任务序列。

T1：一级车辆调度时间集合，即 T1=｛t1φ1，

t1φ2，…，tφP｝。其中，t1φg（g=1，2…，P）表示第 g个运输工具的调度完成时间。整个调度任务完成时间T1s=max（t1φg）。

T2：二级车辆调度时间集合，即 T2=｛t2ω1，t2ω2，…，t2ωq｝。其中，t2ωh（h=1，2，…，q）表示第 h个运输工具的调度完成时间。整个调度任务完成时间T2s=max（t2ωh）。

目标函数：m in（max｛T1s，T2s｝）。

3 两层调度算例

一级仓库点分别为 b1，二级仓库点分别为 c1，c2，c3，灾害点分别为e1，e2，e3，e4，e5，3种应急物资w1，w2，w3，即分别对应为药品、食品、生活用品。一级序列有2种车型，分别为大、小货车，车辆编号分别为1～6，7～8，运载量分别为10 t和5 t，满载速度分别为80 km/h和85 km/h。二级系统有2种车型，分别为大、小货车，车辆编号分别为1～4，5～14，运载量分别为10 t和5 t，满载速度分别为60 km/h和65 km/h。公路运输路径关系如图1所示，一级高速公路运输路径距离（高速公路）如表1所示，二级高速公路运输路径距离（普通公路）如表2所示。3种应急物资在各仓库点中的库存量和在各灾害点中的需求量如表3所示，其中，“∞”表示两点间的道路不通。求解目标：以调度完成时间最短为目标，求解调度方案。

图1 各仓库、灾害点的运输路径关系

表1 一级各仓库、二级各仓库的运输路径距离 km

表2 二级各仓库、灾害点的运输路径距离 km

表3 各仓库、灾害点的存储量与需求量

4 应用遗传算法的算例求解过程

4.1 参数编码

在一次应急物资调度中，参加调度任务的所有车辆的调度任务序列为一条染色体，其中任一辆车的全部调度任务为一个基因，任一辆车的部分调度任务定义为基因序列，任一辆车的单次完整调度任务为一个基因单元。

本文研究模型采用符号编码方式，具体编码符号定义如下：

b1代表一级仓库点。

c1，c2，c3分别代表3个二级仓库点。

e1，e2，e3，e4，e5分别表示5个灾害点。

w1，w2，w3分别代表药品、食品和生活用品。

r1，r2分别代表一级2种运输工具：大货车和小货车，且r1=｛10，80，6｝，r2=｛5，85，2｝，即大货车和小货车的载重量分别为10 t和5 t，满载速度分别为80 km/h和85 km/h。大小货车按先大车后小车依次编号。

ν1，ν2分别代表二级2种运输工具：大货车和小货车，且 ν1=｛10，60，4｝，ν2=｛5，65，10｝，即大货车和小货车的载重量分别为10 t和5 t，满载速度分别为60 km/h和65 km/h。编号同一级。

μ=（bi，wf，cj）代表一级的基因序列单元，其中，bi代表一级仓库点；wf代表运输物资种类；cj代表目的二级仓库点。

Φ=｛φ1，φ2，…，φP｝表示某个运输工具在某次调度任务中的全部调度任务。

τ=（ci，wf，ej）表示二级的基因序列单元，其中，ci代表出发二级仓库点；wf代表运输物资种类；ej代表目的灾害点。

Ω=｛ω1，ω2，…，ωq｝表示某个运输工具在某次调度任务中的全部调度任务。

种群初始化即为按照设定的种群规模，生成相应数目的染色体。本文遗传算法中种群规模为50。

本文将调度任务完成时间定为目标函数值。

4.2 遗传算子

遗传算子具体如下：

（1）基本遗传算子

染色体间交叉操作和基因的变异操作实现遗传算法的基础功能。在独立处理各级调度任务的遗传算法中，染色体的杂交过程中采用多点一致杂交。多点一致杂交的具体杂交操作为：对2条父代染色体的每个相同基因位置上的基因序列依次进行杂交操作，即选取两相同基因位置的基因序列的一共有的杂交点，互换杂交点后续的该基因位置的基因序列。

（2）辅助遗传操作算子

根据供求关系约束条件，对遗传变异产生的染色体进行处理，使各需求点的需求均满足，使得一级仓库点的各型物资出货量不超过对应物资储量。修复操可以分为：补给量大于需求量，补给量小于需求量，供给量大于存储量。分别按照相应的处理方法进行修复。

计算遗传算法生成的染色体所对应的调度方案中的每个物资需求点的对应补给量。逐个将各需求点的各型物资需求量与其补给量进行比较，若对某点某型物资补给量小于需求量，则在最先完成任务链的车增加一次运输这种物资到该点的任务，重复此步骤至所有需求点对各类型物资需求均得到满足。

若某点某型物资补给量过多，则在染色体中将含有到该点该型物资运输任务的车中找到完成任务链耗时最长的那辆车，并删除一次过量补给的任务，重复此步骤至各需求点对各型物资至补给均不过剩。

对于仓库点修复处理则在染色体中搜索某物资出货量大于实际储量的仓库，随机将含有这些不合理的任务的车辆的转货点转移到储量富余的仓库，重复此步骤至一级仓库点对各型物资出货量不超过其储量。二级仓库的物资出货大于其储量产生的缺口由一级调度系统来补充完成，因此计算二级调度的遗传算法中无此修复操作。

本文将目标函数值的倒数定义为适应度值。若调度方案任务完成时间越短，则目标函数值越小，其适应度值越高。

4.3 分层独立求解

本文算例二级仓库有一定储备保证二级车辆在二级仓库不会有等待现象、一级调度任务时间相对二级调度任务时间较短。基于此，采用分层独立求解方法。

本文应用遗传算法先对二级调度系统进行求解得出在满足二级灾害点时的二级优秀调度方案，根据此方案得出二级仓库的理论出货量，进而判断各二级仓库的物资是否不足，根据二级仓库的理论不足量再对一级调度系统进行遗传算法求解得出补足二级仓库的理论物资缺口的一级优秀调度方案。

详细流程如下：首先初始化二级种群（50条染色体），对二级种群进行杂交、变异、修复操作生成新的50条二级染色体，经过自适应度评价的筛选得到较优的新的二级种群，再对新的一级种群进行杂交、变异、修复操作生成最新的50条一级染色体，如此重复上述过程，直到满足终止条件，得到满足各个二级仓库点的需求二级染色体序列。通过分析满足要求的二级染色体序列可以计算出各二级仓库需要从一级仓库需求的物资种类和数量，需要从一级仓库补货的二级仓库即为一级调度系统的需求点，再用遗传算法对一级调度系统进行同样的操作即可得出一级调度方案。

5 算例求解分析

5.1 求解过程

本文将遗传算法迭代过程中染色体的目标函数值即任务完成时间与迭代次数的关系数据进行保存并绘图分析。当迭代至某级调度的任务完成时间稳定时，此时种群中的最优染色体所对应的调度方案即可对应得到该级的一个优秀调度方案。

（1）二级任务完成时间的收敛情况

基于遗传算法求解一级序列并且在迭代50 000次基础上，得到最优一级序列和二级仓库获得量，将二级仓库获得量与二级仓库的原有存储量作为二级序列现有存储量，基于遗传算法求解满足要求的二级序列。

分析前50 000次迭代任务时间和迭代次数的关系数据简单算出任务时间下降梯度，在完成50 000次迭代后得到最优二级序列的任务完成时间的收敛情况下，二级序列的调度任务完成时间（T2s）与迭代次数的关系分别如图2和表4所示。

图2 迭代50 000次后二级任务完成时间的收敛情况

表4 二级任务完成时间与迭代次数的关系1

由图2可知，在50 000次迭代后，二级序列任务完成时间的收敛图中能看到收敛比较明显，但是数值没有稳定。根据之前的数据预测任务时间稳定发生在200 000次以内，因此本文分析迭代200 000次的调度任务时间与迭代次数的关系，其二级序列调度任务完成时间与迭代次数的关系分别如图3和表5所示。

图3 迭代200 000次后二级任务完成时间的收敛情况

表5 二级任务完成时间与迭代次数的关系2

由图3可知，当将二级迭代200 000次时，可以看到数据有明显收敛趋势，迭代次数为90 000时任务完成时间已经稳定。由表5可知，当二级序列迭代次数达到50 000次以上，任务完成时间下降速度缓慢，当迭代次数到达 90 000次时，收敛值达到70.04 h。

（2）一级任务完成时间的收敛情况

本文将一级序列的迭代过程的循环终止条件设定为最大迭代次数50 000次，在完成50 000次迭代后得到一级序列任务完成时间的收敛情况下，一级序列的调度任务完成时间（T1s）与迭代次数的关系分别如图4和表6所示。由图4可知，当将一级序列终止条件定为迭代50 000次时，任务时间有明显的收敛趋势，因此将非联动调度中的一级序列的循环终止条件设定为50 000次。由表6可知，当迭代至20 000次时，收敛值达到45.25 h。

图4 迭代50 000次后一级任务完成时间的收敛情况

表6 一级任务完成时间与迭代次数的关系

5.2 调度方案

由两层调度任务完成时间稳定时对应的最优染色体可得最终调度方案，如表7和表8所示。其中，一级大货车编号为1～6，小货车编号为7～8；二级大货车编号为1～4，小货车编号为5～14。

表7 一级调度方案

表8 二级调度方案

5.3 结果分析

通过表7和表8可以看出，一级调度方案任务完成时间问 45.25 h，二级调度方案任务时间是70.04 h，通过对车辆各自运输任务的运货量计算和仓库点物资的实时统计可得调度方案严格地符合供求条件，即一级仓库各种物资的出货量均不大于其实际存储量，二级各仓库的补给量与原有存储量之和均不小于出货量，各灾害点的各种物资的补给量均严格满足其实际需求量。同时每级调度方案中车辆各自任务时间相互偏差较小，调度合理。

6 结束语

本文以调度任务完成时间最短为目标，提出求解多种物资、多种车型的应急物资分层调度问题，并对此问题建立数学模型。从简化问题的角度设计求解方法，通过设定符合实际情况的条件，使得串联的调度系统间耦合程度降低，采用遗传算法对各调度层进行依次独立求解。设计一个典型算例进行程序设计并得出结果，通过结果分析可知约束条件均严格满足且系统调度资源得到充分利用，分层独立求解方法在满足二级仓库有一定储备的情况下，求解步骤较简洁，并可明显提高求解速度。因此，本文求解方法对求解分层调度问题具备可行性。然而，本文求解方法无法从全局最优的角度求得不同条件下的调度结果，因此，如何应用整体联动的求解方法对物资分层调度进行求解将是今后研究的方向。并且对本文求解方法进行扩充，将调度问题扩展至多阶段调度，也是有待研究的内容。

［1］ Mladenovic N.基于单点搜索的元启发式算法［M］.赵秋红，肖依永，译.北京：科学出版社，2013.

［2］ 张俊伟，王 勃，马范援.多仓库多配送点的物流配送算法［J］.计算机工程，2005，31（21）：192-194.

［3］ 廖良才，王 栋，周 峰.基于混合遗传算法的物流配送车辆调度优化问题求解方法［J］.系统工程，2008，26（8）：27-32.

［4］ 陈子侠，叶庆泰.基于城市配送的单车线路算法研究［J］.计算机工程，2005，31（11）：32-34.

［5］ Wei Yi，Kumar A.Ant Colony Optimization for Disaster Relief Operations［J］.Transportation Research Part E，2007，43（6）：660-672.

［6］ Hindi K S，BastaT.Effieient Solution of a Multicommodity，Multi-modal Network Flow Model for Disaster Relief Operations［J］.Transportation Researchpart A，1996，30（3）：231-235.

［7］ Sheu Jiuh-Biing.Special Issue on Emergency Logistics Management Transportation Research Part E：Logistics and Transportation Review［J］.Transportation Research Part E，2005，41（5）：459-460.

［8］ Barbarosoglu G，Arda Y.A Two-stage Stochastic Programming Framework for Transportation Planning in Disaster Response［J］.Journal of the Operational Research Society，2004，55（1）：43-53.

［9］ Beradi P，Bruni M E.A Probabilistic Model Applied to Emergency Service Vehicles Location［J］.European Journal of Operational Research，2009，196（1）：323-331.

［10］ Barbarosoglu G，Arda Y.A Two-stage Stochastic Programming Framework for Transportation Planning in Distaster Response［J］.Journal of the Operational Research Society，2004，55（1）：43-53.

［11］ Ozdamar L，Ekinci E.Emergency Logistic Planning in Natural Disasters［J］.Annals of Operations Research，2004，129（1-4）：217-245.

［12］ 张 军.计算智能［M］.北京：清华大学出版社，2009.

［13］ 徐 磊.基于遗传算法的多目标优化问题的研究与应用［D］.长沙：中南大学，2007.

［14］ 徐宗本，张讲社，郑亚林.计算智能中的仿生学理论与算法［M］.北京：科学出版社，2003.

编辑 陆燕菲

Research on Hierarchical Scheduling of Emergency Supp lies Based on Genetic Algorithm

HU Feihu，TIAN Chaohui，LI Wei，HAN Xin

（Department of Industrial Automation，School of Electrical Engineering，Xi’an Jiaotong University，Xi’an 710049，China）

Aiming at the hierarchical scheduling problem of multi-vehicle and multi-supply，this paper proposes a hierarchical scheduling scheme.A two-layer scheduling example is demonstrated for the problem，and it decouples the tow-layer example into two single-layer problem s.Taking minimize system scheduling task completion time as the objective function，it uses the genetic algorithm to get the scheduling scheme which describes the specific type of carried cargo，the source and the destination for each type of vehicle in sequence.In this hierarchical scheduling scheme，the output in each warehouse is below its storage，the requirement quantity of supplies in each emergency point meets requirement by the real-time statistics in each warehouse and the calculation of carried cargo in each task.The solving process of this scheme is simple and fast.

emergency supplies scheduling；hierarchical scheduling；vehicle scheduling；genetic algorithm；objective function

胡飞虎，田朝晖，李 威，等.基于遗传算法的应急物资分层调度研究［J］.计算机工程，2015，41（10）：53-58.

英文引用格式：Hu Feihu，Tian Chaohui，Li Wei，et al.Research on Hierarchical Scheduling of Emergency Supp lies Based on Genetic Algorithm［J］.Computer Engineering，2015，41（10）：53-58.

1000-3428（2015）10-0053-06

A

TP311.1

10.3969/j.issn.1000-3428.2015.10.011

国家自然科学基金资助项目（61174154）；中央高校基本科研业务费专项基金资助项目。

胡飞虎（1973-），男，副教授、博士生导师，主研方向：复杂网络建模及优化调度，嵌入式智能控制系统；田朝晖、李 威、韩 鑫，硕士研究生。

2014-09-22

2014-11-15E-mail：2476008926@qq.com