...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Euler is standing in line dial-a-ride problems with precedence-constraints
【24h】

Euler is standing in line dial-a-ride problems with precedence-constraints

机译：欧拉站在优先约束的排队拨号问题中

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

摘要

In this paper we study algorithms for "Dial-a-Ride" transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and approximation algorithms for general graphs and trees with performances of 9/4 and 5/3, respectively.
机译：在本文中，我们研究了“ Dial-a-Ride”运输问题的算法。在问题的基本版本中，我们为图的顶点之间提供了运输作业，目标是找到可以满足所有作业需求的最短运输。众所周知，即使在树上，这个问题也很难解决。当给出具有相同来源的作业之间的优先关系时，我们考虑扩展。我们的结果包括针对路径的多项式时间算法和针对一般图和树的逼近算法，其性能分别为9/4和5/3。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号