资源描述：
《环状区域的车辆路径方案生成系统及优化模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第卷第期管理科学学报,年月,《卫①环状区域的车辆路径方案生成系统及优化模型‘,‘,胡祥培黄敏芳大连理工大学管理学院,大连伍斯特理工学院管理系,美国马萨诸塞州一摘要针对,以大幅度地缩减问题求顾客满足环状区域分布的车辆路径问题解的状态口,,空间为突破引入人工智能和运筹学理论提出求解这类特殊车辆路径问题的两阶段方法第阶段考虑行车时间和车载容量,提出带有控制策略的深度优先搜索算法自动生成备选的车辆路径方案集合第阶段将此备选方案集合归结为整数规划模型采用编程语言,构建了车辆路径方案生成系统并实现该系统与运筹学求
2、解软件的集成通过案例验证了上述方法及自动求解系统的有效性该项研究为解决环状配送区域的车辆路径问题这一难题提供了新方法关键词车辆路径问题方案生成系统人工智能整数规划模型一一一中图分类号文献标识码文章编号【引言解决一问题来说有着不可估量的作用因此大部分研究的文献主要是在构造各种高一‘「车辆路径规划是城区物流,质量的启发式算法上述两大类算法已用于配送的重要环节、。,解决大量的实际问题这些成果极大地推进了物车辆路径问题川一’,已被证实是问题〔〕该问题由和流配送中的研究但是当面临较大规模’,,,〔〕提出后一直是
3、运筹学与组合优化领域时上述算法显得力不从心算法的求解效研究的热点和难点问题之一率随着问题规模的增大而迅速降低其主要根源,近,在于随着问题规模的增大问题求解的状态空间四十多年来国内外学者在的求解理、方、,急剧膨胀大幅度地缩减问题求解的状态空间就论法算法方面取得了丰富的研究成果应用多种技术和工具建立了不少模型,并开发出相应成为求解大规模的关键问题之一,〕,,的求解系统’,在已有的研究成果中算法方面为了缩减问题求解的状态空间本文针对环的成果尤其突出,大致可分为精确算法状配送区域的提出两阶段求解方法它在根和启
4、发式包据客户分布、城市交通要道的布局等特点划分配括元启发式算法两大类精确算法方面的研送区域的基础上,第阶段引人人工智能状态究综述可参阅文献「」启发式算法是一种基于空,,,直观或经验构造的算法目标是在可接受的费用间搜索理论考虑行车时间和车载容量采用带有计算时间、占用空间等下得到待解决问题的满控制策略的深度优先搜索算法自动生成较好的车,一,意解而不是最优解考虑到是问辆路径方案集合这样就可以把相对较差的车辆题,而启发式方法能够比较快地得到满意解,这对路径方案从解答空间中舍去,以此来大大缩小可一一一一①收稿日
5、期修订日期基金项目国家杰出青年科学基金资助项目国家自然科学基金资助项目以教育部重点科研资助项目高等学校博士点基金资助项目辽宁省科学基金资助项目作者简介胡祥培一,男,安徽绩溪人,博士,教授,博士生导师￡一一管理科学学报年月行解,的状态空间第阶段应用运筹学规划理论率还是处理问题的实时应变能力方面都难以满足将,通生成的备选方案集合归结为整数规划模型需要本文的车辆路径方案生成系统和自动求解,,过构建车辆路径方案的生成系统实现该系统与系统就是为了应对这种动态变化而构建的它可运筹学求解软件。的集成,形成通用的自动
6、以由计算机实时生成最优的车辆路径方案求解系统,以应对城区物流配送过程中需求的动态变化,实时生成最优车辆路径方案,提高决策效车辆路径方案的生成方法率最后通过案例验证了上述方法及自动求解系统的有效性问题描述及变量的假设关于配送区域的划分问题,可能存在多种情本文研究的环状配送区域的可定义为,、、、况其几何形状也可能呈现出环状扇形块状条、、供货点可以为物流中心调度中心货场等拥状等多种结果以及它们的组合由于配送区域划有多种类,型不同的车载容量的车辆它需要在,分的复杂性因此将另撰文研究区域划分本文针’」指定时间段
7、内即硬时间窗给分布在周边的对配送区域满足环状分布的一类特殊提出客户送货,车辆在限定条件内为客户服务完后不车辆路径方案智能生成方法这类特殊的详必回到供货点这类属于开放式车辆路径问细描述见节该问题的求解目标是找出最少题根据某一指标或特征如配送时间、车辆的最优路径方案集合这类涉及的参数配送费用、城市交通要道的布局等将配送区域,、较多如配送区域的种类各种配送区域中客户的进行划分本文研究的是环状配送区域的,、、数量供货点到达各配送区域所需的行车时间各这类问题在我国具有典,型性国内有部分大城市客户之间相互到达所需
8、的行车时间等,这些参数如北京、成都等市内的环状快速路简称环路,都不尽相同因此车辆路径方案集合具有数据量形成了城市的交通要道由于环路具有交通状况、、,,,大种类多数据之间关系复杂等特点虽然可以良好没有红绿灯限制不易堵车等特点因此根用手工方法寻找和列举出车辆路径方案的集合,据环路及环路的配送辐射带划分配送区域图并用传统的,所示的就是环状配送区域的车辆路径问题示意运筹学规划理论进行求解这样也可,以解决这类特殊的,但是随着客户数量、客图同一环状区域内的客户属于同
