一类动态车辆路径问题模型和两阶段算法

发布时间：2017-09-05 09:14

  本文关键词：一类动态车辆路径问题模型和两阶段算法

  更多相关文章： 物流工程 两阶段算法 动态车辆路径问题 K-d树分割策略 算法搜索解空间

【摘要】：针对一类动态车辆路径问题,分析4种主要类型动态信息对传统车辆路径问题的本质影响,将动态车辆路径问题(Dynamic Vehicle Routing Problem,DVRP)转化为多个静态的多车型开放式车辆路径问题(The Fleet Size and Mixed Open Vehicle Routing Problem,FSMOVRP),并进一步转化为多个带能力约束车辆路径问题(Capacitated Vehicle Routing Problem,CVRP),基于CVRP模型建立了DVRP模型;然后,在分析DVRP问题特点基础上,提出两阶段算法,第一阶段基于利用K-d trees对配送区域进行分割的策略,提出了复杂度仅为O(nlogn)的快速构建型算法,第二阶段通过分析算法搜索解空间结构原理,设计混合局部搜索算法;最后,基于现有12个大规模CVRP标准算例,设计并求解36个DVRP算例.求解结果表明了模型和两阶段算法的有效性.
【作者单位】： 山东科技大学经济管理学院;大连理工大学系统工程研究所;东北财经大学管理科学与工学院;
【关键词】： 物流工程 两阶段算法 动态车辆路径问题 K-d树分割策略 算法搜索解空间
【基金】：国家自然科学基金(71271041) 山东省优秀中青年科学家科研奖励基金(BS2014SF001) 山东科技大学人才引进基金(RCJJ2013020) 山东省软科学研究计划项目(2014RKB01506)
【分类号】：U492.22
【正文快照】： 1引言车辆路径问题(Vehicle Routing Problem,VRP)自1959年Dantzig等[1]提出以来一直受到人们的广泛关注,其研究意义毋庸置疑.随着移动通讯(Global System of Mobile communication,GSM)、电子商务(Electronic Commerce,EC)、全球定位系统(Global Positioning System,GPS)和智

【参考文献】

中国期刊全文数据库 前7条

1 郭耀煌,谢秉磊;一类随机动态车辆路径问题的策略分析[J];管理工程学报;2003年04期

2 葛显龙;王旭;邓蕾;;基于联合配送的开放式动态车辆路径问题及算法研究[J];管理工程学报;2013年03期

3 饶卫振;金淳;;求解大规模CVRP问题的快速贪婪算法[J];管理工程学报;2014年02期

4 郭耀煌;钟小鹏;;动态车辆路径问题排队模型分析[J];管理科学学报;2006年01期

5 陈久梅;张旭梅;肖剑;但斌;;随机动态装卸混合问题的分区求解策略[J];管理科学学报;2012年01期

6 刘霞;齐欢;;带时间窗的动态车辆路径问题的局部搜索算法[J];交通运输工程学报;2008年05期

7 谢秉磊,郭耀煌,郭强;动态车辆路径问题:现状与展望[J];系统工程理论方法应用;2002年02期

【共引文献】

中国期刊全文数据库 前10条

1 徐新明;陈培友;;物流调度问题的优化方法评述[J];商业研究;2009年05期

2 黄作维;张喜梅;;GIS支持下的物流配送系统研究[J];江西师范大学学报(自然科学版);2009年01期

3 李林波;吴兵;;2010年上海世博会行李跟随系统[J];城市交通;2009年03期

4 郑国华;周小强;张力敏;;基于时间窗的城市医药品动态配送路径优化模型与算法[J];铁道科学与工程学报;2011年04期

5 杨文超;胡祥培;王征;;顾客时间窗变化的物流配送问题干扰管理方法研究[J];大连理工大学学报;2012年02期

6 肖增敏,李军;动态网络车辆路径问题:研究现状及展望[J];系统工程;2004年07期

7 刘兴,贺国光,高文伟;一种有时间约束的多车辆协作路径模型及算法[J];系统工程;2005年04期

8 孙丽君;胡祥培;王征;;车辆路径规划问题及其求解方法研究进展[J];系统工程;2006年11期

9 李永先;胡祥培;熊英;;基于eM-Plant的车辆路径问题仿真模型[J];系统工程;2007年06期

10 陆朝荣;朱焕勤;刘新建;;有严格时间限制大宗物资运输问题研究[J];工业工程;2006年05期

中国重要会议论文全文数据库 前3条

1 杨世坚;陈韬;;随机车辆路径问题研究综述[A];中国系统工程学会决策科学专业委员会第六届学术年会论文集[C];2005年

2 饶卫振;金淳;刘锋;杨磊;;动态车辆路径问题的模型及快速两阶段算法研究[A];中国系统工程学会第十八届学术年会论文集——A03系统科学理论研究创新[C];2014年

3 XU Zhengzheng;TANG Jiafu;;Customer Point Collaboration-Based Multi-trip Vehicle Scheduling Algorithm to Pickup and Delivery Service to Airport[A];第26届中国控制与决策会议论文集[C];2014年

中国博士学位论文全文数据库 前10条

1 彭北青;第三方物流配送车辆路径问题模型及算法研究[D];华中科技大学;2009年

2 王艳玲;取货车辆动态调度问题研究[D];北京交通大学;2010年

3 孙丽君;物流配送干扰管理问题的知识表示与建模方法[D];大连理工大学;2011年

4 施朝春;基于供应链的汽车零部件库存与运输整合优化研究[D];重庆大学;2010年

5 林云;汽车物流服务供应链体系构建与应用研究[D];重庆大学;2011年

6 葛显龙;面向云配送模式的车辆调度问题及算法研究[D];重庆大学;2011年

7 陈森;基于可变路网结构的应急资源调度问题研究[D];国防科学技术大学;2011年

8 谢秉磊;随机车辆路径问题研究[D];西南交通大学;2003年

9 余福茂;关于物流系统规划若干关键技术的研究[D];浙江大学;2003年

10 张建勇;模糊信息条件下车辆路径问题研究[D];西南交通大学;2004年

中国硕士学位论文全文数据库 前10条

1 周伟武;基于GIS烟草配送线路优化技术的研究[D];浙江理工大学;2010年

2 陈加萍;图转换方法求解带时间窗的时间依赖中国邮路问题[D];大连理工大学;2010年

3 蔡翱鹏;遗传算法在动态车辆调度问题中的研究[D];长沙理工大学;2010年

4 谷金媛;面向动态调度的邮政运输信息资源整合研究[D];昆明理工大学;2008年

5 吴丽荣;响应需求的园区巴士实时调度模型研究[D];大连理工大学;2011年

6 王涛;带多重交通网络的联盟运输调度问题的差分进化算法研究[D];广东工业大学;2011年

7 杨娟;带服务优先级的煤矿物资配送车辆路径问题研究[D];中国地质大学;2011年

8 邓敏皓;SOA-BPM物流信息平台下的车辆路径选择研究[D];中南大学;2011年

9 钱艳婷;动态多目标车辆路径问题的算法研究[D];天津理工大学;2011年

10 李文忠;有捎带的车辆路径问题的研究[D];西南交通大学;2010年

【二级参考文献】

中国期刊全文数据库 前10条

1 石洪波,郎茂祥;JD多车型配送车辆调度问题的模型及其禁忌搜索算法研究[J];长沙交通学院学报;2005年03期

2 熊浩;胡列格;;多车型动态车辆调度及其遗传算法[J];系统工程;2009年10期

3 郭耀煌,谢秉磊;一类随机动态车辆路径问题的策略分析[J];管理工程学报;2003年04期

4 李冰;;多车型确定性动态车辆调配问题[J];管理工程学报;2006年03期

5 张建勇;李军;;具有模糊旅行时间的VRP的一种混合遗传算法[J];管理工程学报;2006年04期

6 宋卫斌,苏秦;虚拟顾客服务系统排队模型[J];管理科学学报;2001年03期

7 郭耀煌;钟小鹏;;动态车辆路径问题排队模型分析[J];管理科学学报;2006年01期

8 李延晖;刘向;;沿途补货的多车场开放式车辆路径问题及蚁群算法[J];计算机集成制造系统;2008年03期

9 张景玲;赵燕伟;王海燕;介婧;王万良;;多车型动态需求车辆路径问题建模及优化[J];计算机集成制造系统;2010年03期

10 杨瑞臣,周永付,云庆夏;寻找车辆最优路径的混合算法[J];交通运输工程学报;2005年01期

中国硕士学位论文全文数据库 前1条

1 钟小鹏;动态车辆路径问题实时策略与技术支撑分析[D];西南交通大学;2003年

【相似文献】

中国期刊全文数据库 前10条

1 曹二保;赖明勇;张汉江;;模糊需求车辆路径问题研究[J];系统工程;2007年11期

2 唐连生;梁剑;;突发事件下的车辆路径问题研究综述[J];铁道运输与经济;2008年12期

3 刘红梅;陈杨;;车辆路径问题的形式化方法研究[J];科技资讯;2008年05期

4 徐俊杰;;利用微正则退火算法求解车辆路径问题[J];安庆师范学院学报(自然科学版);2009年02期

5 宁晓利;;车辆路径问题的组合优化算法[J];物流技术;2009年06期

6 黄敏芳;胡祥培;王征;Amy Z. Zeng;;车辆路径问题的三阶段求解方法研究[J];管理科学;2009年03期

7 孙中悦;关忠良;范高贤;;面向对象的车辆路径问题仿真研究[J];物流技术;2010年07期

8 李琳;刘涛;;带收益的车辆路径问题研究综述[J];沈阳航空工业学院学报;2010年05期

9 王科峰;叶春明;唐国春;;节点具有双重需求的车辆路径问题及其性质[J];系统科学与数学;2011年10期

10 谢秉磊;胡小明;张一U，

本文编号：797116