ON THE MIXED CHINESE POSTMAN PROBLEM

被引：14
|
作者：
RALPHS, TK
机构：
[1] School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY
来源：
OPERATIONS RESEARCH LETTERS | 1993年 / 14卷 / 03期
基金：
美国国家科学基金会;
关键词：
CHINESE POSTMAN PROBLEM; HALF-INTEGRALITY; GRAPH; FLOW;
D O I：
10.1016/0167-6377(93)90021-8
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
The mixed Chinese postman problem is a version of the well-known Chinese postman problem in which the underlying graph consists of both directed and undirected edges. We give an integer linear programming formulation for this problem and then show that the extreme points of its linear relaxation polyhedron are all half-integral.
引用
收藏
页码：123 / 127
页数：5
相关论文
共 50 条
  • [31] Sharp bounds for the Chinese Postman Problem in 3-regular graphs and multigraphs
    Suil, O.
    West, Douglas B.
    DISCRETE APPLIED MATHEMATICS, 2015, 190 : 163 - 168
  • [32] Path Optimization Along Lattices in Additive Manufacturing Using the Chinese Postman Problem
    Dreifus, Gregory
    Goodrick, Kyle
    Giles, Scott
    Patel, Milan
    Foster, Reed Matthew
    Williams, Cody
    Lindahl, John
    Post, Brian
    Roschli, Alex
    Love, Lonnie
    Kunc, Vlastimil
    3D PRINTING AND ADDITIVE MANUFACTURING, 2017, 4 (02) : 98 - 104
  • [33] Solving the Time Dependent Chinese Postman Problem by Branch-and-Bound Algorithm
    Tan, Guozhen
    Sun, Jinghao
    Meng, Yakun
    INFORMATION-AN INTERNATIONAL INTERDISCIPLINARY JOURNAL, 2012, 15 (12A): : 5263 - 5270
  • [34] CHINESE POSTMAN PROBLEM APPROACH FOR A LARGE-SCALE CONVENTIONAL RAIL NETWORK IN TURKEY
    Yilmaz, Mustafa
    Codur, Merve Kayaci
    Yilmaz, Hamid
    TEHNICKI VJESNIK-TECHNICAL GAZETTE, 2017, 24 (05): : 1471 - 1477
  • [35] An integer programming approach for the Chinese postman problem with time-dependent travel time
    Sun, Jinghao
    Meng, Yakun
    Tan, Guozhen
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (03) : 565 - 588
  • [36] A tabu search algorithm for the min-max k-Chinese postman problem
    Ahr, Dino
    Reinelt, Gerhard
    COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (12) : 3403 - 3422
  • [37] The k-centrum Chinese Postman delivery problem and a related cost allocation game
    Granot, Daniel
    Granot, Frieda
    Ravichandran, Harshavardhan
    DISCRETE APPLIED MATHEMATICS, 2014, 179 : 100 - 108
  • [38] An integer programming approach for the Chinese postman problem with time-dependent travel time
    Jinghao Sun
    Yakun Meng
    Guozhen Tan
    Journal of Combinatorial Optimization, 2015, 29 : 565 - 588
  • [39] Genetic Algorithm for Chinese Postman Problems
    Jiang Hua
    Wuhan University Journal of Natural Sciences, 2003, (S1) : 316 - 318
  • [40] Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
    Fernandes, Cristina G.
    Lee, Orlando
    Wakabayashi, Yoshiko
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (02) : 272 - 279
12345