Arc Routing Based on the Zero-Suppressed Binary Decision Diagram

• Main Authors: Tan, Renzo Roel P, Sikora, Florian, Ikeda, Kazushi, See, Kyle Stephen S
• Format: text
• Published: Archīum Ateneo 2020
• Subjects: arc routing; enumeration algorithm; frontier-based search; graph optimization; rural postman problem; zero-suppressed binary decision diagram; Mathematics
• Online Access: https://archium.ateneo.edu/mathematics-faculty-pubs/167; https://link.springer.com/chapter/10.1007/978-981-15-8273-8_9
• Institution: Ateneo De Manila University

A wide range of problems in operations research falls under arc routing problems, a domain which focuses on arc or edge features rather than node or vertex attributes. The undirected rural postman problem is a well-known problem in arc routing that seeks to determine a minimum cost walk that traverses a certain set of required edges on a given graph. The problem, arising in numerous real-world applications, is nondeterministic polynomial-time hard. The chapter presents a solution to the undirected rural postman problem based on the zero-suppressed binary decision diagram, a compact data structure that represents a family of sets. Through an extension to the frontier-based search method of diagram construction, the approach solves the problem by efficient enumeration, producing all feasible routes in addition to the optimal route. Instances of the problem put forward in literature are then solved as benchmark for the decision-diagram-based solution. As reasonable time is consumed, the method proves to be a practicable candidate in solving the undirected rural postman problem.