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: | Daskin Mark S., Malandraki Chryssi |
Keywords: | programming: travelling salesman, networks: path |
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.