基于遗传算法的路径优化问题研究

摘要：近几年，物流配送业急速发展，配送任务密集而繁重，如何高效、合理的完成配送任务决定了一个企业的市场竞争力。该文基于遗传算法设计了单一目标的路径优化方案，并将算法融入模块设计中，实现了基于Java的物流配送管理平台。通过仿真测试，该方案在搜索效率和性能上都表现出较好的特性。

关键词：物流；配送；遗传算法；路径优化

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2014）02-0288-04

随着电子商务时代的到来，网络购物已成人们生活不可或缺的购物途径，动动鼠标足不出户就可以买到物美价廉的商品，这是电子商务最大的便捷性，也是其急速发展的重要因素，但鼠标不能代替车轮，产品要送到客户手中，必须从虚拟经济转为实际运输，因此物流配送的效率成为制约电子商务的发展的重要环节。

物流配送活动不受时间、地域的限制，配送任务复杂又琐碎。作为一种经济活动，配送的成本始终备受企业关注，而影响配送成本的直接因素就是配送路程的长短，因此为了降低运营成本，管理者都在配送策略上寻找出口。

1 路径优化问题描述

配送路径优化本着效率高、成本低、距离短、消耗小等原则。这些原则使得路径选择受多元因素影响，但为了更有效的阐述路径优化方案，该文确定了“路径最短”的单一研究目标。

假设某次的配送活动中，有L个配送车辆、一个物流配送中心和I个配送的终端客户，要求合理安排车辆和配送路线，将货物从配送中心配送到终端客户，并使路径方案最优。

现实生活中的车辆调度和路径选择问题十分复杂，为了方便建模和求解，该文对研究的问题进行了抽象和简化。现对本文研究的物流配送车辆调度问题做如下界定：

货物统一从一个物流配送中心发往多个客户终端；配送中心和终端的位置固定并已知；多个包裹可以混放在一辆车中；同一个客户的配送总量不超过车辆的载重；每个客户的货物不允许分批配送；每台车辆的最大载重量固定，不许超载；每台车辆均从物流中心出发，配送后返回物流中心；客户无到货时间的限制；不考虑交通运输中的汽车流量限制。

2 路径优化问题数学建模

3 遗传算法

遗传算法的基本思想是从问题可能的多个解开始，通过一定进化原则多次迭代不断产生新的解，随着迭代次数的增加，得到的解越来越接近最优解，该算法是一个“生成+检测”的迭代优化过程。这多个解的集合称为一个种群。一般种群中元素的个数在进化过程中不变，称为群体规模。种群中的每个个体称为染色体。算法的基本流程如下[2]：

编码并生成初始群体：遗传算法必须先通过编码将空间数据表示成遗传空间的基因型数据串。然后随机产生M个不同的染色体构成算法的初始群体，其中每个染色体对应问题的一个初始解。

评估适应度并繁殖：遗传算法在搜索过程中采用适者生存的原理来评估个体，并根据个体的适应度高低进行繁殖操作。在初始种群中将适应度较高的M个个体作为父代繁殖下一代子孙。

杂交：杂交是遗传算中最关键的信息交换操作，分为两步：一是随机抽取群体中个体进行配对，该文中按事先确定的杂交概率Pc在M个个体中随机选择两个个体；二是对配对个体设定随机交叉点，使两者交换部分信息，并产生两个新个体进入下一代。重复这个过程，直到所有需杂交的个体完成杂交过程。

变异：变异是按一定概率随机改变个体的基因链。目的是挖掘个体的多样性，避免算法陷入局部最优解。该过程在M个个体中根据事先确定的变异概率Pm随机选择个体，并按变异策略进行运算。

停止条件：当优化的结果满足判断条件或迭代的次数达到指定要求是运算停止；否则继续重复以上的优化过程，不断产生新一代群体。

在遗传算法的运算过程中，群体规模、交叉概率、变异概率、中止进化代数等因素都会对算法结果和效率有直接影响。

4 路径优化问题的遗传算法设计与实现

4.1 染色体编码

本文中的染色体编码选用实数编码方式。用矢量表示一个染色体个体，如矢量T（t1，t2， ……，tI），ti取[1，I]中的任一个自然数，表示第i个配送点，每个染色T是[1，I]之间I个不重复自然数的随机排列。假设共有9个配送点，预先对每个配送点进行编号1～9，个体T（3，5，7，2，4，6，9，8，1）表示依次按照“配送点3、配送点5、……、配送点1”的顺序完成9个配送点的任务。随机产生一组这样的染色体个体Tm（m=1，2，……M）构成规模为M的初始种群。

4.2 可行化分析

4.4 自然选择过程

本文中自然选择的过程，在保证最优个体进入下一代同时，让其他个体根据适应度不同而按概率进入下一代。

基本设计：将一代种群中M个个体按适应度gh由大到小排列，排在前10%的直接进入下一代，而另外M-10%个个体从当前种群M个染色体中生成，生成的过程使用轮转选择法[4]，该自然选择过程保证了新一代个体的多样性和算法的收敛速度。

4.5 交叉操作

分析数据得出，配送规模在8个需求点的路径优化问题上，本算法的搜索时间基本控制在1000毫秒以内。为了对比算法优越性，该文还实现了禁忌搜索算法的搜索仿真，实验结果证明文中设计的遗传算法在路径优化问题的搜索效率上明显具有优势。

6 结束语

本文分析了遗传算法的原理，并针对路径优化问题进行遗传算法优化设计。该算法的特点是对车辆的数目没有作事先要求，省去了可行性判断过程中的大量搜索浪费。实验数据表明算法的搜索性能相比其他搜索方案具有明显的效率优势。

参考文献：

[1] Gendreau M， Hertz A， Laporte G.A tabu Search Heuristics for the Vehicle Routing Problem[J].Management Science，1994，40：1276-1290.

[2] 玄光男，程润伟.遗传算法与工程优化/应用数学译丛[M].于歆杰，周根贵，译.北京：清华大学出版社，2004.

[3] Teodorovic D，Pavkovic G.A simulated annealing technique approach to the vehicle routing in the case of stochastic demand[J].Transprotation Planning and Technology，1992，16：16：291-293.

[4] Chang Wook Ahn，Ramakrishna R S.A genetic algorithm for shortest path routing problem and the sizing of populations[J].IEEE Transaction on evolutionary computation，2002，6（6）.

[5] 陈国良，王煦法，庄镇泉，等.遗传算法及其应用[M].北京：人民邮电出版社，2001.

[6] 张思亮，葛洪伟.求解车辆路径问题的一种混合方法[J].计算机工程与应用，2011，3.