Optimizacin yRuteo en Transporte:teora y aplicacin de dos casos en Colombia JosFidel TorresyEdgar Gonzales Butrn Universidad de Los Andes, Bogot, Colombia. RESUMEN Los problemas combinatorios de redes de transporte son de creciente inters a pesar de su elevada complejidad.Se presentandosaplicacionesexitosasenColombia,quehandemandadoaportesmetodolgicosenlasolucinde problemas de planeamiento de rutas.El primero de ellos se refiere a la optimizacin de un sistema de recoleccin de residuos slidos en la acera, de especial importancia en grandes centros urbanos que generan un alto volumen de desperdicios.En esta red, todos los arcos son atravesados bajo restricciones de capacidad de vehculos y de tiempo.Se propone una formulacin flexible que trabaja con redes separadas de recoleccin y desplazamiento, as como un esquemadesecuenciamientoparaasignacinderutas.Eldesempeodelmodeloseanalizabajodiferentes escenariosyseaplicaaunazonaderecoleccindeBogotconresultadossatisfactorios.Elsegundodeellos, consisteenlaprogramacinderutasdeunhelicpteroparacumplircontodoslosviajes,bajorestriccionesde secuenciaenlasvisitasalosnodosycapacidaddelvehculo.Elhelicpteronoterminanecesariamentesu recorrido en el nodo inicial.Se propone una heurstica de insercin basada en ahorros mximos, dos heursticas de intercambiodesegmentos,2-opty3-opt,yunadeenfriamientosimulado,paraencontrarunarutasubptima.El procedimiento asegura la factibilidad detodas las soluciones quegenera.Se presenta un anlisis comparativo de estas soluciones, que demuestra las ventajas del procedimiento propuesto. PALABRASCLAVE:Asignacinderutas,tourdeEuler,ProblemadelCarteroChino,SistemadeInformacin Geogrfica(SIG),ProblemadeRuteodeHelicpteroconCapacidadFinita(CHRP),procedimientodek-intercambios (k-opt), Enfriamiento Simulado, procedimiento metaheurstico. 1.INTRODUCCION Esteartculopresentadosproblemascombinatoriosdeprogramacinderutas,quemuestrantratamientos sistemticosdelosmismos,atravsdeldesarrollodemodelosdeprogramacinmatemticaydeherramientas heursticas.Surgieroncomoproductodenecesidadesrealesquerepresentaronverdaderosretosparasu planteamientoysolucin,puestoquelacomplejidadcomputacionaldelosmismos,lossitaentrelaclasede problemascombinatoriosmasdifcilesderesolver.Dadoqueestosdoscasospresentanparticularidadesquelos hacen nicos mas all de sus diferencias, se ha optado por separar completamente esta presentacin.Primeramente, seexponeelproblemaderecoleccinderesiduosslidosenzonasurbanasyseterminaconladiscusinde resultadosylasconclusionesdelcaso.Acontinuacin,seexponeelproblemadeprogramacinderutascon restriccionesdeprecedenciaycapacidad,parafinalmentepresentarlarespectivadiscusinderesultadosy conclusiones. 2.EL PROBLEMA DE RECOLECCION DE RESIDUOS SOLIDOS EN LA ACERA 2.1GENERALIDADES Elcrecimientoaceleradodelapoblacinenlosltimosaos,ascomoelprocesodeindustrializacinhan ocasionadounaumentonotableenlageneracindedesperdicios,haciendoquelalogsticaderecoleccinseams compleja.Hoy en da la generacin de residuos por persona se estima entre 500 y 1.000 gr/hab/da, y se ha estimado queelcostoderecoleccinpuedellegararepresentarentreun50yun70%deloscostostotalesdelmanejode residuos slidos (Tchobanoglous [1]).En Santaf de Bogot, esta cifra tpicamente representa alrededor del65% de estos costos. 2 El problema de asignacin de rutas de vehculos tienen como objetivo especificar rutas de recoleccin para una flota de vehculos que satisfaga la oferta de los clientes. Este problema es de tipo NP, es decir, se conjetura que no puede resolverse en tiempo polinomial. En1974losautoresBeltrami&Bodin[2],presentarontcnicaseficientesparalasolucindetipodeproblemas, motivando el desarrollo de otras propuestas de solucin debidas a Shuster & Schur [3], Male & Liebman [4]yOr & Curi[5].Actualmente,seprefierenusarmodelosmatemticosasociadosalacapacidaddeanlisisespacialque proveen los Sistemas de Informacin Geogrfica.Entre ellos, cabe citar los trabajos de Massie [6],Osegueda [7] yChang [8]. Un anlisis de la red de recoleccin, tipifica a la herramienta de solucin competente.Si un vehculo debe atravesartodoslosnodos,setratadeunNRP(NodeRoutingProblem),quesetraduceenunTSP(TravelingSalesman Problem),( Laporte [9]).En cambio,s un vehculo debe recorrer todos los arcos, se trata de un ARP (Arc Routing Problem), que se traduce en unCPP (Chinese Postman Problem), (Edmons & Johnson [10]). 2.2MODELO DE ASIGNACION DE RUTAS DE VEHICULOS 2.2.1Introduccin Elproblemadeasignacinderutasdevehculosparaunsistemaderecoleccinderesiduosslidosenlaacera,puede considerarse como una variante delCPP oProblema del Cartero Chino, en el cual todos los arcos de una red mixtadebenserrecorridosporlomenosunavez.Paraello,serequierequeelgrafocumplaconlassiguientes condiciones que garanticenla formacin de un Tour de Euler(Evans & Minieka [11]): 1.El grafo G debe ser conectado, permitiendo el traslado entre cualquier par de nodos.2.Cadanodo delgrafo Gdebeser degrado par, es decir, elnmero dearcos que incidenenun nodo es igual al nmero de arcos que salen del mismo. 3.Para cada subconjunto S de nodos, la diferencia entre el nmero de arcos dirigidos desde S a su complemento y el nmero de arcos dirigidos desde el complemento deS aS es menor o igual alnmero de arcos no dirigidos paraS y su complemento. Evans&Minieka[11,planteanunaformulacinnovedosapararesolverelproblemaARV.Laestrategiabsica consiste en agregarunanuevavariablededecisinYijvkquerepresentauna nuevared idnticaaladefinidapor la variableXijvk (Figura1),endondelaredformadaporlosXijvkrepresentalaredderecoleccin(carga)ylared formada por los Y ijvk representa la red de desplazamiento o transporte.De esta manera, se hace una distincin clara entreunvehculoqueatraviesaunarcorealizandoactividadesderecoleccin;yunvehculoquesloutilizaeste arco como medio de trnsito para desplazarse de un nodo a otro. Figura 1VARIABLES DE DECISION PARA EL PROBLEMA DE RECOLECCION 2. 2.2Informacin de entrada -Configuracindelared:Permiteconvertirelmapadeunaregingeogrficaenunaredformadaporun conjunto de nodos y arcos.Para ello, se requiere conocer el sentido de circulacin de las vas, las distancia entre Yijvk Xijvk Red de recoleccin Red de desplazamiento 3 puntos de recoleccin, las caractersticas del trfico, el estado de las vas, la velocidad promedio de circulacin, la ubicacin del garaje o base de operaciones y el sitio de disposicin final. -Estimacindelademanda:Lademandavaraencadapuntoderecoleccin.Paraestimarunademandaen particular, se necesita conocer el rea total (ha), la densidad de la poblacin (hab / ha)y la tasa de generacin de residuos slidos (Kg / hab *da). -Tiempos de proceso: Se deben estimar los tiempos de viaje entre garaje-microruta, microrutarelleno y relleno-garaje,eltiempoenmicroruta(quepuedeserderecoleccindesplazamiento)yeltiempodedescargade permanencia en el relleno sanitario. -Disponibilidaddelvehculo:Estadisponibilidadestadeterminadaporeltamaodelaflotadevehculos (nmero de vehculos), la capacidad de cada tipo de vehculo (yardas cbicas, 1 yd3 = 0.7645 m3) y la densidad de la basura en el vehculo recolector (Kg / m3). -Disponibilidad de la tripulacin:Esta disponibilidad esta determinada por la duracin de la jornada de trabajo (horas/hombre), el tamao de la tripulacin (hombres / tripulacin) y el nmero de viajes que puede realizar una tripulacin en un da. -Costosvarios:Esteproblemapuedeinvolucrardiversostiposdecosto,talescomo:costosdeoperacin, mantenimiento, administracin, inversin y comercializacin. Estos se estiman, ya sea por tonelada recolectada o por kilmetro recorrido. 2.2.3Formulacin matemtica El modelo de asignacin de rutas de vehculos para un sistema derecoleccin de residuos slidos en la acera, posee una estructura similar a la presentada porChang [8]. Se emplea la siguiente notacin: Xijvk :Variablededecisinenteraparalaseleccindelarco(i,j)enlaredderecoleccincorrespondientealk-simo recorrido (tour), de un vehculo recolector tipo v. Yijvk :Variable de decisin entera para la seleccin del arco (i ,j) en la red de desplazamiento correspondiente al k-simo recorrido (tour), de un vehculo recolector tipo v. Dij :Distancia a travs del arco (i, j), (Km, mts). Qij= Cantidad de residuos a ser recolectados a travs del arco (i,j), (Ton, Kg) Cv= Capacidad de un tipo especifico de vehculo recolector (Ton, Kg). V :Nmero total de tipos de vehculos de una flota. Kv :Numero mximo de servicios que puede realizar un vehculo en un da. Tvk =Mximo lmite de tiempo de recoleccin en el k-simo viaje para un vehculo recolector tipo v, (hrs, min). tc ij =Tiempo de carga recoleccin a lo largo del arco (i, j) para el k-simo viaje en un vehculo recolector tipo v, (hrs, min). td ij =Tiempo deviajeo desplazamiento alo largo delarco (i, j) paraelk-simo viajeen un vehculo recolector tipo v, (hrs, min). N :Nmero total de nodos en la red. I=Conjunto de todos los nodos alrededor del nodo i en la red. N=Nmero total de nodos en el vecindario del nodo i en la red. I =Conjunto de todos los nodosalrededor del nodo j en la red. N =Nmero total de nodos en el vecindario del nodo j en la red. = = = =+KvkVvNjNiijvk ij ijvk ijY D X D Minimizar1 1 1 1 sujeto a: A j i XKvkVv A j iijvke = = = e) , ( 11 1 ) , ( (1a) 4 A i j A j i X XKvkVv A i jjivkKvkVv A j iijvke e = + = = e = = e) , ( ) , ( 11 1 ) , ( 1 1 ) , ( (1b) N i Y XKvkVvNI jijvk ijvk,..., 2 , 1 11 1'= > += = e (2a) N j Y XKvkVvNI iijvk ijvk,..., 2 , 1 11 1' ''= > += = e (2b) = = e= s||.|

\|NiNjvA j iijvk ijV v C X Q1 1 ) , (,... 2 , 1 (3) V v T Y td X td tcvkKvkNjNiijvk ijKvkNjNiijvk ij ij,... 2 , 1 ) (1 1 1 1 1 1= s + + = = = = = = (4) N i K k V v Y Y X XVNI jNI jNI jNI jvk i j ijvk vk i j ijvk,.. 2 , 1 ; ,.. 2 , 1 ; ,.. 2 , 1 0' ' ' '= = = = + e e e e (5) 0 ; 0 > >ijvk ijvkY X(6) El objetivo bsico de este problema es obtener un conjunto de rutas de recoleccin desde un origen a varios puntos deoferta(arcos),minimizandoladistanciatotalrecorrida.Elprimergrupoderestriccionesaseguraquetodoslos arcosenlaredderecoleccin(variableXijvk)vanaserrecorridossolamenteunavez.Deacuerdoaqutipode topologa de red se trate, se trabajar con uno de los siguientes conjuntos de restricciones:uno para cuando la red es simtrica(1a)yelotroparacuandolaredesasimtrica(1b).Lasrestricciones(2)aseguranquecadanodoservisitadoalmenosporunvehculo.Adems,juntoalasrestricciones(5),garantizanqueelgraforesultantesea Euleriano. Las restricciones(3) hacenrespetar lacapacidad de la flota de vehculos.Las restricciones(4) limitan el tiempo total de recoleccin disponible en un da.Las restricciones(5) garantizan que el vehculo que ingresa a un nodo deba salir del mismo, es decir, se trata de las llamadas restricciones de conservacin de flujo, que se establecen portour ypor nodo, teniendo encuenta lavecindad decadanodo.Las restricciones (6) garantizan que todas las variablesdedecisinseanenterasynonegativas.Lasrestriccionesderompimientodesubtouresenestetipode problema, no debieran aplicarse, puesto que las restricciones de visitas a nodos (2) tienen valoresmayores o igualesa uno, permitiendo que un arco sea recorrido mas de una vez si as se requiriese dentro de una solucin cualquiera. 2.2.4Supuestos -Todos los arcos en la red de recoleccin deben ser recorridos al menos una vez. -Para que se genere un Tour de Euler, la red debe ser conectada.Asi mismo, para garantizar que el recorrido se inicieenelpuntomscercanoalabasedeoperaciones(garaje)yfinaliceenelpuntomscercanoalsitiode disposicinfinal,esnecesarioagregarunarcoficticio(t,s)queconecteelltimopuntoderecoleccindela microrutaconelprimero.Estearcoseconoceenlateoradegrafoscomoarcodetrnsito,ysusvaloresde distancia, demanda, tiempo de carga y tiempo de desplazamiento, deben tener un valor de cero oprximo a cero para que su incidencia sea mnima en el la generacin del recorrido ptimo. -Slo existe un lugar (nodo) de disposicin final de residuos. -Dadoqueelpresenteestudioserefiereaunproblemademicroruteo,lostiemposdeviajeentregaraje- microruta, microruta- relleno yrelleno - garaje, as como el tiempo en el relleno sanitario, no sern tenidos en cuenta. 2.2.5Construccin del itinerario Elitinerarioquedebeseguirseporcadaruta,debeiniciarsurecorridoenelpuntomscercanoalgaraje,debe minimizar los giros en U y a la izquierda, debe evitar, en lo posible, recorrer los arcos mas de una vez y finalmente debe terminar el recorrido en el punto ms cercano al sitio de disposicin final.Estas directrices, han sido estudiadas yreglamentadasporlasautoridadescorrespondientes(MDE-RAS[12]).Seproponeentonces,elsiguiente procedimiento de secuenciamiento: 5 Paso 1.Con base en los resultados del ARV, elabore una lista con todos los arcos disponibles (i, j) Paso 2.Elimine de la lista de disponibles el arco (t, s) que une el nodo final t con el nodo inicia s. Paso 3.Actualice la lista de arcos disponibles (i, j). Paso 4.Si la lista de arcos disponibles esta vaca vaya al paso (10) de lo contrario continu con el paso (5)Paso 5.Ubique los arcos candidatos cuyo nodo origen i sea el ltimo j asignado. Paso 6.Seleccione el arco (i, j) que permita ir de frente y vaya al paso (3), de lo contrario vaya al paso (7). Paso 7.Seleccione el arco (i, j) que permita girar a la derecha y vaya al paso (3), de lo contrario vaya al (8) Paso 8.Seleccione el arco (i, j) que permita girar a la izquierda y vaya al paso (3), de lo contrario vaya al (9) Paso 9.Seleccione el arco (i, j) que permite girar en U asgnelo y vaya al paso (3). Paso 10.Elabore el itinerario de recoleccin final con base en el orden dado a cada arco. 2.3RESULTADOS 2.3.1Validacin El problemadeasignacin de rutas devehculos tienedos estrategias desolucin:unapermitelaformacin deun grantourquerecorratodalazona,ylaotrapermitequesegenerenrutasqueinteractenentres.Elmodelofu implementadobajo distintosescenariosenloscualessemodificanlasrestriccionesdetiempoycapacidadafinde analizar su comportamiento y determinar las variaciones entre los recorridos generados en cada microruta. En un escenario 1, seutiliza la estrategia de formacin de un gran tour con un solo vehculo empleando restricciones de capacidad y tiempo ilimitadas.Bajo este escenario,se generan recorridos contnuos, ptimos desde el punto de vista de la programacin matemtica, que son fciles de implementar ycontrolar a nivel administrativo. Cuando se permite la formacin de rutas que interactan entre, pueden ocurrir los siguientes dos escenarios: 1.Slasrestriccionesdetiempoycapacidadtienensuficienteholgura(Escenario2),segeneranrutascontinuas, ptimas desde el punto de vista la programacin matemtica y relativamente fciles de supervisar.Aunque para su implementacin se deban tomar decisiones de tipo administrativo que prescriban el punto de inicio y trmino de algunos recorridos. 2.Slasrestriccionesdetiempoycapacidadestnmuyrestringidasotienepocaholgura(Escenario3),seda origen a laformacin de rutas continuas y discontinuas, ptimas desde el punto devistade lala programacin matemtica,peroquepresentanciertadificultadalmomentodeserimplementadas,puestoqueesnecesario definir elpunto deinicioy trmino dealgunos recorridos, as comoprescripcindealgunos delos tramos que deben ser agregados para garantizar la continuidad del itinerario. 2.3.2Aplicacin ElmodeloARVfuimplementadoenunazonaderecoleccindeSantafdeBogotconelnimodeobtener resultadosquepermitanrealizarcomparacionesconrespectoadossolucionesconocidas,unarutageneradaporun SistemasdeInformacinGeogrficaylarutautilizadaactualmenteporlaempresaprestadoradelserviciode recoleccin. La ruta generada por el Modelo ARV (Figura 2) presenta los resultados que se muestran en la Tabla 1. En trminos de distancia, se genera un ahorro de 458.13 mts respecto a la ruta actual. En trminos de tiempo, se logra unahorrode4.47minutos,loscualespodranincrementarsenotablementeencasodellegarautilizarfactoresde penalizacin por giros a la izquierda, en U y por arcos repetidos.En cuanto a la estructura del itinerario, se obtiene unahorrodel50%,enloqueserefiereagirosenUyalaizquierda.Loscrucesdecalle(continuardefrente) aumentan,loquequieredecirqueseincrementanlostrayectosenlnearecta,alavezqueelnmerodearcos repetidos (deadheading) se reduce en un 25%. Valelapenaresaltarqueaunquelasmejoraslogradassonobvias,stasnosonmuysignificativasentrminos relativos puesto quese estan comparando contramuybuenas soluciones. Sin embargo, los beneficios potenciales pueden ser muy altos en aplicaciones a gran escala, y mas an,cuando se trate dereas urbanas pocos estudiadas.Se esperaentonces queseperciban reducciones sustanciales decostos, sobretodo al tener en cuentazonas grandes que demanden cotidianamente grandesvolumenes de recoleccin de residuos. 6 Tabla 1RESULTADOS GLOBALES DE LAS MICRORUTAS PARMETROMICRORUTA EMPRESASIGARV Recorrido recoleccin9326,939365,619365,61 DISTANCIARecorrido desplazamiento4783,544583,554286,73 (metros)Distancia total recorrida 14110,4713949,1613652,34 Ahorro en metros161,31458,13 Red de recoleccin321,60321,86321,86 TIEMPORed de desplazamiento32,8130,1928,08 (minutos)Tiempo total del recorrido354,41352,05349,94 Ahorro en minutos2,364,47 Cruce de calle Frente695179 Giro a la derecha405233 ESTRUCTURAGiro a la izquierda192310 DEL ITINERARIOGiro en U Reversa1055 (nmero de veces)Total arcos recorridos138131127 Arcos de recoleccin899090 Arcos de trnsito (repetidos)494137 Giro a la izquierda (10 seg)3,1673,8331,667 Giro en U Reversa (30 seg)7,5003,7503,750 PENALIZACIONESArcos repetidos (5 seg)4,0833,4173,083 (minutos)Total penalizaciones (min)14,75011,0008,500 Tiempo total (min)369,160363,050358,440 Ahorro en minutos6,11010,720 8 9 112 13 1417 18 1922 23 2433 34 3542 43 4449 50 5125245329 25 26 27 2838455753563658555461015203139467111621324048 47413037 RECOLECCION DESPLAZAMIENTO REVERSA NO ATENDIDADISTANCIA RECORRIDA: 13652,34 mtsDURACION DEL RECORRIDO: 349,94 minFigura 2.RECORRIDO MICRORUTA ARV7 2.3.3Generacin de itinerarios El Modelo ARV tambin puede emplearse enmacroruteo.Es asi que para la generacin de distritos de recoleccin, bastaconimplementarelmodeloARVpara,ensuprimeraetapa,obtenerungrafopar.Luegosepuedeusarlametodologa que se describe a continuacin: Paso 1.Convertir la red en un grafo de grado par, implementando el modelo ARV. Paso 2.Generar ciclos, cuanto mas pequeos mejor. Paso 3.Convertir la red de arcos en una red con los ciclos asi asignados. Paso 4.Construir el mnimo rbol cobertor capacitado. Paso 5.Definir las rutas en la red original. 2.4 CONCLUSIONES El modelo de asignacin de rutas de vehculos para un sistema de recoleccin de residuos slidos en la acera, que se hapresentado,ofrecelaposibilidaddetrabajarcondosconjuntosdevariablesdedecisinenteras.Estopermite flexibilizarformulacionesdelproblema,pudindoseefectuarcambiosenlafuncinobjetivoyenlasrestricciones segnconvenganalcasoenparticular.Tambinpermitenidentificarclaramentelasactividadesquerealiza determinada tripulacin de recoleccin.Se facilitan tambin las tareas administrativas de elaboracin de itinerarios de recoleccin, al generar resultados en forma separada por vehculo, que redunda en una mejor evaluacin de la tasa de utilizacin por vehculo y del tiempo de recorrido por tripulacin. Se observa que el modelo ARV genera una mejor ruta que la sugerida por el SIG y la empleada actualmente porla empresaprestadoradelservicioderecoleccin,obtenindoseunarutademenorlongitud,queserecorreenmenos tiempo.Adems, al emplear el algoritmo de secuenciamento, se minimizan considerablemente los giros prohibidos. Seconcluyequelaestrategiadeformacindeungrantour,resultaserlamsindicadaparatrazarrutasde recoleccin, ya que proveesolucionesptimas que a la vez facilitan la implementacin y el control de recorridos a nivel administrativo. Esta formulacin puede extenderse al problema de asignacin de rutas sobre nodos (NRP), simplemente eliminando las restricciones de cobertura ycambiando el sentido de las restricciones de visitas a nodos.Tambin, segn se ha visto en la Seccin 2.3.3, se pueden generar distritos o zonas de recoleccin para cualquier tipo de red. Como lneas de investigacin futura, se plantean:la posibilidad de integrar este modelo ARV como parte de un SIG ymodificar laformulacin, agregando variables dedecisin, parapermitirms deun sitio dedisposicin yvarias estaciones de transferencia.Tambin podra disearseun procedimiento que adjudiquepenalizaciones por giros en U,girosalaizquierdaodesplazamientosenreversaapartirdelprocedimientodesecuenciacinpropuesto. Finalmente,estasherramientaspuedenextendersuaplicacinaproblemasafinescomoeldereparticinde peridicos o correo, barrido de calles o recoleccin de nieve. 3. PROBLEMA DE RUTEO DEL HELICPTERO CON CAPACIDAD FINITA El problema de ruteo de un helicptero con restriccin de capacidad finita y precedencias en los nodos, consiste en programarlarutaptimaquedebeseguirunhelicpteroalrecorrerunazonageogrficaconelfindetransportar personasentrediferentesnodos.Esnecesarioentoncesqueelhelicpterotransportedesdecadanodounnmero especificadodepasajerosqueviajarnalosdems.Laprogramacindelarutadeberespetarlarestriccinde capacidad delaparato. Adems, elhelicptero deberiniciar elrecorrido desdeun nodo inicialfijo yterminarloen algn otronodo tambin fijo,y quepuedeser diferentedel inicial.Por otro lado sesuponeque los pasajeros estn disponiblesenelmomentoenqueelhelicpterollegaacadanodo.Elproblemasuponeunconocimientodelas coordenadasgeogrficasdecadanodo,locualpermitelaconstruccindelamatrizdedistanciasotiemposque especifica la distancia o el tiempo de recorrido entre cada par de nodos. La solucin del problema buscar determinar larutaderecorridootiempototalmnimoquepermitetransportartodoslospasajerosrespetandolacapacidaddel aparato. No se consideran restricciones adicionales tales como: capacidad de recorrido mximo o nmero mnimo o mximo de pasajeros que puedan entrar o salir de cada nodo. 8 3.1.CONSIDERACIONESGENERALESSOBREELPROBLEMADERUTEODELHELICPTERO CON CAPACIDAD FINITA Este tipo de problema se puede considerar como una variacin del problema del agente viajero con restricciones de direccin de recorrido entre los nodos. En ste ltimo problema el agente debe realizar el recorrido ptimo de todos losnodosdesdeunnodoinicialhastaunnodofinal,respetandounconjuntoderestriccionesdesecuenciaque especifican un sentido de recorrido. Este problema es idntico al del ruteo del helicptero suponiendo una capacidad infinita, ya que cada pasajero genera una restriccin de recorrido que especifica una direccin en la ruta. En el problema de ruteo del helicptero de capacidad infinita, si el pasajerop viaja desde el nodo i hasta el nodo j, cada ruta factible del aparato deber recorrer primero el nodo i y luego el nodo j, con el fin de asegurar el transporte del pasajero desde i hasta j. Para el problema con restriccin de capacidad finita del helicptero, valen exactamente las mismas consideraciones. Sin embargo la restriccin adicional de capacidad restringean ms el espacio de soluciones factibles. Este tipo de problemas es conocido en la literatura como problema de tipo NP completo y su solucin involucra la utilizacin de tcnicas de optimizacin combinatoria (Ascheuer, Jnger & Reineld [13], Hamacher, Hochsttter & Moll [14]) 3.2. NOTACIN UTILIZADA EN LA FORMALIZACIN DEL PROBLEMA Se suponeun conjuntot dePpasajeros quedeben ser transportados,y un conjuntovdeNnodos ubicados enuna zonageogrfica.ExistendosfuncionesOyD,deorigenydestinorespectivamente,definidassobreelconjunto t que representan el nodo inicial y final de recorrido para cada pasajero: ) (:p O pO v t ) (:p D pD v t Se conoce la matriz de distancia M(n,m), definida para cada par de nodos n,m del conjunto v. Elhelicpterocomienzasurecorridoenelnodoiyterminasurecorridoenelnodof.Dondelosnodosiyf pertenecen al conjunto N. El helicptero tiene una capacidad de transporte de C pasajeros en cada trayecto de un recorrido cualquiera. Una ruta o recorrido factible R del helicptero es una secuencia ordenada de nodos de longitud finitaque comienza en el nodo i y finaliza en el nodo f, representada en el vector R. Es posible que los nodos se repitan. La longitud L(R) del recorrido R es el nmero de nodos que lo componen, incluyendo repeticiones de nodos. De esa manera R(1) = i, R(L(R))=f. R = [R(1), R(2), ..., R(L(R))] (7) La distancia total recorrida por el helicptero en el trayecto R es igual a M(R), calculada como: =+ =1 R L1 j1 j R j R M R M) ()) ( ), ( ( ) ( (8) 9 3.3. TCNICA PROPUESTA PARA LA SOLUCIN DEL PROBLEMA DE RUTEO DEL HELICPTERO CON CAPACIDAD FINITA La tcnica propuesta de solucin del problema de ruteo supone la utilizacin de tres tipos de heursticas: una primera heurstica se encarga de obtener una solucin inicial factible a travs de una tcnica de insercin basada en ahorros (Timlin & Pulleyblanck, [15]). Una segunda heurstica tiene como objetivo obtener mejoras en la solucin inicial por mediodeintercambiosdetipok-opt,parak=2ok=3(Laporte,Gendreau,Potvin&Semer,[16]).Unatercera heurstica est basada en la tcnica de enfriamiento o recocido simulado en donde la heurstica de vecinaje tenida en cuentaesdeltipo2-opto3-opt(Phan&Karaboga[17],Kirkpatrick&Gelatt[18]).Lastrestcnicassern explicadas a continuacin. 3.3.1. Heurstica de insercin basada en ahorros La tcnica de insercin que a continuacinproponemos est basada en trabajos anteriores de Timlin & Pulleyblanck (Timlin & Pulleyblanck, [15]) y supone la construccin iterativa de una ruta factible a partir de rutas no factibles. La idea consiste en completar una ruta actual no factible, por medio de la insercin del mejor trayecto determinado por la combinacin de un pasajero que no viaje en la ruta actual y de un punto de insercin en la ruta actual. Suponemos que el trayecto actual es R, de longitud L(R) , y que el pasajero p no viaja en la ruta R, por dos razones: 1.la ruta no hace el recorrido desde O(p) hasta D(p), o2.si el helicptero realiza esa ruta, no tiene capacidad para transportar el pasajero p. Existen dos maneras de insertar el pasajero p en la ruta actual: 1.Insertando elcamino[O(p), D(p)]en cualquier punto deinsercinkdelaruta actual,donde,1