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

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

0.00 Avg rating0 Votes
Article ID: iaor200937828
Country: Netherlands
Volume: 17
Issue: 2
Start Page Number: 214
End Page Number: 234
Publication Date: Feb 2009
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: programming: integer
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 (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.

Reviews

Required fields are marked *. Your email address will not be published.