The shortest-path problem with resource constraints with (k,2)-loop elimination and its application to the capacitated arc-routing problem

Claudia Bode and Stefan Irnich

European Journal of Operational Research, 2014, vol. 238, issue 2, 415-426

Abstract: In many branch-and-price algorithms, the column generation subproblem consists of computing feasible constrained paths. In the capacitated arc-routing problem (CARP), elementarity constraints concerning the edges to be serviced and additional constraints resulting from the branch-and-bound process together impose two types of loop-elimination constraints. To fulfill the former constraints, it is common practice to rely on a relaxation where loops are allowed. In a k-loop elimination approach all loops of length k and smaller are forbidden. Following Bode and Irnich (2012) for solving the CARP, branching on followers and non-followers is the only known approach to guarantee integer solutions within branch-and-price. However, it comes at the cost of additional task-2-loop elimination constraints. In this paper, we show that a combined (k,2)-loop elimination in the shortest-path subproblem can be accomplished in a computationally efficient way. Overall, the improved branch-and-price often allows the computation of tighter lower bounds and integer optimal solutions for several instances from standard benchmark sets.

Keywords: Constrained shortest paths; Cycle elimination; Capacitated arc-routing problem (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221714003130
Full text for ScienceDirect subscribers only

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:eee:ejores:v:238:y:2014:i:2:p:415-426

DOI: 10.1016/j.ejor.2014.04.004

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().