基于遗传算法的物流配送车辆路径优化问题

苏楠，鹿静，王栋梁

（长安大学汽车学院，陕西 西安 710064）



基于遗传算法的物流配送车辆路径优化问题

苏楠，鹿静，王栋梁

（长安大学汽车学院，陕西 西安 710064）

在当代社会，物流越来越受到各国的重视，是企业创造利润的又一有效途径。文章主要研究在物流配送中的一个方面，也就是车辆路径优化问题，主要采用遗传算法进行计算。依据遗传算法，建立车辆路径优化的数学模型，配送路径的限制条件。在用遗传算法进行计算时，采用自然数序列进行编码，在选择时采用最优个体保留策略和轮盘赌法，变异时不只是单一的变异，而是两位基因同时变异，最终求得最优解。我国物流起步较晚，不及一些发达国家，所以有很大的进步空间。

物流；路径优化；遗传算法

10.16638/j.cnki.1671-7988.2016.06.002

CLC NO.: U468.8 Document Code: A Article ID: 1671-7988 (2016)06-04-03

引言

遗传算法是来源于达尔文的进化论，模拟生物的一代代繁衍，进化。它是由美国Michigan大学的John，H. Holland教授在20世纪60年代中期提出，并和他的学生逐渐完善起来的[1]。在众多的智能优化算法中，遗传算法是对生物进化过程的模拟，应用最为广泛，研究历史很长。

在现代社会中，物流的重视度在不断被提高，所以，降低物流运输的成本，提高运输效率，将效益最大化就是很重要的问题。本文主要是针对车辆路径优化问题进行研究。

1、本文的研究背景与意义

当代全球越来越趋于全球村，物流产业也开始壮大起来，逐渐成为一个庞大的产业，越来越受到各个企业的重视。物流本身所具备的流动性和开放性，能够大力的促进社会经济的进步。

物流配送就是运输衍生出来的一种功能，是市场不断发展的必然产物，也是经济发展的重点之一。在尽可能的减少成本，提高利益的目的下，而物流配送中更关键的就是怎样合理的调度车辆[2]。

配送中心的地理位置，各个客户的地理位置也是已知的，还有各个客户的需求量以及配送车辆的限载量和最远配送距离都是已知的，要求合理安排车辆的行驶路线，从调度中心出发，依次到达各个客户，最后返回配送中心，使行驶距离最短，成本最低，利益最大化。

2、基于遗传算法的车辆路径问题研究

2.1物流配送车辆路径优化的数学模型

2.1.1变量的设定

在保证满足每个客户的要求的前提下，不超过每台车的限载量和最远行驶距离，使配送距离最短，效益最优，并且还需要满足以下条件[3]：

每一条配送路径上的所有客户的需求量的总和不能超过该台车的限载量；

每一条配送路径的总长度不得超过该车辆的最远行驶距离；

必须保证每个客户都能拿到相应数量的货物，并且每个客户只能由一台车进行配送；

K：物流中心共有K台配送车辆。

Qk：每台配送车辆的限载量为Qk(k = 1、2……K)。

Dk：每台配送车辆的最远行驶距离为Dk。

L：一共的客户数为L个。

qi：每个客户需要的货物量为qi（i=1.2……L）。

dij：从客户i到客户j的运输距离为dij。

d0j：物流中心到各个客户之间的的距离为d0j(i、j = 1、2……L)。

nk：第k台车辆一共配送的客户数为nk(nk=0表示未使用第k台车辆)。

Rk：第k条路径。

rki：rki表示客户在路径k中的顺序为i(不包括物流中心)。rk0=0表示物流中心。

若以配送距离最短为目标函数，则可建立如下最优化物流配送路径问题的数学模型[3]:

2.1.2约束条件

(1)式为目标函数值，既总配送距离。

(2)式限制每一条配送路径上的所有客户的需求量的总和不能超过该台车的限载量。

(3)式限制每一条配送路径的总长度不得超过该车辆的最远行驶距离。

(4)式限制每条配送路线上的的客户数不得多于总客户数。(5)式保证每个客户都能拿到相应数量的货物。(6) 式限制每个客户只能由一台车进行配送。(7)式中为0表示该台车没有被利用[4]。

2.2针对算法优化物流配送车辆路径优化的遗传算法构造

2.2.1编码方法的选定

采用直接编码方式，有L个客户，将1~（L+1）间的自然数进行随机排列，0表示的是配送中心，有K台配送车辆，将K-1个0随机插入该排列中，则形成了一个类似于二进制码的代码。

2.2.2初始种群的产生

随机产生一个由1~（L+1）和K-1个0组成的的序列，形成一条染色体，种群大小为M，则由M条不同的染色体构成初始种群。

2.2.3适应度评估

每一条染色体对应一个配送方案，在计算他的目标值之前，要先判断它的可用性，不可用的话，为不可行路径，直接淘汰掉，对剩下的可用染色体计算目标值。可行染色体的适应度可用下式表示：

式中：G为权重因子，取一个较大的正数(G值太小则会影响适应度的比较)。

2.2.4选择操作

同时采用最优个体保留策略和轮盘赌法[5]。先是最优个体保留策略，将最优的个体，也就是适应度值最高的个体，直接进行复制到下一代。然后，运用轮盘赌法。将该代种群中所有可用染色体适应度加起来，得到，再计算出每条染色体的适应度在总的适应度值里所占的比例，得到，这就是该条染色体被选中的概率。

2.2.5交叉操作

交叉操作，就是将两个随机组合的染色体相互交换对方的一部分基因，从而形成两个全新的个体。

由第n代到第n+1代产生的新种群，除了一条直接复制过来的最优染色体外，其余的都要依据交叉概率进行交叉配对[6]。

例如：两条n代染色体分别为A=52|073|6014，B=31| 507|0264，将B中间的交配区域加到A染色体的的前面，A的中间交配区域加到B染色体的前面，将其中的0去掉得：A1=57|520736014，B1=73|315070264；在A1、B1中自交配区域后删除与交配区相同的自然数,得到的最终下一代个体为：A2=572036014，B2=73150264。

2.2.6变异操作

本文中因为特殊的编码方法，也要采用一种特殊的变异方法[7]，根据变异概率，染色体的一个部位发生变异时，另一个相应的部位也要发生相应的变异。例如：染色体572036014上的3位发生了变异，变成了4，则4位上也要发生变异，变成3。

2.3实验与计算

例：某物流中心一共拥有2台配送车辆,两台车辆的限载量均为8t，车辆每次配送的最大行驶距离也均为50km,配送中心与8个客户之间以及8个客户相互之间的距离、8个客户的货物需求量均见表 1。要求合理的安排物流配送路线，使车辆配送总里程最短。

表1　已知条件表

表2　计算结果表

计算时采用以下参数：初始群体规模M取为20，进化代数N取为25，交叉概率取为0.9，变异概率取为0.09，变异时基因换位次数取5，惩罚权重取100km。随机求解10次，得到的计算结果见表2。

从结果可以看出，遗传算法的计算效率非常高，求解结果也比较稳定，在10次求最优解时中，有3次得到了问题的最优解，7次得到了问题的近似最优解。

3、结论

由实验结果可以看出，先随机建立物流配送的模型，然后再用遗传算法进行求解，是一种比较方便，快捷的求解方式，可以在较短的时间内就求得物流配送路径的最优解。

但是遗传算法也有缺点，虽然全局搜索能力比较强，但是局部搜索能力很弱，能够在短时间内就接近最优解，但是在接近最优解后，达到最优解还需要一段时间，如果能和其他算法一起计算，则能迅速提高效率。

[1] 武交锋. 应用遗传算法提高蚁群算法性能的研究[D]. 太原:太原理工大学2007.

[2] 占焱发. 基于遗传算法的物流配送车辆路径问题研究[D]. 西安:长安大学2010.

[3] 余玥;胡宏智. 基于改进遗传算法的物流配送路径求解[J]. 计算机技术与发展,2009,19(3):52-55.

[4] 朗茂祥.基于遗传算法的物流配送路径优化问题研究[J].中国公路学报,2002,15(3):77-78.

[5] 周和平.军事物流配送路径优化问题研究[D]. 合肥:合肥工业大学2009.

[6] 王旭升;尤小霞. 基于混合遗传优化算法的物流配送路径分析[J].物流技术,2014,5:269-271.

[7] 安立军;俞宏生.基于遗传算法(GA)的配送路径优化问题研究[J].物流科技,2007,10：33-36.

Routing optimization problem of logistics distribution vehicle based on genetic algorithm

Su Nan, Lu Jing, Wang Dongliang
( College of automotive engineering, Chang'an University, Shaanxi xi'an 710064 )

In contemporary society, the logistics gets more and more national attention ,it is another effective way for enterprises to create profits.This paper studies one aspect of the logistics and distribution, which is the vehicle routing problem, mainly using genetic algorithms to calculate. The mathematical model of VRP is built on genetic algorithm with distribution route restrictions.When calculated with the genetic algorithm, the natural number sequence is encoded,the best individual retention policies and roulette method is used on choosing.Compiled with not just a single mutation, but simultaneously two gene mutation, and ultimately get the optimal solution.China's logistics start late, less than some developed countries, so there is great potential for improvement.

Logistics; Route optimization; Genetic Algorithm

苏楠，就读于长安大学。

U468.8

A

1671-7988 （2016）06-04-03