On path-bridge inequalities for the orienteering arc routing problems. (2nd January 2021)

• Record Type: Journal Article
• Authors: Khorramizadeh, Mostafa
• Is Part Of: Optimization. Volume 70:Number 1(2021)
• Page Start: 101
• Page End: 120
• Publication Date: 2021-01-02
• Subjects: Orienteering arc routing problem -- path-bridge inequality -- facet inducing -- arc routing problem -- routing problem with profits; 90C10 -- 90C57; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2019.1702984
• Languages: English
• ISSNs: 0233-1934

Abstract

ABSTRACT: One of the recent variants of arc routing problems is the orienteering arc routing problem. In Archetti et al. [A branch and-cut algorithm for the orienteering arc routing problem, Computers and Operations Research. 2016;66:95–104] an integer programming formulation is proposed for the problem and some families of valid inequalities introduced and proven to be valid for the associated polyhedron. Here, the class of path-bridge inequalities is introduced for the problem and is proven to be facet inducing. Since the large class of path-bridge inequalities contain those classes introduced in Archetti et al. [A branch and-cut algorithm for the orienteering arc routing problem, Computers and Operations Research. 2016;66:95–104] this paper can be considered as a generalization of the results of that paper.