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". [Working Paper / Technical Report] Sabanci University ID:SU_FENS_2010/0005

PDF - 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:Working Paper / Technical Report
Additional Information:The technical report has a different mathematical analysis than the eventually published version (URL specified above).
Uncontrolled Keywords:Time-constrained routing; large-scale linear programming; column-and-row generation; column-dependent-rows
Subjects:T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Q Science > QA Mathematics
ID Code:14198
Deposited By:Kerem Bülbül
Deposited On:10 Aug 2010 11:59
Last Modified:25 Jul 2019 11:30

Repository Staff Only: item control page