An extension of the relaxation algorithm for solving a special case of capacitated arc routing problems

Saman Eskandarzadeh (), Reza Tavakkoli-Moghaddam () and Amir Azaron ()
Additional contact information
Saman Eskandarzadeh: University of Tehran
Reza Tavakkoli-Moghaddam: University of Tehran
Amir Azaron: Dalhousie University

Journal of Combinatorial Optimization, 2009, vol. 17, issue 2, No 7, 214-234

Abstract: Abstract In this paper, we propose an exact method for solving a special integer program associated with the classical capacitated arc routing problems (CARPs) called split demand arc routing problems (SDARP). This method is developed in the context of monotropic programming theory and bases a promising foundation for developing specialized algorithms in order to solve general integer programming problems. In particular, the proposed algorithm generalizes the relaxation algorithm developed by Tseng and Bertsekas (Math. Oper. Res. 12(4):569–596, 1987) for solving linear programming problems. This method can also be viewed as an alternative for the subgradient method for solving Lagrangian relaxed problems. Computational experiments show its high potential in terms of efficiency and goodness of solutions on standard test problems.

Keywords: Nonlinear programming; Capacitated arc routing; Monotropic and integer programming; Lagrangian relaxation (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-007-9109-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:17:y:2009:i:2:d:10.1007_s10878-007-9109-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-007-9109-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().