6533b874fe1ef96bd12d6431

RESEARCH PRODUCT

The Windy clustered prize-collecting arc-routing problem

José M. SanchisElena FernándezÁNgel CorberánCarles Franquesa

subject

Arc routingMathematical optimizationMathematical programmingTransportation68W AlgorithmsSeparation problemsCutting plane algorithmsArc routing problems:Informàtica::Informàtica teòrica [Àrees temàtiques de la UPC]Prize-collectingPolyhedral modellingNumerical resultsProfitability indexProfitabilityPolyhedral analysisComputational experimentMATEMATICA APLICADAArc routingCutting plane algorithmValid inequalityAlgorithmsCivil and Structural EngineeringSeparation problemMathematicsMathematicsofComputing_DISCRETEMATHEMATICS

description

This paper introduces the windy clustered prize-collecting arc-routing problem. It is an arc-routing problem where each demand edge is associated with a profit that is collected once if the edge is serviced, independent of the number of times the edge is traversed. It is further required that if a demand edge is serviced, then all the demand edges of its component are also serviced. A mathematical programming formulation is given and some polyhedral results including several facet-defining and valid inequalities are presented. The separation problem for the different families of inequalities is studied. Numerical results from computational experiments are analyzed. © 2011 INFORMS.

yearjournalcountryeditionlanguage
2011-08-01
10.1287/trsc.1110.0370https://hdl.handle.net/2117/13482