智能调度算法

智能调度算法（精选八篇）

智能调度算法 篇1

随着现代城市化进程的不断加快, 人口的不断增多, 人口膨胀带来的交通问题也日趋严峻。作为居民日常生活中的重要途径, 公交承担着社会交通运输的主要任务。由于城市中心人口密度较低, 城区面积扩大, 机动车数目显著增多等原因, 公交面临的时间长、成本增加、路程远、运载能力不足等问题, 都制约着公共交通的发展。如何提高运载效率, 尽可能多的解决居民的交通问题是城市公交系统当前面临的最大挑战。

公交调度算饭的研究是典型的交通调度算法优化问题。在一定的要求和条件下, 怎样才能高效地安排车辆的调度顺序、所占资源来最大化地获取时间和空间效益。公交的运营调度可以分为两类:静态和动态。静态调度指的是在长时间不变的情况下的一种调度模式, 用来指导车辆的行驶路线及运行时间、停靠站点等;而动态调度主要是根据先进的设备和技术支持, 使车辆能够面临堵车、道路维修等实时情况, 对突发情况作出及时的反应。

国内外研究现状

1.国外研究现状

公交发车频率的研究:如何确定时发车的时刻频率表的规划方法最早是由Furth以及Wilson等人提出。他们建立的模型的目标函数是使社会利益最大, 包括乘客节省的等车时间, 约束条件是车队规模、经济效益和乘客满载率水平。

对发车频率的研究:Seheele提出, 旨在优化乘客最少等待时间的公交发车频率。它是非线性规划的, 其决策变量是线路发车频率。在优化发车频率的基础上, 同时考虑了客流如何分配问题。Shih和Mahmassani在给定条件网络中, 运用了迭代的方法, 首先对车辆进行优化, 然后根据运输乘客数量确定发车频率, 进而达到优化运输的目的, 直到结果相差较小为止。

2.国内研究现状

根据西安公交的调查数据, 孙芙灵提出时段配车数的理论, 探讨了不同状态下确定配车数、发车频率的方法。张飞舟针对公交的现状以及所处的运营环境, 使用了遗传算法的交叉方式来智能化相关特征, 确定了不同规模的调度方式。童刚以总效益最大为调度目的, 建立了参数优化的模型, 给出了求解模型的基本步骤, 并进行了相关验证。

遗传算法

遗传算法是使用计算机模拟自然选择和生物进化过程的方法, 是通过模拟自然进化来得到搜索最优解。由J.Holland教授于1975年提出, 并有相关理论书籍《Adaptation in Natural and Artificial Systems》。

遗传算法也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法, 是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。该算法最初是模拟生物进化发展起来的, 包括遗传、变异、选择以及杂交。遗传算法通常的效率比其他传统的优化方法低, 在适应度函数选择不当的情况下, 有可能收敛于局部最优, 而不能达到全局最优。

公交调度中的问题

在以前的公交调度运营中, 调度人员对车辆的运行状况、运输量、客流量的情况不能实时掌握, 按照计划表来进行调度, 这样会造成资源的浪费和乘客滞留的情况。也就是说, 在传统的公交调度中, 只能按照经验来进行, 完全无法实现信息化的反馈机制, 无法实现真正意义上的智能公交调度。

公交调度的遗传算法设计实现

1.数据模型的建立

遗传算法重点研究了公交调度中的如何根据各个时段的客流量来计算相应时间的发车间隔情况。

为设计公交调度方案, 可以从乘客和公司的两个角度来看问题。乘客总是希望等待的时间尽可能的少, 公司总是希望发车的次数少, 运力尽可能的大, 运营成本低。所以就以乘客总的等待时间和公司的发车次数合并为加权目标函数。

首先对实际公交运营进行抽象, 建立下面的数据模型。

公交数据:某一时段的站点编号、上车人数、下车人数、到站概率、下车概率

2.遗传算法的实现

发车区间与编码的映射关系:假设发车区间为[1, 7], 即区间长为7, 采用3位二进制编码, 当遗传算法生成二进制数111时, 不进行处理。采用3位的二进制编码, 译码时根据对应关系取的对应整数。

(1) 染色体编码

实现如下:假设最大间隔是10分钟, 最小间隔是3, 区间长度是8, 将区间分成8份, 表示每个时段的串长度需要3位。如果把一天分成K个时段, 则染色体长度为3K。

编码对应的解是唯一的, 将结构转化为3位一组, 共计K个组, 转化成十进制数, 分别对应K个发车间隔, 从而得到发车时序。

(2) 选择交叉

a:从选择操作得到的临时种群中随机抽取两个染色体编码;

b:通过概率计算来判断是否进行交叉, 是则执行c, 否则执行f;

c:按照交叉规则, 任选交叉位, 进行单点交叉, 记录染色体的操作次数;

d:计算约束条件, 是则执行f, 否则执行e;

e:判断染色体的交叉次数是否超过阀值, 是则使用交叉操作之前的染色体, 执行f, 否则执行c;

f:进入下一代种群, 判断是否超过种群规模阀值, 是则停止交叉, 否则执行a。

(3) 变异操作

变异操作的基本步骤如下:

(1) 从所有个体的编码范围内任选基因。

(2) 使用变异概率来对这些基因进行变异。

(4) 终止条件

预设最大迭代数, 达到该数目时, 算法终止。使用最大迭代数作为遗传算法的终止条件, 最大迭代数一般是根据具体情况而定, 这里取500代。

(5) 算法总框架

a:初始化;

b:根据对应的编码规则, 产生若干个染色体, 形成初始种群;

c:将目标转化为适应度函数, 将每个个体转化为发车间隔, 计算适应度函数, 然后按适应度值升序排列;

d:按轮盘赌选择个体, 形成种群;

e:在交叉率的要求下, 在种群中随机选择若干个个体进行单点交叉;

f:交叉操作后的个体按照变异率进行变异操作;

g:保持规模为标准规模, 计算适应度函数值, 并根据结果升序排列;

h:从前一代种群中选择适应度高的优良个体替换新种群中适应度较低的个体, 同时必须保持现有的种群规模;

I:对新种群中的个体按照适应度升序排序;

g:判断已经完成迭代次数, 是则结束, 否则到d。

3.参数设置

种群规模size=30、最大进化代数为500、交叉率为0.8、变异率为0.01、最大交叉次数10、最大变异次数为10。加权系数α、β根据情况而定。

4.结果分析

适应度函数的选择方法的不同会造成不同的遗传算法的结果:采用给定标准的适应度函数可克服未成熟的收敛情况以及可能发生的漫游情况, 从而使得遗传算法的搜索性能大大提高。适应度函数的设计和遗传算法的选择操作有关, 另一方面适应度函数影响遗传算法的停止条件.

选择方法的影响.当时用排序选择法和轮盘赌选择法比较, 在使用排序选择法时, 适应度高的个体数量一定会迅速增加, 从而排挤掉其他低适应度的个体, 降低了种群多样性, 造成了算法可能的过早收敛情况。可以将适应度函数进行一定次数的线性变换, 然后采用按适应度的轮盘赌算法来进行选择, 遗传算法的结果准确性会得到很大的提高。

浅析邵阳烟草干线运输调度系统算法 篇2

关键词：信息化；调度管理算法；概要设计

中图分类号：TP393

1 干线运输管理背景

邵阳市烟草公司从2007年开始推行了“一库式”方案，采取二级配送模式，中心库至各中转站为干线运输，各中转站到零售户为二级运输。公司拥有8个中转站（含本级），7台箱式货车，通过统一调度，负责全区的卷烟干线运输。每年卷烟的干线运输总量接近24万箱（5件烟称为1箱），其中，最大的中转站年运输量（8.59万箱），是最小的中转站年运输量（0.85万箱）的10倍多，最远的中转站单程距离（173公里）是最近的中转站单程距离（23公里）的7倍多，而负责干线运输的7台箱式货车的装载量大小不一，部分干线货车还需要在最大中转站（本级）过夜……因此，分配运输任务和管理调度车辆，成为一个复杂而繁琐的工作。当前的做法是，根据每日各个中转站的运输量，由人工计算后将运输任务分配给每台干线货车，调度作业效率低，难以保证成本最低和效率最优，也无法记录和平衡各车辆年度总任务量，迫切需要设计合理的调度管理算法，进而搭建配套的信息管理系统。

2 干线运输约束条件

2.1 基础信息

现有的8个中转站（本级、隆回、洞口、绥宁、城步、武冈、新宁、邵阳县）和7台干线送货车，为了简化说明分别用“A站、B站、C站……H站”和“湘E01、湘E02、湘E03……湘E07”表示。干线运输车以整托盘卷烟的“垛”为单元进行装卸和运输，为了提高车辆装载率，根据货车的车厢高度，将每垛的容量定义为35件，即每个托盘可以放35件烟（合计1750条烟）。干线货车中，湘E01、湘E02、湘E03、湘E04和湘E05等五台车，每台车最大可装17垛；湘E06最大可装16垛；湘E07最大可装13垛。8个中转站单程距离远近不一，其中，A站30公里，B站23公里，C站76公里，D站173公里，E站155公里，F站105公里，G站140公里，H站55公里。根据历史数据显示，各中转站的日平均干线运输量为A站1789件，B站740件，C站519件，D站240件，E站177件，F站439件，G站388件，H站619件，但各中转站的运输量会随着销售旺淡季而不断变化，且波动幅度较大，因此，每天各站的实际运输量无法准确预测。

2.2 约束规则

公司每个月按照4个周期访销，每个周期5个工作日，干线货车全年约有240天的工作日需要出车。8个中转站虽然每天实际运输量波动幅度大，但每个中转站每天都有运输任务。7台货车分别对应7个司机，负责8个中转站全年共计约120万件卷烟的运输任务。经过梳理，调度约束规则包括：

（1）不同中转站的卷烟必须采用不同托盘进行码垛，以便中转站快速卸货。

（2）D站和E站的日送货量之和小于17垛（595件烟）时，必须安排给同一辆车，且D站的货物先行装载进入货箱，以便E站先行卸货。

（3）路途最远的3个中转站（D站173公里、E站155公里、G站140公里），每个站货物应尽量避免拆分成多车，以避免增加总行驶里程。

（4）当同一站点的货物需要拆成多车时，应尽量实现车辆满载的次数最多化。例如：某站有18垛货物时，不能拆分成“9垛+9垛”，而要拆成“17垛+1垛”或“16垛+2垛”，大货车装多数垛，小货车则装少数垛，满载车次最多化。

（5）同一中转站有多车货物时，尽量安排给不同车辆，以便同站货物尽快装走，也便于同站货物的所有车辆同时出发，避免货物长时间占用发货区面积。

（6）每台车每天的送货总里程应尽量均衡。此外，每日送货趟数最多的车，与当日送货趟数最少的车，一般只差1趟，最多只能差2趟。

（7）尽量不让同一车辆连续两天跑的趟数最多，或者连续两天跑的里程最长，除非无法安排过来。

（8）在不增加车次的前提下，尽量把A站货物作为每个执行A站运输任务的车辆的最后一趟进行运输，以便有尽可能多的货车在A站过夜。

（9）原则上，每台车要轮流、循环为每个站点送货，且尽量不让同一车辆连续两天跑相同的站点序列，除非无法安排过来。

（10）除了D站和E站货物拼车，其它货物拼车由系统依次按照“总车次最少”、“总行驶里程最短”、“平均装载率最大”的原则计算，并支持人工调整。

（11）销售旺季（日运输总量大于5000件）时每台车每天均需出车；销售淡季（日运输总量小于等于5000件）时，只需派出6台车（余下1台车检修或司机轮休）。同时，要求全年每个车（司机）轮休的天数大致相等。

（12）通过干线运输调度管理，要求派出的总车次尽量少，货车平均装载率尽量大，且全年每台车的行驶里程大致相等。

除约束规则外，根据系统算法要求，还需确定每项约束规则之间的优先级，以便当两项约束规则之间有冲突时，信息系统优先遵循哪项规则。依据业务实际需求，确定以上约束规则的优先级排列为：规则（1）优先级>规则（2）优先级>规则（3）优先级>……>规则（12）优先级。

3 调度系统框架与流程

按照整理归纳的约束规则，我们采用高级语言可得出与干线运输调度业务相匹配的算法，設计出适合公司的卷烟干线运输调度系统。为了便于系统部署和管理，确定系统框架为B/S架构，采用PHP开发，支持PHP+MySQL平台发布。

系统每天从卷烟订单系统中获取每个中转站当天的货物运输量，并以35件为1托的单元进行运输任务调度分配，确保调度结果满足上述约束规则。结合业务实际情况，确定具体流程如下：

（1）数据同步。调度员在干线运输调度系统中，通过数据同步模块，从卷烟订单系统中抽取所有中转站的干线运输量。

（2）调度运算。系统根据所有优先级和约束规则，进行调度运算，生成调度结果。

（3）调度结果审核。人工审核调度结果，并根据车辆和司机的临时状态进行调整，最终确认每辆车每天的运输任务。

（4）发布通知。通过审核后，系统将在服务器上生成调度结果图片，服务器上安装LED屏幕控制程序，每间隔5秒钟将该图片发送至装卸平台附近LED屏幕上显示，以便作业人员按照调度结果进行作业。同时，系统将通过短信网关，向相关人员（包括司机）发送手机短信通知，告之其运输任务和作业时间。

（5）即时优化。当车辆在执行任务过程中遇到突发事件需要变更任务单时，即时优化并重新调度尚未执行的任务。

（6）任务执行情况反馈。车辆遇到突发事件，导致其实际的运输时间和行驶路线变化时，当班司机通过管理人员将实际情况反馈至系统中，以便系统长期策略的准确实行。

4 结束语

邵阳烟草干线运输调度系统将应用在卷烟配送中枢业务上，因其调度管理的作业具有多目标特性，区域特征明显，约束规则复杂，只有结合邵阳卷烟配送业务的实际情况，全面总结和分析适当调度规则和相应的调度优先级，建立合理的干线运输调度管理算法，进而构建配套的调度管理信息系统框架和业务流程，才能最终搭建高效的干线运输调度系统。

参考文献：

[1]雷德明，严新平.多目标智能优化算法及其应用[M].北京：科学出版社，2009（03）.

[2]朱伟.邵阳烟草精益物流课题[C].资料汇编，2014（06）.

[3]湖南省烟草公司.卷烟物流综合管理平台调研报告[Z].2013（09）.

作者简介：蔡永长（1981-），男，湖南新化人，国际物流师，高级营销师，网络工程师，硕士，2012年毕业于北京工业大学软件工程专业，研究方向：信息管理。

智能调度算法 篇3

可中断负荷管理在维持电力系统安全可靠运行和缓解电力市场价格飞升等方面具有重要作用,并已得到广泛应用[1]。在可中断负荷管理实际应用中,需要考虑多个可中断用户的可中断负荷优化调度问题,即在一定的优化目标和约束条件下,如何在多个可中断用户中分配要求的负荷中断容量?考虑多时段的可中断负荷优化调度问题往往是一个复杂的多目标组合优化问题,有关该问题求解算法的研究具有重要的理论和实际应用意义。

现有相关研究大多采用传统的优化算法,如文献[2-3]采用动态规划方法结合启发式规则来解决可中断负荷优化调度问题,文献[4]采用类似于解决机组检修规划的基于优先次序的启发式算法。以上研究在原理上无法保证获得可中断负荷优化调度问题的最优解。

本文研究现代智能优化算法在多时段可中断负荷优化调度中的应用问题,建立的优化调度模型可考虑中断补偿费用最小化和中断频率最小化等多个优化目标,并可计入可中断用户的不同中断特性,如中断补偿价格、每次中断的时间限制,调度周期内的总中断时间限制等。采用离散粒子群优化算法[5,6,7]和遗传算法[8]来求解。算例分析着重比较这两种智能优化算法的性能。

1 可中断负荷优化调度问题

可中断负荷优化调度问题,是在一定的优化目标和约束条件下,解决要求的负荷中断量在多个可中断用户中的分配问题。在电力市场环境下,电力公司中断用户负荷时需要给予用户一定的经济补偿,相应的中断补偿价格可通过用户报价的形式获得[4]。从电力公司的角度来看,一个合理的可中断负荷优化调度目标是在满足需要的负荷中断量的条件下,使得电力公司支付给用户的中断补偿费用最小。在多时段情况下,可中断负荷优化调度还需充分考虑不同用户的负荷中断特性[9],如每次中断的最大持续时间限制、两次中断之间的最小时间间隔限制、调度周期内的总中断时间限制等,而且,从用户角度考虑,一个合理的要求在调度周期内中断次数(或频率)越小越好。基于这些考虑,本文给出如下可中断负荷优化调度模型。

考虑N个可中断用户在T个时段中的可中断负荷调度问题,假设第t个时段(1 h)要求的最小负荷中断量为△C(t),t=1,2,…,T。第i个用户的可中断容量为C(i),中断补偿价格为p(i),每次中断的最大持续时间为max(i),两次中断的最小时间间隔为min(i),要求的最大总中断时间为Total(i),i=1,2,…,N。x(i,t)为中断决策变量(0-1变量),x(i,t)=1表示第t时段中断第i用户容量C(i),x(i,t)=0表示第t时段不中断第i用户的负荷。

可中断负荷调度问题的优化目标取为在中断频率尽量低的情况下,总的中断补偿费用最小,即目标函数可表示为:

约束条件为:

(a)第t个时段要求的最小中断负荷约束

(b)第i个用户每次中断的最大持续时间约束

(c)第i个用户两次中断的最小时间间隔约束

(d)第i个用户在调度周期内的总中断时间约束

由式(1)~(6)组成的可中断负荷优化调度模型,是一个含时段耦合约束的多目标组合优化问题。需要指出的是,该模型的目标函数和约束条件还可根据实际使用时的具体要求加以调整或补充,如:在各时段批发价格已知时,电力公司可考虑以获得的负荷中断效益最大为目标;用户也可能有其他中断要求,如不希望在某些特定时段被中断供电,等。不管模型如何调整,本文介绍的方法应同样适用。

2 求解算法

为了求解上节给出的可中断负荷调度问题,本文采用两种智能优化算法:粒子群优化算法(PSO)和遗传算法(GA)。与GA算法相比,PSO算法没有选择操作,因而所有候选解(包括劣解)均始终参与搜索,而对于离散的组合优化问题,好的解可能位于劣解的附近,因而PSO算法更可能求得最优解。为了求解离散的可中断负荷优化调度问题,本节侧重给出基于离散的二元粒子群优化算法的求解方法。

2.1 离散二元粒子群优化算法

在PSO算法中,优化问题的候选解是搜索空间中的一个“粒子”,通过随机初始化一群粒子,然后经过迭代找到最优解(最优粒子位置)。在每次迭代中,每个粒子通过跟踪两个“极值”来更新自己的位置。两个“极值”分别为粒子本身所找到的最优解(个体极值Pbest)和整个种群当前所找到的最优解(全局极值Gbest)。在离散的二元粒子群优化算法(BPSO)[5]中,每个粒子根据式(7)来更新自己的速度:

其中:k表示迭代次数;rand()为[0,1]间服从均匀分布的随机数;w为惯性因子;c1和c2是非负的学习因子;xkid是粒子i在第k次迭代中第d维的当前位置;Pbestkid是粒子i在第k次迭代中第d维的个体极值点的位置;G bestdk是整个粒子群在第k次迭代中第d维的全局极值点的位置。

BPSO算法中粒子的位置由式(8)、(9)来确定。

其中,S(·)是一个Sigmoid函数。

2.2 采用离散BPSO算法的可中断负荷调度

可中断负荷调度问题的候选解x(i,t),t=1,2,…,T,i=1,2,…,N,表示为一个粒子,因而每个粒子的维数为N×T。本文采用罚函数法[10]来处理多目标优化问题及其约束条件,从而把可中断负荷调度问题转化为一个无约束单目标优化问题,再通过离散BPSO算法或GA算法来求解。

对于最小化中断次数的优化目标式(2),定义一个罚函数f2:(1)任何用户第一次被中断时罚函数值为0;(2)第二次中断罚函数为100;(3)为了最小化中断频率,每次中断后该用户的罚函数值均加倍。则f2可表示为

其中:NC(j)表示中断j次的用户数;J表示所有用户中被中断最多的次数。

对于式(3)、(4)、(5)、(6)的约束条件,也采用目标惩罚的方法来处理,可得到如式(11)单目标无约束优化问题:

其中:f0为离散BPSO算法或GA算法的适应函数;NV为不满足约束条件式(4)、(5)和(6)的个数;K1,K2为惩罚系数,本文取K1=106,K2=105。

3 算例分析

考虑19个可中断用户在白天16个小时时段(8:00~23:00)中的可中断负荷调度问题,每个时段要求的最小负荷中断量△C(t)如表1所示。每个用户的可中断容量C(i),中断补偿价格p(i),每次中断的最大持续时间max(i),两次中断的最小时间间隔min(i),总中断时间Total(i),如表2所示。需要说明的是,以上有关可中断用户特性的基础数据主要参考了文献[3]中的算例数据,并略做了调整。尽管不是实际数据,但应该在合理范围之内。在实际应用时,需根据具体的基础数据来进行优化计算。基础数据的改变不会影响有关算法性能的主要结果。

采用离散的二元粒子群优化算法(BPSO)与遗传算法(GA)进行求解,其中,BPSO算法中粒子群种群数为50,迭代次数为1 250;GA算法种群数为50,迭代次数为2 000,采用锦标赛法进行选择操作,多点均匀交叉变异,交叉率为0.7,变异率为0.01。结果如表3和表4所示。

由表3可知,BPSO算法得到了具有更小中断补偿费用的解,两个算法得到了相同的中断次数。

由表4可知,GA算法的调度解中并没有涉及到用户15,而BPSO算法的调度解中则对每个用户进行了中断。

图1给出了由BPSO和GA算法得到的可中断负荷调度结果,其中阴影部分为要求的最小负荷中断量。可以看出,在第2,6,10时段,GA算法调度的中断量明显高于BPSO算法,从而导致相对较高的中断补偿费用。

表5给出了BPSO算法和GA算法的平均性能比较。与GA算法相比,虽然BPSO算法的计算时间稍长,但其具有较好的收敛成功率,适应函数平均值也优于GA算法。

图2给出了BPSO和GA算法的收敛曲线,可看出,GA算法会陷入局部最优解,而BPSO算法的收敛解优于GA算法。

4 结论

本文探讨了智能优化算法在多时段可中断负荷调度问题中的应用,建立的优化模型可考虑中断补偿费用最小化和中断频率最小化等多个优化目标,并可计入不同可中断用户的不同中断特性。给出的算例分析着重比较了基于离散二元粒子群优化算法和遗传算法的结果,表明离散粒子群算法可获得优于遗传算法的解,因而在多时段可中断负荷调度中具有较好的应用前景。

在本文研究中,有关用户的可中断负荷量、中断补偿价格等信息假设是已知的。在实际情况下,电力公司通常很难获得真实合理的用户信息,从而会影响优化调度结果的有效性。对于这类问题,一方面可采用机制设计理论,通过设计激励性合同来合理引导用户披露真实信息[11,12]。另一方面,可引入竞争机制,建立一个可中断负荷竞争市场,通过投标竞价可在一定程度上缓解可中断用户虚报信息带来的不理想结果,当然,当参与竞争的可中断用户数量不够多时,也会存在用户的策略性报价问题和市场力问题。如何解决这些问题,还需要下一步深入研究。

摘要：考虑多个可中断用户的多时段可中断负荷优化调度问题一般是一个多目标的组合优化问题,建立了一个多时段多目标可中断负荷优化调度模型,可考虑中断补偿费用最小化和中断频率最小化等多个优化目标,并计入不同可中断用户的不同中断特性和时段耦合约束。给出了应用离散二元粒子群优化算法的多时段可中断负荷调度问题求解方法。基于一个含19个可中断用户和16个时段的可中断负荷调度问题的算例仿真,通过比较采用离散二元粒子群优化算法和遗传算法的优化结果,表明离散粒子群算法在收敛解的质量上优于遗传算法。

关键词：多时段可中断负荷调度,组合优化问题,离散二元粒子群优化,遗传算法

参考文献

[1]Tuan L A,Bhattacharya K.Competitive framework for procurement of interruptible load services[J].IEEE Trans on Power Systems,2003,18(2):889-897.

[2]Huang K Y.Demand subscription services—an iterative dynamic programming for the substation suffering from capacity shortage[J].IEEE Trans on Power Systems,2003,18(2):947-953.

[3]Huang K Y,Chin H C,Huang Y C.A model reference adaptive control strategy for interruptible load management[J].IEEE Trans on Power Systems,2004,19(1):683-689.

[4]王建学,王锡凡,王秀丽.电力市场可中断负荷合同模型研究[J].中国电机工程学报,2005,25(9):11-16.WANG Jian-xue,WANG Xi-fan,WANG Xiu-li.Study on model of interruptible load contract in power market[J].Proceedings of the CSEE,2005,25(9):11-16.

[5]Kennedy J,Eberhart R.A discrete binary version of the particle swarm optimization[C].//Proceedings of IEEE International Conference on Systems,Man and Cybernetics.1997:4104-4108.

[6]Galing Zwe-lee.Discrete particle swarm optimization algorithm for unit commitment[C].//Proceedings of IEEE Power Engineering Society General Meeting.Toronto(Canada):2003:418-424.

[7]刘涌,候志俭,蒋传文.求解机组组合问题的改进离散粒子群算法[J].电力系统自动化,2006,30(4):35-39.LIU Yong,HOU Zhi-jian,JIANG Chuan-wen.Unit commitment via an enhanced binary particle swarm optimization algorithm[J].Automation of Electric PowerSystems,2006,30(4):35-39

[8]Kazarlis S A,Bakitrtzis A G,Petridis V.A genetic algorithm solution to the unit commitment problem[J].IEEE Trans on Power Systems,1996,11(1):83-92.

[9]王建学,王锡凡,张显,等.电力市场和过渡期电力系统可中断负荷管理—可中断负荷运营[J].电力自动化设备,2004,24(6):1-5.WANG Jian-xue,WANG Xi-fan,ZHANG Xian,et al.Interruptible load management in power market and interim system——operation of interruptible load[J].Electric Power Automation Equipment,2004,24(6):1-5.

[10]Coello C A.Theoretical and numerical constraint-handling techniques used with evolutionary algorithms:a survey of the state of the art[J].Computer Methods in Applied Mechanics and Engineering,2002,191(11-12):1245-1287.

[11]张少华,方勇,李渝曾.电力市场中的激励机制设计[J].电网技术,2003,27(1):52-56.ZHANG Shao-hua,FANG Yong,LI Yu-zeng.Incentive mechanism design in electricity markets[J].Power Systems Technology,2003,27(1):52-56.

智能调度算法 篇4

关键词：炼钢-连铸生产调度,多目标优化,设备冲突,多目标进化算法,冲突消解

炼钢-连铸生产过程是现代钢铁联合企业生产流程中的核心环节。以数学规划的视角来看，这是一个多段生产、多段运输、多段存储的离散和连续相混杂的大型高温生产过程，加上其离散性、随机性、多目标和多约束性等特点，使该生产过程具有相当程度的复杂性。炼钢-连铸生产过程效率的提高对整个钢铁企业有重要影响，而制定合理的生产调度计划，是保证其高效率运行的关键。

炼钢-连铸生产调度计划可以分为2类[1]:一类是生产批量计划，另一类是生产时间计划。生产批量计划是以客户合同数据为原始数据，根据工艺限制条件将不同的合同需求进行最佳组合而生成的，包括炉次计划和浇次计划。生产时间计划是在生产批量计划的基础上，以炉次为最小计划单位，在追求某一评价函数(如最小等待时间、最小提前拖期费用、最小总流程时间)最佳的情况下的一类特殊的job-shop排序问题，其最终结果是确定以何种顺序、在何时、何种设备上安排钢水从转炉到连铸机的生产过程的各个工序。

对于炼钢-连铸生产调度问题，许多国内外学者都做了深入的研究，如唐立新等[2]、A.Bellabdaou等[3]、冯振军等[4]、郑忠等[5,6,7]、俞胜平等[8]和李铁克等[9]。文献[2,3,4,5,6,7,8,9]都围绕着作业排序、工序设备指派和时间安排等关键问题建立了炼钢-连铸生产调度的线性或非线性规划模型，并综合运用启发式方法和/或遗传算法等智能搜索算法对模型求解，以得到优化的排程方案。但是，对于转炉炼钢厂在生产任务繁忙、调度复杂(如炉机不匹配)等极端情况下经常出现的设备冲突问题，调度数学模型和算法实际上欠缺直接、有效的处理方法。

针对现有方法存在的不足，作者紧密结合实际生产工艺，应用多目标优化的基本思想，建立了新的炼钢-连铸生产智能调度模型，将炼钢-连铸生产调度问题转化为具有两个目标的多目标优化问题，其中，第1个目标为最小化全厂完工时间与所有炉次等待时间，第2个目标由不能消解的设备冲突时间转换得到，这样利用多目标优化方法的先天优势来克服传统方法处理设备冲突问题时存在的缺陷;并设计了基于多目标进化算法NSGA-Ⅱ的求解算法;此外，针对设备冲突困境，还提出了一种基于等待时间松弛的冲突消解方法，通过迭代松弛调整炉次的等待时间长度完全消解设备冲突。在国内某大型转炉炼钢厂的应用实践表明，所提方法和模型能较好地满足繁忙和复杂工况下的优化调度需求，对计划排程和生产组织起到较好的指导作用，最终达到提高全厂生产效率的目的。

1 问题描述及假设

常规的大型转炉炼钢厂包含的工序环节有:脱硫(KR)、转炉冶炼(LD)、吹氩(Ar)、钢包炉(LF)、真空精炼(RH)和连铸(CC)等。满足如下工艺前提条件。

1)不同钢种对应着不同的工艺处理路径，会依次经过上述全部或部分工序环节，但工艺路径上不存在回环，即不会两次通过同一工序，回炉和改钢的情况不在考虑范畴之内。

2)钢水在转炉炼钢厂的时间分为下面几类:工序的处理时间(包含辅助时间)，相邻工序间的运输时间，以及工序前的等待时间。现在不考虑前两类时间的柔性，而只有最后一类等待时间根据需要可调整。一个炉次钢水的处理-运输-等待流程示例如图1所示。

3)将上述柔性可调的时间具体到真空和连铸工序处理开始之前的等待时间，通过松弛这两处的等待时间来消解可能发生的设备冲突，但必须满足最大等待时间约束或相邻工序间的最大间隔时间约束。

2 基于多目标优化的炼钢-连铸生产智能调度模型与算法

2.1 炼钢-连铸生产智能调度模型

基于多目标优化方法建立的炼钢-连铸生产智能调度模型具有如下的表达形式:

数学符号描述如下。

序号:i为浇次编号，共有I个浇次，i=1,2，…，I;j为炉次编号，第i个浇次中包含的炉次数为Ji，即j=1,2，…，Ji;k为工序编号，共有K道工序，定义脱硫工序编号为k=1，连铸工序编号为k=K;另外，为了表述方便，还定义kl、kr和kc分别为转炉、真空精炼和连铸工序的编号;(i,j,k)为序号组合，用于唯一标识第i个浇次中的第j个炉次在第k道工序的处理操作;(i^,j^,k)为序号组合，用于唯一标识与第i个浇次中的第j个炉次在第k道工序使用同一设备的紧前炉次的处理操作，它对应第i^个浇次中第j^个炉次的第k道工序。

变量:x(i,j,k)为(i,j,k)的开始时刻;y(i,j,k)为(i,j,k)指定的设备序号;tw为(i,j,k)开始处理之前的等待时间，只在真空和连铸工序处理开始前设置等待时间，特别地，定义在这两处的等待时间分别为tw(i,j,kr)和tw(i,j,kc)。

常量:twmax(kr)为炉次在第1个可等待工序(真空精炼工序)的等待时间上限;twmax(kc)为炉次在第2个可等待工序(连铸工序)的等待时间上限;tp(i,j,k)为(i,j,k)的处理时间;tt(i,j,k)为第i个浇次中的第j个炉次在工序k和后工序之间的运输时间。

集合:Θ为全部浇次的集合，满足Θ={i|i∈[1,I]};Φi为第i个浇次中的炉次集合，满足Φi={j|j∈[1,Ji]};Ψ为全部处理工序的集合，满足Ψ={k|k∈[1,K]}。

在上面的优化调度模型中，式(1)为目标函数集，其中f1表示全厂完工时间f1,1与所有炉次等待时间f1,2两项之和，全厂完工时间f1,1为最后一道工序的最晚完成时刻(即开始时刻x(i,j,K)与处理时间tp(i,j,K)之和)与第一道工序的最早开始时刻x(i,j,1)之差，所有炉次等待时间f1,2为所有炉次在两处可等待工序的等待时间总和;f2表示设备冲突时间之和，若紧前炉次的结束时刻大于当前炉次(i,j,k)的开始时刻，则会发生设备冲突。

优化变量为各浇次的开浇时刻构成的向量x，也即是各浇次中第1个炉次在连铸工序的开始时刻x(i,1,K)构成的向量，如式(2)所示。

设置上述目标函数集的工艺意义为:通过优化计算，搜索浇次开浇时刻向量，随后根据“时间并行倒推算法”[5]，依次为各炉次进行时间分配和设备指派，并在发生设备冲突时执行冲突消解;最优的浇次开浇时刻向量将在无设备冲突的前提下，使全厂完工时间与所有炉次等待时间之和最小。针对每组给定的浇次开浇时刻向量，时间分配和设备指派方法见参考文献[5]中的“时间并行倒推算法”，不再赘述，而冲突消解采用本文提出的基于等待时间松弛的冲突消解方法，见节3所述。

式(3)～式(6)是编制常规的炼钢-连铸生产调度计划时必须满足的约束，其中:式(3)表示连浇约束，x(i,j,k)和x(i,j+1,K)分别为第i个浇次中相邻的两个炉次在连铸工序的开浇时刻，tp(i,j,k)为其中前一个炉次的浇注时间;式(4)表示同一炉次的相邻工序之间，后一工序需在前一工序处理完毕才能开始，还需考虑相邻工序间的运输时间，x(i,j,k)和x(i,j,k+1)分别为炉次在相邻工序的开始时刻;式(5)表示对每一对当前炉次和其紧前炉次而言，它们使用的是同一工序中的同一设备，y(i,j,k)和分别为给这一对相邻炉次分配的设备序号;式(6)表示需将炉次的每一个处理时间不为0的工序分配到相应工序的某台设备上加工。式(7)和式(8)表示等待时间约束，每个炉次在两个可等待工序环节的等待时间均不能超过对应的上限设定值。

2.2 求解算法

多目标进化算法(MOEA)近年来一直是学术界研究的热点，学者们针对不同的实际问题，提出了多种不同的MOEA。在借鉴国内外研究成果的基础上，运用Deb等提出的NSGA-II[10]求解炼钢-连铸生产智能调度问题。下面介绍基于NSGA-II的求解算法中的核心内容。

2.2.1 染色体构成与适应度计算

2.1节已经述及，炼钢-连铸生产智能调度模型的优化变量为各浇次的开浇时刻构成的向量，自然地，求解算法的染色体也由与浇次开浇时刻对应的基因拼接而成。另外，每条染色体都有与模型的目标函数值f1和f2对应的两个适应度值。

2.2.2 改进的Pareto支配关系

设xi和xj是进化种群中的任意两个不同的个体，称xi支配xj，或xi优于xj，表示为，“”表示Pareto支配关系，则必须满足下列条件之一

即对于任意两个个体，设备冲突时间之和f2较小的个体占优，若两个个体具有相同的适应度值f2，则比较它们的另一个适应度值f1，即全厂完工时间与所有炉次等待时间两项之和较小的占优。

2.2.3 边界集和偏序集的构造方法

设包含N个个体的种群P，要求按照某种构造方法将种群P分类排序为n个互不相交的子集P1,P2，…Pn，满足也表示Pareto支配关系，即Pr+1中的个体受Pr中个体的支配(r=1,2，…，n-1)。子集Pr称为种群P的第r层边界集(Pareto front)，其构造方法如下

式(9)中，dj表示种群P中支配个体x的个体数，即

式(10)中，“#”表示集合中的元素个数。

偏序集是NSGA-II算法维持解集分布性的策略，它基于以下两点构造:

(1)位于不同边界集上的两个个体，边界集序号小的个体优化序号大的个体;

(2)同一边界集上的两个个体，聚集距离大的个体优于聚集距离小的个体。

其中，聚集距离等于个体与其相邻的另外两个个体在每个子目标上的距离差之和。

2.2.4 总体流程

现设计的基于NSGA-II的求解算法的总体流程如图2所示。

3 基于等待时间松弛的冲突消解方法

转炉炼钢厂包含的所有工序中，虽然每个工序都可能在编制生产计划时发生设备冲突，但是转炉冶炼工序一般是全厂生产能力的瓶颈所在，在该工序发生冲突的可能性最大，消解该工序冲突最困难，方法也最复杂。基于此，下面以转炉冶炼工序为例阐释基于等待时间松弛的冲突消解方法的基本思路。

对于每组给定的浇次开浇时刻向量，根据“时间并行倒推算法”，可推知各个炉次在转炉工序的开始时刻，将所有炉次在转炉工序的开始时刻按时间升序排列。

下面从已经排好序的所有炉次在转炉工序的开始时刻组成的序列的末尾开始，以最后一个炉次为当前炉次，计算当前炉次和其紧前炉次开始时刻之间的间隔，紧前炉次的开始时刻需沿序列向前追溯，为当前炉次开始时刻之前第N(kl)个数据，其中，N(kl)为转炉工序包含的设备数量。

以图3为例说明。

如图3所示，若定义炉次m为当前炉次，其开始时刻为x(i,j,kl)，则在假定转炉数量为3座且各炉次转炉工序处理时间相等的前提下，其紧前炉次为m-3，紧前炉次的开始时刻为

若二者之间的间隔小于转炉工序的处理时间tp(i,j,kl)，则定义:

式(11)中，tconf(i,j,kl)为当前炉次与其紧前炉次发生设备冲突的时长，为消除此冲突，需提前紧前炉次的开始时刻。因为转炉后续工序的开始时刻已经先于转炉工序倒推得到，所以需在转炉后的可等待环节设置等待时间。除了部分高品质钢之外，并不是所有钢种的工艺路线中都包含第1个可等待环节，因而可按紧前炉次是否经过该工序分为2种情形，下面以经过真空精炼工序为例来描述，不经过该工序情形下处理方式类似，不再赘述。

查看紧前炉次在转炉工序后的第1个可等待环节已经分配的等待时间，若小于twmax(kr)，则说明此处的等待尚未达上限，还有可用于消解转炉工序设备冲突的时间裕量。即

若

则令

式(13)中，为松弛调整后紧前炉次在真空精炼工序的等待时间。

此时，若紧前炉次在转炉工序和真空精炼工序之间还有其他工序，则需将其他工序和转炉工序的开始时刻一并提前，即

式(14)中，分别为松弛调整前后第i个浇次的第j个炉次在工序k的开始时刻。

若

则还需查看紧前炉次在转炉工序后的第2个可等待环节已分配的等待时间，与第1个可等待环节的处理逻辑类似。

若冲突时长满足式(16)和式(17)

则令

式中，为松弛调整后紧前炉次在连铸工序的等待时间。

值得注意的是，若在本次松弛调整中，紧前炉次在真空精炼和连铸工序的等待时间均有改变，则需要将其在转炉和连铸工序之间的其他工序的开始时刻同转炉工序一并提前，提前的算法为

若两个可等待环节的时间裕量之和小于冲突时长，则经过上述调整过程后，当前炉次在转炉工序与其紧前炉次依然存在设备冲突，该冲突值计入炼钢-连铸生产智能调度模型的目标函数f2中。

当前炉次处理完毕，则沿开始时刻序列向前移动，以当前炉次的前一个数据作为新的当前炉次开始时刻，循环执行上述处理流程。

4 案例研究

以国内某大型钢铁企业的转炉炼钢厂为研究案例。该炼钢厂有3个脱硫站、3座转炉、3个吹氩站、2个RH真空精炼炉，以及4台连铸机。转炉的炉容为70 t，单座转炉的日生产能力为90炉左右。由于该转炉炉容相对其他新建转炉较小，生产组织较为灵活，所以承担了钢铁企业内几乎所有的高规格和小批量订货合同，以及多个新钢种的试制工作;另外，由于该炼钢厂的转炉和连铸机数量不相等，传统的“炉机匹配”法则在此不适用，协调转炉和连铸机比较困难。正因为上述两点原因，导致该炼钢厂对计划排程和生产组织的要求较高。选择这样一个有代表性的转炉炼钢厂，来验证本文模型和算法的有效性。

以该炼钢厂2012年2月13日白班(8小时工作制)的生产计划为例，当班计划中总炉数达到31炉，钢种数量为6种，是典型的多品种小批量合同生产，因而对排程的要求较高。具体的生产计划由上层的ERP系统编制并提前下发，如下表1所示。

具体地，各钢种的工艺路径和各工序的处理时间如下表2所示。表中，工序处理时间的单位为分钟，若某钢种在具体工序上没有数值，则说明其不经过该工序。

通过应用本文提出的模型和算法，得到的优化调度结果如图4(a)和图4(b)所示。其中，真空精炼和连铸工序前的等待时间上限均设置为15 min。

在图4(a)和图4(b)中，很多炉次在真空精炼和连铸工序的处理时间方块的左上方都有一个小矩形，这代表炉次在这些工序前的等待时间优化值，小矩形的宽度对应等待时间的长度。

之所以有2个不同的调度Gantt图，是因为在优化计算结束时，种群的边界集中有2个个体，它们对应的全厂完工时间均为519 min，所有炉次等待时间总和均为90 min，而设备冲突时间之和均为0min，以个体选择和排序的准则来判断，它们是分不出优劣的。实际上，从Gantt图中可以看出，这2个优化调度结果的区别有二:其一，炉次5.2和炉次6.5在转炉工序设备指派的不同;其二，多个炉次在缓冲工序前等待时间长度的细微区别。

5 结论

针对现有数学规划模型和算法对设备冲突欠缺直接、有效的处理方法，应用多目标优化的基本思想，建立了新的炼钢-连铸生产智能调度模型，将炼钢-连铸生产调度问题转化为具有两个目标的多目标优化问题，这样利用多目标优化方法的先天优势来克服传统方法的不足，并设计了基于多目标进化算法NSGA-II的求解算法;此外，针对设备冲突困境，还提出了一种基于等待时间松弛的冲突消解方法，通过迭代松弛调整炉次的等待时间长度完全消解设备冲突。在国内某大型转炉炼钢厂的应用实践表明了所提模型和算法的有效性。

参考文献

[1]唐立新,杨自厚,王梦光.炼钢-连铸生产的计划与调度结构.东北大学学报(自然科学版),1996;17(6):664—667Tang Lixin,Yang Zihou,Wang Mengguang.Research on framework of steelmaking-continuous casting production planning and scheduling.Journal of Northeastern University(Natural Science),1996;17(6):664—667

[2] Tang L X,Luh P B,Liu J Y,et al.Steel-making process scheduling using Lagrangian relaxation.International Journal of Production Research,2002;40(1):55—70

[3] Bellabdaoui A,Teghem J.A mixed-integer linear programming model for the continuous casting planning.International Journal of Production Economics,2006;104(2):260—270

[4] 冯振军,杨根科,杜斌,等.炼钢连铸调度的启发式和线性规划两步优化算法.冶金自动化,2005;29(4):18—22Feng Zhenjun,Yang Genke,Du Bin,et al.Two stage optimization algorithms based on heuristic and linearprogramming in continuous casting scheduling.Metallurgical Industry Automation,2005;29(4):18 —22

[5] 郑忠,朱道飞,高小强.混合流程作业计划编制的时间并行倒推算法.计算机集成制造系统,2008;14(4):749—756Zheng Zhong,Zhu Daofei,Gao Xiaoqiang.Parallel backward inferring algorithm for production planning of mixed-mode processes.Computer Integrated Manufacturing Systems,2008;14(4):749—756

[6] 朱道飞,郑忠,高小强.炼钢连铸作业计划的混合遗传优化与仿真分析.计算机工程与应用,2010;46(1):241—245Zhu Daofei,Zheng Zhong,Gao Xiaoqiang.Hybrid genetic algorithm optimization-based production planning and simulation analysis for steelmaking and continuous casting.Computer Engineering and Applications,2010;46(1):241—245

[7] 郑忠,高小强,陈开,等.基于混合智能优化算法的炼钢-连铸生产作业计划与实时调度优化方法与系统.中国:CN101770615A,2010Zheng Zhong,Gao Xiaoqiang,Chen Kai.Steelmaking-continuous casting production operation plan and real-time dispatching optimization method and system based on mixed intelligent optimization algorithm.China:CN101770615A,2010

[8] 俞胜平,柴天佑,郑秉霖.炼钢连铸混合智能优化调度方法及应用.系统工程学报,2010;25(3):379—386Yu Shengping,Chai Tianyou,Zheng Binglin.Hybrid intelligent optimal scheduling method for steelmaking and continuous casting and its application.Journal of System Engineering,2010;25(3):379—386

[9] 李铁克,周健,孙林.连铸连轧和冷装热轧并存环境下的炼钢-连铸生产调度模型与算法.系统工程理论与实践,2006;26(6):117—123Li Tieke,Zhou Jian,Sun Lin.Model and algorithm for steelmakingcontinuous casting schedulingin DHCR and CCR environment.Systems Engineering-theory&Practice,2006;26(6):117—123

智能调度算法 篇5

云计算是一种新型的商业计算模式,是分布式处理、并行处理和网络计算的拓展和延伸,已成为工业界和学术界的研究热点。云计算的本质是以虚拟化技术为基础,实现数据共享和服务共享。云平台通过虚拟机的方式,通过高速的互联网互连,形成虚拟资源池。虚拟机调度问题是云计算的关键技术之一,主要实现将虚拟机有效映射到相应的物理机上,达到物理机的负载均衡,有效利用现有资源。由于虚拟机需求量与物理集群的异构,可行部署空间增大,使云计算虚拟机调度成为一个NP⁃hard问题。本文主要基于K⁃means和蝙蝠混合算法研究了云计算虚拟机调度问题,实现了资源的高效平衡分配。

1 相关研究

云计算中虚拟机调度策略对云系统的性能具有很大的影响,能够提高资源的利用率,最大化满足用户的需求。目前已有不少学者对云计算的虚拟机调度机制进行了研究。文献[1]提出了一种基于多属性层次分析的虚拟机部署与调度策略,该算法将虚拟机按资源特点进行分类量化,根据量化后的权向量和服务器资源的使用记录,实现虚拟机的调度。文献[2]在分组遗传算法的基础上,提出了基于多维资源协同聚合的虚拟机调度策略,对均衡资源分配具有一定的优势。文献[3]提出了云计算的改进的credit调度算法,根据空闲率、缓存等因素选择与其相关的任务,能提高缓存效率和增加延迟敏感型任务的响应速度。文献[4]提出基于能耗比例模型的虚拟机调度算法,并采用“最近最小能耗比例优先”的策略进行调度,提高了云系统的能效。文献[5]提出了基于改进NSGAⅡ的虚拟机调度算法,将该模型的求解转化为一个多目标优化问题,在任务执行时间、负载均衡和能量消耗方面具有一定的进步。本文在以上研究的基础上提出基于K⁃means和蝙蝠混合算法的云计算虚拟机调度方法,将虚拟机分配到与其资源互补的物理机上,充分利用物理机上的资源,达到最优化目标。

2 蝙蝠算法和K均值算法

2.1 蝙蝠算法

蝙蝠算法是剑桥大学学者Xin⁃She Yang于2010年提出的一种新型优化算法,主要是受自然界中的蝙蝠搜寻、捕食行为启发形成的新型优化算法,每个优化问题的解是搜索可行空间的一个蝙蝠[6,7,8]。

(1)蝙蝠的运动

蝙蝠算法在d维空间中定义了蝙蝠的位置和速度的变化情况,蝙蝠i在t时刻的位置和速度的变化通过下列公式描述:

式中:β表示在[0,1]之间的随机变量;x*表示当前全局最优位置;fi为频率大小,根据要搜索的范围大小确定其最大值和最小值。局部搜索时,蝙蝠位置的更新公式为:

式中:ε∈[-1,1]是随机数;At是所有蝙蝠在同一时间段的平均音量。

(2)音量和脉冲发生率

当蝙蝠i找到目标时,音量Ai就会降低,同时脉冲发生率ri就会增加,其更新公式如下:

式中:α和γ为常量,为简化变化过程通常取α=γ=0.9。

2.2 K⁃means算法

K⁃means算法以K为参数,把n个对象分为K个类,通过距离大小衡量聚类结果的优劣,聚类的距离越近,说明其相似度就越大,聚类效果越好[9,10]。聚类结果中在同一类中的对象相似度较高,而不同聚类中的对象相似度较小,其基本思想是在数据空间中任意选择K个数据对象作为初始聚类中心,根据其余数据与对应聚类中心的相似度进行聚类划分,然后再计算新的聚类中心,不断重复执行这一聚类过程,即可得到最终类别划分结果。聚类结果实际上是寻找数据集的划分过程,各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。

3 云计算虚拟机智能调度模型

云计算数据中心有m个物理节点,有n个虚拟机发送调度请求,每个物理节点的资源向量分为已使用的资源向量和空闲的资源向量,物量节点上的资源是多维的,包括CPU、内存、带宽和I/O等,每个物理节点已使用的资源等于分配到该节点的虚拟机资源之和[11,12]。设虚拟机集合为,物理节点集合为,虚拟机调度的目的是利用最少的物理节点获得最大的资源利用率,并且保证物理节点分配的资源利用率不超过其资源的最大容量,其可以建立如下的目标和约束条件:

(1)目标函数:

式中:ui表示第i个物理节点是否使用;ui,j表示物理节点在第j维度的利用率;qi,k表示虚拟机对资源k的需求量。

4 基于K⁃means和蝙蝠算法的虚拟机调度方法

4.1 调度思想

本文提出的虚拟机调度方法的基本思想是将每个虚拟机分配到距离最近的物理节点上,通过多次迭代,每个虚拟机都与所在的物理节点最近。在本文中虚拟机与物理节点的距离用资源相关系数表示,相关系数越小,说明虚拟机所需资源与物理节点拥有的资源之间具有更多的互补,在空闲资源满足条件的情况下,将其分配到相关系数小的物理节点,有利于更充分地利用资源。虚拟资源与物理节点之间的相关性采用皮尔逊相关系数表示,取值范围为[-1,1]:

将虚拟机与物理节点的距离定义为:

则虚拟机与物理节点的距离取值范围为[0,1]。本文将虚拟机到不活跃物理节点的距离定义为最大,将其取为1,表示只有当虚拟机无法放置时才分配到新物理节点。

4.2 蝙蝠编码规则

蝙蝠算法采用实数据编码,一个编码对应一个可行解。本文采用m个物理节点为初始聚类中心,这样聚类对应的物理节点限定了聚类的大小,简化了对资源的考虑,并且确定的聚类减少了迁移的次数,使资源的分配更加稳定。

每个蝙蝠由m个聚类中心构成。设当前虚拟机分为m类,每个数据为d维特征,用于实数进行编码,以K均值聚类中心作为寻优变量,每个可行解是由m个聚类中心构成,由于解的维数是d维,这里可行解的位置是m×d维向量,可行解的编码示例,其结构如下:

其中Zm1,Zm2,…,Zmd代表第m类的d维聚类中心。

4.3 虚拟机调度步骤

(1)蝙蝠初始化:给定含有n个虚拟机对象的数据集T和物理节点数m,基于蝙蝠算法的K⁃means聚类方法,将每类的聚类中心作为蝙蝠的位置编码,反复进行多次,生成N个初始蝙蝠。以上聚类中心方法执行多次,生成含有n个蝙蝠的初始化种群XI(I=1,2,…,n),其目标函数为f(X),X=(x1,x2,…,xd)T。

(2)初始化蝙蝠种群的速度、脉冲频率、脉冲响度和脉冲发射速率。

(3)根据适应度公式计算每个蝙蝠的适应度值,保留最优解,并利用速度和位置公式对其他蝙蝠进行更新。

(4)产生一个随机数rand1,if(rand1>ri),则对当前群体中最佳蝙蝠位置进行随机扰动得到替换当前蝙蝠的位置。

(5)通过随意飞行产生新解,产生随机数rand2,if(rand2<A and f(xi)<f(x*),则接受这个新解,利用音量Ai和脉冲发生率ri公式减少音量,增大脉冲发生率。

(6)利用K⁃means方法对蝙蝠位置进行优化,按照最近邻近法原则确定对应的聚类划分,并重新计算聚类中心,更新蝙蝠的适应度,根据适应度函数排列蝙蝠,找到当前最佳位置,如果达到结束条件(满足条件的位置或最大迭代次数)则聚类完成,转到步骤(7),否则转到步骤(3)。

(7)输出最优的蝙蝠位置对应的数据聚类结果。

5 仿真实验

采用Cloud Sim 3.0云平台软件对本文提出的调度方法进行模拟仿真,Cloud Sim是澳大利亚墨尔本大学的网格实验室和Gridbus项目宣布推出的云计算仿真软件。本仿真实验将虚拟机分别设置为100,200,300,400,500,每个实例取10次运算的平均值,将所需物理节点数量和系统资源综合利用率两方面与K⁃means调度方法进行比较。

(1)物理节点数据对比

物理节点使用数量的对比情况见图1,可以看出,本文调度方法的物量节点的数量比K⁃means调度方法平均降低12%左右,有效地减少了资金投入,物理机节点的能耗也降低,使数据中心具有高密度、低成本的优点。主要原因是本文调度方法通过聚类方法将虚拟机分配到服务器中,并且将虚拟机到不活跃物理节点的距离设置为最大,表示只有当虚拟机无法放置时才分配到新的物理节点,这样有效地提高了数据中心物理节点的分配密度,降低了物理节点的节点数量。

(2)系统资源综合利用率比较

系统资源综合利用率对比见图2,可以看出本文调度方法系统资源综合利用率比K⁃means调度方法平均提高了11%左右,有效地提高了资源的综合利用率。主要是因为本文调度方法在调度时考虑了虚拟机与服务器资源的互补性,有效地防止了一种资源过于饱和导致其他资源不能使用的情况,通过资源互补分配虚拟机有效地提高了资源的综合利用率。

6 结语

在开放的云计算环境下,合理的虚拟机调度策略有利于提高资源的综合利用率,并有效地降低能耗。本文提出了一种云计算环境中使用的虚拟机智能调度方法,考虑了虚拟机与服务器资源的互补性,降低了云服务提供者的运营成本,仿真实验表明该方法在节省物理节点和提高综合资源利用率方面都取得了较好的效果,是一种可行的方法。

摘要：针对云计算虚拟机调度中存在的资源分配不均衡问题,提出了一种基于K-means和蝙蝠算法的云计算虚拟机智能调度方法。该方法充分考虑物理节点空闲资源和虚拟机所需资源的互补性,以物理节点作为初始聚类中心,使用资源的相关性定义二者的距离,利用蝙蝠算法的全局寻优能力迭代寻优,达到合理调度虚拟机的目的。模拟实验仿真的结果表明,该方法在降低物理节点数量和提高资源利用率方面具有一定的优势,是一种可行的方法。

关键词：K-means,蝙蝠算法,云计算,虚拟机,调度

参考文献

[1]庄威,桂小林,林建材,等.云环境下基于多属性层次分析的虚拟机部署与调度策略[J].西安交通大学学报,2013,47(2):28-32.

[2]袁爱平,万灿军.云环境下基于改进遗传算法的虚拟机调度策略[J].计算机应用,2014,34(2):357-359.

[3]暴锡文.一种云计算环境下基于Xen的虚拟机调度机制[J].计算机测量与控制,2014,22(10):3381-3384.

[4]肖鹏,刘洞波,屈喜龙.云计算中基于能耗比例模型的虚拟机调度算法[J].电子学报,2015,43(2):305-310.

[5]殷小龙,李君,万明祥.云环境下基于改进NSGAII的虚拟机调度算法[J].计算机技术与发展,2014,24(8):71-75.

[6]李煜,马良.新型全局优化蝙蝠算法[J].计算机科学,2013,40(9):225-228.

[7]金伟健,王春枝.基于蝙蝠算法的云计算资源分配研究[J].计算机应用研究,2015,32(4):1184-1187.

[8]全雪姣,孟凡荣,王志晓.对K-mean初始聚类中心的优化[J].计算机工程与设计,2011(8):165-167.

[9]吴夙慧,成颖,郑彦宁,等.K-means算法研究综述[J].现代图书情报技术,2011,31(5):30-35.

[10]宋旭东,朱文辉,邱占芝.大数据K-Means聚类挖掘优化算法[J].大连交通大学学报,2015,36(3):91-94.

[11]李乔,郑啸.云计算研究现状综述[J].计算机科学,2011,38(4):32-37.

智能调度算法 篇6

网格计算技术是一种先进的资源共享模型,是连接网格低层和高层功能的桥梁,是协调整个网格系统有效运转的核心,而资源调度技术是网格主要服务之一。这里的资源除了包括数据资源外,还包括多样的网络资源如计算资源、存储资源、信息资源等。网格计算的主要目标是解决资源分布和资源利用率的不平衡问题。资源调度技术对网格系统的应用是至关重要的,它能有效降低网格计算的总执行时间和总耗费量,从而使网格达到最大的性能。目前网格环境下的资源调度主要在改进调度算法上。

在以往的研究中,产生了许多调度算法,如OLB算法、MCT算法、Min-min算法、Max-min算法、SA算法、UDA算法、Tabu算法、A*算法等。根据以往的实验数据表明,OLB、UDA、Max-min和Tabu算法通常情况下调度性能不是很好。Min-min和A*算法显示了较好的搜索性能,而在跨度差异上却非常大,且A*算法的搜索性能不稳定,时好时坏。

2. 问题描述

遗传算法在解决网格计算中的任务调度的时候,使用的是一种静态任务算法。本文讨论的是网络中客户子任务的数量远远大于网络中服务资源的数量时的模拟任务调度策略,如果服务子任务的数量小于资源总数量的时候,按照当前网络的实际服务状态实时分配优先级高的或速度快的节点来完成当前任务即可。首先假设:

(1)任务处理采用批处理模式,任务在资源上的消耗时间是随机产生的,且所有元任务之间相互独立;

(2)已将一大型任务分解成很多分布及执行均匀的很多子任务,并且子任务之间的数据依赖关系为已知;

(3)每个子任务在标准资源上运行所需要的时间已知,且资源每一资源的处理速度相对的计算速度的比例关系已知;

(4)所有资源为单处理器处理。

3. 设计与实现

3.1 遗传算法简介

美国密西根大学教授Jhon.H.Hollnad为遗传算法创始人,Hollnad认为,可用一组二进制串来模拟一组计算机程序,并且定义了一个衡量每个“程序”的正确性的度量:适应度。Holland模拟自然选择机制对这组“程序”进行“进化”,直到最终得到一个正确的“程序”。Hollnad认为,所有的适应问题都可以表示为“遗传”问题,并用“进化”方法来解决。遗传算法将“适者生存的进化理论引入串结构,在串之间进行有组织但又随机的交换彼此的信息。通过遗传操作,使优良品质被保留下来、组合,从而不断产生出更佳的个体。子代个体中包含父代个体的大量信息,并在总体上优于父代个体,从而使种群向进化发展,即不断接近最优解。

遗传算法类似于自然进化,通过作用于染色体上的基因寻找好的染色体来求解问题。遗传算法对求解问题的本身一无所知,它所需要的仅仅是对算法所产生的每个染色体进行评价,并基于适应值来选择染色体,使适应性好的染色体有更多的繁殖机会。在遗传算法中,通过随机方式产生若干个所求解问题的数字编码,即染色体,形成初始种类;通过适应度函数给每个个体一个数值评价,淘汰低适应度的个体,选择高适应度的个体参加遗传操作。

3.2 编码方案和初始化

该问题可以用数学方法来描述:任务集T={T1,T2,……Tn};Ti为第i个任务。资源集R={R1,R2,……Rn};Ri为第i个资源。Mi为完成第i个任务所需要的时间。Rri为第i个资源与执行单位资源所需要时间的比率。

在举例中假设子任务分别为T1~T7;资源分别为R1,R2,R3;资源完成时间与执行所需要的单位时间比率Rr1,Rr2,Rr3;完成标准资源所需要的时间M1~M7分。可以用一个DAG图来表示这个问题,以图1为例。

由DAG图,可得一种编码方案T3T1T4T5T6T7T2。按照这样的顺序随机最先完成任务可以生成一个任务分配序列。假定分配资源的概率速度为:

其中Mp=(M1+M2+…Mn)/n;

根据这样的概率对三层的子任务进行资源调度的分配。任务在计算资源上的调度顺序也需要随机分配,并将所有层次的资源连在一起,产生一个染色体,该初始种群生成算法受到高度分层排序约束,使每个资源上的任务调度按高度升序排列,其目的是保证调度过程中任务先后关系的一致,避免因遗传操作破坏任务的先后关系而产生无效的染色体,这相对于遗传操作后再检查有效性的算法,提高了运行效率。

3.3 适应度函数

根据以上的编码方案,我们可以得到每一个资源上运行的子任务的集合,种群建立以后,计算每一个染色体的适合度。查找最优解实际上是一个寻求最大值的过程,对于一个最大值问题来讲,第i个成员的适合度fi通常是目标函数在这个成员处(或参数空间中的点)的估计值。适合度值可以用复杂的分析公式、仿真模型来确定,或者根据对实验或日常问题设定的观察来确定。恰当的确定适合度值可以使遗传算法正确地工作。在一次遗传算法的运算过程中,某一个资源完成所有分配给它的子任务所需要的时间即为本资源在此次运算过程中所需要的时间。而本次计算中所需运行的时间最久的资源的运行时间则为完成本次计算所需要的时间,我们取其倒数为适应度,因此时间越长适应度越低。则适应度公式为:

计算每个资源在本次计算中所需要的运行时间,我们只需要计算染色体中资源编码为S的任务的Mj的合计,然后除以S相对于标准资源的运算速度即可。

3.4 交叉与变异

交叉的目的是为了在下一代产生新的个体,通过交叉操作,遗传算法的搜索能力能够得以飞跃地提高。选出种群中适应度最大的染色体作为父染色体将父染色体跟剩下的每一个染色体以一定的概率(10%)进行交叉,交叉的时候随机寻找染色体的一个基因点,将这个基因点作为交叉点,将父染色体于此染色体在这个基因点以及后面的两个基因点互相交换完成一次交叉。交叉的概率选择为1。然后将普通染色体之间亦进行交叉。

好的性状的染色体更有几率产生优良的后代,由于本算法是强父代染色体的遗传,因此重要的种群多样性能量来源于种群的变异,因此不同于传统的变异算子,本算法的变异算子将选择比较大的概率。描述如下:在交叉运算完以后,按照变异概率PM=0.1的几率进行变异,变异的方法就是,随机寻找染色体的一个基因点,在此基因点上按照资源的平均概率重新分配此任务的资源。变异算子的主要作用是拓展搜索空间,在种群局部收敛的时候,通过变异算子的突变作用,来保持种群的多样性。

3.5 算法流程

(1)随机产生T个任务,R个资源,按照任务的层次生成任务链。

(2)按底层优先完成原则初始化种群,并将种群分成若干个子种群,每一个种群选出使用度最大的作为父染色体。

(3)对每一个种群进行强父交叉及变异。

(4)判断是否产生适应度大于父染色体的后代,若是则产生新的父染色体,并去除无效的以及适应度低的染色体,并返回(3)。否则再次判断是否有超过50代没有代替父染色体,若否则返回(3)。

(5)若不超过50代则判断是否为最后一种群,若否则与父染色体适应度最大的种群合并,并返回(3)。

(6)若是最后一个种群,则输出最佳适应度的染色体。

4. 仿真结果与分析

本实验是对传统遗传算法深入研究,并在改进的基础上进行的,任务的长度范围、资源的执行能力范围等是模仿gridsim计算得到的,数据跟现实的情况比较相似。该算法一共产生5个种群,每一个种群产生20条染色体(当子任务的数量很多的时候产生具体的种群数量以及染色体数量可以适当变化)。在每一个种群中,找出适应度最大的染色体作为父染色体,与剩下的19条染色体作一定的几率(譬如100/0)进行交叉、变异繁殖,完成父染色体交叉以后,剩下的染色体随机地进行两两交叉变异,在生成的种群中,如果在新的子代中有适应度更大的后代,则新的子代作为父染色体,去除适应度低于平均数的子代,继续进行下一代繁殖。如果在新的子代中没有适应度大于父染色体的,则去除适应度低于平均数的子代,继续下一代。如果连续繁殖一定的代数(例如50代)仍然没有出现新的代替父染色体的子代,则将同剩下的4个父染色体中适应度最大的种群进行合并,组成新的种群。直到最后所有种群合并成一个种群,再经过一定代数的遗传变异,找出最优解。由于强父代染色体的单个种群的收敛速度非常快,因此初始种群必须有一定的数量,才能满足种群的多样化。

从实验数据可以看出,每一个种群在单个遗传中,基本上在25到50代左右,每一个资源经过2000次的交叉变异运算后基本上每一个种群趋于收敛于局部的最优点,而个别的种群还会在继续的遗传变异中有进一步的提高。在经过200代6万多次的遗传变异运算后,只能收敛在0.25左右。并且在随机的10次每次遗传200代实验中,没有一次适应度能够达0.6。在种群合并以后整个种群还会有较好的表现,经过80代的遗传变异,使最终的结果收敛在0.5,有时候甚至能够收敛在0.6,整个运算交叉变异的次数是20000次左右。而传统的遗传变异算法表现不稳定,可以看出,本文所提出的遗传变异方法的适应度要高于传统的适应度。

5. 结语

本文在借鉴前人的基础上,改进了传统遗传算法,提高了多种群遗传算法的运算效率。通过仿真实验可以看出,这种算法不但能够提高遗传算法在网格计算的任务调度中的收敛速度,而且在相同的遗传变异次数时,可以得到比传统遗传算法更高效的调度方法,是一种有效的网格任务调度算法。

摘要：提出了一种基于改进遗传算法的任务调度策略算法,该算法并将子任务按照层次深度排序,兼顾网格资源的运算能力。通过DAG图获取层次关系,解决种群中的非法染色体问题。在种群进化的时候采用多种群、强父代染色体进化重组的方案。通过仿真实验表明,该算法具有一定的全局搜索能力和局部搜索能力,通过仿真对比可以表明该算法在搜索能力和搜索速度上优于普通的遗传算法。

关键词：网格计算,任务调度,遗传算法

参考文献

[1]Foster I,Carl Kesselman.网格计算[M].金海,袁平鹏,石柯译.北京:电子工业出版社,2005.

[2]Foster Ian,Kesselman Car1.The grid:Blueprint for a future com-puting.

[3]都志辉,陈渝,刘鹏等.网格计算[M].北京:清华大学出版社,2002.

智能调度算法 篇7

在中国北方严寒地区的冬季寒冷天气中, 当飞机在机场过夜停留时, 飞机蒙皮表面会因为雨雪霜的影响而形成表面冰层。由于飞机表面冰层的影响, 飞机在飞行过程中升力损失较大, 因此飞机需要在起飞前进行除冰操作。目前一般采用分散式除冰方法, 即除冰车辆到飞机停放地对飞机表面除冰, 但是该方法缺乏统筹规划, 随机性强, 效率较低。

遗传算法来自于对生物在自然环境中的进化和遗传等现象的算法模拟, 该算法采用以概率搜索基础, 在种群初始化的基础上, 采用选择、交叉、变异等操作促进种群进化, 从而找到问题的最优解。遗传算法具有并行性、非线性的特点, 比较适用于飞机除冰调度算法[1,2]。

2 除冰数学模型

飞机除冰优化调度是指在一定时间内完成飞机除冰操作, 并且满足某项指标最优。除冰优化调度算法根据飞机机型和除冰车所载冰液的不同为每辆除冰车分配合理的除冰顺序和除冰目标, 从而使所有的除冰车在一定的时间范围内完成所有飞机的除冰操作。在除冰过程中, 除冰车辆按照调度的安排排列在除冰车道两旁, 飞机依次从进入除冰区域, 排完冰后再从两侧滑出, 飞机除冰作业过程如图1所示。

在飞机除冰调度中, 除冰时间包括除冰车辆工作时间和除冰过程中添加除冰液的时间和添加冰液时间。设有m辆除冰车, 每辆除冰车载运量为qk, 除冰车为n架飞机执行除冰任务, M为每辆除冰车添加除冰液的时间, 飞机i需要除冰液Fi, 每辆除冰车辆的除冰喷洒速度为v, xik表示除冰车k为飞机i服务, 为1表示为é飞机i服务。则每架机喷洒除冰液的速度为, 第i架飞机除冰需要的时间为, 第k辆除冰车添加冰液的时间为, 在除冰过程中添加除冰液的时间和为, 则飞机除冰调度数学模型如式1所示[3,4]。

3 基于遗传算法的除冰模型

3.1 染色体结构设计

采用布尔矩阵对染色体进行编码, 从而使一条染色体代表一种可能的除冰车辆优化调度方案, 如下所示。

该染色体中行表示飞机, 行数表示飞机数目, 列表示车辆, 列数表示车辆数目, 为1表示除冰车为飞机进行除冰操作。如第一行就表示1号车辆, 2号车辆分别为飞机1除冰。

3.2 适应度函数

根据飞机除冰优化调度模型, 构建适应度函数如式2所示:

其中, b为常数, T'为最有染色体适应度值, Tk为第k条染色体的目标值, 计算公式如式1所示。

3.3 遗传操作

3.3.1 选择算子

选择操作采用轮盘赌法模型, 即染色体适应度值越大, 个体被选中的概率越高, 并且在轮盘赌选择法基础上采用最佳个体保存选择策略。

3.3.2 交叉算子

因为染色体由多行数字构成, 因此交叉时采用同行交叉法, 随机选择染色体行数和交叉位置进行染色体交叉, 如选择A, B两染色体第一行从第二个点开始交叉的过程如图2所示。

3.3.3 变异算子

变异算子采用随机选择个体染色体, 然后在该染色体同一行上选择一个1和一个0互换, 得到新的染色体, 变异操作如图3所示。

4 仿真结果

在MATLAB中仿真验证飞机除冰调度算法的有效性, 假设有10辆除冰车辆在有4个除冰位置的除冰场为20架飞机除冰, 每架飞机的除冰液需求量和除冰车除冰液载运量如表1所示。

遗传算法的参数为:种群规模为10, 迭代次数为100, 交叉概率为0.9, 变异概率为0.3, 采用MATLAB遗传算法工具箱进行优化, 遗传算法优化过程如图4所示。

通过算法得到的最优染色体对应的除冰车除冰顺序如下所示。

5 小结

本文研究了基于遗传算法的飞机除冰调度算法, 针对现有飞机除冰调度存在缺乏统筹规划, 随机性强, 除冰效率较低的问题。采用遗传算法对飞机除冰调度进行统筹规划, 仿真结果显示, 该算法能够寻找到显著提高飞机除冰效率的调度方法, 从而为飞机除冰调度提供了一个新思路。

摘要：飞机除冰作业是飞机经常性的冬日维护工作, 一般采用分散除冰的方式除冰, 除冰过程存在时间长、效率低等问题。针对此问题, 该文研究了基于遗传算法的飞机除冰调度算法, 通过染色体结构设计、种群初始化方法、适应度函数设计和遗传寻优, 完成除冰车辆调度。算法仿真结果显示, 遗传算法在飞机除冰操作中具有较好的性能。

关键词：遗传算法,飞机除冰调度

参考文献

[1]丁书斌.基于混合遗传算法的车问作业调度方法研究与应用[D].大连:大连理工大学, 2006.

[2]刘晓霞, 谢里阳, 陶泽, 等.柔性作业车间多目标调度优化研究[J].东北大学学报, 2008, 29 (3) :362-365, 382.

[3]石旭东, 刘胜飞.飞机集中除冰车辆调度方法研究[J].计算机工程与应用, 2009, 45 (4) .

车辆优化调度算法研究初探 篇8

国外将物流配送车辆优化调度问题称之为Vehicle Routing Problem[1]和Vehicle Scheduling Problem。物流配送车辆优化调度问题最早是由Dantzig和Ramser[2]于1959年首次提出的, 自此, 很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学和计算机应用等学科的专家与运输计划制定者和管理者的极大重视, 成为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研究及实验分析, 取得了很大进展。但是, 对随机车辆调度问题的研究还不是很多;而且, 在实际中, 车辆调度问题包含许多随机的因素, 因此, 研究随机车辆优化调度问题具有广泛的应用背景和经济价值。

2 车辆路径规划问题求解算法概述

由于VRP包含了旅行商问题 (Traveling Salesman Problem, TSP) , 而TSP本身就是NP难题, 所以VRP也是一个NP组合优化难题。自该问题被提出之日起, 国内外学者力求构造高效的算法来解决这一难题, 这些求解算法大体可分为两类, 一类为精确算法 (exact algorithm) , 另一类为近似算法 (approximation algorithm) , 其中的近似算法又可以大致分为三类:构造启发式 (constructive heuristics) 算法, 改进启发式 (improving heuristics) 算法, 亚启发式 (meta-heuristics) 算法。下文就这四类算法近些年的研究成果做简要评述。

2.1 精确算法

基于VRP的传统数学模型的精确型求解算法代表性的研究成果主要有:Fisher提出的K-树法、Padberg等提出的分枝剪枝法、Kohl和Madsen用拉格朗日松弛算法求解带有时间窗的VRP、Fumero等的修正拉格朗日松弛及子梯度优化方法、Lorena Luiz等对列生成方法的改进等。精确算法主要适用于解决问题结构比较清晰、所含各元素之间的关系明确、边界清楚的良性结构问题。另外, 还有许多实际的VRP不具有良性结构, 并且有些问题不存在严格最优解 (例如, 目标之间相互矛盾的多目标决策问题) , 或者有些问题要得到最优解需花费过大的代价, 当采用精确算法求解这种类型的问题时难以得到理想的效果, 它们的解决就需依赖于近似算法。

2.2 构造启发式算法

构造启发式算法[3]是将尚未指定路线的客户按照某些标准插入到现有的已部分形成的路线中去, 以最终形成解。该算法是求解VRP问题最早使用的近似算法。Clarke和Wright提出的C-W节约算法, Gillett和Miller提出的扫描算法, 以及Solomon提出的最近邻启发式算法都是构造启发式算法中最为经典的算法。其后虽有很多学者将这些经典算法加以改进, 但这些改进大都以缩短计算时间和减少内存的占用为目标, 对于当代如此发达的计算机而言, 这些改进都是微不足道的。虽然构造启发式算法简单易懂, 但有时找到的解离最优解差的较远, 因此该算法现已不单独用来求解VRP问题, 而是与改进算法相结合, 用在构造初始解阶段。

2.3 改进启发式算法

改进启发式算法[4]可以将构造启发式算法得到的比较差的解, 通过邻域的搜索反复改进, 得到较好的解。改进启发式算法大概可以分为路线内部改进和路线间改进两种, 路线内部改进是将某条路线内部的某些边和结点互换位置, 而路线间改进是在相邻路线之间交换一些边和结点来改进当前的解。具有代表性的求解VRP的改进启发式算法有k-opt以及λ-interchange算法。Opt算法来自于Lin提出一种旅行商问题 (Traveling Salesman Problem, TSP) 的路径优化思想, 其思想是对给定的初始回路, 通过每次交换k条边来改进当前解。该算法在求解VRP问题时, k条边可以是路线内部的, 也可以是路线之间的。λ-interchange算法由Osman发起, 它的思想是在几条线路之间相互交换一些客户来改进路线。该算法在后续的研究中也被应用解决多类VRP问题, 如有时间窗的VRP。该类算法的优点是得到最优解的概率较高, 缺点是随着k和λ值的增大, 运算时间会成倍增长, 不利于实时系统的处理。

2.4 亚启发式算法

构造启发式算法和改进启发式算法都不允许劣质中间解的产生, 而只允许解的优化结果朝好的方向单向递增, 因此这两种算法都较容易陷入局部最优, 为了克服这一缺点, 多种亚启发式算法相继出现。亚启发式算法在优化问题的过程中允许劣质的中间解出现, 能够跳出局部最优而在全局内寻优。用于求解VRP问题的亚启发式算法有遗传算法、模拟退火算法、蚁群算法等。

遗传算法[5]通过多个个体间的选择、交叉等的遗传操作, 相互协力地进行解的探索, 与以前的算法中对单纯的并列的解的探索相比, 容易发现更好的解。遗传算法运用到VRP上, 对于解诸如带有时间窗的VRP, 先分组后安排路径的路径规划问题等等一些具有多目标的路径规划问题, 取得了很好的效果。然而在运用该方法的过程中, 问题的遗传因子型的表现依赖于设计者的能力。并且该算法所得结果的好坏, 主要依赖于遗传代数和解组规模, 在实际应用中只能根据具体要求, 在合理的时间内对问题进行求解, 若所得解不能令人满意, 就要增大解组规模或遗传代数, 从而有希望得到问题的全局最优解, 当然, 这是以延长计算时间为代价的。

模拟退火算法 (simulated annealing algorithm) [6]是由irkpatrick等提出的一种求解组合最优化问题的算法。该方法适用的领域较多, 具有较强的实用性, 并可人为地控制迭代次数, 反复求解。然而该方法所得解的好坏与初始状态、温度函数等都有一定的联系, 降温较快的效果不一定很好, 效果好的, 其降温过程又极其缓慢。该法创立之初对于解决单目标路径规划问题可以得到非常满意的解, 虽然后经过一些学者如Ulungu和Teghem (1994) 的研究改进, 可以解决多目标问题, 但是就其运算过程和得到的解来说不如遗传算法的效果好。

蚁群算法是近十几年来新兴起的一种摹仿蚂蚁觅食行为的算法。可以查到的最早将该算法应用到路径规划问题上的文献的年代始于1995年。此后, Gambardella和Dorigo, Stutzle和Hoos, 以及Mazzeo和Loiseau都有将该算法应用到路径规划问题中并获得成功。蚁群算法具有群体合作、正反馈选择、并行计算等三大特点, 并且可以根据需要为人工蚁加入前瞻、回溯等自然蚁所没有的特点。因此, 该算法具有很强的发现较好解的能力。但是这种算法也存在一些缺陷, 如搜索时间较长, 容易出现停滞现象 (stagnation behavior) , 即搜索进行到一定程度后, 所有个体所发现的解完全一致, 不能对解空间进一步进行搜索, 不利于发现更好的解。现在对该算法的研究大多数都集中在对这些缺陷进行改进上。

结束语

综合上文分析可以发现, 每一种算法单独工作都会存在一些比较大的缺陷, 而且随着社会的发展, 问题规模不断扩大化, 结构不断复杂化, 单一的算法很难解决现实中复杂化的问题。如果将几类算法融合贯通, 取长补短, 就可以克服很多缺点, 构造出比较好的算法。近十几年对算法的研究开始侧重于融合多种算法, 构造混合算法上。回顾了国内外求解该问题的现有算法并总结了它们的优缺点, 为下一步的研究提供指导, 并期能为在该领域内从事研究工作的学者提供借鉴。

摘要：分四大类讨论求解该问题的算法:精确算法 (exact algorithm) , 构造启发式算法 (constructive heuristic algorithm) , 改进启发式算法 (im-proving heuristic algorithm) , 和亚启发式算法 (meta-heuristic algorithm) , 评述各类算法适用的问题求解阶段以及各自的优缺点。

关键词：车辆路径规划问题 (Vehicle Routing Problem, VRP) ,算法,优化调度

参考文献

[1]vehicle routing problem[J].Computers&Oper-ations Research, 1999, 26 (12) :1153～1173.

[2]Dantzig G, Ramser J.The truck dispatching problem[J].Management science, 1959, (6) :80～91.

[3]李军.有时间窗的车辆路线安排问题的启发式算法[J].系统工程, 1996, 14 (5) :45～50.

[4]林晓宇, 李金铭, 纪寿文.车辆路径问题Clarke-Wright算法的改进与实现[J].交通与计算机, 2004, 6 (22) :72～75.

[5]李军, 谢秉磊, 郭耀煌.非满载车辆调度问题的遗传算法[J].系统工程理论方法应用, 2000, 9 (3) :235～239.