.png){kind=icon}
返回
The Stochastic Eulerian tour problem
.png){kind=icon}
OA
AI
DOI：10.1287/trsc.1080.0232.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper defines the stochastic Eulerian tour problem (SETP) and investigates several characteristics of this problem. Given an undirected Eulerian graph G = (V, E), a subset R (vertical bar R vertical bar = n) of the edges in E that require service, and a probability distribution for the number of edges in R that have to be visited in any given instance of the graph, the SETP seeks an a priori Eulerian tour of minimum expected length. We derive a closed-form expression for the expected length of a given Eulerian tour when the number of required edges that have to be visited follows a binomial distribution. We also show that the SETP is NP-hard, even though the deterministic counterpart is solvable in polynomial time. We derive further properties and a worst-case ratio of the deviation of the expected length of a random Eulerian tour from the expected length of the optimal tour. Finally, we present some of the desirable properties in a good a priori tour using illustrative examples.
Keyword:
arc routing
Eulerian tour problem
stochastic demand
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4.8
论文数:
1.9K
被引数:
8.4K
机构
引用论文
.png){kind=icon}
没有更多内容
没有更多内容