Title of article
An efficientLagrangeanheuristicforrentalvehiclescheduling
Author/Authors
Andreas T. Ernst، نويسنده , , ElenaO.Gavriliouk ، نويسنده , , LeoreyMarquez، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2011
Pages
11
From page
216
To page
226
Abstract
In thisarticlewepresentaheuristicbasedonLagrangeanrelaxationforschedulingrentalvehicles.The
schedulingproblemcanbeformulatedasasetoflargeassignmentproblemswithlinkingconstraints.
We discussthetheorybehindtheheuristic,includingtheabilitytoobtainlowerbounds.Theheuristicis
based onideasfirstintroducedbyD.Wedelin.
EmpiricaltestingshowsthatourheuristicissuperiortotheexactsolutionprocedureoftheMILP
formulationwiththecommercialILOGCplexsolverasitgenerallyproducesbettersolutionswithina
set timelimit.Moreover,theheuristiccaneasilybeparallelizedtotakeadvantageofmulticoreCPUs.
The workpresentedherehasbeenmotivatedbyareal-lifeapplicationandiscurrentlybeingusedby
companiesthatrentoutrecreationalvehicles.Testingondatasetsfromthesecompaniesshowsthe
practicalityofouralgorithm.
Keywords
Rental vehicle scheduling , Lagrangean relaxation , Assignment problem , Large scale optimization , Network flows , Parallel computing
Journal title
Computers and Operations Research
Serial Year
2011
Journal title
Computers and Operations Research
Record number
927848
Link To Document