Arc Routing Based on the Zero-Suppressed Binary Decision Diagram
Tan, Renzo Roel P.; Sikora, Florian; Ikeda, Kazushi; See, Kyle Stephen S. (2020), Arc Routing Based on the Zero-Suppressed Binary Decision Diagram, in Ao, Sio-Iong; Gelman, Len; Kon Kim, Haeng, Transactions on Engineering Technologies, Springer, p. 105-120. 10.1007/978-981-15-8273-8_9
TypeCommunication / Conférence
Conference title27th World Congress on Engineering (WCE 2019)
Conference countryUnited Kingdom
Book titleTransactions on Engineering Technologies
Book authorAo, Sio-Iong; Gelman, Len; Kon Kim, Haeng
Number of pages247
MetadataShow full item record
Author(s)Tan, Renzo Roel P.
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
See, Kyle Stephen S.
Abstract (EN)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.
Subjects / KeywordsArc routing; Enumeration algorithm; Frontier-based search; Graph optimization; Rural postman problem; Zero-suppressed binary decision diagram
Showing items related by title and author.