附录C_英语翻译.docVIP

附录C 外文翻译 关于约束车辆路径安排的一种蚁群算法 摘要：运输车辆路线安排问题（VRP）是关于对服务于某个特定消费者集的一个车辆集作一个最佳路径集的选择决定。在这里，我们解决约束车辆路径问题即有一个最大的重量或者体积使得每个车辆都能负担的起。基于Colorni, Dorigo 和 Maniezzo发明的次经验演算法，我们为约束车辆路径安排问题（CVRP）开发了一种蚁群算法。我们得出初步的结果证明蚂蚁算法和其他次经验演算法一样能解决约束车辆路径安排问题。 关键词：约束车辆路径安排问题，蚁群，次经验演算法 ----------------------------------------------------------------------------------------------------------------------1绪论 运输车辆路径安排问题需要对服务于对服务于某个特定消费者集的一个车辆集作一个最佳路径集的选择决定。这个问题随着它在现实生活中出现的时候，可能有着几种附加约束的分类，例如运输车辆的容量限制，服务于顾客的时间窗口限制，一个司机可以工作的时间限制，可以选择路径的长度限制等等。这个问题首先是于1957年由Dantzig 和 Ramser提出的。由于对最优组合问题难度的内在兴趣，VRP应用已经得到许多得注意的经济重要性，和许多不仅精确而且富于启发性的算法已经被开发出来去解决普通问题以及真实世界案例，所以关于这个学科的文献非常广泛。看[8]可以知道一个关于VRP模型和算法的必威体育精装版回顾。那里面也有为真实世界问题提供各种好地解决办法的许多可行得商业包。在这里，我们解决约束车辆路径安排问题，也即一个运输车辆开始和结束他们路径的仓库，一个客户和他们需求的集合，一个每条路径能负载车辆的最大重量和体积的集合，以及各客户间，和客户和仓库之间的成本和距离。我们希望能定义运输车辆开始和结束的路径安排的仓库使得客户满意和成本最小化。但是在大多数运输车辆路线安排问题（VRP）困难中，最显著的是约束车辆路径安排问题（CVRP）中的NP问题。 2蚁群算法 蚁群算法的灵感来自于类似现实生活中一群蚂蚁寻找食物的行为。在它们的寻找过程中，它们通过留下一种叫做信息素的物质来标志它们经过的痕迹，一条路上的信息素的总量可以让其他蚂蚁知道这条路是否有前途。这种观察为Colorni, Dorigo 和 Maniezo提出次经验演算法提供了灵感：蚂蚁们就是为最优化问题的提供解决办法的程序员。关于如何在解决空间里面探测纪录的某些价值和蚂蚁们的信息素行为相类似，解决办法的目标价值和食物源相类似。关于这种算法的一个重要论点就是类似性：几种解决办法同时建立，它们在生产过程中互相交换信息以及反复使用以前的信息。 在每个基本蚁群算法的反复使用中，每个蚂蚁一步一步建立解决办法，在每一步这个蚂蚁都向前移动一步，以求能完成实际的由许多元素和一个扩充集Ak组成的部分解决方案，它有下列一个概率方程。任何一只蚂蚁k从目前的情形I向另外一种情形j向前移动的概率Pk(i, j)被计算进总量： 每一步的吸引系数η取决于这个问题的信息 每一步信息素的水平τ显示了刚走的那一步有多好 Tabuk 是禁止移动的列表 在这个蚁群算法中，最初的Pk(i, j)公式是： 其中α, β是用来建立η和τ相关影响的系数，经过t步反复完成，也即当所有的蚂蚁完成它们的解决办法，这个信息素水平就会被更新到 其中是各持续信息素水平的相关系数，表示的是所有蚂蚁在它们路径中选择移动(i,j)的奉献度。 成功的蚂蚁算法已经被应用于各种最优组合问题。 3CVRP的蚁群算法 这里我们列举关于CVRP的ACO算法的主要特征。我们尝试这个算法每个组成部分的各种不同选择： 建立路径：在ACO的每一步反复中，一个蚂蚁为CVRP建立一个解决办法，通过基于每一弧形和长度的信息素总量的转换规则[参照下面的（2）]而移向下一个顾客（普通的ACO方案情形）。在前面片断所提到的禁止列表要扮演的角色是一个已经被访问的集合，禁止蚂蚁的当前互换。在路径特定的情况下我们执行命令的两次转换： 连续的：每一只蚂蚁开始它们的解决方案于第一辆运输车辆选择的路径直到所有的容量空间都完成。然后它与其他运输车辆连续直到完成所有的路径。每一只蚂蚁开始它们的路径都是来自于不同的客户。 平行的：每一只蚂蚁同时为所有的运输车辆决定它们的路径。根据转换规则，在算法的每一次交换中只有一个客户被选择。然后最好的漫游被延伸。 （2）转换规则： 随机均衡规则：根据在第二部分所描述的，计算出来的概率Pk(i, j)随机选择一个相邻客户。 伪随机均衡规则：在这个规则中，每选择下一个客户去访问有着最优项的联合随机选择。取 q0 满足条件0 ≤ q0 ≤