.png){kind=icon}
返回
Mutually Beneficial Confluent Routing
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2016.2590435.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We investigate a new multi-user routing problem: mutually beneficial confluent routing (MCR). In the MCR, every user has his/her own source and destination; confluences of user routes occur so that users can mutually benefit from travelling together on the confluences. The idea of gaining benefit from travelling together is valuable in various practical applications, such as ride sharing, delivery routing, and pedestrian navigation. We formulate the MCR as a new combinatorial optimization problem on road networks. The MCR is more general and complex than single vehicle routing problems, ride-sharing problems, and the Steiner tree problem. We propose exact and efficient algorithms for the MCR for the setting of two or three users. The setting is reasonable for various practical applications. The key ideas of our algorithms are to use confluence patterns of the optimal solutions and exploit the properties of geometric graphs. Experimental results obtained on large scale road networks reveal that our algorithms are sufficiently efficient.
Keyword:
Combinatorial optimization on graphs
routing problem
confluent routes
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.4
论文数:
6.9K
被引数:
3.2W
机构
引用论文
.png){kind=icon}
The travelling salesman problem with time windows: Adapting algorithms from travel-time to makespan optimization带时间窗的旅行推销员问题: 从旅行时间到makespan优化的适应算法
PREAI
分享收藏
查看更多内容