ISSN 0253-2778

CN 34-1054/N

Open AccessOpen Access JUSTC Original Paper

Asynchronous parallelism weighted A* algorithm for the finding shortest path on road networks

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2014.10.011
  • Received Date: 17 January 2014
  • Accepted Date: 19 May 2014
  • Rev Recd Date: 19 May 2014
  • Publish Date: 30 October 2014
  • Finding the shortest path is a classic problem with numerous applications. For road networks, it is desirable to find a sufficient short path within a limited period of time, and find a shorter path if there is more time. Since the traditional shortest path algorithms did not consider this constraint when designed, they can not meet the application requirement. To address this issue, an algorithm called APWA*, asynchronous parallelism weighted A*, was proposed, which can respond to users interrupt signal and return to the currently shortest path. Experiments on multiple maps show APWA* can meet the application requirement.
    Finding the shortest path is a classic problem with numerous applications. For road networks, it is desirable to find a sufficient short path within a limited period of time, and find a shorter path if there is more time. Since the traditional shortest path algorithms did not consider this constraint when designed, they can not meet the application requirement. To address this issue, an algorithm called APWA*, asynchronous parallelism weighted A*, was proposed, which can respond to users interrupt signal and return to the currently shortest path. Experiments on multiple maps show APWA* can meet the application requirement.
  • loading
  • [1]
    Morgan Stanley Global Technology & Telecom Reseach. The Mobile Internet Report[M]. America: Morgan Stanley Research, 2009.
    [2]
    中国互联网络信息中心.第28次中国互联网络发展状况统计报告[R].北京:中国互联网络信息中心,2011.
    [3]
    Federal Railroad Administration. Study of high-speed wireless data transmissions for railroad operation[R]. Department Of Transportation, US, 2007.
    [4]
    Eriksson J, Balakrishnan H, Madden S. Cabernet: Vehicular content delivery using wifi[C].// Proceedings of the 14th Annual International Conference on Mobile Computing and Networking. San Francisco, USA: ACM Press, 2008: 199-210.
    [5]
    朱铨,蒋新华,邹复民.交通干线无线宽带覆盖网络传输性能研究[J].计算机工程与应用,2012,48(9):15-17,50.
    [6]
    邹复民,蒋新华,林漳希,等.一种基于榕树型拓扑的铁路无线Mesh网络结构[J].铁道学报,2010,32(2):47-54.
    [7]
    康玉文,邹复民,康兴斌,等.几种典型车载移动环境的WiFi扫描机制研究[J].计算机工程与应用,2012,49(19):89-96.
    [8]
    邹复民,蒋新华,王桐森,等.一种支持车-地宽带互联的广义AP间切换模型[J].铁道学报,2011,33(2):45-51.
    [9]
    蒋新华,邹复民,王桐森,等.一种多无线模块快速切换方法,中国,200810071237[P].2009-12-23.
    [10]
    鄢丹,蒋新华,邹复民,等.采用多无线模块的AP间硬切换的实验研究[J].计算机工程与应用,2010,46(29):124-126.
    [11]
    鄢丹.车载WiFi应用快速AP间切换关键技术研究[D].长沙:中南大学,2011.
  • 加载中

Catalog

    [1]
    Morgan Stanley Global Technology & Telecom Reseach. The Mobile Internet Report[M]. America: Morgan Stanley Research, 2009.
    [2]
    中国互联网络信息中心.第28次中国互联网络发展状况统计报告[R].北京:中国互联网络信息中心,2011.
    [3]
    Federal Railroad Administration. Study of high-speed wireless data transmissions for railroad operation[R]. Department Of Transportation, US, 2007.
    [4]
    Eriksson J, Balakrishnan H, Madden S. Cabernet: Vehicular content delivery using wifi[C].// Proceedings of the 14th Annual International Conference on Mobile Computing and Networking. San Francisco, USA: ACM Press, 2008: 199-210.
    [5]
    朱铨,蒋新华,邹复民.交通干线无线宽带覆盖网络传输性能研究[J].计算机工程与应用,2012,48(9):15-17,50.
    [6]
    邹复民,蒋新华,林漳希,等.一种基于榕树型拓扑的铁路无线Mesh网络结构[J].铁道学报,2010,32(2):47-54.
    [7]
    康玉文,邹复民,康兴斌,等.几种典型车载移动环境的WiFi扫描机制研究[J].计算机工程与应用,2012,49(19):89-96.
    [8]
    邹复民,蒋新华,王桐森,等.一种支持车-地宽带互联的广义AP间切换模型[J].铁道学报,2011,33(2):45-51.
    [9]
    蒋新华,邹复民,王桐森,等.一种多无线模块快速切换方法,中国,200810071237[P].2009-12-23.
    [10]
    鄢丹,蒋新华,邹复民,等.采用多无线模块的AP间硬切换的实验研究[J].计算机工程与应用,2010,46(29):124-126.
    [11]
    鄢丹.车载WiFi应用快速AP间切换关键技术研究[D].长沙:中南大学,2011.

    Article Metrics

    Article views (19) PDF downloads(74)
    Proportional views

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return