首页 数学建模案例新型遗传模拟退火算法求解物流配送路径问题

数学建模案例新型遗传模拟退火算法求解物流配送路径问题

数学建模案例新型遗传模拟退火算法求解物流配送路径问题收稿日期:2003-10-09 基金项目:国家自然科学基金项目资助(60272040) 作者简介:阎庆(1978-),女,安徽六安人,硕士研究生,主要研究方向:地理信息系统在物流管理系统中的应用; 鲍远律(1947-),男,安徽六安人,教授,主要研究方向:控制理论与系统集成、全球定位系统GPS、交通矢量地图GIS、移动目标监控专用数字通信. 文章编号:1001-9081(2004)06Z-0261-03 新型遗传模拟退火算法求解物流配送路径问题阎庆,鲍远律 (中国科学技术大学自动化系,安...

收稿日期:2003-10-09 基金项目:国家自然科学基金项目资助(60272040) 作者简介:阎庆(1978-),女,安徽六安人,硕士研究生,主要研究方向:地理信息系统在物流管理系统中的应用; 鲍远律(1947-),男,安徽六安人,教授,主要研究方向:控制理论与系统集成、全球定位系统GPS、交通矢量地图GIS、移动目标监控专用数字通信. 文章编号:1001-9081(2004)06Z-0261-03 新型遗传模拟退火算法求解物流配送路径问题阎庆,鲍远律 (中国科学技术大学自动化系,安徽合肥230027) 摘要:文中提出了将遗传算法和模拟退火算法结合,并加入了记忆装置。根据这种想法设计了一种有记忆功能的遗传模拟退火算法,并进行了试验计算。结果表明:用这种有记忆功能的遗传模拟退火算法求解物流配送路径优化问题,可以在一定程度上解决一些问题,从而得到较高质量的解。关键词:物流配送;遗传模拟退火算法;遗传算法;模拟退火算法;路径优化中图分类号:TP301.6 文献标识码:A 1 引言物流配送是现代化物流管理中的一个重要环节。它是指按用户的定货要求,在配送中心进行分货、配货,并将配好的货物及时送交收货人的活动。在物流配送业务中,存在许多优化决策的问题。本文只讨论物流配送路径优化问题。物流配送路径优化问题最早是在1959年由Dantmig和Ramser首先提出的,即所谓的车辆路径问题VRP[1]。它也是目前在物流系统中较受关注的一个方面。它是指在客户需求位置已知的情况下,确定车辆在各个客户间的行程路线,使得运输路线最短或运输成本最低。VRP问题已经被证明是一个 NP- hard问题。也就是说当问题的规模较大时,很难得到全局最优解或满意解。而且随着问题规模的增大,算法的计算时间将以指数速度增加。因此研究的重点就转移到各种启发式算法上。求解物流配送路径优化问题的方法有很多,常用的有旅行商法、动态规划法、节约法、扫描法、分区配送法、方案评价法等。而遗传算法的出现为求解物流配送路径优化问题提供了新的工具。遗传算法[2]作为一种非数值并行算法,其思想起源于生物遗传学适者生存的自然规律。它对优化对象既不要求连续,也不要求可微,尤其适合求解NP-hard问题。到目前为止,已经有很多人都曾利用遗传算法求解物流配送路径优化问题并取得了一些研究成果。 2 物流配送路径优化问题的数学模型物流配送路径优化问题一般可以这样描述:从某物流配送中心用多辆配送车辆向多个客户送货。每个客户的位置和货物需求量一定,每辆车的载重量一定,其一次配送的最大行驶距离一定。要求合理安排车辆配送路线,使目标函数得到最优。并满足以下条件:(1)每条配送路径上各客户需求量之和不超过配送车辆的载重量;(2)每条配送路径的长度不超过配送车辆一次配送的最大行驶距离;(3)每个客户的需求必须满足,且只能由一辆配送车送货。设配送中心需要向k个客户送货,每个客户的货物需求量是gi(i=1,2,…,k),每辆配送车的载重量是q,且gi 分析实验初始数据取自参考文献[6]。实验1,随机生成1个有8个门店的VRP问题,初始数据如下: 表1 试验1初始数据门店配送中心门店1 门店2 门店3 门店4 门店5 门店6 门店7 门店8 位置 g31,9h g76,38h g77,16h g90,82h g60,74h g76,86h g11,31h g29,90h g10,60h 需求量 0 2.46 0.41 2.16 2.27 1.83 3.76 2.54 2.39 根据各仓库的需求量,计算出需要的汽车数: mk[17.82/(0.85*8)]i1k3,文献[6]采用传统的遗传算法的各算子,并对其中的交叉算子进行了改造,取群体规模为 20,进化代数为50,应用此程序他费时3s得到的结果为: 子路径1:0→8→7→4→0 子路径2:0→6→0 子路径3:0→5→1→2→3→0 运输距离成本:476.29 而我们的算法在上面的算法中加入了一个模拟退火算子,取初始退火温度为10,衰减系数取0.85使用第三节所述算法步骤,在奔腾四的计算机上计算,耗时2s,得结果如下: 子路径1:0→6→0 子路径2:0→2→1→3→5→0 子路径3:0→8→7→4→0 运输距离成本:476.290507 进化代数为:20 实验2,随机生成1个有20个门店的VRP问题,初始数据如下: 表2 试验2初始数据门店配送中心门店1 门店2 门店3 门店4 门店5 门店6 门店7 门店8 门店9 门店10 位置 g52,4h g15,49h g0,61h g51,15h g25,71h g38,62h g35,45h g100,41h g10,52h g26,79h g87,7h 需求量 0 1.64 1.31 1.43V3.38 1.13 3.773.48 0.39 0.24 1.03 续表2 门店门店11 门店12 门店13 门店14 门店15 门店16 门店17 门店18 门店19 门店20 位置 g24,89h g19,25h g20,99h g73,91h g100,95h g7,73h g69,86h g24,3h g66,14h g9,30h 需求量 0.24 2.60 1.00 0.65 0.58 2.56 2.69 3.26 2.97 计算得:需6辆车。用文献[6]的算法取群体规模 100,进化代数分别设为20,50,100,得到的结果不同: 表3 原来算法的结果实验 1 2 3 进化代数 20 50 100 运输成本 1153.12 964.48 908.44 而采用本文的算法,初始退火温度取10,衰减系数取0. 85,在奔腾四的计算机上计算,则结果如下: 表4 本算法的结果实验 1 2 3 进化代数 20 50 100 运输成本 1153.96 963.67 906.29 从以上两个实验可以看出:采用本文中所述的算法,要得到相同的结果可以缩短进化代数,从而节约运算时间。而采用相同的进化代数,虽然在进化代数较少时对结果的改进并不明显,但随着进化代数的增加,必然得到更好的结果。 5 结束语本文使用文献[6]中比较合理的交叉算子和变异算子,采用自然数编码将模拟退火算法与传统的遗传算法相结合,用来求解物流系统中车辆路径问题。这种算法所需的进化代数明显减少,获得了较好的结果。实验结果表明此算法在解决诸如车辆路径问题这类 NP-hard问题确实可行,并有较好的性能。而且随着问题规模的增大,这种缩短进化代数的效果将更加明显。参考文献 b1c 郭耀煌,李军著.车辆优化调度bMc.成都f成都科技大学, 1994. b2c 邢文训,谢金星.现代优化计算方法bMc.北京f清华大学出版社,1999.140. b3c 郎茂祥.物流配送车辆调度问题的模型和算法研究bDc.北京f 北方交通大学,2002. b4c 郎茂祥,胡思继.用混和遗传算法求解物流配送路径优化问题的研究bJc.中国管理科学,2002,10g5hf51-56. b5c 李军,谢秉磊,郭耀煌.非满载车辆调度问题的遗传算法bJc.系统工程理论与实践,2000,20g3hf235-239. b6c 唐坤.车辆路径问题中的遗传算法设计bJc.东北大学学报g自然科学版h,2002,28g1hf66-70. b7c 姜大立,杨西龙,杜文,等.车辆路径问题的遗传算法研究bJc. 系统工程理论与实践,199919g6hf40-45. 3626月阎庆等:新型遗传模拟退火算法求解物流配送路径问题

                    本文档为【数学建模案例新型遗传模拟退火算法求解物流配送路径问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

数学建模案例新型遗传模拟退火算法求解物流配送路径问题

你可能还喜欢