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

[thumbnail of Muter_etal_NoteOnTimeConstrainedRouting.pdf] PDF

Download (118kB)


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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kerem Bülbül
Date Deposited: 10 Aug 2010 11:59
Last Modified: 26 Apr 2022 10:48
URI: https://research.sabanciuniv.edu/id/eprint/14198

Actions (login required)

View Item
View Item