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

Muter, İbrahim and Birbil, Ş. İlker and Bülbül, Kerem and Şahin, Güvenç (2010) A note on “A LP-based heuristic for a time-constrained routing problem”. (Submitted)

WarningThere is a more recent version of this item available.

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


Avella et al. (2006) [Avella, P., D'Auria, B., Salerno, S. (2006). A LP-based heuristic for a time-constrained routing problem. European Journal of Operational Research 173:120-124] investigate a time-constrained routing (TCR) problem. The core of the proposed solution approach is a large-scale linear program (LP) that grows both row- and column-wise when new variables are introduced. Thus, a column-and-row generation algorithm is proposed to solve this LP optimally, and an optimality condition is presented to terminate the column-and-row generation algorithm. We demonstrate that this optimality condition is incorrect and may lead to a suboptimal solution at termination. We identify the source of this error and discuss how the generic column-and-row generation algorithm proposed by Muter et al. (2010) may be applied to this TCR problem in order to solve the proposed large-scale LP correctly.

Item Type:Article
Uncontrolled Keywords:Time-constrained routing; large-scale optimization; linear programming; column generation; column-and-row generation; column-dependent-rows
Subjects:T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
ID Code:15206
Deposited By:Kerem Bülbül
Deposited On:23 Nov 2010 12:45
Last Modified:04 Jul 2012 15:41

Available Versions of this Item

Repository Staff Only: item control page