New models and algorithms for several families of Arc Routing Problems Jessica Rodríguez Pereira ADVERTIMENT La consulta d’aquesta tesi queda condicionada a l’acceptació de les següents condicions d'ús: La difusió d’aquesta tesi per mitjà del repositori institucional UPCommons (http://upcommons.upc.edu/tesis) i el repositori cooperatiu TDX (http://www.tdx.cat/) ha estat autoritzada pels titulars dels drets de propietat intel·lectual únicament per a usos privats emmarcats en activitats d’investigació i docència. No s’autoritza la seva reproducció amb finalitats de lucre ni la seva difusió i posada a disposició des d’un lloc aliè al servei UPCommons o TDX. No s’autoritza la presentació del seu contingut en una finestra o marc aliè a UPCommons (framing). Aquesta reserva de drets afecta tant al resum de presentació de la tesi com als seus continguts. En la utilització o cita de parts de la tesi és obligat indicar el nom de la persona autora. ADVERTENCIA La consulta de esta tesis queda condicionada a la aceptación de las siguientes condiciones de uso: La difusión de esta tesis por medio del repositorio institucional UPCommons (http://upcommons.upc.edu/tesis) y el repositorio cooperativo TDR (http://www.tdx.cat/?locale- attribute=es) ha sido autorizada por los titulares de los derechos de propiedad intelectual únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro ni su difusión y puesta a disposición desde un sitio ajeno al servicio UPCommons No se autoriza la presentación de su contenido en una ventana o marco ajeno a UPCommons (framing). Esta reserva de derechos afecta tanto al resumen de presentación de la tesis como a sus contenidos. En la utilización o cita de partes de la tesis es obligado indicar el nombre de la persona autora. WARNING On having consulted this thesis you’re accepting the following use conditions: Spreading this thesis by the institutional repository UPCommons (http://upcommons.upc.edu/tesis) and the cooperative repository TDX (http://www.tdx.cat/?locale- attribute=en) has been authorized by the titular of the intellectual property rights only for private uses placed in investigation and teaching activities. Reproduction with lucrative aims is not authorized neither its spreading nor availability from a site foreign to the UPCommons service. Introducing its content in a window or frame foreign to the UPCommons service is not authorized (framing). These rights affect to the presentation summary of the thesis as well as to its contents. In the using or citation of parts of the thesis it’s obliged to indicate the name of the author. UNIVERSITAT POLITÈCNICA DE CATALUNYA Department of Statistics and Operations Research New models and algorithms for several families of Arc Routing Problems Author: ThesisAdvisors: JessicaRodríguezPereira ElenaFernándezAréizaga GilbertLaporte Barcelona,January2018 The research carried out in this PhD dissertation has been partially sup- ported by the Spanish Ministry of Economy and Competitiveness and EDRF fundsthroughresearchprojectsMTM2012-36163-C06-05andMTM2015-63779- R(MINECO/FEDER),grantsEEBB-I-17-11968,EEBB-I-16-10670,andBES-2013- 063633,andbytheCanadienNaturalSciencesandEngineeringResearchCoun- cilundergrant2015-06189. ToCito. Abstract Someofthemostcommondecisionstobetakenwithinalogisticsystemsatanoper- ationallevelarerelatedtothedesignofthevehicleroutes. VehicleRoutingProblems andArcRoutingProblemsarewell-knownfamiliesofproblemsaddressingsuchde- cisions. Theirmaindifferenceiswhetherservicedemandislocatedattheverticesor theedgesoftheoperatingnetwork. Inthisthesiswefocusonthestudyofseveralarcroutingproblems. Weconcen- trate on three families of problems. The first family consists of Multi Depot Rural Postman Problems, which are an extension of Rural Postman Problems where there areseveraldepotsinsteadofonlyone. Thesecondfamilyofproblemsthatwestudy areLocation-ArcRoutingProblems,inwhichthedepotsarenotfixedinadvance,so theirlocationbecomespartofthedecisionsoftheproblem. WefinallystudyTarget- Visitation Arc Routing Problems, where the service is subject to an ordering prefer- ence among the connected components induced by demand arcs. Different models arestudiedforeachconsideredfamily. Inparticular,twodifferentMultiDepotRural Postman Problem models are considered, which differ in the objective function: the minimizationoftheoveralltransportationcostortheminimizationofthemakespan. ConcerningLocation-ArcRoutingProblems,westudysixalternativemodelsthatdif- fer from each other in their objective function, whether there is an upper bound on thenumberoffacilitiestobelocated,orwhethertherearecapacityconstraintsonthe demandthatcanbeservedfromselectedfacilities. Finally,twoTarget-VisitationArc RoutingProblemmodelsarestudied,whichdifferfromeachotherinwhetherornot itisrequiredthatalltherequirededgesinthesamecomponentarevisitedconsecu- tively. The aim in this thesis is to provide quantitative tools to the decision makers to identify the best choices for the design of the routes. To this end and for each con- sideredproblem,wefirststudyandanalyzeitscharacteristicsandproperties. Based onthemwedevelopdifferentIntegerLinearProgrammingformulationssuitablefor beingsolvedtroughbranch-and-cut. Finally,allformulationsaretestedtroughexten- sive computational experience. In this sense, for Multi Depot Rural Postman Prob- lemsandLocation-ArcRoutingProblemsweproposenaturalmodelingformulations with three-index variables, where variables are associated with edges and facilities. Forsomeofthemodelswealsopresentalternativeformulationswithonlytwo-index variables,whicharesolelyassociatedwithedges.Finally,fortheTarget-VisitationArc RoutingProblemsweproposethreedifferentformulations,twoalternativeformula- tionsforthegeneralcase,andonefortheclusteredversion,wherealltheedgesinthe samecomponentsareservedsequentially,whichexploitssomeoptimalityconditions oftheproblem. i Resum Algunes de les decisions més habituals que es prenen en un sistema logístic a nivell operatiu estan relacionades amb el disseny de rutes de vehicles. Els coneguts Vehi- cle Routing Problems i Arc Routing Problems són famílies de problemes que s’ocupen d’aquest tipus de decisions. La principal diferència entre ambdós recau en si la de- mandadeserveiestrobalocalitzadaalsvèrtexsoalesarestesdelaxarxa. Aquesta tesi es centra en l’estudi de diversos problemes de rutes per arcs. Ens centrementresfamíliesdeproblemes. LaprimerafamíliaconsisteixenelsMultiDe- potRuralPostmanProblems, quesónunaextensiódelRuralPostmanProblemonhiha diversos dipòsits en lloc d’un de sol. La segona família de problemes que estudiem són els Location-Arc Routing Problems, en els quals els dipòsits no estan fixats amb antelaciói,pertant,lasevaubicacióesdevépartdelesdecisionsaprendreenelprob- lema. Finalment,estudiemelsTarget-VisitationArcRoutingProblems,onelserveiestà subjecte a una preferència d’ordenació entre les components connexes induïdes pels arcsambdemanda. S’estudiendiferentsmodelsperacadascunadelesfamíliescon- siderades. Enparticular,esconsiderendosmodelsdiferentsperalMultiDepotRural PostmanProblem,queesdiferencienenlafuncióobjectiu:laminimitzaciódelcostgen- eral de transport o la minimització de la ruta més llarga. Pel que fa als Location-Arc RoutingProblems,estudiemsismodelsalternatiusquedifereixenenlasevafuncióob- jectiu, considerant si hi ha un límit màxim sobre la quantitat de dipòsits a ubicar o sihiharestriccionsdecapacitatsobrelademandaqueespotservirdesdelsdipòsits seleccionats. Finalment, s’estudien dos models de Target-Visitation Arc Routing Prob- lem,queesdiferencienensiesnecessariquetoteslesarestesrequeridesenlamateixa componentesvisitindeformaconsecutiva. L’objectiud’aquestatesiésproporcionareinesquantitativesalsresponsables,que permetinidentificarlesmillorsopcionsdedissenydelesrutes.Peraixò,iperacadas- cundelsproblemesconsiderats,primerestudiemianalitzemlessevescaracterístiques i propietats. A partir d’aquestes, desenvolupem diferents formulacions de Progra- mació Lineal Entera, adequades per a la seva solució mitjançant un branch-and-cut. Finalment,toteslesformulacionssónprovadesmitjançantunamplitesteigcomputa- cional. Enaquestsentit, peralsMultiDepotRuralPostmanProblemsielsLocation-Arc Routing Problems, proposem formulacions naturals amb variables de tres índexs, on les variables estan associades a les arestes i als dipòsits. Per a alguns dels models tambépresentemformulacionsalternatives,ambvariablesdenomésdosíndexs,que només estan associades a les arestes. Finalment, per als Target-Visitation Arc Routing Problemsproposemtresformulacionsdiferents,duesformulacionsalternativesperal casgeneraliunaperalaversióenclúster, ontoteslesarestesdelamateixacompo- nentesserveixenseqüencialment,cosaqueexploraalgunescondicionsd’optimització pròpies. iii Resumen Algunasdelasdecisionesmáshabitualesquesetomanenunsistemalogísticoanivel operativoestánrelacionadasconeldiseñoderutasdevehículos. LosconocidosVehi- cleRoutingProblemsyArcRoutingProblemssonfamiliasdeproblemasqueseocupan deestetipodedecisiones.Laprincipaldiferenciaentreambasresideensilademanda deserviciosestálocalizadaenlosvérticesoenlasaristasdelared. Esta tesis se centra en el estudio de diversos problemas de rutas por arcos. Nos centramosentresfamiliasdeproblemas. LaprimerafamiliaconsisteenlosMultiDe- pot Rural Postman Problems, que son una extensión del Rural Postman Problem donde hay varios depósitos en lugar de solamente uno. La segunda familia de problemas queestudiamossonlosLocation-ArcRoutingProblems,enlosquelosdepósitosnoes- tán fijados con antelación y, por lo tanto, su ubicación se convierte en parte de las decisiones a tomar en el problema. Finalmente, estudiamos los Target-Visitation Arc RoutingProblems,dondeelservicioestásujetoaunapreferenciadeordenaciónentre lascomponentesconexasinducidasporlosarcoscondemanda.Seestudiandiferentes modelosparacadaunadelasfamiliasconsideradas. Enparticular,seconsiderendos modelosdiferentesparaelMultiDepotRuralPostmanProblemquesediferencianenla función objetivo: la minimización del coste general de transporte o la minimización de la ruta más larga. En cuanto a los Location-Arc Routing Problems, estudiamos seis modelosalternativosquedifierenensufunciónobjetivo,ensihayunímitemáximo sobre la cantidad de depósitos a ubicar, o en si hay restricciones de capacidad sobre la demanda que se puede servir desde los depósitos seleccionados. Finalmente, se estudian dos modelos de Target-Visitation Arc Routing Problem, que se diferencian en siesnecesarioquetodaslasaristasrequeridasenlamismacomponentesevisitende formaconsecutiva. Elobjetivodeestatesisesproporcionarherramientascuantitativasalosrespons- ables, quepermitanidentificarlasmejoresopcionesdediseñodelasrutas. Porello, y para cada uno de los problemas considerados, primero estudiamos y analizamos sus características y propiedades. A partir de estas, desarrollamos diferentes for- mulaciones de Programación Lineal Entera, adecuadas para su solución mediante un branch-and-cut. Finalmente, todas las formulaciones son probadas mediante un amplio testeo computacional. En este sentido, para los Multi Depot Rural Postman ProblemsylosLocation-ArcRoutingProblems,proponemosformulacionesnaturalescon variables de tres índices, donde las variables están asociadas a las aristas y a los de- pósitos. Para algunos de los modelos también presentamos formulaciones alternati- vas con variables de sólo dos índices, que sólo están asociadas a las aristas. Final- mente,paralosTarget-VisitationArcRoutingProblemsproponemostresformulaciones diferentes, dosformulacionesalternativasparaelcasogeneralyunaparalaversión enclúster,dondetodaslasaristasdelamismacomponentesesirvensecuencialmente, loqueexploraalgunascondicionesdeoptimizaciónpropias. v