The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem

The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor19961409
Country: Netherlands
Volume: 65
Issue: 2
Start Page Number: 218
End Page Number: 234
Publication Date: Mar 1993
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: travelling salesman, networks: path
Abstract:

This paper introduces the maximum benefit Chinese postman problem (MBCPP) and the maximum benefit traveling salesman problem (MBTSP). For the MBCPP a benefit is realized each time a link of a directed graph is traversed. The MBCPP relaxes the constraint of the Chinese postman problem that each link be traversed at least once and finds a four of maximum total net benefit. For the MBTSP a benefit is derived when a node is visited and a cost is incurred when a link is traversed. The MBTSP relaxes the constraint of the traveling salesman problem that each node be visited eactly (or at least) once and finds a tour of maximum total net benefit. Both problems are formulated as linear integer programming problems. A solution algorithm is given that repeatedly solves a relaxation of the formulation as a minimum cost flow problem using a branch-and-bound procedure. Computational examples are presented.

Reviews

Required fields are marked *. Your email address will not be published.