原文传递
考虑交叉口转向的最短路径拍卖算法
| 专利名称： | 考虑交叉口转向的最短路径拍卖算法 |
| 摘要： | 本发明公开了一种考虑交叉口转向的最短路径拍卖算法，涉及对道路最短路径网络表示 方法的改进。该方法先根据路段信息和结点信息构建星型数据结构，然后指定路径起点和终 点，从起点产生初始路径，计算路径末结点对所有下游结点的估计量，并与路径末结点的价 值量作比较：当某一估计量与路径末结点价值量相等时，延伸路径至该估计量对应的下游结 点，当估计量都大于路径末结点价值量时，取路径末结点价值量为最小的估计量，并将路径 收缩一个结点。如此重复迭代过程直至路径延伸至终点，此时的路径即为起止点之间的最短 路径。本方法能够准确地求解限制网络中的最短路径，具有更快的运算速度，继承了原始算 法易用于并行计算的基本性质。 |
| 专利类型： | 发明专利 |
| 申请人： | 东南大学 |
| 发明人： | 程 琳;杜牧青 |
| 专利状态： | 有效 |
| 申请日期： | 2009-06-11T00:00:00+0800 |
| 发布日期： | 2019-01-01T00:00:00+0800 |
| 申请号： | CN200910033091.8 |
| 公开号： | CN101571404 |
| 代理机构： | 南京经纬专利商标代理有限公司 |
| 代理人： | 许 方 |
| 分类号： | G01C21/34(2006.01)I |
| 申请人地址： | 210096江苏省南京市玄武区四牌楼2号 |
| 主权项： | 1、一种考虑交叉口转向的最短路径拍卖算法，其特征在于包括如下步骤： 对于有向网络G(V，E，A，D)： (1)给定路径起点r和终点s，在价格矢量p中为路径起点r增设虚拟上游结点0； (2)初始化路径P和价格矢量p： P＝(r)，pl，k＝0， |
| 所属类别： | 发明专利 |
检索历史
应用推荐
