用混合遗传算法求解物流配送路径优化问题其研究.pdf

文章编号: ! " " # $ % " & ( % " " % ) " ’$ " " ’! $ " ( 用混合遗传算法求解物流配送路径优化问题的研究郎茂祥, 胡思继( 北方交通大学交通运输学院, 北京! " " " ) ) ) 摘要: 论文建立了物流配送路径优化问题的数学模型, 并针对遗传算法在局部搜索能力方面的不足, 提出将爬山算法与遗传算法相结合, 从而构造了求解物流配送路径优化问题的混合遗传算法, 并进行了实验计算。计算结果表明, 用混合遗传算法求解物流配送路径优化问题, 可以在一定程度上克服遗传算法在局部搜索能力方面的不足和爬山算法在全局搜索能力方面的不足, 从而得到质量较高的解。关键词: 物流配送; 混合遗传算法; 遗传算法; 爬山算法; 优化中图分类号: * + # ! : , % % ) 文献标识码: - 收稿日期: % " " ! $ " . $ " + 作者简介: 郎茂祥( ! + ( + $ ) , 男( 汉族) , 山东高唐人, 北京交通大学交通运输学院, 副教授, 研究方向: 交通运输规划与管理! 引言物流配送是现代化物流系统的一个重要环节, 它是指按用户的订货要求, 在配送中心进行分货、配货, 并将配好的货物及时送交收货人的活动。在物流配送业务中, 存在许多优化决策问题, 本文只讨论物流配送路径优化问题。合理选择配送路径, 对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。由于配送路径优化问题是一个/ 0 难题, 因此, 用启发式算法求解该问题就成为人们研究的一个重要方向。求解配送路径优化问题的方法很多, 常用的有旅行商法、动态规划法[ ! ] 、节约法[ % ] 、扫描法[ # ] 、分区配送算法[ ) ] 、方案评价法[ ’] 等。遗传算法的出现为求解物流配送路径优化问题提供了新的工具。 1 2 3 4 5 6 7 8 、 9 : 7 ; < 6 3 = 、, > 5 ? 、姜大立、李大卫、李军、谢秉磊、张涛等人都曾利用遗传算法求解物流配送路径优化问题[ ( $ ! ’] , 并取得了一些研究成果。作者也尝试采用新的编码方法和遗传算子构造了求解配送路径优化问题的遗传算法, 并进行了实验计算[ ! ( ] 。计算结果表明, 尽管用遗传算法可以求得物流配送路径优化问题的可行解或满意解, 但总体上解的质量不是很高, 有时其计算结果比爬山算法还要差。究其原因, 是由于遗传算法局部搜索能力不强造成的。为此, 作者将局部搜索能力很强的爬山算法与全局搜索能力很强的遗传算法结合, 从而构造了求解物流配送路径优化问题的混合遗传算法, 并通过实验计算证明了该算法的良好寻优性能。" 物流配送路径优化问题的数学模型物流配送路径优化问题可以描述为: 从某物流中心用多台配送车辆向多个客户送货, 每个客户的位置和货物需求量一定, 每台配送车辆的载重量一定, 其一次配送的最大行驶距离一定, 要求合理安排车辆配送路线, 使目标函数得到优化, 并满足以下条件:( ! ) 每条配送路径上各客户的需求量之和不超过配送车辆的载重量;( % ) 每条配送路径的长度不超过配送车辆一次配送的最大行驶距离;( # ) 每个客户的需求必须满足, 且只能由一台配送车辆送货。设物流中心有@ 台配送车辆, 每台车辆的载重量为! A ( A B ! , % , ?, @ ) , 其一次配送的最大行驶距离为" A , 需要向 C 个客户送货, 每个客户的货物需求量为# ? ( ? B ! , % , ?, C ) , 客户? 到 D 的运距为$ ? D , 物流中心到各客户的距离为$ " D ( ? 、 D B ! , % , ?, C ) , 再设% A 为第 A 台车辆配送的客户数( % A B " 表示未使用第 A 台车辆) , 用集合& A 表示第 A 条路径, 其中的元素’ A ? 表示客户’ A ? 在路径 A 中的顺序为? ( 不包括物流中心) , 令’ A " B " 表示物流中心, 若以配送总里程最短为目标函数, 则可建立如下物流配送路径第! " 卷第’期% " " % 年! " 月中国管理科学* 5 ? E 2 F 2 G 6 H 3 E : 7 6 I 9 : E : = 2 ; 2 E 4 J > ? 2 E > 2 K 6 7 L ! " , / 6 L ’, > 4 L , % " " % 万方数据优化问题的数学模型: ! " # ! " ! # $ " $ [ ! % $ & " $ ’( $ ( & ) $ ) ( $ & * ’( $ % $ ( $ % · + & , % ( % $ ) ] ( $ ) & ’( ’! % $ & " $ - ( $ & " . $ ( ) ) ! % $ & " $