A Branch-and-Price Algorithm for Capacitated Arc Routing Problem with Flexible Time Windows

Hasan Murat Afsar (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

In this paper we study Capacitated Arc Routing Problem with Flexible Time Windows where violating a time windows implies some extra cost. We propose a branch-and-price algorithm due to the Dantzig-Wolfe decomposition. The subproblem is a non-elementary capacitated shortest path problem. Experimental results are presented on the instances up to 40 nodes and 69 required edges.

Keywords: Capacitated arc routing; flexible time windows; column generation

Domains: Operations Research [cs.RO]; Discrete Mathematics [cs.DM]

Hasan Murat Afsar. A Branch-and-Price Algorithm for Capacitated Arc Routing Problem with Flexible Time Windows. Electronic Notes in Discrete Mathematics, 2010, 36, pp.319-326. ⟨10.1016/j.endm.2010.05.041⟩. ⟨hal-02475804⟩