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 条
  • [1] A Heuristic Algorithm for the Mixed Chinese Postman Problem
    Yaoyuenyong, Kriangchai
    Charnsethikul, Peerayuth
    OPTIMIZATION AND ENGINEERING, 2002, 3 (02) : 157 - 187
  • [2] A Heuristic Algorithm for the Mixed Chinese Postman Problem
    Kriangchai Yaoyuenyong
    Peerayuth Charnsethikul
    Vira Chankong
    Optimization and Engineering, 2002, 3 : 157 - 187
  • [3] On ability of orthogonal genetic algorithms for the mixed Chinese postman problem
    Masuyama, Hiroshi
    Ichimori, Tetsuo
    Sasama, Toshihiko
    ICSOFT 2006: Proceedings of the First International Conference on Software and Data Technologies, Vol 1, 2006, : 39 - 45
  • [4] Chinese Postman Problem with priorities
    Kramberger, T
    Zerovnik, J
    SOR 05 Proceedings, 2005, : 357 - 362
  • [5] An implementation of Chinese postman problem with priorities
    Nilofer
    Rizwanullah, Mohd
    JOURNAL OF INTELLIGENT & FUZZY SYSTEMS, 2020, 38 (03) : 3301 - 3305
  • [6] Cost allocation in the Chinese postman problem
    Hamers, H
    Borm, P
    van de Leensel, R
    Tijs, S
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 118 (01) : 153 - 163
  • [7] Chinese postman problem in stochastic networks
    Tan, GZ
    Cui, XT
    Zhang, Y
    2005 JOINT INTERNATIONAL CONFERENCE ON AUTONOMIC AND AUTONOMOUS SYSTEMS AND INTERNATIONAL CONFERENCE ON NETWORKING AND SERVICES (ICAS/ICNS), 2005, : 482 - 487
  • [8] On the Maximum Benefit Chinese Postman Problem
    Pearn, WL
    Wang, KH
    OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2003, 31 (04): : 269 - 273
  • [9] Robust Optimization Approach in Chinese Postman Problem
    Nehezova, Tereza Sedlarova
    38TH INTERNATIONAL CONFERENCE ON MATHEMATICAL METHODS IN ECONOMICS (MME 2020), 2020, : 516 - 522
  • [10] Lower Bounds For Hierarchical Chinese Postman Problem
    Damodaran, Purushothaman
    Krishnamurthi, Murali
    Srihari, Krishnaswami
    INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING-THEORY APPLICATIONS AND PRACTICE, 2008, 15 (01): : 36 - 44
12345