基于改进遗传算法的物流配送路径优化方法研究*

金巳婷 吕 闪 吴阳明 王宇瑶

(大连交通大学电气信息工程学院 大连 116028)

基于改进遗传算法的物流配送路径优化方法研究*

金巳婷 吕 闪 吴阳明 王宇瑶

(大连交通大学电气信息工程学院 大连 116028)

基于目前快递行业在配送过程中成本增加,速度减慢,服务质量下降等问题,提出一种基于改进遗传算法的物流配送路径优化方法。在基本遗传算法的基础之上作出改进,加入时间窗约束,保证算法的实时实现;优化遗传操作,提高搜索能力,从而保证寻优速度,得出最优配送路径。经过仿真后证明优化策略可行,达到对配送过程的最优化处理。

改进遗传算法; 路径优化; 时间窗约束

1 优化概述

物流配送路径的优化是传统的车辆路径优化问题,一直是物流行业的研究热点,也有许多思想方法被不断地提出、改进。但此类问题大多数较为复杂,无法在短时间内得出最优解,因此在现阶段的研究中,智能搜索的方法应用较为广泛[1～5]。但大多数方法只能解决局部区域内的车辆路径问题,在解决大规模车辆路径问题时,运算时间过长。针对这一问题,本文提出对传统遗传算法的改进措施,使得大规模问题更容易求解,实现对配送路径优化处理的目标。

2 构建VRPTW模型

在现代物流配送过程中,车辆路径的优化是一项综合性问题,受到广泛关注,其路线安排可以描述为:在客户需求位置、配送中心位置以及道路情况已知的情况下,对于m辆车,N个客户,在客户需求的时间窗范围[a,b]内安排确定的运输路线,使得成本最少,则可以构建如下所示的VRPTW模型[6]:

目标函数:

(1)

约束条件:

(2)

(3)

Tj+Ti≤Tko,k=1,2,…,m

(4)

在目标函数与约束条件中,各变量定义如表1所示。

表1 变量定义

默认车辆从配送中心出发的起始时间为0时刻,定义变量xijk与yjk默认值为1;式(2)表示配送车辆运载容量约束;式(3)表示配送车辆的配送服务是封闭的,最后必须回到配送中心;式(4)表示配送车辆的服务时间与行驶时间不得超过规定的返回时间范围。

3 改进遗传算法求解模型

本文对基本遗传算法[7～10]进行改进来求解VRPTW模型,具体实现步骤如下:

1) 改进染色体编码

将配送中心设定为编号0,各个客户按照1,2,…,N进行编号,每个客户编号固定不可变更,按客户需求安排路径子串,并首尾添0,形成染色体。如“0250”表示路径0→2→5→0。

2) 种群初始化

考虑到实际情况,将初始种群规模设定为60。

3) 计算适应度值

对目标函数取倒数,实现最大值与最小值之间的转换。即

(5)

4) 迭代判断及局部搜索

设置最大进化代数,求解时判断每次的迭代代数是否达到最大值,若达到,则停止迭代。选取最优个体进行局部搜索,直到获得最优解。

5) 遗传选择操作

每一次遗传操作均选择最优的个体直接复制到下一代,这样减少算法的总体操作个数,提高了寻优速度。

6) 交叉变异处理

随机选取交叉变异位置,一般来说,交叉变异的概率均由实验得出,保证了种群多样性与算法收敛性,确保最优结果顺利搜寻。

4 仿真结果分析

本文所提出的优化算法主要是将基本遗传算法与局部搜索算法结合,根据用户要求的时间窗范围,在不超载的情况下,当时间窗范围发生变化时,以最快速度寻求最优解,并及时调整配送路线,获得满足优化目标的最优路径。

1) 对其搜索效果进行验证,仿真时,设置种群规模为60,交叉率Pc=0.95,变异率Pm=0.05。实验结果对比如图1所示。

图1 算法改进前后适应度值对比图

实验结果表明,采用改进后的算法在进化代数达到一定值时,适应度值明显提高,证明优化后的寻优效果明显,寻优能力增强,保证了算法的实时性。

2) 当时间窗范围发生变化时,对算法改进前后的配送成本以及配送时间进行比较,客户的位置信息与时间窗范围如表2～3所示。

表2 客户位置信息(km)

当时间窗范围发生变化后,利用改进的遗传算法对车辆路径进行重新优化,得到两次实验结果为:优化前的配送成本为367.5(元/天),优化后的配送成本为284.7(元/天);优化前的运输时间为12(小时/天),优化后的运输时间为15(小时/天)。

表3 客户时间窗范围

试验结果表明,优化前后,虽然运输的时间略有增加,但配送成本明显降低,达到优化目的。

5 结语

针对目前快递行业的现状以及客户的不同需求建立了车辆路径问题的优化模型以及采用遗传算法对模型进行求解、仿真,实验结果表明基于遗传算法的路径优化方法能够有效解决带有软时间窗的路径优化问题,且运行结果可靠,证明优化策略有效可行。

[1] 关伟,王万平,于绪利.遗传算法在货物配送问题中的应用[J].交通运输系统工程与信息,2002,2:19-23. GUAN Wei, WANG Wanping, YU Xuli. The application of Genetic Algorithms in goods distribution problem[J]. Transportation Systems Engineering and Information,2002,2:19-23.

[2] 张良智,姜华平.基于遗传算法的交通流量组合预测[J].山东交通学院学报,2005,2:76-79. ZHANG Liangzhi, JIANG Huaping. Traffic flow combination forecasting based on genetic algorithm[J]. Journal of Shandong Jiaotong University,2005,2:76-79.

[3] 唐坤.车辆路径问题中的遗传算法设计[J].东华大学学报(自然科学版),2002,1:66-70. TANG Kun. Genetic algorithm design for vehicle routing problem[J]. Journal of Donghua University(Natural Sciences),2002,1:66-70.

[4] Barrie M, Baker MA, Ayechew. Agenetic algorithm for thevehicle routing problem[J]. Computers & Operations Research,2003,30:787-800.

[5] 姜大立,杨西龙,杜文,等.车辆路径问题的遗传算法研究[J].系统工程理论与实践,1999,6:41-46. JIANG Dali, YANG Xilong, DU Wen, et al. Research on genetic algorithm of the vehicle routing problem[J]. System Engineering Theory and Practice,1999,6:41-46.

[6] 蒋波.基于遗传算法的带时间窗车辆路径优化问题研究[D].北京:北京交通大学,2010. JIANG Bo. Research on the vehicle routing problem with time windows based on genetic algorithm[D]. Beijing: Beijing Jiaotong University,2010.

[7] 陈松岩,张良智,华相刚.遗传算法在车辆路径问题中的优化[J].山东交通学院学报,2006,3:42-47. CHEN Songyan, ZHANG Liangzhi, HUA Xianggang. Optimization of Genetic algorithm in vehicle routing problem[J]. Journal of Shandong Jiaotong University,2006,3:42-47.

[8] 周森.基于遗传算法的物流运输中的车辆路径问题研究[D].北京:对外经济贸易大学,2006. ZHOU Sen. Research on the vehicle routing problem in logistics transportation based on genetic algorithm[D]. Beijing: University of International Business and Economics,2006.

[9] 赵辰.基于遗传算法的车辆路径优化问题研究[D].天津:天津大学,2012. ZHAO Chen. Research on the optimization of vehicle routing problem based on genetic algorithm[D]. Tianjin: Tianjin University,2012.

[10] 詹孝龙.遗传算法在带时间窗的车辆路径问题中的应用[D].赣州:江西理工大学,2014. ZHAN Xiaolong. The application of genetic algorithm in vehicle routing problem with time windows[D]. Ganzhou: Jiangxi University of Technology,2014.

Method of Logistics Distribution Routing Optimization Based on Improved Genetic Algorithm

JIN Siting LV Shan WU Yangming WANG Yuyao

(School of Electrical and Information Engineering, Dalian Jiaotong University, Dalian 116028)

Based on the increase of the costs during distribution in current courier industry like slow speed, decline of service quality and so on, a method of logistics distribution routing optimization is proposed based on improved genetic algorithm. Improvements are made based on the basic genetic algorithm, time windows constraint to ensure real-time implementation of the algorithm, operation of genetic is optimized, the search ability is improved to ensure optimization speed, and the optimal distribution path is obtained. After simulation, the optimization strategy is proved to be feasible, and the optimization of the distribution process is achieved.

improved genetic algorithm, routing optimization, time windows constraint Class Number TP301

2016年10月9日,

2016年11月17日

金巳婷,女,硕士,研究方向:嵌入式技术、通信及关键技术。吕闪,女,硕士,研究方向:信号与信息处理、通信及关键技术。吴阳明,男,硕士,研究方向:信号与信息处理、通信及关键技术。王宇瑶,女,硕士,研究方向:轨道交通信号与控制、通信及关键技术。

TP301

10.3969/j.issn.1672-9722.2017.04.007