遗传算法基于路径优化问题应用的改进探索研究

　　当然遗传算法也不可避免地存在着它的不足之处：（1）存在编码不规范及表示不准确等问题。（2）单一的遗传编码不能全面地将优化问题的约束表示出来。（3）大量研究也表明，GA存在早熟、算法参数敏感等缺点，取得良好的性能需要依赖较大的种群并对算法进行精心设计。
　　采用遗传算法等智能优化算法来求解带能力约束的车辆路径问题 （Capacitated Vehicle Routing Problem，即CVRP），一般能在较短的计算时间内获得质量较高的近似解。
　　三、问题描述
　　CVRP可描述如下:配送中心有m辆货车，每辆车的能力为q；配送中心需为n个客户提供货物配送任务，每个客户的需求量为gi（i=1，2，…，n），gi　　有1个配送中心和8个商店，商店0表示配送中心，配送中心有两辆载重量为8吨的货车，要求合理安排车辆行驶路径，使总运输距离最小。商店之间的相互距离及各商店的商品需求量（见表1、表2）：
　　表1 各需求点对货物需求量 单位：吨
　　表2配送中心与各需求点之间的距离单位：KM
　　四、算法改进
　　在现有遗传算法中，个体的染色体编码还需要用到最优车辆数。这两种编码方案有三个缺点:（1）由于染色体维数变长，使组合空间变大，从而降低了搜索到最优解的几率。（2）由染色体解码后获得的子路径有可能不满足车辆的能力约束。（3）需要预先知道最优解所需车辆数。
　　为了避免上述缺点，本文提出一种新的双层染色体编码方案Double Layers Chromos Coding Shema，DLCCS）。标准遗传算法中染色体是单层的。而在DLCCS中，染色体是两层的，其构成为：第一层是n维向量L1，代表n个客户的一种排列。第二层是一个维数可变的向量L2，在L2中存放的元素代表每辆车所服务的第一个客户在Ll中的顺序号，需根据车辆的能力限制计算得出。以上节的例为例，用自然数1～8代表8个客户，其需求量分别为（1，2，1，2，1，4，2，2），车辆的能力约束为8个单位。假定某个体的第一层染色体为L1（4，l，3，7，2，6，5，8），第二层染色体的计算过程如下:（1）第一辆车编为0号车，其第一个客户为客户4，在L1中的顺序号为0，因此第二层染色体暂时为LZ（0）。编号顺序都从0开始，这便于编程实现，因为在很多编程语言中，都将数组的起始编号设为0。（2）继续让0号车服务后面的客户，直到超出车辆的能力约束，在本例中，0号车可以服务前5个客户，到第6个客户，由于违反车辆的能力约束，需派出1号车（第二辆车）。1号车所服务的第一个客户为客户6，其在Ll中的顺序号为5，将其加入LZ，第二层染色体变成L2（0，5）。（3）继续应用步骤2，直到所有的客户都得到服务为止。
　　设置遗传算法的种群规模为60，交叉概率为0.8，变异概率为0.05。在计算机上用MATLAB优化软件求得标准遗传算法与改进后的遗传算法结果（如表3所示）。
　　由表3可以看出，改进后的遗传算法比标准的遗传算法收敛性要好得多，并且在运算速度以及占用内存方面也有很大优势。
　　参考文献：
　　[1]张远昌.物流运输与配送管理[M].北京:中国纺织出版社，2004.
　　[2]荣耀华.传统物流与现代物流[M].北京:中国物资出版社，2007.
　　[3]叶耀华，陈霖，朱晓梅.一种带时间窗口和在前约束的车辆路线问题及其算法[J].系统工程理论与实践，2000，(3).
　　[4]程世平.物流管理[M].合肥:合肥工业大学出版社，2007.
　　[5]王凌.智能优化算法及其应用[M].北京:清华大学出版社，施普林格出版社，2001.
　　[6]邢文训，谢金星，等.现代优化计算方法:第2版[M].北京:清华大学出版社，2005.
　　[7]Dantizg G，Ramser J.The truck dispatching problem，Management Science，1959，(6):80-91.
　　[8]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社，2001:11.
　　[9]Holland J H.Adaption in natural and artificial systems.MIT Press，1975.