基于改进遗传算法的车辆路径优化.pdf-资料库

weixin_38668335-12113830-4744300845403419791.pdf-第1页.png

第1页 / 共6页

weixin_38668335-12113830-4744300845403419791.pdf-第2页.png

第2页 / 共6页

weixin_38668335-12113830-4744300845403419791.pdf-第3页.png

第3页 / 共6页

weixin_38668335-12113830-4744300845403419791.pdf-第4页.png

第4页 / 共6页

weixin_38668335-12113830-4744300845403419791.pdf-第5页.png

第5页 / 共6页

weixin_38668335-12113830-4744300845403419791.pdf-第6页.png

第6页 / 共6页

基于改进遗传算法的车辆路径优化 http://www.paper.edu.cn 李轶舜 1，徐建闽 1，徐鹏 2 1 华南理工大学交通信息工程及控制，广州（510640） 2 河海大学交通学院，南京（210098） E-mail：li.yishun@163.com 摘要：自从 VRP 被证明为 NP 难题后，许多学者进行了各种求解算法的研究。本文采用遗传算法来求解 VRP 问题, 其思想是对遗传算法初始种群确定、染色体序列排序、交叉算子进行创新改进,使得算法更加趋于合理、收敛更快、运行效率更高。关键词：车辆路径优化，遗传算法，时间窗中图分类号：U491 1. 问题提出一般车辆路径问题是指有 q 个货物需求点,已知每个需求点的需求量及位置,至多用 k 辆汽车从配送中心到达这批需求点,每辆汽车载重量一定,安排汽车路线使运距最短,且满足每条路线不超过汽车载重量和每个需求点的需求必须且只能由一辆汽车来满足的约束条件,其目的是使总成本(如距离、时间等)为最小[1]。 2. 面向物流配送问题的数学模型假定只有一个物流中心，运输车辆为同一型号，节点的货物需求量均小于单辆的汽车容量，一辆车完成多项货运任务，且每辆车一次运送的是同一种类的货物。 2.1 费用的确定在理想状态下时间的费用表现为一定的边权费用，即网络上各线段长度折算的时间费用，但在实际配送过程中并非如此简单，在此我们需要对时间费用进行细分。（1）路段里程形成的时间费用路段里程形成的时间费用在各类文献中多描述为有向图中的边权费用，这一点大家已有共识。在实际配送过程中，表现为根据长期统计而得出的该路段行程车速和推导出的车辆通过时间。但这种时间费用并不是一个固定的值，而是根据不同交通时段有不同的时间费用，形成不同的时段方案。这个问题同样存在于下面的两个时间费用中。（2）节点上消耗的时间费用节点费用包括两个方面，一个是在各交叉口节点信号等候等时间费用，表现为其左右转与直行的不同时间费用。另一个是在零售点货物交接需要的时间费用，主要依据于货物品种、数量等产生时间延误不同。 2.2 基于交通逻辑与配送规则的弹性约束模型的建立综合考虑交通因素和配送管理因素，构建弹性约束 VRP 模型，并据此构建合理的数据结构和改进算法。对物流配送下的 VRP 问题作如下数学描述：设图 G=（V, E）为各零售点间的拓扑结构，其中 V 中各点代表零售点，E 中各边表示 , 其中 0v 为中心点，亦即货源对应的零售点间或零售点与货源点间有路相通。令 0 V =′ \ vV - 1 -

)(x weight 为定义在V ′ 上的函数，函数值为对应零售商所需的货物量。 cos xt 为定点。义在 E 和 V 上的函数，函数值为货车在两零售商间或零售商与货源点间运行所需的综合费用。现欲将V ′ 剖分成 k 块，使其满足如下的条件： )( http://www.paper.edu.cn ∪k iV i 1= weight 1. V =′ 令 W i = ∑ iVx ∈ 物量。， V ∩ i V Φ=j 对任意的 i ≠ 。 j x )( （ i ≤≤1 k ）。则 Wi ≈ ，其中Tol 为单车所能运载的最大货 Tol 令 iU 为从货源点出发，经过 iV 中各点至少一次且回到货源点所需的最少费用。我们希望在各 iU 的值相差不大的约束条件下，总费用 ∑ U = k i 1 = iU 尽可能的小。目标函数建立如下： min u = n m n ∑∑∑ k 1 = j 1 = i 1 = CX ijk + m ∑ k 1 = − 1 + WF ( ) ' k m ∑ k 1 = − 1 TF ( ' k ) 3,2,1=∀ijk m ∑ kW k 1 = ,…,…m ,n （2-1） ' = D 3,2,1=∀i ,…,…m （2-2） m =∑ kiy k 1 = 1 3,2,1=∀i ,…,…m （2-3） x =∑ kij i =1 n n x =∑ kij j =1 n KW ' =∑ i 1 = y kj 3,2,1=∀i ,…,…n （2-4） y ki 3,2,1=∀j ,…,…n （2-5） Kid 3,2,1=∀i ,…,…n （2-6） n n n 1 − ∑ ∑∑ + t ki i 1 = j 1 = i 1 = t kij = ' T K 3,2,1=∀ij ,…,…n （2-7）式中： yki=1 or 0 点 i 的任务由车辆 k 完成则等于 1，否则等于 0； xijk＝1 or 0 车辆 k 从 i 行驶到 j 则等于 1，否则等于 0；本目标函数解决的是由一个配送中心向多个连锁分店配送货物，每个分店对货物的需求不同，而且，解决的是非满载（每个分店的需求都小于车辆的载货量）的所谓的 VRP 问题，其考虑了时间、载货量的弹性约束、过街送货等问题。 2.3 应用改进遗传算法对车辆路径问题的求解车辆路径优化问题是一类具有 NP 难性质的复杂问题,应用遗传算法求解有着比较显著 - 2 -

http://www.paper.edu.cn 的优势。从车辆路径优化模型中可知,求解车辆路径问题的关键是合理确定车辆与各需求点的关系,在满足车辆载重量、时间和各需求点需求量的约束条件下使得总费用最小[2]。下面是改进基本遗传算法求车辆路径问题优化解的方法。 2.3.1 面向 VRP 的遗传编码序列改进根据 VRP 的具体特点，采用自然数编码，即符号编码[3]。物流中心用 0 表示，用序数 1 到 L 表示有货运要求的 L 个货运节点，完成这些货运任务需要的车辆数目为 m，用序号 1 到 m 表示。VRP 的一条可行的线路编成长度为 L＋m+1 的一个染色体： , i m 1 , i i 1 x i 12 i 11 , ,0, ,0( 其中，ikj 表示第 Ikj 项任务，k 表示编号为 k 的车，j 表示第 k 辆车承担的第 j 项货运任 ,0, )0, ,0, , , , , , i i 21 i 2 y i mz m 2 22 务。如染色体 0453028607190 表示 9 项货运任务由 3 辆车来完成，各条行车线路图：图 2-1 基于自然数编码的一条染色体（0 代表配送中心） Fig2-1 One chromosome of natural number coding 图 2-1 中染色体结构子路径内部是有序的，若子路径 1 中的 4，5 货运任务互相交换位置，会使目标函数改变数值；但其子路径之间是无序的，若子路径 1 和子路径 2 互换位置，目标函数的数值不会发生改变。由于非满载 VRP 编码子路径内部有序，子路径之间无序的特点，这种初始群体在进行交叉运算时，如果使用以往的一些交叉算子，难以保证双亲的优良特性，甚至得到大量的不可行解。针对此问题，常见的解决方法如最大保留交叉策略求解：如果染色体交叉点处的两个基因都为 0 ,直接进行 PMX(部分匹配交叉)运算;如果染色体交叉点处的基因不全为 0 ,则将交叉点左移(右移) ,直到左右两个交叉点处的基因都为 0 ,再进行 PMX 运算。但这类方法存在着一定的局限性。首先，是难以保证配对染色体间必定能找到节点数相等的两条子路径进行 PMX 运算；其次，在进行交叉时仍然会使许多相距较远的路径之间产生交叉从而得到大量的不可行解。由经验可知，相邻路径间基因交叉能得到比较优的解。因此，有必要对染色体结构进行改进，优化染色体编码序列，即在种群初始化过程中及后续的染色体排序中，子路径内部有序，子路径之间亦有序。 2.3.2 初始种群的设计传统的遗传算法求解 VRP 问题时，初始种群多半采取随机生成法，即从所有的配送点中随机选取点直到满足一定的条件或接近满足一定条件后停止，形成一条子路径，乃至形成一条染色体（一套配送方案）。但这种方式使初始种群的形成过于随意，以致于一开始就可能形成许多不可行的方案，之后要进行较为大量的计算后才能得到优化的方案，这样很大程度上降低了算法的运算效率。扇区扫描法搜索初始种群基于对上述缺点的考虑，我们摒弃传统的随机初始化种群的方式，对初始种群给予基于知识型启发策略，使得初始种群一开始就表现为一种较优状态。其具体流程将在系统实现中给予详细介绍。 - 3 -

http://www.paper.edu.cn 具体流程如下：（1）过配送中心与某任务点产生射线顺时针转动。（2）累计扇面覆盖的配送点需求量之和，直至满足运量约束停止构成一个客户分群。（3）采用节约插入算法将该客户群形成优化子路径。（4）以原射线末位置为新射线的初始位重复上述过程。直至形成一条包含所有子路径的染色体序列。（5）将射线顺位偏移某一角度，同样按以上方法产生第二染色体。最终形成 N/2 条染色体的种群。（6）为保证种群多样性，上述方法逆时针做同样操作，再形成 N/2 条染色体。图 2-2 扇区扫描示意图 Fig2-2 Pie slice scanning sketch map 2.3.3 交叉算子改进遗传算子是决定算法好坏的重要的因素之一。遗传算子包括交叉，选择和变异三种算子。交叉算子用来产生新的个体，常见的交叉算子有单点交叉，双点或多点交叉，均匀交叉，算术交叉等。交叉算子的设计和实现与所要解决的问题密切相关，一般要求它既不要太多的破坏个体编码串中表示优良性状的模式，又能够有效的产生出一些较好的新的个体模式[4] 我们在项目中作如下改进：（1）子路径以几何邻近原则进行排序，子路径之间亦有序，两条染色体交叉时其质心邻近的子路径进行基因交叉。（2）对基因进行选择，即通过拓扑叠加分析，标识出每条子路径的边界基因，将这些边界基因进行交叉，形成具有较好适应度的下一代染色体。 2.3.4 适应度函数的确定最终适应度函数确定为： z = n n m ∑∑∑ 0 k 1 = i = 0 c x ij ijk + n m ∑∑ i = 0 1 = c y i ki + 1/ M 1 m ∑ ( max( k 1 = n ∑ i 1 = g y W i − ki , 0)) j = m k n n 1/ M 2 ∑ ( max(( k 1 = ∑ ∑∑ + t i i 1 = j 1 = n i 1 = t ij ) − T ,0)) 这里 xijk 和 yki 的含义同前文， ijc 为节点 i 和 j 之间的资源消耗， ic 为在节点 i 时 k 车的消耗，包括转向、卸货、虚拟节点过街等消耗。 - 4 -

http://www.paper.edu.cn ))0, 表示若违反容量约束处以的惩罚值，W 为每辆车的额 Wyg i − ki max( l ∑ i 1 = m 1/ ∑ ( M 1 1 = k 定载货量。 m 1/（ ∑ M 2 k 1 = (max( n ∑ i 1 = t i + n n ∑∑ i 1 = j 1 = t ij ) − T )0, ）表示若违反宽时间窗约束处以的惩罚值， T 是各辆车规定的每日的工作时间， it0 为车辆在节点 i 上所消耗的时间， it1 为在路段上消耗的时间。对于 M 考虑的是面对现实情况下的，应该是符合实际情况下的对应于时间、或者对应于货物的取值的时候应该出现的‘反映’，而且，所给定的函数的表达式是通过现实的统计数据进行拟合得来的、相对合理的表达式。当运载量或者工作时间超过了给定的数据范围时取一个相当小的值对其进行惩罚，其会反映为资源消耗的不能忍受，以此来对此路径进行摒弃。 2.3.5 其他运行参数（1）工作量均衡目标：采用各子路径方差办法解决，在算法中将方差大的方案排除。（2）个体编码串长度：配送需求零售点数量＋子路径数量＋1 （3）群体规模 N：根据试算染色体个数取 20～40 （4）交叉概率 pc、变异概率 pm：根据系统迭代动态确定（5）终止代数 T：取一个适当的迭代次数值 3. 小结本文采用了改进的交叉算子，可以最大限度的将已经具有双亲优良特性的子串复制到下一代，有效的提高了染色体的质量，另外在种群中各个个体均相同的情况下，也不会影响遗传迭代的进行，摆脱了对种群多样性的要求，有效的提高了对种群的搜索能力。 - 5 -

http://www.paper.edu.cn 参考文献 [1] 姜灵敏.基于改进遗传算法的车辆路径问题求解[J]. 计算机应用与软件,2006 年,23 卷第 4 期 95-97 [2] 谢秉磊.有时间窗约束旅行商问题的启发式遗传算法[J]. 西南交通大学学报, 2001, 36(2) 210-213. [3] 李军.车辆调度问题的分派启发式算法[J].系统工程理论与实践, 1999, (1) 27-33 [4] 周明,孙树栋. 遗传算法原理及应用[M], 北京,国防工业出版社, 1999, 61-62 The optimizeation of Vehicle Routing Problem based on ameliorational heredity algorithm 1College of Traffic and Communication, South China University of Technology, Li Yishun1, Xu Jianmin1, Xu Peng2 2School of Transportation, Hehai University, Nanjing (210098) Guangzhou（510640） Abstract Since VRP by the proof is the NP difficult problem, many scholars have conducted each kind of solution algorithm research.. Its thought is in the heredity algorithm initial population determined, the chromosome sequence arrangement, the overlapping operator make the innovation improvement, causes the algorithm even more to tend to reasonably, restrains, the operating efficiency quickly is higher. Keywords: VRP, eredity algorithm, ime windows 作者简介：李轶舜，男，1986 年生，硕士研究生，主要研究方向是交通控制、交通诱导。 - 6 -

资料库

基于改进遗传算法的车辆路径优化.pdf

相关推荐

开发技术

热门标签

最新资料