A note on “A LP-based heuristic for a time-constrained routing problem”

• DOI: 10.1016/j.ejor.2012.03.048
• Publication Date: 2012-04-09T19:36:51Z
• Authors: İbrahim Muter; Ş. İlker Birbil; Kerem Bülbül; Güvenç Şahin
• Keywords: Column generation; Duality (order theory); Vehicle Routing Problem

In their paper, Avella et al. (2006) investigate a time-constrained routing problem. The core of the proposed solution approach is a large-scale linear program that grows both row- and column-wise when new variables are introduced. Thus, a column-and-row generation algorithm is proposed to solve this linear program optimally, and an optimality condition is presented to terminate the column-and-row generation algorithm. We demonstrate by using Lagrangian duality that this optimality condition is incorrect and may lead to a suboptimal solution at termination.