We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Concerning a Decision-Diagram-Based Solution to the Generalized Directed Rural Postman Problem.
- Authors
Tan, Renzo Roel P.; Jun Kawahara; Kazushi Ikeda; Garciano, Agnes D.; See, Kyle Stephen S.
- Abstract
Decision-diagram-based solutions for discrete optimization have been persistently studied. Among these is the use of the zero-suppressed binary decision diagram, a compact graph-based representation for a specified family of sets. Such a diagram may work out combinatorial problems by efficient enumeration. In brief, an extension to the frontierbased search approach for zero-suppressed binary decision diagram construction is proposed. The modification allows for the inclusion of a class-determined constraint in formulation. Variations of the generalized directed rural postman problem, proven to be nondeterministic polynomial-time hard, are solved on some rapid transit systems as illustration. Lastly, results are juxtaposed against standard integer programming in establishing the relative superiority of the new technique.
- Subjects
COMBINATORIAL enumeration problems; PUBLIC transit; INTEGER programming; NP-hard problems
- Publication
IAENG International Journal of Computer Science, 2020, Vol 47, Issue 2, p8
- ISSN
1819-656X
- Publication type
Article