Disponible en: http://redalyc.uaemex.mx/src/inicio/ArtPdfRed.jsp?iCve=149212815002 RedalycSistema de Informacin CientficaRed de Revistas Cientficas de Amrica Latina, el Caribe, Espaa y PortugalDaza, Julio Mario; Montoya, Jairo R.; Narducci, FrancescoRESOLUCIN DEL PROBLEMA DE ENRUTAMIENTO DE VEHCULOS CONLIMITACIONES DE CAPACIDAD UTILIZANDO UN PROCEDIMIENTOMETAHEURSTICO DE DOS FASESRevista EIA, Nm. 12, diciembre-sin mes, 2009, pp. 23-38Sin InstitucinColombia Cmo citar?Nmero completoMs informacin del artculoPgina de la revistaRevista EIAISSN (Versin impresa): 1794-1237revista@eia.edu.coSin InstitucinColombiawww.redalyc.orgProyecto acadmico sin fines de lucro, desarrollado bajo la iniciativa de acceso abiertoRevista EIA, ISSN 1794-1237 Nmero 12, p. 23-38. Diciembre 2009Escuela de Ingeniera de Antioquia, Medelln (Colombia)RESOLUCIN DEL PROBLEMA DE ENRUTAMIENTO DE VEHCULOS CON LIMITACIONES DE CAPACIDAD UTILIZANDO UN PROCEDIMIENTO METAHEURSTICO DE DOS FASESJulio Mario Daza* Jairo r. Montoya** Francesco narDucci***RESUMENEste artculo presenta un procedimiento alternativo para resolver el problema de enrutamiento de vehculos con limitaciones de capacidad y flota homognea (CVRP). Se propone un algoritmo metaheurstico que consta de la combinacin de dos fases: diseo de rutas y planificacin de la flota. La primera fase est compuesta de procedimientos heursticos y metaheursticos donde se construye una solucin inicial que es mejorada mediante bsqueda tab obteniendo soluciones no dominadas en tiempo de clculo polinomial. Para la segunda fase, correspondiente a la planificacin (scheduling) de la flota, se propone abordar el pro-blema partiendo de una analoga con el problema de programacin de mquinas paralelas idnticas. Este procedimiento tiene como funcin objetivo minimizar el costo fijo causado por la utilizacin de la capaci-dad instalada. Esta alternativa se aplic sobre una instancia generada aleatoriamente y una instancia real arrojando resultados significativos al compararse con las heursticas evaluadas.PALABRAS CLAVE: problema de ruteo de vehculos; problema del agente viajero; optimizacin combi-natoria; heurstico.*Ingeniero Industrial, Magster en Ingeniera Industrial. Profesor, Corporacin Universitaria de la Costa, Barranquilla, Colombia. juliomariodaza@hotmail.com.** Ingeniero Industrial. Master of Science in Industrial Engineering and Managment; Doctor en Ingenieria Industrial. ProfesorAsociado,EscuelaInternacionaldeCienciasEconmicasyAdministrativas,UniversidaddeLaSabana, Cha (Cundinamarca), Colombia. jairo.montoya@unisabana.edu.co. *** Ingeniero Industrial, Magster en Ingeniera Industrial. Ingeniero consultor y docente catedrtico, Departamento de Ingeniera Industrial, Universidad del Norte, Barranquilla, Colombia. fnarducci78@hotmail.com.Artculo recibido 27-VI-2009. Aprobado 18-XI-2009Discusin abierta hasta junio de 201024Revista EIAResolucin del pRoblema de enRutamiento de vehculos...SOLVING THE CAPACITATED VEHICLE ROUTING PROBLEM USING A TWO-PHASE METAHEURISTIC PROCEDUREABSTRACTThis paper presents an alternative procedure to solve the Capacitated Vehicle Routing Problem (CVRP) with homogeneous fleet. The paper proposes a two-phase metaheuristic algorithm: routes design and fleet scheduling. The first phase is based on heuristics and metaheuristics procedures in order to build an initial solution that is then improved using tabu search to obtain non-dominated solutions in polynomial computational time. For the second phase, corresponding to fleet scheduling, the problem is approached using an analogy with the identical parallel machine scheduling problem. This procedure looks for the minimization of the fixed cost of using installed capacity as the objective function. The proposed procedure was tested using both a random-generated instance and real data, giving competitive results in comparison with other heuristics tested.KEY WORDS: vehicle routing problem; traveling salesman problem; combinatorial optimization; heuristic.RESOLUO DO PROBLEMA DE ROTEAMENTO DE VECULOS COM LIMITAES DE CAPACIDADE UTILIZANDO UM PROCEDIMENTO METAHEURSTICO DE DUAS FASESRESUMOEste artigo apresenta um procedimento alternativo para resolver o problema de roteamento de veculos com limitaes de capacidade e frota homognea (CVRP). Prope-se um algoritmo metaheurstico que consta da combinao de duas fases: desenho de rotas e planejamento da frota. A primeira fase est composta de pro-cedimentos heursticos e metaheursticos onde se constri uma soluo inicial que melhorada mediante busca tabu obtendo solues no dominadas em tempo de clculo polinomial. Para a segunda fase, correspondente ao planejamento (scheduling) da frota, se prope abordar o problema partindo de uma analogia com o problema deprogramaodemquinasparalelasidnticas.Esteprocedimentotemcomofunoobjetivominimizaro custo fixo causado pela utilizao da capacidade instalada. Esta alternativa se aplicou sobre uma instncia gerada aleatoriamente e uma instncia real dando resultados significativos ao se comparar com as heursticas avaliadas.PALAVRAS CDIGO: problema de roteo de veculos; problema do agente viajante; otimizao combi-natria; heurstico.1.INTRODUCCINEl problema de enrutamiento o ruteo de ve-hculos (VRP, vehicle routing problem) data del ao de 1959 y fue introducido por Dantzig y Ramser, quie-nes describieron una aplicacin real de la entrega de gasolina a las estaciones de servicio y propusieron una formulacin matemtica. Cinco aos despus, Clarke y Wright propusieron el primer algoritmo que result efectivo para resolverlo. Y es as como se dio comienzo a grandes investigaciones y trabajos en el rea de ruteo de vehculos.Esteproblemapuedeentendersecomola interseccindedosconocidosproblemasdeopti-mizacincombinatoria.Elprimero,eldelagente 25Escuela de Ingeniera de Antioquiaviajero (TSP, traveling salesman problem) conside-rando la capacidad de cada automvil como infinita (Applegate et al., 2006) y el de empaquetamiento en compartimentos(BPP,binpackingproblem)(Mar-tello y Toth, 1990).Porende,elproblemadeenrutamientode vehculosconlimitacionesdecapacidadyflota homognea (CVRP-HF, capacitated vehicle routing problem with homogenous fleet) estudiado se con-sideraunproblemadeoptimizacincombinatoria y pertenece a la clase de problemas NP-completos, paralosquenoexisteunalgoritmodetiempo polinomialquepuedaresolverlosaoptimalidad. Esto ha llevado a muchos investigadores a explorar diversosmtodosparaabordarlos.Lamayorade estos mtodos puede ser ampliamente clasificados ya sea como algoritmos exactos o de optimizacin (Aarts y Lenstra, 2003). Los algoritmos exactos son los que producen una solucin ptima empleando varias tcnicas que permitan explorar el espacio de bsqueda. Estos m-todos exactos incluyen los que se basan en tcnicas como ramificacin y acotamiento, planos cortantes y programacin lgica de restricciones. Estos algorit-mos son razonablemente eficientes para problemas de tamao modesto (Ignizio y Cavalier, 1994); aun-que con ellos es posible en principio resolver los de cualquier tamao, en la prctica no es as, debido al gran nmero de soluciones posibles para cualquier problema de tamao razonable.Durantelosaossesenta,losinvestigado-restratabanderesponderlasiguientepregunta: Existeunalgoritmodeoptimizacincontiempo deejecucinpolinomialparaunproblemacomo elTSP?Hastaahora,nadiehapodidoencontrar una respuesta a esta pregunta. Sin embargo, Karp (1972)mostrquesilarespuestaessparael TSP,haytambinotrosproblemasdifcilespara los cuales podra hallarse un algoritmo polinomial. Como ningn algoritmo se ha encontrado para al-guno de estos problemas, Reeves (1996) dice que esto sugiere categricamente que la respuesta a la preguntaoriginalesno.Porellomismoelrea deoptimizacincombinatoriaresultacadavez msatrayenteparainvestigadoresyacadmicos, ya que cualquier contribucin en este mbito tiene repercusiones directas en la industria.En este artculo se propone un procedimiento eficientebasadoentcnicasmetaheursticaspara resolver el problema de enrutamiento de vehculos con limitaciones de capacidad y flota homognea, denominado CVRP-HF.Esteartculoestorganizadodelasiguiente manera. La seccin 2 presenta el VRP, sus variantes ysureduccinaotrosproblemasdeoptimizacin combinatoria.Laseccin3presentalosmtodos desolucinutilizadosparaabordarestaclasede problemas. La seccin 4 presenta el planteamiento delaalternativadiseadaparagenerarunasolu-cin factible al problema planteado. Finalmente, se presentan en las secciones 5 y 6 respectivamente la evaluacin de desempeo del modelo planteado y las conclusiones.2.ASPECTOS TERICOS2.1Problema de ruteo de vehculos(VRP)Agrandesrasgosunproblemaderuteode vehculos (VRP) consiste en, dado un conjunto de clientesydepsitosdispersosgeogrficamentey una flota de vehculos, determinar un conjunto de rutas de costo mnimo que comiencen y terminen enlosdepsitos,paraquelosvehculosvisitena los clientes mximo una vez. Dentro de esta defini-cin, el problema se ubica en un amplio conjunto de variantes: CVRP (Capacitated VRP) (Ralphs, Hartman y Galati, 2001) MDVRP (Multi-Depot VRP) (Hjorring, 1995) PVRP(PeriodicVRP)(Baptista,Oliveiray Zquete, 2002) 26Revista EIAResolucin del pRoblema de enRutamiento de vehculos...SDVRP (Split Delivery VRP) (Dror, Laporte yTrudeau,1994;Archetti,MansiniySperanza, 2001) SVRP (Stochastic VRP) (Laporte y Louveaux, 1998) VRPB(VRPwithBackhauls)(Ralphs,Hart-man y Galati, 2001); Jacobs-Blecha y Goetschalckx, 1992) VRPPD(VRPwithPick-UpandDelivering) (Righini, 2000) VRPSF (VRP with Satellite Facilities) (Bard et al., 1997) VRPTW (VRP with Time Windows) (Cordeau et al., 2002)2.2Problema del agente viajero(TSP)ElTSPconstituyelasituacingeneralyde partida para formular otros problemas combinato-riosmscomplejos,aunquemsprcticos,como el ruteo de vehculos y la programacin de tareas dependientes del tiempo de alistamiento. En el TSP se dispone de un solo vehculo que debe visitar a todos los clientes en una sola ruta y a costo mni-mo.Nosuelehaberundepsito(ysilohubiera, no se distinguira de los clientes), no hay demanda asociada a los clientes y tampoco hay restricciones temporales.Denotaremos por +(i) y (i) al conjunto de nodosadyacenteseincidentesalnodoi,esdecir, +(i) = {jV | (i, j)E} y (i)={jV | (j, i)E}. De manera similar, el conjunto de arcos incidentes hacia el exterior e interior del nodo i se definen como +(i) = {(i, j)E} y -(i) = {(j, i) E}.Elproblemapuedeformularsematemtica-mente mediante programacin lineal entera (PLE) como sigue (Clarke y Wright, 1964):min`c]x](,])eL (1) `x]]ez+()= 1 vi e I(2) `x]ez-(])= 1 v] e I(3) ` x]eS,]ez+()\S~ 1 vS c I(4) x] e {u,1]v(i, ]) e E(5) 2.3Complejidad del TSPy aproximacionesLamayorpartedelosproblemasderuteo devehculossongeneralizacionesdelTSP.Enese sentido,puedeconsiderarseelVRPmssimple. No obstante, pertenece a la clase de problemas NP, debidoaquetomandounasecuenciacualquiera (certificado)stapodraserverificadaentiempo polinomial. Adems, este problema puede conside-rarse del tipo NP-completo lo cual puede compro-barse reducindose el problema de optimizacin a uno de decisin mediante un ciclo hamiltoniano de lasiguientemanera:dadoungrafoG,esposible determinar una ruta a travs de todos los nodos de G una sola vez? (Garey y Johnson, 1979).El tiempo de clculo necesario para resolver el TSP se incrementa con rapidez a medida que au-menta el nmero de ciudades n. En un caso general el nmero de rutas factibles que debe considerarse es(n1)!/2,puestoquehay(n1)posibilidades paralaprimeraciudaddespusdelaciudadde residencia del agente, (n 2) posibilidades para la si-guiente ciudad y as sucesivamente. El denominador 2 surge porque cada ruta presenta una ruta inversa equivalente con la misma distancia (TSP simtrico). As,mientrasunTSPcon10ciudadestieneno Sujeto a:27Escuela de Ingeniera de Antioquiamenos de 200.000 soluciones factibles que deben ser consideradas,unproblemacon20ciudadestiene alrededor de 1016 soluciones factibles, mientras que un problema con 50 ciudades tiene alrededor 1062 (Hillier y Lieberman, 2001).Lassolucionesptimasaesteproblema parapequeasinstanciaspuedenserencontra-dasentiemporazonable(polinomial)mediante programacinlinealentera(Nilsson,2003).Sin embargo, el ser considerado NP-duro ocasiona que no se obtengan para grandes instancias algoritmos (exactos)queencuentrensolucionesptimasen untiempopolinomialdeterminstico.Todosestos algoritmoscrecenexponencialmente.Podemos disminuirelcrecimientopolinmicoalproblema si establecemos tours cercanos al ptimo. Con esto ganamos velocidad, a costa de la calidad del tour, siendolavelocidadyelencierrounapropiedad interesantedelasheursticasparaesteproblema. Hay dos modos de encontrar el tamao ptimo de una instancia para el TSP. El primero es resolverlo ptimamente encontrando as la longitud. El otro es el clculo de la cota inferior de Held-Karp (HKLB), queproduceunlmiteinferiorparalasolucin ptima. Esta cota inferior es la norma que se juzga en el rendimiento de un algoritmo de aproximacin para el problema (Nilsson, 2003). Adems, la HKLB es en la actualidad la solucin a la relajacin a la PLE en la cual est formulado el TSP. La solucin puede encontrarse en el tiempo polinmico usando elmtodosimplexyunalgoritmodeseparacin de restricciones polinomial (Johnson, McGeoch y Rothberg, 1996).Para resolver el TSP normalmente se utilizan algoritmos de aproximacin o heursticos, la diferen-cia radica en que stos nos dan una garanta de cmo podemosobtenermalassoluciones.Normalmente especificada como un tiempo c del valor ptimo. El algoritmo de mejor solucin existente es el de Arora (1998). El algoritmo garantiza una aproximacin de (1+1/c) veces el valor ptimo, para todo c > 1. Esto se basa en particin geomtrica y rboles de expan-sin. Aunque tericamente c puede ser muy grande, esto tendr un efecto negativo en su tiempo de co-rrida (O(n(log2n)O(c) para instancias bidimensionales).2.3.1Problemadeempaquetamientoen compartimentos (BPP)El problema consiste en embalar un conjunto de objetos en varias cajas o contenedores tal que el peso o el volumen total no exceda un valor mximo de las cajas. De una manera precisa, definimos un problema de empaquetamiento en compartimentos (BPP, bin packing problem) como sigue. Tenemos un conjunto finito de artculos e cada uno de los cuales tienen un peso w y una restriccin de precedencia entre estos, incurriendo en un costo cij (tal vez infi-nito). Posteriormente definimos un grupo ordenado para ser un subconjunto de artculos de modo que el peso total del grupo pedido no exceda la capacidad de la caja y ningn costo entre los artculos adyacen-tes en el grupo sea infinito.Lametaprimariaescrearunasolucinfac-tible con el nmero mnimo de grupos ordenados. Cuandodossolucionestienenelmismonmero degruposordenados,elqueposeacostomnimo seescoge.Matemticamentelaformulacindel problemapuedeseras:dadounconjuntofinito deelementosE={e1,,en}conpesosasociados W={w1,,wn}talesque0wiw(Bin),sedivide E en N subconjuntos, de forma que la suma de pesos en cada particin sea a lo sumo w(Bin), teniendo en cuenta que N sea mnimo.2.3.2Problemademagentesviajeros, m-TSPEl problema de los m agentes viajeros o m-TSP es una generalizacin del TSP en la cual se tienen undepsitoymvehculosoagentes.Elobjetivo esconstruirexactamentemrutas,unaparacada vehculooagente,demodoquecadaclientesea visitado una vez por uno de los vehculos o agentes. Cada ruta debe comenzar y terminar en el depsito y puede contener a lo sumo p clientes, esto se deter-mina mediante la solucin de BPP. Una formulacin 28Revista EIAResolucin del pRoblema de enRutamiento de vehculos...mediantePLE,dadaporMiller,TuckeryZemlin (1960) es la siguiente:min`c]x](,])eL (6) `x0]]eA+(0)= m (7) `x]eA-(])= 1 v] e I\{u](8) `x]eA-(])~ 1 v] e I\{u](9) px] < p -1 v(i, ]) e E, i = u, ] = u (10) x]e {u,1]v(i, ]) e E(11) 2.3.3Problemadeenrutamientodeve-hculos con limitacin de capacidades y flota homognea (CVRP-HF)Matemticamente,unainstanciaI=(G,C, T,D,F)delCVRP-HFsepuededefinircomouna extensin del m-TSP, dado un grafo dirigido G = (V, E), donde V es el conjunto de nodos que representan las ciudades o clientes y E es el conjunto de arcos que los conectan, relacionados con la matriz de costos C = (cij ), de tamao N x N, de modo que cada arco tieneasignadouncostocij.Desunarreglodela forma (pi) que especifica la informacin de deman-da de cada cliente. F es un arreglo de la forma (Pk) que contiene los datos de capacidad mxima de los vehculos. La flota est compuesta por M vehculos, es decir, 1 k M.El problema tiene el objetivo de encontrar una matrizX = (xijk), de tamao N x N x M, donde las variables binarias xijk indican si el arco (i, j) se utiliza en la solucin para ser visitado por k. El problema de PLE es como sigue:min```c]x]kMk=1N]=0N=0(12) ``x]kN]=1Mk=1< Hi = u(13) ``x]kN]=0Mk=1= 1vi e |1, N](14) `x]kN]=1= `x]kN=1 vk e {1, H], i = u (15) ``px]kN]=0N=0< Pkvk e {1, H](16) ``x]kN]=1]eSN=1eS< |S| - 1 vS L (I - {u]), |S| ~ 2, k e {1, H] (17) x]k e {u,1] vi, ] e |1, N], vk e {1, H] (18) Las restricciones (13) indican que del centro dedistribucindebenpartirmximoMvehculos. Lasrestricciones(14)y(15)garantizanqueunoy solo un vehculo visite y abandone cada cliente for-mando por cada ruta un TSP. Las ecuaciones (16) muestranrestriccionesdecapacidadvehicularen trminos de peso, de acuerdo con lo sugerido por DantzigyRamser(1959);determinarelconjunto piquenosobrepasepksedenominaproblemade empaquetamiento en compartimentos (BPP por sus siglaseningls).Finalmentelosconjuntosderes-tricciones(17)y(18)establecen,respectivamente, lainexistenciadesubrutasinconexasylosvalores admisibles para las variables de decisin.2.3.4Mtodos de solucinEn la actualidad, la atencin se ha centrado msymsenelusodemtodosdeoptimizacin combinatoria,debidoalacomplejidaddeestos Sujeto a:Sujeto a:29Escuela de Ingeniera de Antioquiaproblemasenlaobtencindesolucionesptimas entiempopolinomial.Estastcnicassedividen entcnicasdeoptimizacinlocalconvencional (heursticas) y tcnicas de optimizacin local inteli-gente (metaheursticas). A diferencia de un enfoque algortmico exacto, un mtodo de optimizacin no tiene una base de matemtica formal que lo sustente, es desarrollado ms o menos por intuicin (Ignizio y Cavalier, 1994).La idea ms genrica del trmino heurstica est relacionada con la tarea de resolver inteligen-temente problemas reales usando el conocimiento disponible (Narducci, 2005). Heurstica proviene de una palabra griega con un significado relacionado con el concepto de encontrar y se vincula a la su-puesta exclamacin eureka de Arqumedes al descu-brir su famoso principio (De la Cruz, 2003). Reeves (1996)defineeltrminoheursticadelasiguiente forma: Una tcnica heurstica (o simplemente una heurstica) es un mtodo que busca buenas solucio-nes(esdecir,solucionescercanasalptimo)aun costo computacional razonable sin poder garantizar optimalidad.LastcnicasheursticasparaelVRP,en general,puedenserclasificadasdentrodecuatro categoras (Gaskell, 1967), as: constructivas, como el mtodo de los ahorros de Clarke y Wright, con base en el ahorro generado por insertar nuevos clientes en cada vehculo hasta completar una solucin final; mtodosdeagruparprimero,luegoenrutar,que agrupan los clientes en varios subconjuntos, asignan cada subconjunto a un vehculo y luego resuelven cada TSP correspondiente (por ejemplo, el mtodo deFisheryJaikumar,basadoenelproblemade asignacingeneralizadoyelalgoritmodebarrido deGilletyMiller);mtodosheursticosdeenrutar primero, luego agrupar, que empiezan resolviendo el TSP definido por todos los clientes y luego parten la ruta hallada para asignar un tramo a cada vehculo (comoel mtodo de curvas de llenado de Bower-man, Calamai y Brenthall, y el mtodo de particin ptimadeBeasley);yfinalmente,losmtodosde mejoramiento, como los intercambios OrOpt.Las metaheursticas (tambin llamadas heurs-ticas modernas) han aparecido durante las ltimas dos dcadas (Yu, 1998) y tienen como funcin tomar inicialmente una solucin factible, para luego mejo-rarla usando heursticas de mejoramiento embebidas enunaestructuramsgeneral.Lacaracterstica comn de estos enfoques es el uso de mecanismos para evadir ptimos locales (Moraga, 2002). Glover y Laguna (1997) definen el trmino metaheurstica como una estrategia maestra que gua y modifica otras heursticas para producir soluciones ms all de aqullasquesonnormalmentegeneradasen una solicitud por optimalidad local. Las heurs-ticas guiadas por tal metaestrategia pueden ser procedimientosdealtonivelonadamsque unadescripcindemovidasdisponiblespara transformarunasolucinenotra,juntocon reglas de evaluacin asociadas.Por otra parte, entre las tcnicas metaheurs-ticasparaelVRPseencuentranlascoloniasde hormigas, bsqueda dispersa, algoritmos genticos ylabsquedatab,entreotras.Enlafigura1se puede observar un compendio de las tcnicas meta-heursticas utilizadas para resolver los problemas de optimizacin combinatoria. Se puede observar que se han empleado varias estrategias para resolver el problema, que se pueden agrupar en tres grandes categoras: bsqueda secuencial por entornos (o ve-cindarios), redes neuronales y algoritmos evolutivos. Dentro de cada categora se encuentran subclasifi-caciones, con el fin de especificar las caractersticas delosprocedimientos,segnseanprobabilistaso deterministas,conunoovariosoperadores,cons-tructivos, con perturbaciones, con cruzamiento de informacin o sin l, etc.En esta investigacin se optimiz la solucin mediante la metaheurstica llamada bsqueda tab. sta es la ms reconocida entre las metaheursticas y ha sido extensamente aplicada a numerosos proble-mas combinatorios tales como VRP, TSP, el problema de asignacin cuadrtica (QAP) o el problema de la mochila 0-1 multidimensional (0-1 multidimensional knapsack problem). De acuerdo con Laporte et al. (2000), el procedimiento de bsqueda tab ha sido la 30Revista EIAResolucin del pRoblema de enRutamiento de vehculos...ms exitosa metaheurstica, en especial para resolver el VRP. En su libro, Glover y Laguna (1997) presentan una muy buena discusin sobre la aplicabilidad de bsqueda tab en problemas de optimizacin reales.3.METODOLOGA DE SOLUCIN PROPUESTALa alternativa diseada e implementada para resolverelCVRP-HFesunaaproximacinmeta-heurstica que consta de la combinacin de dos fases que son el ruteo y la planificacin, como se muestra en la figura 2.3.1Fase I. Diseo de rutasLaprimerafaseesdebsquedaestratgica ysecomponedeprocedimientosheursticosque pueden subdividirse en dos partes. La primera parte esdenominadadeconstruccinyutilizamtodos deoptimizacinlocalconvencional(heursticas), con el objetivo de acercar el proceso hasta una muy buenasolucininicial.Lasegundaparte,llamada mejoramiento, emplea un mtodo de bsqueda local inteligente(metaheurstica)concaractersticasde memoria para mejorar as los resultados logrados en la primera parte y obtener soluciones no dominadas, esto con un tiempo polinomialmente razonable.Mtodo de asignar primero, rutear despus. Los mtodosasignarprimeroyruteardespus(cluster first, route second) procede en dos fases. Primero se buscagenerargruposdeclientes,tambinllama-dos clusters, que estaran en una misma ruta en la solucin final. Luego, para cada cluster se crea una ruta que visite a todos sus clientes. Las restricciones decapacidadseconsideranenlaprimeraetapa, asegurandoquelademandatotaldecadacluster nosuperelacapacidaddelvehculo.Porlotanto, Figura 1. Tcnicas para resolver problemas de optimizacin combinatoria31Escuela de Ingeniera de Antioquiaconstruir las rutas para cada cluster es un TSP que, dependiendo de la cantidad de clientes en el cluster, se puede resolver en forma exacta o aproximada.Heursticadelbarridoosweep.Enla heursticadebarrido(Wren,1971;Wreny Hol liday, 1972; Gillett y Miller, 1974), los clusters se forman girando una semirrecta con origen eneldepsitoeincorporandolosclientes barridos por dicha semirrecta hasta que se viole la restriccin de capacidad. Cada cluster luego se rutea resolviendo un TSP.El procedimiento se repite n veces, co-menzando en cada ejecucin por un cliente diferentealaformaenquesegeneranlos clusters; las rutas obtenidas no se superponen, lo que puede ser bueno en algunos casos. Un posible resultado de la aplicacin de este algo-ritmo se muestra en la figura 3 donde las lneas punteadas indican los lmites de los clusters.Figura 2. Planteamiento detallado del algoritmo propuesto Figura 3. Solucin obtenida mediante el algoritmo de barrido32Revista EIAResolucin del pRoblema de enRutamiento de vehculos...Este algoritmo puede aplicarse en problemas planos, es decir, en los que cada nodo se correspon-de con un punto en el plano y las distancias entre ellos se definen como la distancia euclidiana o, en su defecto, distancia de Manhattan.3.1.1Heurstica de insercin ms prximaEste es un mtodo voraz (greedy, en ingls), que gradualmente construye un tour por la repetida seleccin de los arcos ms cortos y los adhiere a un tour, con tal de que no cree un ciclo con menos de los N bordes, o aumentos el grado de cualquier nodo a ms de 2. No se debe agregar el mismo borde dos veces durante el tour. La complejidad est dada por (O(n2log2(n)) y normalmente presenta entre el 15 y 20 % de la HKLB (Johnson y McGeoch, 1995).3.1.2Algoritmo k-OptUna versin reducida del algoritmo 3-opt es el algoritmo Or-opt (Or, 1976), que consiste en eli-minar una secuencia de k clientes consecutivos de la ruta y colocarlos en otra posicin de la ruta, de modo que permanezcan consecutivos y en el mismo orden.Primeroserealizanlasmovidasconk=3, luego con k = 2 y finalmente con k = 1. En la figura 4 se muestra una ruta y todas las posibles maneras de reubicar los 3 primeros clientes a la manera de Or-opt. El tiempo de corrida del 2-opt producir en el peor de los casos un tamao de tour menor que el 5 % sobre la HKLB, mientras que el mejoramiento de la heurstica 3-opt tendr usualmente un tour de 3 % sobre la HKLB (Aarts y Lenstra, 2003). La com-plejidad en el peor de los casos es de O(log2(n)) para ambos movimientos (Fredman et al.,1995). 3.1.3Bsqueda tab (BT)La bsqueda tab es una tcnica iterativa de bsquedalocalinteligentequetratadeevitarque las soluciones caigan en ptimos locales. Para esto se utilizan unas estructuras de memoria de corto y largo plazo, acompaadas de criterios de aspiracin. En esta tcnica en una iteracin se pretende pasar de una solucin a la mejor solucin vecina, sin impor-tar si esta es mejor o peor que la solucin actual. El criterio de terminacin puede ser un cierto nmero mximo de iteraciones o un valor de la funcin por optimizar.Entrelascaractersticasrelevantesque posee este mtodo e implementadas en esta inves-tigacin se encuentran la denominada lista tab y el criterio de aspiracin. El objetivo ms general de la lista tab es continuar estimulando el descubrimiento de soluciones de alta calidad. En general, un tipo co-mn de restriccin opera seleccionando algn sub-conjunto de atributos y declarando un movimiento tab un determinado nmero mnimo de veces. Otra caracterstica de la BT son los criterios de aspiracin que se introducen para determinar cundo pueden ser reemplazadas las restricciones tab, eliminando as una clasificacin tab aplicada a un movimiento en otro caso (Glover y Melian, 2003).Figura 4. Movidas para reubicar los 3 primeros clientes de una ruta 33Escuela de Ingeniera de AntioquiaEnestainvestigacinsetienenencuenta dos tipos de criterios de aspiracin. El primero es el criterio de aspiracin por defecto, que se presenta si todos los movimientos disponibles estn clasificados comotab,entoncesseseleccionaelmovimiento menos tab. El segundo criterio es el de aspiracin por objetivo forma global, la cual consiste en eliminar una clasificacin tab de un movimiento cuando el movimiento conduce a una solucin mejor que la mejor obtenida hasta ahora. Teniendo en cuenta las caractersticasanteriores,elprocedimientometa-heurstico implementado permite guiar un algoritmo heurstico de bsqueda local para explorar el espacio de soluciones ms all de la simple optimalidad local, como se muestra en la figura 5.deseados,satisfaciendoalavezungrannmero derestriccionesdetiempoyrelacionesentrelas actividadesylosrecursos.Laprogramacinde operaciones se encarga de la localizacin de tareas atravsdeltiempo,enrecursosquesonsiempre escasos debido a sus costos. Es un proceso de deci-sin, con la meta de optimizar uno o ms objetivos (Narducci, 2005).La planeacin (scheduling) de transporte con-siste en la asignacin de un conjunto de vehculos en un orden y a ciertos instantes determinados, con el fin de completar una serie de tareas de carga/despacho paraobtenerciertosresultados(funcinobjetivo), comoelmnimotiempolibredelosvehculos,o inclusoeltiempodeterminacinmscorto,bajo ciertas restricciones (Qiu y Hsu, 1999).En la presente investigacin se propone opti-mizar el uso de la capacidad instalada abordando un problema de secuenciacin en mquinas paralelas idnticas,dondelosrecursossonlosvehculoso transportadores, y los trabajos, las rutas a las cuales debenservir.Encuantoalostiemposdeprocesa-miento, estos son reemplazados por el tiempo que se tarda un transportador en abastecer todos los clientes de la ruta. Los tiempos son tomados de T, T = (Tij), una matriz de tamao N x N que contiene los tiempos de ruta entre clientes, esto es, viajar desde el cliente i hasta j requiere Tij unidades de tiempo. En cuanto a las restricciones del modelo, encontramos primero las precedencias de las rutas y segundo el umbral de tiempo en el cual se debe realizar la programacin de la jornada.Una manera de extensa difusin para la pre-sentacindeplanesoperativoseseldiagramade Gantt, que en la programacin de operaciones re-presenta tiempo contra recursos. De esta manera es posible representar efectivamente informacin sobre asignacin de tareas en recursos, secuenciacin de trabajos y fechas de principio y fin de tareas parciales y totales. Se muestra el diagrama de Gantt realizado de esta investigacin en la figura 6.Figura 5. Procedimiento de mejoramiento mediante bsqueda tab3.2Fase II. Planificacin de la flotade vehculosPara la segunda fase (planificacin) se propo-ne un procedimiento que tiene como funcin primor-dial minimizar el costo fijo causado por la utilizacin de la capacidad instalada. En otras palabras, se busca disminuirloscostosenqueincurreunoperador logstico al definir una cantidad de vehculos en un ruteo determinado.De forma genrica, Morton y Pentico (2003) afirman que programar operaciones es el proceso de organizar, elegir y dar tiempos al uso de recursos para llevar a cabo todas las actividades necesarias, paraproducirlassalidasdeseadasenlostiempos Lista TabUsa tcnicas de memoriapara ayudar a identificar un cicloSolucinptima34Revista EIAResolucin del pRoblema de enRutamiento de vehculos...En la figura 7, es posible apreciar la manera en que la fase de planificacin funciona. La mejor utilizacindelostiemposinactivosproduceuna compresindellapso,ademspermitedisminuir loscostosenqueincurreunoperadorlogsticoal definir una cantidad de vehculos en un ruteo deter-minado, esto mediante la utilizacin de los tiempos inactivos de las rutas preconcebidas en las fases de construccin y mejoramiento, para reorganizar as estas tareas.Lo anterior ocasiona una leve variacin en la funcin objetivo de la formulacin del CVRP-HF des-plegada anteriormente; esta se encuentra expresada en trminos de los costos Cij asociados a los arcos (i,j) entre clientes del grafo G=(V, E), en funcin de c H +```c]x]kMk=1M]=0N=0 DondeMeseltamaodelaflota determinado en la fase de ruteo y (repre-senta el costo fijo asociado a la flota) es un valor de su costo, en caso de que se tuviera la necesidad de subcontratar vehculos.Cabe afirmar que sta es una varia-ble muy usada en los sistemas reales, debi-do a que tercerizar es, por lo general, ms econmicoquenohacerlo.Enlaimple-mentacin algortmica, es un parmetro adicional que depende exclusivamente del tipo de flota elegido para realizar el ruteo.Figura 6. Diagrama de Gantt Figura 7. Funcionamiento de la fase de planifcacinlas distancias o tiempos de ruta entre ellos. En este caso, la solucin ptima al CVRP-HF podra no ser la ms conveniente en la prctica, si su valor objetivo correspondeaenrutarunagrancantidaddeve-hculos (por supuesto, el tamao de flota representa un costo fijo asociado a la gestin, no contemplado en la formulacin matemtica).Unametodologaheursticapodramanipu-larse para encontrar una solucin ms prctica que la ptima, aunque sacrifique el valor ptimo de la distancia(oeltiempotrascurrido),dehecho,esto es lo que se intenta hacer al ejecutar esta segunda fasedenominadaplanificacin.Enelalgoritmo propuesto, se implement, por lo tanto, una funcin objetivo de la forma:35Escuela de Ingeniera de AntioquiaLa reduccin de la flota vehicular y, por ende, su costo consiste, entonces, en asignar el mayor n-meroderutasposiblesavehculos,sinsobrepasar lashoras-hombrelaboralesdelpersonaloperativo (esto genera clusters de rutas o recorridos); aquellos clientes que no son asignados se asignan a un nuevo vehculoquepartedemanerasimultneaaeste. Luego de haber asignado todas las rutas, se procede acambiarencadaiteracinelorigendelasrutas para asignar (generando una vecindad en las rutas) y repetir el procedimiento para as explorar un nuevo espacio de solucin que mejorar considerablemen-te el tamao de la flota.4.EVALUACIN DEL DESEMPEOEstemodeloseaplicsobredosinstancias, una de ellas proveniente de una aplicacin real. Por cuestiones de confidencialidad no es posible presen-tar los datos utilizados, puesto que refleja la aplicabi-lidad de una herramienta algortmica en la realidad. Debido a la escala de la problemtica, la evaluacin deldesempeodeCVRP-HFhasidoconcentrada enlasvariablesdetransportedeunnicotipode productos en una flota homognea. En la bibliografa existente se hace referencia a procedimientos heurs-ticos y metaheursticos; es extenso el tratamiento del problema con las variables mencionadas, siendo al mismotiempoescasaencuantoaltratamientode problemas relacionados con programacin vehicu-lar.Lasinstanciaspresentadashansidoevaluadas enlasaplicacionesUN-TechVRSchedulerv1.0.El procedimiento propuesto fue comparado con otras herramientasdisponiblesparaelenrutamientode vehculos,comosonBTforVRP,AAVRPyVRP Solver.BTforVRP(Cabarcas,2002)proponeun procedimientobasadoenalgunascaractersticas de memoria de bsqueda tab y obtiene resultados satisfactorios. AAVRP (Filadelfo y Prez, 2003) utiliza mtodos de optimizacin local convencional como el barrido o sweeping y algunas caractersticas de la heurstica de insercin, con lo que obtiene resultados satisfactorios en tiempo polinomialmente razonable. VRP Solver v1.3 (Snyder, 2004) es una aplicacin que lleva a cabo una adaptacin de algoritmo de aho-rros en combinacin con una versin reducida del algoritmo 3-opt, el cual construye rutas del ve hculo que visitan cada ciudad precisamente una vez obe-deciendo a la capacidad del vehculo especificado por el usuario y sus lmites de distancia.Las aplicaciones descritas fueron evaluadas en condiciones iguales en un computador Laptop marca Acer TravelMate 2423 WXCi, Intel Celeron M pro-cessor 370 (1.5 GHz, 400 MHz FSB, 1MB L2 cache), 40GB HDD, 256MB DDR2 (support dual-channel). Con estas condiciones se presentan a continuacin, los resultados obtenidos de las instancias empleadas para evaluar el desempeo de la alternativa algort-mica diseada e implementada.Con el objetivo de evaluar el desempeo de los procedimientos heursticos y metaheursticos, lo comparamos con los siguientes mtodos de optimiza-cin: algoritmo de ahorros (Snyder, 2004), bsqueda tabsincriteriosdeaspiracin(Cabarcas,2002), insercin ms prxima multipunto (Filadelfo y Prez, 2003). Los resultados de las dos instancias evaluadas pueden observarse en la tabla 1.Es notable el grado de optimizacin mostrado enlaherramientaalgortmicapropuesta,debido aquepresentunresultadoalentadorenloque respectaaladistanciatotalrecorridaocupandoel segundo lugar y solo siendo superada por el VRPSolv-er v1.3, pero en lo que respecta a la disminucin de lacapacidadinstalada(mediantelaplanificacin) presentundesempeomejorquetodaslasapli-cacionesevaluadas.Elresultadoparalainstancia realasciendealautilizacinde15camiones,la herramientaestableciuntotalde6vehculos,lo que muestra ahorros significativos. Este resultado for-talece la validez y la pertinencia del procedimiento.Es notable tambin el poco tiempo de corrida empleado para la obtencin de resultados, con una calidad superior, en cuanto a optimizacin de la ca-pacidad,alosobtenidosenperiodossimilares,por las heursticas que se utilizaron como comparacin. Cabe resaltar que, a diferencia de los procedimientos 36Revista EIAResolucin del pRoblema de enRutamiento de vehculos...heursticos existentes, la heurstica propuesta present un comportamiento estable en cuanto a la pertinencia y calidad de la solucin. Esto implica que, mediante la aplicacin de un procedimiento heurstico suple-mentarioinnovador,segarantizaunasolucincon mscalidadquelamejorsolucinposibledelos procedimientos algoritmo de ahorros, bsqueda tab sincriteriodeaspiracineinsercinmsprxima multipunto.5.CONCLUSIONESLosresultadosobtenidosconbaseenla alternativa metaheurstica de dos fases para el pro-blemaderuteodevehculos,conrestriccionesde capacidadyflotahomognea,permitenconcluir quelaaplicacindeprocedimientosheursticos que implementen un proceso de programacin de operacionesvehicularespuedepresentaruncom-portamientohomogneoyconfiableante diversas instanciasdesituacionesproblemticasrealesdel ruteo de vehculos.En general, se encontraron soluciones muy buenasalproblemaenloquerespectaaltiempo computacional Tc requerido, el cual es sorprenden-temente menor de un minuto (Tc