On the Maximum Benefit Chinese Postman Problem

檔案

日期

2003-08-01

類型

期刊名稱

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE

卷期與頁次

第 31 卷第 4 期,頁 269–273

ISSN

0305-0483

語言

英文

摘要

The Maximum Benefit Chinese Postman Problem (MBCPP) is a practical generalization of the classical Chinese Postman Problem (CPP), which has many real-world applications. In this paper, we consider the MBCPP on undirected networks, and show that the MBCPP is more complex than the Rural Postman Problem (RPP). We present a sufficient condition for the MBCPP solution to cover the whole network, and provide an upper bound. Based on the upper bound, we propose an efficient solution procedure to solve the MBCPP approximately. The proposed algorithm applies the minimal spanning tree and the minimal-cost matching algorithms, which performs well on problems satisfying the sufficient condition. (C) 2003 Elsevier Science Ltd. All rights reserved.

所屬典藏

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

引用此條目

Pearn, W., & Wang, K. (2003). On the Maximum Benefit Chinese Postman Problem. OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 31(4), 269–273. https://doi.org/10.1016/S0305-0483(03)00051-3

BibTeX RIS

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

分享

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