基于遗传算法的运输路径选择问题

王荣 檀小璐

摘要：近年来，车辆路径问题一直作为物流配送领域研究中的热门话题，由于运输路径选取的不同，直接决定了物流配送问题中运输成本的差异，企业的管理者积极寻找着各种有效的配送策略。本文分析了车辆路径问题的实际背景，设计并实现了一个基于遗传算法的车辆路径问题的求解方法。

关键词：遗传算法；路径选择1VRP问题描述

物流配送车辆问题归纳为一般的网络模型：设G=(V，E，A)是一个连通的混合网络，V是顶点集(表示物流公司、客户等)，E、A分别为无向的边集和有向的弧集，E中的边和A中的弧均被赋权(可以表示配送的距离、时问或费用)，V、E、A分别为V、E、A的子集，求满足约束条件(包括客户的货物需求或供应数量约束、需求或供应时间约束、配送车辆一次配送的最大行驶距离约束、车辆的最大载重约束等)，并包含V、E、A的一些巡回路线，使目标函数取得优化，目标函数可以取配送总里程最短、配送车辆总吨位公里数最少、配送总费用最低、配送总时间最少、使用的配送车辆最少、配送车辆的满载率最高等。

2VRP问题的界定

一个物流公司向多个客户送货；物流公司和客户的位置一定；物流公司运送的货物能够达到所有客户的需求。各个客户需求的货物均可以相互混装，即可以装在同一配送车辆内；每个客户的需求量不超过配送车辆的最大载重量；每个客户的送货要求必须满足，且仅能一次性完成，不允许分批配送。每台车辆的最大载重量一定，不允许超载；配送时，每台车辆都从物流公司出发，向一些客户提供配送服务后，最终返回物流公司。对于客户要求将需求货物送到的时间，无时间限制。物流中心与客户之间以及客户相互之间的最短距离已知且固定；不考虑运输网络中车辆流量的限制。

3VRP问题的数学建模

设配送中心用K辆车对所有需求点进行配送(K的值由算法动态决定)。每个车的载重为bk(k=1,2,3…K)，每个需求点的需求量为di(i=1,2,3…L)，L为需求点的个数。需求点i到j的距离为Cij。设nk为第k辆车要负责运送的需求点总数，用集合Rk={rki|0≤i≤nk|}来对应第k辆车要送货的需求点，rki表示第k辆车要送达的第i个需求点，rko表示第k辆车起始点。数学建模：

归结出有约束条件的最优化问题：

上述表达式中，(1)式为所有需求点都应得到配送；不等式(2)为每条路径的需求量不超过配送车辆的载重量：不等式(3)为每个车辆对应的需求点总和不大于总的需求点数；(4)式为每需求点只有一辆车进行配送。

4VRP问题的遗传算法设计

从上述模型可知，求解VRP问题的关键是合理确定车辆与各需求点的关系，在满足车辆载重和各需求点的约束条件的情况下使得总路径成本最小，因此可以构造以下遗传算法：

(1)染色体结构编码二进制字符集{0,1}产生通常的0,1字符串来表示问题空间的候选解。用矢量(s1,s2,…sL)表示一个染色体(也称个体)G，其中sj的取值范围为[1,L]中任一个自然数，sj表示第j个被考虑的需求点。每个染色体G是1到L之间L个不重复自然数的一组随机排列。随机产生这样一组染色体Gm(m=1,2,…,M)(其中M为一代种群中的个体数)，构成初始种群。

(2)可行化过程 将染色体的编码向量映射为满足全部约束条件的可行解的过程称为可行化。在VRP问题中，可行化就是将编码的个体映射为一组可行的路径选择方案。过程设计如下：

(a)令车辆的初始剩余装载量

(b)考虑第j个基因sj对应的需求点，令k=1即从第一辆车开始考虑；

(c)若sj对应的需求点的待运货物重量 ，则令；如果 ，则令K=k；否则K不变，转5；如果 ，转(d)。

(d)令k=k+1，即考虑下一辆车是否能装载，转(c)。

(e)令j=j+1，即考虑下一个需求点，转(b)，重复上面的过程，直到j=L。

(f)此时K记录了所用车辆总数，即路径总数，Rk包含了第k条路径中依次配送的需求点，即Rk(k=1,2,…K)记录了一组可行的路径。

(3)适应度分析 初始种群形成以后，霈要通过种群的适应度函数，对种群中的每个染色体进行评价，并以此为标准选择最优解。对某一代种群中每个染色体Gh(s1,s2,…sL)，将可行化路径带入目标函数：

将得到该个体对应的路径代价。路径代价越小，表示该染色体越优。令Gh的适应度函数为fk=1/Zh，fk表示染色体在生命竞争中的能力，fk越大对应的个体越接近最优解。

(4)判断停止条件 当迭代搜索的次数满足要求的代数N，则停止，选出该代种群中适应度最优的个体，将其对应的可行路径集合作为该VRP问题的优化解输出；反之，继续进行(5)。

(5)自然选择 将一代种群中M个个体按适应度fk由大到小排列。排在最先的直接进入下一代，而下代中另外M-1个个体从前代种群M个染色体中采用轮转法选取，即按以下概率选择个体Gh进入下一代： ，其中， 共选择M-1次。用轮转选择法，既保证了最优个体进入下一代，又避免个体间因适应度大小不同而被选择进入下一代机会相差悬殊，保证了下一代的多样性并提高了算法的收敛速度。

(6)交叉操作 交叉概率PC控制着交叉操作被使用的频度。交叉概率PC在0.6--0.8之间时，进化性能较好，选择交叉概率为 PC=0.7，并引入一种新颖的交叉算子，这种交叉算子的最大特点是当两父代相同时，仍能产生全新的两个个体，这就减弱了对群体多样性的要求，能够有效避免传统遗传算法“早熟收敛”的缺点。

任意选取两个互不相同的个体A和B，设每个染色体含有n个基因，随机产生1--n之间的两个不等的整数S和 ，将染色体A和B同样分成三个部分，其中1→s-1为第一部分，s→ι为第二部分，ι+1→n为第三部分。将A的第三部分移到B的个体首部，并除去B中相同的基因，得到新的个体B'；同时将原B中的第一部分移到A的尾部，并将于A中相同的基因除去，便得到一个新的个体A'。交叉后分别计算个体A'、B'和A、B的适应度，选取适应度最大的两个个体进入下一代。采用新的交叉算子，当个体都相同时仍能够进行迭代进化，继续寻找问题的最优解，避免陷入局部最优解，克服了“早熟收敛”的缺点。

(7)变异操作 主要目的是维持解群体的多样性。低频度的变异可防止群体中重要的、单一基因的可能丢失，高频度的变异将使遗传算法趋于纯粹的随机搜索。变异概率Pm为0.02左右。变异策略是随机变换选中的一个染色体中任意两个基因值。对变异后的个体产生对应的可行路径并计算适应度，将其适应度与变异前个体进行比较，择优进入下一代。返回(3)、(4)步重复以上循环，直到满足终止条件。

根据上一节对VRP问题遗传算法的设计，对实现的各个步骤进行抽象提取，共构造了12个函数，包括：newcode()(生成随机个体)、initGA()(产生初始种群)、avFitness()(平均适应度函数)、natureChek()(自然选择函数)、crossover()(交叉操作)、mutation()(变异操作)等等，使用纯java编写代码，完成了设计的每一步操作函数。为了减少系统中的耦合性，在实现中采用EJB对路径选择算法进行模块封装，该模块封装了多个函数的调用关系，留給客户的只有一个输入接口，客户可以通过用户界面对系统参数进行设置，包括：种群大小M、遗传搜索的代数N、变异概率Pm，交叉概率Pc等，确认输入后，系统开始对用户选择的订单(含配送要求)进行处理，并自动读取数据库中的路径关系表，最后得出一个优化后的配送方案。

[参考文献]

[1]李敏强.遗传算法的基本理论与应用[M].科学出版社,2002.