发明名称 | 一种含有多层次剪枝策略的位置查询优化方法 | ||
摘要 | 本发明提出一种含有多层次剪枝策略的位置查询优化方法,包括:S1、获取所有顶点到达最近设施的距离,包括客户顶点和路网顶点;S2、划分路网为区域;S3、计算划分后各区域的上界,按上界从大到小将区域进行排序;S4、依序逐一选择区域进行筛选,如已知的最大效益值大于当前需要筛选的区域上界,结束;否则计算当前区域各边上界,按上界从大到小将边进行排序;S5、依序逐一筛选区域内的边,如当前边的上界小于已知的最大效益值,则,结束该区域的筛选进入下一区域返回S4,否则使用边上的顶点剪枝策略对当前边上的顶点进行筛选,并同步更新最大效益值及其所在位置,然后进入下一条边,返回S5。 | ||
申请公布号 | CN106372265A | 申请公布日期 | 2017.02.01 |
申请号 | CN201611038447.3 | 申请日期 | 2016.11.23 |
申请人 | 中山大学 | 发明人 | 刘玉葆;徐葎;麦港林;戴戈南 |
分类号 | G06F17/30(2006.01)I | 主分类号 | G06F17/30(2006.01)I |
代理机构 | 广州粤高专利商标代理有限公司 44102 | 代理人 | 林丽明 |
主权项 | 一种含有多层次剪枝策略的位置查询优化方法,其特征在于,包括以下步骤:步骤一:获取所有顶点到达最近设施的距离,包括客户顶点和路网顶点;步骤二:划分路网为区域;步骤三:计算划分后各区域的上界,按上界从大到小将区域进行排序;步骤四:依序逐一选择区域进行筛选,如果已知的最大效益值大于当前需要筛选的区域上界,则说明最优位置已经全部找到,结束;否则进入步骤五;步骤五:计算当前区域各边上界,按上界从大到小将边进行排序;步骤六:依序逐一筛选区域内的边,如果当前边的上界小于已知的最大效益值,说明该区域中已没有其他边存在最优位置,结束该区域的筛选进入下一区域返回步骤四,否则进入步骤七;步骤七:使用边上的顶点剪枝策略对当前边上的顶点进行筛选,并同步更新最大效益值及其所在位置。然后进入下一条边,返回步骤六。 | ||
地址 | 510275 广东省广州市海珠区新港西路135号 |