A new model for path planning with interval data

doi:10.1016/j.cor.2008.06.002

CSpace > 应用数学研究所

	A new model for path planning with interval data
	Chen, Xujin; Hu, Jie; Hu, Xiaodong
	2009-06-01
发表期刊	COMPUTERS & OPERATIONS RESEARCH
ISSN	0305-0548
卷号	36 期号:6 页码:1893-1899
摘要	In this paper, we establish a new model for path planning with interval data which arises in a variety of applications. It is formulated as minimum risk-sum path problem: given a source-destination pair in a network G = (V, E), traveling on each link e in G may take time x(e) in a prespecified interval [l(e), u(e)] and take risk (u(e) - x(e))/(u(e) - l(e)), the goal is to find a path in G from the source to the destination, together with an allocation of travel times along each link on the path, so that the total travel time of links on the path is no more than a given time bound and the risk-sum over the links on the path is minimized. Our study shows that this new model has two features that make it different from the existing models. First, the minimum risk-sum path problem is polynomial-time solvable, and second, it provides many solutions that vary with time bounds and risk sums and leaves the choice for decision makers. Therefore, the new model is more flexible and easier to use for the path planning with interval data. (C) 2008 Elsevier Ltd. All rights reserved.
关键词	Path planning Minimum risk-sum Interval data
DOI	10.1016/j.cor.2008.06.002
语种	英语
WOS研究方向	Computer Science ; Engineering ; Operations Research & Management Science
WOS类目	Computer Science, Interdisciplinary Applications ; Engineering, Industrial ; Operations Research & Management Science
WOS记录号	WOS:000262120300019
出版者	PERGAMON-ELSEVIER SCIENCE LTD
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/7578
专题	应用数学研究所
通讯作者	Chen, Xujin
作者单位	Chinese Acad Sci, Inst Appl Math, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Chen, Xujin,Hu, Jie,Hu, Xiaodong. A new model for path planning with interval data[J]. COMPUTERS & OPERATIONS RESEARCH,2009,36(6):1893-1899.
APA	Chen, Xujin,Hu, Jie,&Hu, Xiaodong.(2009).A new model for path planning with interval data.COMPUTERS & OPERATIONS RESEARCH,36(6),1893-1899.
MLA	Chen, Xujin,et al."A new model for path planning with interval data".COMPUTERS & OPERATIONS RESEARCH 36.6(2009):1893-1899.