资源描述：
《混合启发式算法在汽车调度中的运用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、车站车辆路径问题是直接关系到客运汽车公司的效率与效益、服务质量和企业形象的关键问题，一直是运筹学、管理学、计算机科学等领域的研究热点问题，在生活中有着广泛的应用价值，对该类问题的研究主要集中在能否找到在较短的时间内给出较优解的算法oDethloff提出了带有参数的插入法，Crispim提出了基于禁忌的混合启发算法，但求解质量还有较人的改进空间。蚁群算法蚁群算法(antcolonyoptimization,ACO),又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为
2、。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制骼参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。1车辆路径的描述本研究利用有向带权图G描述车辆调度路径问题。假设G=(V,A,C),其中,V={i
3、i=0,1,…，n}是顶点集；A={(i,j)i,jWV}是连接各顶点的弧集;C={cij
4、(i,j)WA}是权重矩阵，cij表示从站点i到站点j的距离。任意站点i(i=l,2,…，n)都有一定的上车di与下车需求pi。满足以下条件并使得总行程长度最
5、短：(1)每辆车都从仓库出发，并最终返回仓库。(2)每个客户都只被1辆车服务，且仅被服务1次。(3)任1车辆在行程过程中，载重始终不能超过Q。设s={ri
6、i={l,2,•••,k}}是问题的一个解,其中，ri对应1条车辆路径。由上面问题描述要求可以知道，s作为问题的1个可行解的重要条件是：对任意ri都满足以下条件：(1)ri上所有站点的总上车需求D(x)不超过Q。(2)ri上所有站点的总下车需求P(x)不超过Q。(3)车辆承载门上的任何客户之后人员都不超过Q。若都满足条件(1)、(2)、(3),则称s满足强可行条件，是强可行解；若都满足条件(1)、(2),LS,其他从V,
7、中选择站点人•并将它插入到当前路径厂上的节点i与j之间。这里」i是指满足以下条件的站点节点斤的集合M尚未被访问•假若&加入厂仍能保证厂满足弱可行性条件。呱的定义：o>A=max{
8、丁1]°1%鬥・它决定了站(片)up点人•被选中的可能性的大小。其中"和j是当前路径r上的2个相邻的节点；T^=(Tjj4-TA?)/2t^,Tjj和Tkj是插入2后新增的2条瓠仏耐和(*J)上的值①是删去的瓠(ij)上的值；帶是启发式信息.存-(g+s+Cj),其中，第一项考虑了站点与调度中心之间的距离•以避免距离仓库较远的站点插入较晚.从而增加额外的代价。第二项表示将站点斤插入到当前路径上站点
9、匚与站点j之间时作
10、增加的路径长度；是丁祇和如的相对彫响因子。不满足条件(3),则称s满足弱可行性条件，是弱可行解。由Mosheiov[7]己经证明，如果D(x)和P(x)都不超过车辆容量限制,则ri一定可以通过某种方式转化成可行路径。2混合启发式算法ACS_VND2.1初始化信息素首先使用最近邻启发式构造一个强可行解sO,并且根据t0=l/n•f(sO)设定信息素的初值，其中n是站点数量。则最近邻启发式算法构造解的步骤如下：(1)从尚未访问的节点中选择距离调度中心最小的站点，开始一条新的车辆路径r。(2)若V0不为空，则从中选择距离r上最后1个站点最近的站点，作为下一个访
11、问的节点；否则，转步骤(1),直到所有站点都已经被访问。这里，将V0定义为尚未被访问，且加入r后，使得r仍能约束强可行性条件的所有站点节点的集合。2.2构建可行解由于弱可行性条件检查比较简单，因此在算法ACS_VND的构建阶段，首先产生一组弱可行解，然后转化成强可行解。在ACS_VND中应使用一种基于插入的启发式方法构造弱可行解。首先，从调度中心0出发，随机选择1个站点，开始1条新的路径"然后，根据如下伪随机比例规则：argniaxjcdfc},q三q。从\中选择站点&并将它插入到当前路径/•上的节点i与j之间。这里是指满足以下条件的站点节点2的集合必尚未被访问•假若*加
12、入/•仍能保证/•满足弱可行性条件。5的定义:叫=max{
13、丁'承］“
14、耳承］°}•它决定了站(U)uT点&被选中的可能性的大小。其中"和j是当前路径厂上的2个相邻的节点；7^=(7*4-Tkj)/2T^TA和Tkj是插入*后新增的2条弧(i,k)和(kJ)上的值是ffli去的弧(iJ)上的值；彼是启发式(4息、丽二,其中.第一项考虑了站点与调度中心之间的距离•以避免距离仓库较远的站点插入较晚•从而增加额外的代价。第二项表示将站点2插入到当前路径上站点i与站点j之间时增加的路径长度；a、Q是心和耳承的相对影响因子。
