Heuristics forthemixedswappingproblem

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%.