Show simple item record

dc.contributor.authorTan, Renzo Roel P.
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
dc.contributor.authorIkeda, Kazushi
dc.contributor.authorSee, Kyle Stephen S.
dc.date.accessioned2021-10-20T15:06:02Z
dc.date.available2021-10-20T15:06:02Z
dc.date.issued2020
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22060
dc.language.isoenen
dc.subjectArc routingen
dc.subjectEnumeration algorithmen
dc.subjectFrontier-based searchen
dc.subjectGraph optimizationen
dc.subjectRural postman problemen
dc.subjectZero-suppressed binary decision diagramen
dc.subject.ddc003en
dc.titleArc Routing Based on the Zero-Suppressed Binary Decision Diagramen
dc.typeCommunication / Conférence
dc.description.abstractenA 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.en
dc.identifier.citationpages105-120en
dc.relation.ispartoftitleTransactions on Engineering Technologiesen
dc.relation.ispartofeditorAo, Sio-Iong
dc.relation.ispartofeditorGelman, Len
dc.relation.ispartofeditorKon Kim, Haeng
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofdate2021
dc.relation.ispartofpages247en
dc.relation.ispartofurl10.1007/978-981-15-8273-8en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-981-15-8275-2en
dc.relation.conftitle27th World Congress on Engineering (WCE 2019)en
dc.relation.confdate2019-07
dc.relation.confcityLondonen
dc.relation.confcountryUnited Kingdomen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-981-15-8273-8_9en
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2021-10-20T14:51:55Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record