Improved solutions for the Chinese postman problem on mixed networks

檔案

日期

1999-07-01

類型

期刊名稱

COMPUTERS & OPERATIONS RESEARCH

卷期與頁次

第 26 卷第 8 期,頁 819–827

ISSN

0305-0548

語言

英文

摘要

The Chinese postman problem (CPP) is that of finding the shortest postman tour covering all the roads in the network. The CPP is polynomial-time solvable on totally directed or undirected networks, but is NP-complete on mixed networks (MCPP). Several heuristic solution procedures including Mixed-1, Mixed-2 Modified Mixed-1, and Modified Mixed-2 algorithms, have been proposed to solve the problem approximately. In this paper, we briefly review these four existing algorithms, then propose two improvement procedures to improve the solutions. The proposed procedures are tested and compared with the four existing algorithms. The results show that the proposed procedures significantly improve the existing solutions. (C) 1999 Elsevier Science Ltd. All rights reserved.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Pearn, W., & Chou, J. (1999). Improved solutions for the Chinese postman problem on mixed networks. COMPUTERS & OPERATIONS RESEARCH, 26(8), 819–827. https://doi.org/10.1016/S0305-0548(98)00092-6

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/31236