资源描述：
《混合启发式算法在汽车调度中的运用.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
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=
5、l,2,n）都有一定的上车di与下车需求pio满足以下条件并使得总行程长度最短：（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）车辆承载ri上的任何客户之后人员都不超过Q。
7、若以“都满足条件（1）、（2）、（3）,则称s满足强可行条件，是强可行解；若都满足条件（1）、（2）,从陷中选择站点&并将它插入到当前路径「上的节点i与j之间。这里是指满足以下条件的站点节点&的集合M尚未被访问•假若&加入厂仍能保证「满足弱可行性条件na)h的定义：04=max{
8、丁1鬥7?卩鬥・它决定了站(ij)UF点&被选中的可能性的大小。其中"和j是当前路径厂上的2个相邻的节点；丁貝=(丁*+巧)/2右,丁》和巧是插入&后新增的2条瓠仏灯和(AJ)上的值E是删去的弧(心)上的值：7}补是启发式fd息.巧*=Cqi-(C"+S+C
9、»),其中，第一项考虑了站点与调度中心之间的距离•以避免距离仓库较远的站点插入较晚■从而增加额外的代价。第二项表示将站点斤插入到当前路径上站点i与站点j之间时增加的路径长度；a、0是*貝和如的柑对影响因子。不满足条件(3),则称s满足弱可行性条件，是弱可行解。由Mosheiov[7]已经证明，如果D(x)和P(x)都不超过车辆容量限制,则ri一定可以通过某种方式转化成可行路径。2混合启发式算法ACS_VND2.1初始化信息素首先使用最近邻启发式构造一个强可行解sO,并且根据tO=l/n・f(sO)设定信息索的初值，其中n是站点数量。则
10、最近邻启发式算法构造解的步骤如下：(1)从尚未访问的节点中选择距离调度中心最小的站点，开始一条新的车辆路径G(2)若V0不为空，则从中选择距离r上最后1个站点最近的站点，作为下一个访问的节点；否则，转步骤(1),直到所有站点都已经被访问。这里，将V0定义为尚未被访问，且加入r后，使得r仍能约束强可行性条件的所有站点节点的集合。2.2构建可行解由于弱可行性条件检查比较简单，因此在算法ACS_VND的构建阶段，首先产生一组弱可行解，然后转化成强可行解。在ACS_VND中应使用一种基于插入的启发式方法构造弱可行解。首先，从调度中心0出发，随
11、机选择1个站点，开始1条新的路径口然后，根据如下伪随机比例规则：argmaxS.其他0,其他从16中选择站点人•并将它插入到当前路径厂上的节点i与丿•之间。这里•儿是指满足以下条件的站点节点*的集合M尚未被访问•假若R加入厂仍能保证厂满足弱可行性条件=叫的定义：^=max{
12、丁1$
13、7^鬥・它决定了站UJ）—点人•被选中的可能性的大小。其中"和/是当前路径r上的2个相邻的节点；丁尸仏+巧）/2右,丁*和岛是插入A后新增的2条瓠仏A）和仏J）上的值・右是删去的瓠（订）上的值；存是启发式信息・7J^=Ca-（CA+C^+Cj）,其中•第一
14、项考走了站点与调度中心之间的距离•以避免距离仓库较远的站点插入较晚•从而增加额外的代价。第二项表示将站点R插入到当前路径上站点i与站点j之问时增加的路径长度；a、0是丁卩和乃尹的相对影响因子。不断地从VI中选择站点，宜到
