.png){kind=icon}
返回
On the Hierarchical Chinese Postman Problem with linear ordered classes
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2004.06.003.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The Hierarchical Chinese Postman Problem (HCPP) is a Chinese Postman Problem with the arcs partitioned into priority classes ordered by a precedence relation. The problem under the sum criterion is polynomially solvable if the ordering is linear and each class is connected. For a known HCPP algorithm we give an O(n) improvement (n the number of nodes) leading to O(kn(4)) with k the number of classes. The same complexity appears to hold for the lexicographic criterion which minimises the costs of the first priority class, then the costs of the second class, etc. The notions of servicing and traversing related to arcs, allow for more real life models of arc routing problems. We show how to incorporate these notions in known algorithms, without increasing the complexity. (c) 2004 Elsevier B.V. All rights reserved.
Keyword:
routing
Chinese Postman Problem
lexicographic objective
matching
post-optimality
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
暂无机构信息
引用论文
Nanoformulated water-soluble paclitaxel to enhance drug efficacy and reduce hemolysis side effect
PREAI
分享收藏A segment feedrate profile fitting method for parametric interpolation.png)
Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture
Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering ManufactureIF0
PREAI
分享收藏
查看更多内容