Title of article
The undirectedcapacitatedarcroutingproblemwithprofits
Author/Authors
Claudia Archetti، نويسنده , , DominiqueFeilletb، نويسنده , , AlainHertzc، نويسنده , , M.GraziaSperanzaa، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2010
Pages
10
From page
1860
To page
1869
Abstract
A profitandademandareassociatedwitheachedgeofasetofprofitableedgesofagivengraph.A
travel timeisassociatedwitheachedgeofthegraph.Afleetofcapacitatedvehiclesisgiventoservethe
profitable edges.Amaximumdurationoftherouteofeachvehicleisalsogiven.Theprofitofanedgecan
be collectedbyonevehicleonlythatalsoservesthedemandoftheedge.Theobjectiveofthisproblem,
which iscalledtheundirectedcapacitatedarcroutingproblemwithprofits(UCARPP),istofindasetof
routes thatsatisfytheconstraintsonthedurationoftherouteandonthecapacityofthevehicleand
maximize thetotalcollectedprofit.Weproposeabranch-and-pricealgorithmandseveralheuristics.We
can solveexactlyinstanceswithupto97profitableedges.Thebestheuristicsfindtheoptimalsolution
on mostofinstanceswhereitisavailable.
Keywords
Undirected capacitated arc routing with profits , Auctions in transportation , Carrier , Heuristics , Branch-and-price
Journal title
Computers and Operations Research
Serial Year
2010
Journal title
Computers and Operations Research
Record number
927792
Link To Document