Volume 56, Number 3, May-June 2022
|Page(s)||1283 - 1291|
|Published online||02 June 2022|
An improved heuristic algorithm for the maximum benefit Chinese postman problem
Department of Industrial and Systems Engineering, Faculty of Science and Engineering, Hosei University, Koganei-shi, Tokyo, Japan
* Corresponding author: firstname.lastname@example.org
Accepted: 18 March 2022
The maximum benefit Chinese postman problem (MBCPP) is a practical generalization of the Chinese postman problem. A distinctive feature of MBCPP is that the postman can traverse each edge arbitrary times and obtains a benefit for each traversal of an edge, which depends on the number of times that the edge has been traversed. (Pearn and Wang, Omega 31 (2003) 269–273) discussed MBCPP under the assumption that the benefits of each edge is a non-increasing function of the number of traversals. They showed that MBCPP under this assumption is NP-hard, and proposed a heuristic algorithm which applies the minimum spanning tree and the minimal-cost T-join algorithms. (Corberán, Plana, Rodríguez-Chía and Sanchis, Math. Program. 141 (2013) 21–48) presented an integer programming formulation and a branch-and-cut algorithm for MBCPP without the assumption on the benefits. This is based on the idea of integrating the benefits of each edge into two benefits, each representing that the edge is traversed an odd or even number of times. In this paper, by applying the idea of Corberán et al., we improve the heuristic algorithm of Pearn and Wang. Our algorithm applies to the general case with no assumption on the benefits, and can perform better even if the benefits are non-increasing. We then analyze the efficiency of our heuristic algorithm in theory and in practice, and prove that it finds the optimal solution when the benefits satisfy a certain property.
Mathematics Subject Classification: 90C59 / 90C27 / 05C85
Key words: Combinatorial optimization / maximum benefit Chinese postman problem / heuristic algorithm / spanning tree / T-join
© The authors. Published by EDP Sciences, ROADEF, SMAI 2022
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.