Title of article
Heuristics forthemixedswappingproblem
Author/Authors
Charles Bordenave، نويسنده , , MichelGendreau، نويسنده , , GilbertLaporteb، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2010
Pages
7
From page
108
To page
114
Abstract
In the swapping problem, toeachvertexofacompletedirectedgraphareassociatedatmosttwoobject
types representingitssupplyanddemand.Itisassumedthatforeachobjecttypethetotalsupply
equals thetotaldemand.Avehicleofunitcapacity,startingandendingitsrouteatanarbitraryvertex,
is availabletocarrytheobjectsalongthearcsofthegraph.Theaimistodetermineaminimumcost
route suchthateachsupplyanddemandissatisfied.Whensomeoftheobjecttypesareallowedtobe
temporarily unloadedatsomeintermediateverticesbeforebeingcarriedtotheirfinaldestination,the
problem iscalledthe mixed swappingproblem. Inthispaperwedescribeconstructiveandimprovement
heuristics whichweresuccessfullyappliedtorandomlygeneratedinstanceswithupto10,000vertices,
with anaverageoptimalitygapnotexceeding1%.
Keywords
Transportation problem , vehicle routing , Heuristic
Journal title
Computers and Operations Research
Serial Year
2010
Journal title
Computers and Operations Research
Record number
927627
Link To Document