基于时间依赖的物联网络模型的路径规划

广西师范大学学报（自然科学版） ›› 2013, Vol. 31 ›› Issue (3): 152-156.

基于时间依赖的物联网络模型的路径规划

杨俊瑶, 蒙祖强

广西大学计算机与电子信息学院,广西南宁530004

收稿日期:2013-05-28 出版日期:2013-09-20 发布日期:2018-11-26
通讯作者: 杨俊瑶(1986—),男,湖南娄底人,广西大学硕士研究生。E-mail:faerysword@163.com
基金资助:
国家自然科学基金资助项目(61063032);广西自然科学基金资助项目(2012GXNSFAA053225)

Path Planning Based on Time-dependent Logistics Networks Model

YANG Jun-yao, MENG Zu-qiang

College of Computer and Electronic Information,Guangxi University,Nanning Guangxi 530004,China

Received:2013-05-28 Online:2013-09-20 Published:2018-11-26

摘要/Abstract

摘要： 本文针对基于物联网的物流网络中路径代价的时变性,建立一种时间依赖的物联网络模型,并在此基础上研究物流路径规划问题。针对现实中预测准确性随时间推移而降低,以及在预知程度较低时无法获得较好的路径规划等问题,提出一种带弧代价预知程度参数的最小时间路径算法SWPL以及基于SWPL的逐步规划解决方案。该算法考虑了预测的精度问题,在传统Dijkstra算法的基础上引入一种与时间相关的弧代价计算方法。实验表明,在预知程度较高和在预知程度较低但采用逐步规划的解决方案2种情况下,都能取得良好的路径规划效果。

关键词: 物联网, 路径规划, 时间依赖网络, 最小时间路径算法

Abstract: For the cost of path in logistics networks based on Internet in which things are always varying with time,this paper proposes a time-dependent networks,and studies the logistics path planning problem based on it.For the accuracy of predict decreasing with time in reality,and when the predict level is low it is hard to get a good path planning result,a minimum-time path algorithm with arc cost predict level parameter(SWPL) and a solution with step by step strategy based on SWPL.In this algorithm,the accuracy of predict is taken into consideration,and an arc cost computing method based on traditional Dijkstra algorithm.The experimental result shows that a good path planning result can be obtained when the predict level is high or when the predict level is low but step by step solution is applied.

Key words: internet of things, path planning, time-dependent networks, minimum-time path algorithm

中图分类号:

TP391.9

杨俊瑶, 蒙祖强. 基于时间依赖的物联网络模型的路径规划[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 152-156.

YANG Jun-yao, MENG Zu-qiang. Path Planning Based on Time-dependent Logistics Networks Model[J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(3): 152-156.

参考文献

[1] 谭国真,高文.时间依赖的网络中最小时间路径算法[J].计算机学报,2002,25(2):165-172.
[2] DREYFUS S E.An appraisal of some shortest path algorithms[J].Operations Research,1969,17(3):395-412.
[3] KAUFMAN D E,SMITH R L.Fastest path in time-dependent network for intelligent vehicle-highway systems application[J].IVHS Journal,1993,11(1):1-11.
[4] ORDA A,ROM R.Shortest path and minimum-delay algorithms in networks with time-dependent edge-length[J].Journal of the ACM,1990,37(3):607-625.
[5] ORDA A,ROM R.Distributed shortest path protocols for time dependent networks[J].Distributed Computing,1996,10(1):49-62.
[6] 韩平阳,罗五明,王志敏,等.动态网络中的最短路径改进算法[J].军事运筹与系统工程,2007,21(1):46-50.
[7] 余伟辉,陈闳中.时间依赖网络中非FIFO弧的转化研究[J].小型微型计算机系统,2009,30(1):156-158.
[8] 龙科军,王赛政,肖向良.面向驾驶员特性的路径规划算法[J].计算机工程,2011,37(5):264-267.
[9] 陈京荣,俞建宁,李引珍.多属性随机时间依赖网络路径优化[J].西南交通大学学报,2012,47(2):291-298.
[10] 孙奥,朱桂斌,江铁.基于预测信息的时间依赖网络路径规划算法[J].计算机工程,2012,38(22):133-136.
[11] TIAN Ye,CHIU Yi-chang,GAO Yang.Variable time discretization for a time-dependent shortest path algorithm[C]//Proceedings of the 14th International IEEE Conference on Intelligent Transportation Systems.Washington D C:IEEE Computer Society,2011:588-593.
[12] KHANI A,LEE S,HICKMAN M,et al.Intermodal path algorithm for time-dependent auto network and scheduled transit service[J].Transportation Research Record:Journal of the Transportation Research Board,2012,2284:40-46.
[13] GAO S,HUANG H.Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks[J].Transportation Research Part C,2012,21(1):196-213.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed