• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Automated Planning and Scheduling(ICAPS 2006); 2006; >Optimal Route Planning under Uncertainty
【24h】

Optimal Route Planning under Uncertainty

机译：不确定条件下的最优路径规划

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We present new complexity results and efficient algorithms for optimal route planning in the presence of uncertainty. We employ a decision theoretic framework for defining the optimal route: for a given source S and destination T in the graph, we seek an ST-path of lowest expected cost where the edge travel times are random variables and the cost is a nonlinear function of total travel time. Although this is a natural model for route-planning on real-world road networks, results are sparse due to the analytic difficulty of finding closed form expressions for the expected cost (Fan, Kal-aba & Moore), as well as the computational/combinatorial difficulty of efficiently finding an optimal path which minimizes the expected cost. We identify a family of appropriate cost models and travel time distributions that are closed under convolution and physically valid. We obtain hardness results for routing problems with a given start time and cost functions with a global minimum, in a variety of deterministic and stochastic settings. In general the global cost is not separable into edge costs, precluding classic shortest-path approaches. However, using partial minimization techniques, we exhibit an efficient solution via dynamic programming with low polynomial complexity.
机译：我们提出了新的复杂性结果和在存在不确定性的情况下用于最佳路线规划的高效算法。我们采用决策理论框架来定义最佳路线：对于图中的给定源S和目的地T，我们寻求一条具有最低预期成本的ST路径，其中边缘移动时间是随机变量，而成本是的非线性函数。总旅行时间。尽管这是现实世界道路网络上路线规划的自然模型，但由于难以找到预期成本（风扇，卡拉巴和摩尔）的封闭式表达式以及计算/有效地找到使预期成本最小化的最佳路径的组合难度。我们确定了一系列适当的成本模型和旅行时间分布，这些模型在卷积作用下是封闭的，并且在物理上有效。在各种确定性和随机性设置下，我们获得了具有给定开始时间的路由问题的硬度结果，并且具有全局最小值的成本函数。总的来说，全球成本无法与边缘成本分开，这要排除经典的最短路径方法。但是，使用部分最小化技术，我们通过动态编程以低多项式复杂度展示了一种有效的解决方案。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号