资源描述：
《有时间窗车辆路径问题的模型及其改进模拟退火算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、管理工程学报Vol20,No3JournalofIndustrialEngineeringEngineeringManagement2006年第3期有时间窗车辆路径问题的模型及其改进模拟退火算法研究杨宇栋,朗茂祥,胡思继(北京交通大学交通运输学院,北京100044)摘要:论文在对有时间窗车辆路径问题进行描述的基础上,建立了该问题的基于直观描述的数学模型。论文还根据有时间窗车辆路径问题的特点构造了求解该问题的改进模拟退火算法,并进行了实验计算。计算结果表明,用本文设计的改进模拟退火算法求解有时
2、间窗车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定。关键词:车辆路径问题;模拟退火算法;时间窗中图分类号:F2243文献标识码:A文章编号:10046062(2006)030104040引言效率较高,收敛速度较快的优点。最后论文还通过实验计算车辆路径问题(VRP,VehicleRoutingProblem)是运筹学与证明了这种改进模拟退火算法的良好寻优性能。组合优化领域的前沿与热点问题。在现实生产和生活中,邮政投递问题、飞机、铁路列车、水运船舶及公共汽
3、车的调度问1有时间窗车辆路径问题的数学模型题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题为了使问题易于理解,本文用一个有时限配送车辆调度等都可以抽象为车辆路径问题。按客户对送货时间的要求,问题描述有时间窗车辆路径问题。该问题可以描述为:从某车辆路径问题可分为无时限问题(客户对货物的送到时间无物流中心用多台配送车辆向多个客户送货,每个客户的位置具体要求)和有时限问题(客户要求将需求的货物在规定的和需求量一定,要求将货物送到的时间窗一定,每台配送车时间窗内送到,也称为有时间窗问题)。随着企业JIT(Justin辆
4、的载重量一定,其一次配送的最大行驶距离一定,要求合time)战略的实施,零库存成为许多企业追求的目标,于是客理安排车辆配送路线和行车时间,使目标函数得到优化,并户对货物的送到时间提出了更高的要求。因此,研究有时间满足以下约束条件:(1)每条配送路径上各客户的货物需求窗车辆路径问题具有十分重要的现实意义。量之和不超过配送车辆的载重量;(2)每条配送路径的长度SungChulHong,XiongChen,K.C.Tan,HoongChuinLau,谢不超过配送车辆一次配送的最大行驶距离;(3)每个客户的[1~6]秉磊,叶
5、耀华等都曾研究过有时间窗车辆路径问题,并货物需求必须满足,且只能由一台配送车辆送货;(4)货物必取得了很多研究成果。但现有研究建立的有时间窗车辆路须在客户指定的时间窗内送到。径问题的数学模型多为基于网络图的模型,上述模型具有决设物流中心有K台配送车辆,车辆k的载重量为Qk(k策变量、约束条件和目标函数的表示复杂、抽象、不易理解等=1,2,,K),其一次配送的最大行驶距离为Dk,需要向L缺点,本文在现有研究的基础上建立了有时间窗车辆路径问个客户送货,客户i的需求量为qi(i=1,2,,L),且要求货题的基于直观描述的数学
6、模型,该模型考虑了较为接近实际的约束条件和目标函数,并具有简单、直观、易于理解、易于物在时间范围[ai,bi]内运到,客户i到j的运距为dij,物流设计算法求解及可扩充性强等特点。中心到各客户的距离为d0j(i、j=1,2,,L);设si表示车辆模拟退火算法的出现,为求解车辆路径问题提供了新的到达客户i的时刻,ti表示车辆在客户i的等待时间,tij表示工具。近年来,Osman、AlexVan、Teodorovic、蔡延光、刘浩等人配送车辆由客户i行驶到客户j的旅行时间;ta表示每吨货[7~11]都曾利用模拟退火算法求解
7、车辆路径问题,并取得了一物的卸车时间;再设nk为第k辆车配送的客户数(nk=0表些研究成果,但上述研究一般仅限于对无时限车辆路径问题示未使用第k台车辆),用集合Rk表示第k条路径,其中的的求解,有关用模拟退火算法求解有时间窗车辆路径问题的元素rki表示客户rki在路径k中的顺序为i(不包括物流中研究很少。本文在建立有时间窗车辆路径问题的基于直观描述的数学模型的基础上,基于文献[12]所设计的客户直接心),令rk0=0表示物流中心,s0=0表示配送车辆从物流中排列的解的表示方法构造了求解该问题的改进模拟退火算心出发的时刻
8、为0。取目标函数为配送总里程最短;则可建法,该算法具有解的表示自然直观,算法策略易于理解,计算立如下有时间窗车辆路径问题的基于直观描述的数学模型:收稿日期:20040518修回日期:20041217作者简介:杨宇栋(1968),男(汉族),辽宁省人,北京交通大学交通运输学院在职博士研究生,北京铁路局大同铁路分局高级工程
