基于遗传算法轿车焊装车间车辆路径优化

冯爱军， 胡小建 （合肥四十三研究所，安徽 合肥 230022）

基于遗传算法轿车焊装车间车辆路径优化

冯爱军， 胡小建 （合肥四十三研究所，安徽 合肥 230022）

遗传算法是一种模拟自然进化过程搜索最优解的方法。通过建立某轿车焊装车间车辆路径问题数学模型，然后利用遗传算法求解该问题，最后在Matlab软件中进行编程求解，有效地求解出问题的最优解或近似最优解。

遗传算法；Matlab；车辆路径；焊装车间

车辆路径问题是指一定数量的顾客点，每个顾客点都有自己的货物需求量，供货中心需要向各个顾客点配送货物，货物配送需由一个车队来负责，组织合适的车辆行进路线，并在满足一定的约束条件下 （如客户货物的需求量，车辆载重量等），达到一定的目标 （如路程最短，成本最少，耗时最少等）。

1 建立数学模型

1.1 问题描述

车辆行进路径的优化可描述为：从供货中心使用多辆车向多个顾客点配货，每个顾客点的位置和需求量都是一定的，车辆载重一定，要求合理安排车辆行进路径，使总的行进路程最短，并要求满足下列两个条件：

①各个行进路径上各顾客点的货物需求量总和不能超过车辆的额定载荷；

②每个顾客点的需求必须能够得到满足，并且只能由其中一辆车进行配送。

1.2 建立模型

假设供货中心拥有K辆车，每辆车的额定载量是Qk，它一次配货的最大行进距离是Dh，需要向L个顾客需求点配货，顾客点i的货物需求量是qi，供货中心到顾客点i的距离是doi，顾客点i到j的距离为dij，再假设nk为第K台车配送货物的顾客数 （nk=0指示为未使用第K台车），使用集合Rk表示第k条路径，它们中的元素rki表示顾客点rki在路径k中的顺序为i（不包括供货中心），当rki=0表示供货中心，则可建立以下优化物流车辆路径的数学模型：

2 遗传算法的基本思想

标准的遗传算法包括3个基本的操作：选择、交叉和变异。其步骤描述如下：

图1 标准遗传算法的流程图

（1）产生初始种群，并评价初始种群中每个个体的适应度值。

（2）判断收敛准则是否符合条件。若符合，则输出相应的搜索结果；否则执行以下步骤。

（3）根据适应度大小按照一定方式执行选择操作。

（4）根据交叉概率Pc执行相应的交叉操作。

（5）根据变异概率Pm执行相应的变异操作。

（6）返回步骤 （2）。

3 实例计算

根据上述遗传算法在Matlab中进行编程，并针对某轿车焊装车间为实例进行求解。

某轿车焊装车间有一库房供货中心，该供货中心坐标为 （74,10），供货中心有5辆拖车，每个拖车最大载量为3个标准托盘，需要向15个点送货，15个点的坐标和货物需求量见表1。

实验中采用下列参数；种群大小取80，交叉概率取值为0.65，变异概率取值为0.005，终止代数设置为200，在Matlab中随机求解10次，第2次就获得了最优解，最优解为1 524.2336m。各供货点和仓库坐标显示如图2，求解结果如图3。因此车辆路径具体安排如下：

表1 送货点坐标和货物需求

①1-7-11-16-1； ②1-15-9-8-1； ③1-14-4-5-1； ④1-2-13-6-1； ⑤1-20-3-12-1。

4 结 论

实验结果表明，运用遗传算法可以有效地快速地求得该轿车焊装车间车辆路径安排的最优解或近似最优解，很好地解决车辆路径如何安排的问题。

[1]蔡希贤，夏士智.物流合理化的数量方法[M].武汉：华中工学院出版社，1985.

[2]Holland J.遗传算法的基本理论与应用[M].李敏强,译.北京：科学出版社，2003.

[3]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社，2001.

[4]赵刚.物流运筹[M].成都：四川人民出版社，2002.

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

[6]姜大立，杨西龙，杜文,等.车辆路径问题的遗传算法研究[J].系统工程理论与实践，1999,19(6)：40-44.

[7]米凯利维茨Z．演化程序——遗传算法和数据编码的结合[M].北京：科学出版社，2000.

Optimizing of Vehicle Routing Problem of Car Welding Workshop Based on Genetic Algorithm

FENG Ai-jun,HU Xiao-jian(Hefei Institute 43.,Hefei 230022,China)

Genetic algorithm is a method which simulates natural evolution search optimal solution.By establishing a car welding workshop vehicle routing problem mathematical model,and by using the genetic algorithm to solve the problem,and finally we programme in Matlab software and effectively get the problem's optimal solution or approximate optimal solution.

genetic algorithm;matlab;VRP;welding workshop

F273

A

1002-3100(2011)10-0119-03

2011-08-22

冯爱军（1986-），男，安徽亳州人，合肥四十三研究所硕士研究生，研究方向：物流管理及信息化。