ESTIMATION AND DETERMINATION OF SHORTEST-PATH LENGTH IN A ROAD NETWORK WITH OBSTACLES

被引：7

作者：

DUBOIS, N

SEMET, F

机构：

[1] ECOLE POLYTECH FED LAUSANNE,DEPT MATH,CH-1015 LAUSANNE,SWITZERLAND

[2] UNIV MONTREAL,CTR RECH TRANSPORTS,MONTREAL,PQ H3C 3J7,CANADA

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1995年 / 83卷 / 01期

关键词：

TRANSPORTATION; REGRESSION; SHORTEST PATH;

D O I：

10.1016/0377-2217(94)00015-5

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper presents a modelling of natural obstacles in a road network for improving the commonly applied lower bound on the distance between two points: the Euclidean distance. Then, two applications of this new lower bound are proposed: the estimation of distances and an improvement of the Dijkstra algorithm. In both cases, the numerical experiments performed using the Swiss road network lead to obtaining very good results. Indeed, distances are estimated with a low percentage error on average and CPU times required by the Dijkstra method are significantly lower than those previously measured.

引用

页码：105 / 116

页数：12

共 12 条

[1] ESTIMATING ROAD DISTANCES BY MATHEMATICAL FUNCTIONS [J].