Problemas de rutas de vehículos por arcos

FACULTAD DE MATEM´ ATICAS DEPARTAMENTO: ESTAD´ ISTICA E INVESTIGACI´ ON OPERATIVA Trabajo Fin de Grado: Problemas de rutas de veh´ıculos por arcos Autor: Mar´ıa Calvo Gonz´alez Dirigido por: Justo Puerto Albandoz 2017 - 2018 Abstract At the beginning of this work, we are going to give a historical introduction of arc routing. We will take a look at the complexity of this type of problems, and then, we will focus on the Chinese Postman Problem. It is arguably the most central problem in this area. Given a graph, it basically tries to find a minimun cost tour traversing at least once each edge. We will study the undirected, directed, mixed and windy version in detail, and their respective ways to deal with them. Finally, we will see some applications about real instances for each version. Prop´osito general Comenzaremos nuestro trabajo hablando de los inicios del estudio de las rutas por arcos con el problema de los puentes de K¨onigsberg. Comentaremos otros problemas hist´oricos relacionados, como el trazado de figuras sin levantar el l´apiz del papel o la resoluci´on de laberintos. Esto nos conducir´a a la necesidad del nacimiento de la optimizaci´on, y haremos un planteamiento previo del Problema del Cartero Chino, en el que se pretende encontrar una ruta de coste m´ınimo que recorra todas las aristas o arcos del grafo al menos una vez. Se plantean adem´as ciertos resultados te´oricos que ser´an necesarios posteriormente. Concluiremos nuestra introducci´on comentando la complejidad de los problemas que vamos a estudiar, as´ı como la de otras variantes no tratadas en este trabajo. En el segundo cap´ıtulo plantearemos el Problema del Cartero Chino no dirigido, caso en el que tenemos un grafo no dirigido. La resoluci´on de este se basa en buscar un grafo de aumento que sea Euleriano, y una vez hallado, encontrar un circuito Euleriano en ´el. Veremos como calcular este aumento tanto desde el punto de vista de la programaci´on din´amica como de la programaci´on matem´atica. En el tercer cap´ıtulo daremos el planteamiento del PCC para cuando tenemos grafos dirigidos, mixtos y windy. Veremos as´ı en primer lugar el Problema del Cartero Chino dirigido, y su correspondiente formulaci´on. A continuaci´on, estudiaremos el Problema del Cartero Chino mixto, as´ı como varias formas de abordarlo, tanto cuando existe soluci´on exacta como cuando no, y dos formulaciones de este (adem´as de una comparaci´on de ambas). Finalmente, nos centraremos en el Pro- 5 Prop´osito general blema del Cartero windy, es decir, aquel en el que el coste de cada arista depende de la direcci´on en la que la recorramos. Al igual que en el caso mixto, plantearemos varios algoritmos para su resoluci´on exacta (si es posible) o aproximada (si no), as´ı como su formulaci´on correspondiente. Concluiremos nuestro trabajo con un cap´ıtulo de aplicaciones de las cuatro variantes estudiadas para casos reales. Para ello utilizaremos un programa en Xpress que nos proporcionar´a la soluci´on ´optima para cada caso. 6 ´ Indice general 1. Introducci´on 9 1.1. Notashist´oricas............................. 9 1.2. Resultados te´oricos previos . . . . . . . . . . . . . . . . . . . . . . . 12 1.3. La complejidad de los problemas de rutas por arcos . . . . . . . . . 13 1.3.1. Complejidad del Problema del Cartero Chino . . . . . . . . 16 1.3.2. Complejidad del Problema del Cartero Chino Rural . . . . . 22 1.3.3. Complejidad del Problema de las Rutas por Arcos con Capacidades ............................ 25 1.4. Conclusi´on................................ 27 2. El Problema del Cartero Chino no dirigido 29 2.1. Planteamiento.............................. 29 2.2. Resoluci´on................................ 30 2.2.1. Programaci´on din´amica . . . . . . . . . . . . . . . . . . . . 30 2.2.2. Programaci´on matem´atica . . . . . . . . . . . . . . . . . . . 39 3. El Problema del Cartero Chino para grafos dirigidos, mixtos y windy 41 3.1. El Problema del Cartero Chino dirigido . . . . . . . . . . . . . . . . 42 3.2. El Problema del Cartero Chino mixto . . . . . . . . . . . . . . . . . 42 3.2.1. Algoritmos heur´ısticos . . . . . . . . . . . . . . . . . . . . . 44 3.2.2. Formulaci´on del Problema . . . . . . . . . . . . . . . . . . . 46 3.3. Problema del Cartero windy . . . . . . . . . . . . . . . . . . . . . . 50 7 3.3.1. Algoritmos heur´ısticos . . . . . . . . . . . . . . . . . . . . . 52 3.3.2. Formulaci´on del problema . . . . . . . . . . . . . . . . . . . 53 4. Aplicaciones 57 4.1. Ejemplo del Problema del Cartero Chino no dirigido . . . . . . . . . 57 4.2. Ejemplo del Problema del Cartero Chino dirigido . . . . . . . . . . 59 4.3. Ejemplo del Problema del Cartero Chino mixto . . . . . . . . . . . 61 4.4. Ejemplo del Problema del Cartero windy . . . . . . . . . . . . . . . 62 Bibliograf´ıa 67 8 1 Introducci´on A modo introductorio, haremos un breve recorrido hist´orico desde el inicio del estudio de las rutas por arcos hasta la aparici´on de la optimizaci´on. Adem´as, proporcionaremos ciertos resultados te´oricos que ser´an necesarios posteriormente. En la tercera secci´on, presentaremos esquem´aticamente los problemas en los que se va a profundizar en este trabajo, as´ı como otras variantes. Estudiaremos la complejidad para cada uno de ellos y concluiremos comentando la situaci´on de los problemas de rutas por arcos en la actualidad. 1.1. Notas hist´oricas El estudio de las rutas por arcos se remonta a tiempos en que el matem´atico Leonhard Euler fue llamado a estudiar el famoso problema de los puentes de K¨onisberg, all´a por el siglo XVIII. Sin embargo, aunque algunos matem´aticos pusieron inter´es sobre estos problemas y aportaron comentarios interesantes, no fue hasta 1960 con la primera publicaci´on del Problema del Cartero Chino cuando naci´o este ´area realmente. El problema de los puentes de K¨onigsberg K¨onigsberg es una ciudad en Prusia, atravesada por un r´ıo que se bifurca para rodear con sus brazos a la isla Kneiphof. El terreno se divide as´ı en cuatro regiones distintas, las que entonces estaban unidas mediante siete puentes. El problema 9 1. Introducci´on de decisi´on Q se denomina Tratable mediante Par´ametro Fijado (TPF) con respecto a un par´ametro p si hay alg´un algoritmo que lo resuelva para cada x de Q en tiempo f(k)· |x|cpara alguna funci´on computable f y una constante c. La diferencia entre XP y TPF es que, aunque ambos son resolubles en tiempo polinomial para valores de par´ametros constantes, en XP el grado del polinomio correspondiente depende del par´ametro, mientras que en TPF no. Una propiedad muy importante en la parametrizaci´on es encontrar la manera de medir la efectividad del preprocesamiento. La kernelizaci´on (o problema Kernel) de un problema de decisi´on Q es un algoritmo en tiempo polinomial que, para cada x con par´ametro pde Q, computa un x0con par´ametro p0de Q tal que, para algunas f, g :N−→ Nse tiene que: •x∈Q⇐⇒ x0∈Q • |x0| ≤ g(p) •p0≤f(p) La funci´on g se llama tama˜no del problema Kernel, y constituye una medida de la efectividad del algoritmo de kernelizaci´on. 1.3.1. Complejidad del Problema del Cartero Chino Nos centraremos ahora en el Problema del Cartero Chino, donde su estructura combinatoria muestra su car´acter NP-duro. Veamos una representaci´on gr´afica de un ejemplo de PCC, donde el coste de las aristas es proporcional a su longitud: En la siguiente tabla [35] podemos observar un breve resumen de la complejidad del PCC: 16 1. Introducci´on Variante del PCC Complejidad Cl´asica No dirigido Algoritmo en tiempo O(|V|3) Dirigido Algoritmo en tiempo O(|V|3) Algoritmo en tiempo O((|E|−|V|)|V|2) Mixto NP-completo Resoluble en tiempo O(|V|3) si cada v´ertice tiene grado par Windy NP-completo en P para algunos casos especiales k-Jerarquico NP-completo Resoluble en tiempo O(k|V|4) si hay precedencia de relaci´on linear Min-Sum-k-PCC Resoluble en tiempo O(|V|3) con v´ertice “oficina de correos” En otro caso es NP-completo Min-Max-k-PCC NP-completo Variante del PCC Aproximaci´on Mixto Factor 3/2 en tiempo O(max{|V|3,|A|(max{|A|,|E|})2}) Windy Factor 3/2 Min-Max-k-PCC Factor (2 −1/k) en tiempo O(|V|3) Variante del PCC Complejidad parametrizada Mixto Algoritmo en tiempo O(2|E· |V|3) en TPF con respecto a |A| en XP con respecto al treewidth Min-Sum-k-PCC en TPF con respecto a k sin v´ertice “oficina de correos” El Problema del Cartero Chino cl´asico Como podemos observar en el gr´afico anterior, el PCC puede presentarse a partir de: •Entrada: un grafo no dirigido y conexo G= (V, E) con aristas con coste c(e)≥0 para cada e∈Ey con un coste m´aximo de cmax. •Objetivo: Encontrar una ruta que pase por cada arista en E al menos una vez y con un coste de, a lo sumo, cmax. Acerca del car´acter tratable del problema, Edmonds y Johnson [18] probaron que el PCC es resoluble en tiempo polinomial. Todo se reduce a encontrar un supergrafo Euleriano G0tal que el coste de las aristas en G0no exceda cmax. Por hip´otesis, G es conexo, por lo que solo hay que a˜nadir aristas para que 17 1. Introducci´on cada v´ertice tenga grado par. Esto puede lograrse resolviendo un problema equivalente de emparejamiento perfecto de m´ınimo coste en un grafo auxiliar G∗, con aristas con costes. Es posible transformar un emparejamiento en G∗en un supergrafo Euleriano de G, y viceversa. Como para construir G∗podemos usar un algoritmo ejecutable en tiempo O(|V|3), el PCC es resoluble en dicho tiempo, y est´a en P. Aunque no estamos encontrando una ruta del coste deseado, con los resultados anteriores tenemos asegurada su existencia en un supergrafo Euleriano, decidiendo as´ı el PPC. Para el caso de los grafos dirigidos ser´ıa an´alogo. Grafos mixtos El PCC mixto puede presentarse de la siguiente forma: •Entrada: un grafo mixto y fuertemente conexo G= (V, E, A) con aristas con coste c(e)≥0 para cada e∈E∪Ay con un coste m´aximo de cmax. •Objetivo: Encontrar una ruta (dirigida) que pase por cada arista en E y cada arco en A al menos una vez y con un coste de, a lo sumo, cmax. Si asumimos que P6=NP, entonces el PCC mixto no es resoluble en tiempo polinomial. Sobre su dureza, diremos que su principal dificultad es que, para resolverlo, tenemos que orientar las aristas y a˜nadir algunos arcos m´as para obtener un grafo Euleriano. Es decir, para hacer que todos los v´ertices sean equilibrados. Adem´as: Teorema 5. El Problema del Cartero Chino mixto es NP-completo, incluso si el grafo de entrada es planar, cada v´ertice tiene a lo sumo grado tres, y cada arista y arco tiene coste uno. Acerca del car´acter tratable del problema decir que, si cada v´ertice tiene un n´umero par de aristas y arcos incidentes, el PCC mixto es resoluble en tiempo polinomial por reducci´on a un problema de flujo en redes. Por otro 18 1. Introducci´on lado, cuando el n´umero de aristas (no dirigidas) en el grafo de entrada es peque˜no, el PCC mixto puede resolverse eficientemente. Fernandes et al. [21] demostr´o posteriormente que el PCC mixto est´a en XP con respecto al par´ametro “treewidth (m´ınima anchura entre todas las posibles descomposiciones) del grafo de entrada”, es decir, que es resoluble en tiempo polinomial si la treewidth es constante. Existen algunos casos tratables m´as en los que se obtiene la resoluci´on en tiempo polinomial transformando el PCC mixto en un PCC windy. Finalmente, nos planteamos c´omo podemos obtener una soluci´on aproximada usando solo tiempo polinomial. La primera aproximaci´on que surgi´o fue la de factor 2 [18]. Su origen est´a basado en que, siendo ˜ Gel multigrafo resultante de duplicar cada arista y arco del grafo de entrada G, el algoritmo usado para la aproximaci´on me proporciona una soluci´on de coste como m´aximo el de ˜ G, que es al menos dos veces el ´optimo para G. Posteriormente se propuso una estrategia mixta de factor 5/3 [25], que se mejor´o con una de factor 3/2, sugerida por Raghavachari y Veerasamy [43]. Zaragoza Mart´ınez [52, 51] prob´o adem´as que no es posible aproximar el coste del deadheading con alg´un factor constante, donde deadheading significa atravesar los arcos y aristas m´as de una vez. Este resultado se obtuvo al demostrar la NP-dureza de decidir si un grafo mixto dado tiene una ruta que pase exactamente una vez por cada arista. Costes windy Otra variante del PCC consiste en considerar costes asim´etricos, es decir, distintos costes de una arista dependiendo de en que sentido se recorra. As´ı, el PCC windy se puede formular de la siguiente manera: •Entrada: un grafo conexo y no dirigido G= (V, E) con dos valores de coste c(u, v), c(u, v)≥0 para cada arista u, v ∈Ey con un coste m´aximo de cmax. •Objetivo: Encontrar una ruta (dirigida) que pase por cada arista en E al menos una vez y con un coste de, a lo sumo, cmax. 19 1. Introducci´on Desafortunadamente, es NP-duro [35], pues est´a demostrado que todo PCC mixto puede transformarse en un PCC windy en tiempo polinomial. Sin embargo es resoluble en tiempo polinomial si el coste de pasar por cada ciclo en el grafo de entrada es el mismo independientemente de la direcci´on, y si el grafo de entrada es Euleriano. Aprovechando esto ´ultimo, Z.Win [49] obtuvo una aproximaci´on de factor 2, aunque posteriormente Raghavachari y Veeresamy [44] dieron una de factor 3/2 combinando una estrategia mixta similar a la usada en el PCC mixto. Jerarqu´ıas de aristas y relaciones de precedencia En aplicaciones pr´acticas, es posible encontrarnos una variante del PCC donde algunas aristas deban ser recorridas antes que otras. Sea as´ı G= (V, E) un grafo no dirigido, y sea P={E1, ..., Ek}una partici´on de las aristas, tal que ∪k i=1Ei=EyEi∪Ej=∅para todo 1 ≤i, j ≤k. Denominaremos a los conjuntos Eicomo clases de prioridad. Sea adem´as, R⊆P×P una ordenaci´on parcial. Diremos que un camino en G respeta R si para todo (Ei, Ej)∈Rcada arista en Eies recorrida antes que cualquier otra en Ej. El PCC Jer´arquico se puede formular de la siguiente manera: •Entrada: un grafo no dirigido y conexo G= (V, E) con aristas con coste c(e)≥0 para cada e∈Ey con un coste m´aximo de cmax. Adicionalmente, una partici´on P={E1, ..., Ek}y una relaci´on de ordenaci´on parcial R⊆P×P. •Objetivo: Encontrar una ruta que pase por cada arista en E al menos una vez, con un coste de, a lo sumo, cmax y que respete R. Este problema es NP-duro en general. Sin embargo, hay tres factores que parecen influir en la complejidad, que son [35]: ∗Si las clases est´an conectadas: Hay que resolver el Problema del Cartero Rural como subproblema si una de las clases de prioridad no est´a conectada. Sin embargo, est´a demostrado que el PCC Jer´arquico es NP-duro incluso si las clases si lo est´an. 20 1. Introducci´on ∗N´umero de clases de prioridad: El PCC Jer´arquico es NP-duro incluso cuando s´olo hay dos clases de prioridad. Esto se obtiene de la reducci´on del Problema del Cartero Rural (NP-duro tambi´en). Si las clases est´an conectadas, entonces es necesario tener muchas clases de prioridad en la reduci´on de dureza est´andar. Esta se hace para el Problema del Cartero Rural desde el Problema del Ciclo Hamiltoniano (el cual se pregunta si dado un grafo, este admite un camino cerrado pasando una ´unica vez por cada arista y es NP-duro) creando una componente conectada en las aristas obligatorias para cada v´ertice del caso original. ∗Si la relaci´on de precedencia es una ordenaci´on linear en lugar de parcial, caso en el que el PCC Jer´arquico con clases de prioridad conectadas es resoluble en tiempo polinomial. Recientemente se han descubiertos algoritmos ejecutables en tiempo O(k3|V|3). M´ultiples carteros Otra variante es considerar k rutas en un grafo ponderado G, tal que cada arista sea recorrida por al menos uno de los carteros. Formalmente: •Entrada: un grafo no dirigido y conexo G= (V, E) con coste c(e)≥0 para cada e∈Ey con un coste m´aximo de cmax. Adem´as, un v´ertice distinguido v∈V(la oficina de correos). •Objetivo: Encontrar k rutas T∗que empiece y acabe en V, tal que ninguna ruta sea vac´ıa y cada arista en E sea recorrida al menos una vez, con w(T∗)≤cmax. Centr´andonos en el caso no dirigido, la complejidad del k-PCC depende enormemente de que funci´on objetivo welijamos: Minimizar la suma de los costes de la ruta da lugar al Min-Sum-k-PCC, resoluble en tiempo polinomial, mientras que minimizar el m´aximo del coste de la ruta genera el Min-Max-k-PCC, que es NP-duro. Esto se sigue manteniendo incluso si sustituimos un grafo dirigido por G. Si ambos arcos y aristas est´an presentes, entonces ambas variantes tienen el PCC mixto como caso especial, y son NP-duras. 21 1. Introducci´on M´as variantes Otras variantes existentes ser´ıan considerar que hay ciertas formas de atravesar cruces prohibidas [3], obligar a pasar por al menos una arista de un subconjunto [14] o maximizar el beneficio de repartir en una calle m´ultiples veces [20]. 1.3.2. Complejidad del Problema del Cartero Chino Rural El PCC sirve para modelar el reparto de cartas en casas en cada calle. En ´areas rurales, sin embargo, no en todas las calles hay casas a las que repartir cartas. A continuaci´on, veremos una representaci´on gr´afica de un ejemplo concreto, donde el coste de las aristas vuelve a ser proporcional a su longitud, as´ı como la formalizaci´on del problema: Entrada: un grafo no dirigido y conexo G= (V, E) con aristas con coste c(e)≥0 para cada e∈E, un conjunto R⊆Ede aristas obligatorias (negrita), y con un coste m´aximo de cmax. Objetivo: Encontrar una ruta que pase por cada arista en R al menos una vez, con un coste de, a lo sumo, cmax. En la siguiente tabla podemos observar un breve resumen de la complejidad del PCC Rural: 22 1. Introducci´on Variante del PCC Rural Aproximaci´on No dirigido Factor 3/2 en tiempo O(|V|3) Factor 3/2 en tiempo O(|V|3) para problemas m´as generales Mixto Si se cumple la desigualdad triangular, se tiene: factor 15/8 para el caso sim´etrico factor 9/5 si solo los arcos dirigidos son los obligatorios Variante del PCC Rural Complejidad Parametrizada No dirigido Algoritmo en tiempo O(|V|2γ/γ!·n) Problema kernel de 2|R|v´ertices Algoritmo en tiempo O(23|R|· |R|2+|V|3) Algoritmo aleatorizado en tiempo O(2γ·(cmax +|V|)d), con d = cte. Dirigido Algoritmo en tiempo O(4k· |V|3) Algoritmo en tiempo O(4γlog(bγ2)· |V|4) Algoritmo aleatorizado en tiempo O(2γ·(cmax +|V|)d), con d = cte. No existen problemas kernel con tama˜no polinomial con respecto de γy k Todas las variantes del Problema del Cartero Rural son NP-completas si no todas las aristas son obligatorias, lo cual har´ıa al PCC Rural equivalente al PCC. Acerca de la complejidad cl´asica, decir que si reducimos el Problema del Ciclo Hamiltoniano al PCC Rural, probamos que este ´ultimo es tambi´en NP-duro. Como es an´alogo para el caso dirigido, podemos afirmar que las versiones dirigida, mixta y windy del PCC Rural son tambi´en NP-duras. Los problemas de los carteros son muy similares a problemas en grafos relacionados con la propiedad euleriana. De hecho, un circuito cerrado en un grafo puede considerarse como un multigrafo. As´ı, el PCC Rural puede transformarse en otro, al que llamaremos su Extensi´on Euleriana (y viceversa), que se describir´ıa de la siguiente manera: Entrada: un multigrafo G= (V, E) con coste c({u, v})≥0∀u, v ∈V, y con un coste m´aximo de cmax. Objetivo: Encontrar un multiconjunto E0de pares {u, v}con u, , v ∈V a˜nadiendo las aristas en E0a G para hacer que G sea euleriano y con c(E0)≤ cmax. 23 1. Introducci´on Acerca de la aproximabilidad, se˜nalar que, aunque el Problema del Viajante est´e muy relacionado con el PCC Rural, ´este probablemente no puede ser aproximado al ´optimo con ning´un factor constante. Sin embargo, existen ciertas aproximaciones de factor constante para casos especiales del Problema del Viajante son la base para los algoritmos de aproximaci´on de factor constante del PCC Rural. Para el caso de los grafos dirigidos, es desconocido si es posible encontrar una aproximaci´on con factor constante. Para la resoluci´on de grafos mixtos sim´etricos (donde para cada arco {u, v}en la entrada, hay un arco {v, u}con igual coste), se ha descubierto una aproximaci´on de factor 15/8 si se cumple la condici´on de la desigualdad triangular. Bajo la misma condici´on tambi´en se ha encontrado una aproximaci´on de factor 9/5 si solo los arcos dirigidos son los obligatorios. Sobre la complejidad de parametrizaci´on, se˜nalar que la transformaci´on anteriormente comentada del PCC Rural en el Problema del Vendedor Ambulante crea casos con a lo sumo 3|R|v´ertices. Esto puede usarse para algoritmos parametrizados combin´andolo con el conocido algoritmo de programaci´on din´amica, resolviendo el PCC Rural en tiempo O(23|R|· |R|2+|V|3), siendo R el conjunto de aristas obligatorias. El PCC Rural tambi´en admite un problema kernel sencillo con 2|R|v´ertices. Para el caso de grafos dirigidos y dado un entero k, existe un algoritmo de programaci´on din´amica que computa el m´ınimo coste de una ruta pasando por todos los arcos obligatorios m´as, a lo sumo, k arcos adicionales. Dicho algoritmo se ejecuta en tiempo O(4k· |V|3). Teorema 6. El PCC Rural es TPF con respecto al n´umero de arcos que recorre una soluci´on ´optima m´as los arcos obligatorios. Aunque posteriormente se descubri´o un algoritmo ejecutable en tiempo O(|V|2γ/γ!·n), a´un no se sabe si el PCC Rural es TPF respecto a γ. Se ha demostrado que el PCC Rural respecto a γes “TPF-equivalente”a una variante de emparejamien- to NP-dura. Existe adem´as un algoritmo que resuelve el PCC Rural en tiempo O(4γlog(bγ2)· |V|4), donde brepresenta el n´umero de v´ertices no equilibrados (con grado de entrada distinto del de salida). Teorema 7. El PCC Rural puede resolverse en tiempo O(2γ·(cmax +|V|)d+l)para dado un l > 0real y d > 0constante, describiendo un caso s´ı como un caso no, con probabilidad a lo sumo 1/(cmax +|V|)l. Dicho resultado es v´alido tanto para el caso dirigido como el no dirigido. 24 1. Introducci´on 1.3.3. Complejidad del Problema de las Rutas por Arcos con Capacidades El problema m´as general de rutas por arcos que vamos a estudiar es el de Rutas por Arcos con Capacidades (RAC), introducido por Golden y Wong [26]. Este generaliza el PCC y el PCC Rural, y centr´andonos en el caso concreto de la mensajer´ıa, a˜nade la posibilidad de repartir el correo a un conjunto de calles obligatorias a trav´es de m´ultiples veh´ıculos capaces de llevar un n´umero limitado de paquetes. En un RAC, se nos da un grafo no dirigido, con un coste asociado a cada arista y algunas de ellas con una cierta demanda y un v´ertice especial, al que denominaremos el almac´en. Los almacenes contienen un n´umero ilimitado de veh´ıculos, cada uno con una capacidad, que pueden repartir paquetes en las aristas o simplemente recorrerlas sin repartir. En el siguiente gr´afico podemos ver un ejemplo en el que el v´ertice negro es el almac´en, las demandas respectivas aparecen como etiquetas de las aristas, y las longitudes de estas son proporcionales a sus costes: Todos los veh´ıculos tienen capacidad seis. El objetivo es repartir en cada arista, de acuerdo con su demanda, con un ´unico veh´ıculo, sin que la suma de las demandas de las aristas en las que se reparte excedan la capacidad del veh´ıculo. Adem´as, buscamos que el coste de recorrer las aristas sea m´ınimo. Las rutas de los dos veh´ıculos de la soluci´on se representan en distintos colores. Formalmente tenemos: Entrada: un grafo no dirigido G= (V, E), con un v´ertice almac´en v0∈V, con aristas con coste c(e)≥0 y demanda d(e)≥0 para cada e∈E, una capacidad Wde veh´ıculo, y un coste m´aximo de cmax. Objetivo: Encontrar un conjunto Cde ciclos en G, cada uno correspondiendo a la ruta de un veh´ıculo, pasando por el v´ertice v0, tal que: 25 2. El Problema del Cartero Chino no dirigido de traversabilidad en vi, se debe atravesar dos veces un camino completo desde vi hasta alg´un otro v´ertice vrde V−de grado impar. Esto satisface autom´aticamente la condici´on de traversabilidad del v´ertice vr. Tal proceso es an´alogo para el resto de v´ertices vide V−, lo que significa que todo el conjunto Mde caminos de Gdebe ser atravesado dos veces, y como esto implica que cada arista de G−(M) debe ser atravesada una vez, el teorema se cumple. El algoritmo para la soluci´on del Problema del Cartero Chino es consecuencia inmediata del teorema anterior, ya que ahora lo que tenemos es que encontrar tal conjunto de caminos M∗(hacer un emparejamiento de v´ertices de grado impar) que produce el menor coste adicional. El circuito de menor coste adicional que pasa por Gdeberia entonces tener un coste igual a la suma de los costes de las aristas de Gm´as la suma de los costes de las aristas en los caminos de M∗. Esto es lo mismo que la suma de los costes de todas las aristas, reales y artificiales, del grafo G−(M∗). A continuaci´on, describiremos el algortimo que dar´a soluci´on a PCC. Para ello, utilizaremos otro que veremos previamente, denominado el Algoritmo del Camino M´as Corto. Algoritmo del Camino M´as Corto Este algoritmo calcula el camino m´as corto del v´ertice aal b, considerando que los costes son no negativos. El m´etodo consiste en asignar temporalmente etiquetas a los v´ertices, donde tal etiqueta ser´a un l´ımite superior en la longitud de la rute desde ahasta ese v´ertice. La etiquetas est´an continuamente reduci´endose mediante un proceso iterativo. Descripci´on: Sea Cla matriz de costes, con cij ≥0. Sea l(vi) la etiqueta del v´ertice vi. Inicializaci´on: Paso 1: Consideramos l(a) = 0 y marcamos la etiqueta como permanente (tomaremos como marca un +). Consideramos tambi´en l(vi) = ∞para todo vi6=ay marcamos tales etiquetas como temporales. Tomamos p=a. Actualizaci´on de etiquetas: 32 2. El Problema del Cartero Chino no dirigido Paso 2: Para todo vi∈Γ(p) (siendo Γ(p) el conjunto de los v´ertices adyacentes de p) actualizamos aquellas etiquetas que sean temporales de la forma siguiente: l(vi) = min[l(vi), l(p) + c(p, vi)] Fijaci´on de una etiqueta como permanente: Paso 3: Entre todos los v´ertices etiquetados temporalmente encontrar el v∗ i para el que l(v∗ i) = min[l(vi)]. Paso 4: Marcar la etiqueta de v∗ icomo permanente y fijar p=v∗ i. Paso 5: •Si todos los v´ertices son etiquetados de forma permanente, entonces las etiquetas son las longitudes de los caminos m´as cortos. Stop. •Si algunas etiquetas son temporales volvemos al paso 2. Stop. Algoritmo para resolver el PCC Descripci´on: Paso 1: Sea [cij] la matriz de coste de las aristas del grafo G. Usando el algoritmo anterior del camino m´as corto formamos la matriz D= [dij], de dimensi´on |V−|por |V−|, donde dij es el coste del camino m´as corto desde un v´ertice vi∈V−hasta otro v´ertice vj∈V−. Paso 2: Encontrar el emparejamiento M∗de v´ertices en V−que produce el menor coste de acuerdo con la matriz de costes D. Paso 3: Si un v´ertice vαes asociado con otro v´ertice vβ, identificamos el camino de menor coste µαβ (desde vαhasta vβ) correspondiente al coste dαβ del paso 1. Insertamos artistas artificiales en Gcorrespondientes a las aristas en µαβ y repetimos para el resto de caminos del emparejamiento M∗para obtener el grafo G−(M∗). 33 2. El Problema del Cartero Chino no dirigido Paso 4: La suma de los costes de la matriz [cij] de todas las aristas en G−(M∗) (considerando que el coste de una arista artificial es el mismo que el de una arista real en paralelo con ella) es el circuito de m´ınimo coste que pasa por G. El n´umero de veces que este circuito pasa por una arista (vi, vj) es el n´umero total de aristas en paralelo entre viyvjen G−(M∗). Se˜nalar que, si se verifica la desigualdad triangular, como en el paso 2 estamos usando un emparejamiento m´ınimo, no hay dos caminos m´as cortos, µij yµpq (es decir, los que van de viavj, y de vpavq), en el emparejamiento con aristas en com´un. Esto es porque si tienen una arista en com´un (va, vb) como podemos ver en el siguiente dibujo, entonces un emparejamiento de viavq(usando los subcaminos que van de viavb, y de vbavq), y un emparejamiento de vpavj(usando los subcaminos que van de vpava, y de vaavj), producen un emparejamiento global de coste 2cab menor que el del emparejamiento original. Y esto es una contradicci´on a la suposici´on de que el emparejamiento original era m´ınimo. Esto significa que el grafo G−(M∗) no tiene m´as de dos aristas en paralelo entre dos v´ertices cualquiera, es decir, el circuito ´optimo nunca pasa m´as de dos veces por ninguna arista de G. Ejemplo: Consideramos el grafo Gsiguiente: 34 2. El Problema del Cartero Chino no dirigido Como vemos, G tiene 12 v´ertices y 22 aristas, cada cual con su coste correspondiente. El problema es encontrar un circuito que pase por todas las aristas de G al menos una vez y tenga coste m´ınimo. 1. El conjunto V−formado por v´ertices de grado impar para el grafo es {1,3,4,6,8,9}. Usando el algoritmo del camino m´as corto, construimos la matriz D: Primera iteraci´on: Paso 1: Fijamos: l(v1)=0+ l(vi) = ∞ ∀vi6=v1,p=v1 Paso 2: Como: Γ(p) = Γ(v1) = {v2, v4, v7, v10, v12} y todos tienen etiquetas temporales, actualizamos las etiquetas (primero lo haremos con v2): l(v2) = min[∞,0++ 13] = 13 De forma an´aloga obtenemos que: 35 2. El Problema del Cartero Chino no dirigido l(v4) = 17, l(v7) = 19, l(v10) = 19, l(v12)=4 Paso 3: Calculamos el min [ 13 |{z} v2 ,17 |{z} v4 ,19 |{z} v7 ,19 |{z} v10 ,4 |{z} v12 ,∞ |{z} v3,v5,v6,v8,v9,v11 ] = 4, el cual corresponde con v12. Paso 4: Marcamos como permanente l(v12) = 4+, con p=v12. Paso 5: Como no todos los v´ertices est´an etiquetados como permanentes, vamos al paso 2. Segunda iteraci´on: Paso 2: Como: Γ(p) = Γ(v12) = {v5, v6, v7} y todos tienen etiquetas temporales, actualizamos las etiquetas (primero lo haremos con v5): l(v7) = min[19,4++ 18] = 19 De forma an´aloga obtenemos que: l(v5) = 15, l(v6) = 7 Paso 3: Calculamos el min [ 13 |{z} v2 ,17 |{z} v4 ,15 |{z} v5 ,7 |{z} v6 ,19 |{z} v7 ,19 |{z} v10 ,∞ |{z} v3,v8,v9,v11 ] = 7, el cual corresponde con v6. Paso 4: Marcamos como permanente l(v6) = 7+, con p=v6. Paso 5: Vamos al paso 2. Tercera iteraci´on: Paso 2: Como: Γ(p) = Γ(v6) = {v5, v7, v12} donde {v5, v7}tienen etiquetas temporales. Actualizamos las etiquetas y obtenemos: l(v5) = 13, l(v7) = 14 Paso 3: Calculamos el min [ 13 |{z} v2 ,17 |{z} v4 ,13 |{z} v5 ,7 |{z} v6 ,14 |{z} v7 ,19 |{z} v10 ,∞ |{z} v3,v8,v9,v11 ] = 13, el cual corresponde con v5. Paso 4: Marcamos como permanente l(v5) = 13+, con p=v5. 36 2. El Problema del Cartero Chino no dirigido Paso 5: Vamos al paso 2. Continuamos haciendo iteraciones hasta tener todas los v´ertices etiquetados de forma permanente. El resultado final del proceso visualmente es el siguiente: Las l´ıneas rojas representan los caminos m´as cortos desde el v´ertice v1hasta cada uno de los v´ertices de G. Una vez que tenemos todos estos resultados, nos interesa quedarnos solo con los correspondientes a los v´ertices de grado impar. Estos aparecen representados en azul. De esta manera, ya podemos formar la primera fila de nuestra matriz D, es decir, la fila correspondiente av1(de grado tambi´en impar). Repetimos el proceso para los v´ertices de Gcon grado impar restantes, y obtenemos que D tiene la siguiente forma: 37 2. El Problema del Cartero Chino no dirigido 1 3 4 6 8 9 1- 19 17 7 19 15 319 - 20 12 24 20 417 20 - 24 30 11 67 12 24 - 12 22 819 24 30 12 - 19 915 20 11 22 19 - 2. En el paso 2 el algoritmo del emparejamiento m´ınimo relaciona los siguientes v´ertices: 1 con 6, camino: 1-12-6, coste 7 3 con 8, camino: 3-5-6-7-8, coste 24 9 con 4, camino: 9-2-4 coste 11 3. El grafo G−(M∗) al final del paso 3 tiene la siguiente forma, donde las aristas artificiales son representadas como l´ıneas discontinuas: Una vez que hemos construido el grafo G−(M∗), un circuito Euleriano de 38 2. El Problema del Cartero Chino no dirigido este grafo y, por lo tanto, el circuito ´optimo correspondiente que atraviesa el gr´afico original G, puede construirse inmediatamente mediante la regla de Fleury que mencionaremos posteriormente. 2.2.2. Programaci´on matem´atica El documento de Edmonds y Johnson [18] nos proporcion´o el primer tratamiento de programaci´on matem´atica del PCC. Se dice as´ı que S⊂Ves impar si es un conjunto formado por un n´umero impar v´ertices de grado tambi´en impar. Sea E(S) = {(i, j) : vi∈S, vj∈V\S, ovi∈V\S, vj∈S}. Consideraremos las variables xij, tales que: xij =1 si y solo si la arista (i, j) aparece en el aumento 0 en caso contrario El problema puede formularse de la siguiente forma: (PCC) min P(i,j)∈Ecijxij s.t. P(i,j)∈E(S)xij ≥1, S ⊂V, ∀S impar,(2.1) xij ≥0,(i, j)∈E, xij entero,(i, j)∈E, (2.2) Las restricciones anteriores representan las desigualdades blossom.´ Estas representan que al menos una copia de una arista incidente en un conjunto impar Sdebe formar parte del grafo aumentado, con el fin de lograr la paridad. El poliedro de soluciones de (2.2) es igual a la envolvente convexa de las soluciones del problema y estas desigualdades blossom pueden separarse en tiempo polinomial, resolviendo el problema mediante una adaptaci´on del algoritmo blossom de problemas de emparejamiento (Edmonds [18]). Por tanto (2.2) no es necesario y el problema se puede resolver mediante programaci´on lineal continua. Una vez que obtenemos el grafo Euleriano, determinar el ciclo Euleriano en el puede lograrse aplicando el algoritmo de Fleury [22]: Paso 1: Consideramos un v´ertice vi. Empezando por vi, pasamos por una arista (vi, vj) que no sea una arista puente (es decir, que su eliminaci´on no suponga la desconexi´on del grafo), a no ser que sea una arista final. Eliminamos (vi, vj) del grafo. 39 2. El Problema del Cartero Chino no dirigido Paso 2: Si todas las aristas han sido eliminadas, paramos. Paso 3: Fijamos vi:= vj, y volvemos al paso 1. La principal dificultad de esta algortimo es determinar si una arista es arista puente. Centrandonos en el ejemplo anterior, y aplicando este algoritmo, un circuito Euleriano posible es el dado por la siguiente secuencia de v´ertices (empezando por el v´ertice 1): {1, 4, 3, 5, 3, 2, 4, 2, 1, 12, 5, 6, 7, 8, 10, 1, 7, 6, 12, 6, 5, 11, 9, 2, 9, 10, 11, 8, 7, 12, 1} Este circuito se corresponde con el ´optimo que atraviesa G. Aunque no es ´unico, pues hay otro que pasa por el mismo conjunto de 8 aristas dos veces. Por lo tanto, una vez que se determinan las aristas de Gque deben atravesarse dos veces por un circuito ´optimo, puede haber, en general, m´as que un circuito que atraviese G. 40 3 El Problema del Cartero Chino para grafos dirigidos, mixtos y windy Sea G= (V, E, A) un grafo mixto, donde: Ves un conjunto de v´ertices Ees un conjunto de aristas no dirigidas Aes un conjunto de arcos dirigidos Adem´as, usaremos el t´ermino eje para referirnos tanto a aristas como arcos. Usualmente, los ejes tienen costes asociados no negativos, tanto en grafos no dirigidos, como dirigidos y windy. Diremos que Ges un grafo windy si es no dirigido y hay dos costes relacionados con cada arista representando el coste de atravesarla en cada direcci´on. Adem´as, un grafo mixto es un caso especial de grafo windy, ya que cada arco (i,j) con coste cij puede ser modelado como una arista (i,j) con el mismo coste que el arco y con infinito coste en la direcci´on contraria. El PCC consiste en encontrar una ruta cerrada de coste m´ınimo que pasa por cada arista de Gal menos una vez. Si un grafo G(dirigido, mixto o windy) es euleriano, existe una ruta ´optima que pasa por cada arista una sola vez. Si no, el problema consistir´a en encontrar el conjunto de copias de ejes con un coste m´ınimo, tal que cuando las a˜nadamos a G, consigamos un grafo euleriano. Recordemos finalmente que, para el caso dirigido, el PCC se llama Problema del Cartero Chino dirigido (PCCD), para el caso mixto, Problema del Cartero Chino 41 3. El Problema del Cartero Chino para grafos dirigidos, mixtos y windy Corber´an, Romero, y Sanchis [11], estas ecuaciones, x(δ+(Ki)) = x(δ−(Ki)), i = 1, . . . , q, (3.8) se conocen como las ecuaciones del sistema, donde K1, . . . , Kqdenota el conjunto de v´ertices de las componentes conexas del grafo (V, E). Sea PCCMF1(G) la envolvente convexa de todos los vectores x∈RE∪Asatisfaciendo de (3.4) a (3.6). Por tanto, PCCMF1(G) es un poliedro no acotado, se cumple que dim(PCCMF1(G)) = |E∪A| − q+ 1, y las siguientes desigualdades inducen facetas para PCCMF1(G): 1. Desigualdades triviales: xa≥1, ∀a∈E∪A, 2. Desigualdades de conjuntos equilibrados (3.5), 3. Desigualdades de corte impar (3.7), 4. Desigualdades de zigzag impar (descritas en [10]). Formulaci´on F2 La formulaci´on F2 usa dos variables xij yxji asociadas con cada arista a= (i, j), representando el n´umero de veces que la arista aes atravesada en la direcci´on correspondiente. Como hemos se˜nalado anteriormente, esta formulaci´on est´a basada en las condiciones suficientes para que un grafo mixto sea Euleriano, y tiene la siguiente forma: (PCCM-F2) min Pa=(i,j)∈Eca(xij +xji) + P(i,j)∈Acijxij (3.9) s.t. xij +xji ≥1,∀a= (i, j)∈E, (3.10) x(δ+(S)) −x(δ−(S)) + P(i,j)∈δ(i)(xij +xji) = 0,∀vi∈V,∀S(3.11) xij ≥1 y entero,∀(i, j)∈A, (3.12) xij, xji ≥0 y entero,∀a= (i, j)∈E, (3.13) donde (3.10) y (3.12) implican que todas las aristas y arcos est´an en la soluci´on, 48 3. El Problema del Cartero Chino para grafos dirigidos, mixtos y windy y (3.11) implica que se cumplen las condiciones de simetr´ıa. Se˜nalar que las condiciones de que las variables sean enteras y las de simetr´ıa implican que el grafo resultante ser´a par. Adem´as, se ha demostrado que las coordenadas de los puntos extremos del poliedro asociado a la relajaci´on lineal de F2 toman valores de 0.5 o enteros no negativos, y que los valores fraccionarios ocurren solamente en algunas aristas a= (i, j), donde xij =xji = 0,5. As´ı como con PCW, este resultado podr´ıa ser la base de un algoritmo heur´ıstico simple que consiste en redondear las variables de valores 0.5 a 1. Sea PCCMF2(G) la envolvente convexa de todos los vectores x∈RE∪Asatisfaciendo de (3.10) a (3.13). PCCMF2(G) es un poliedro no acotado, con dimensi´on 2|E|+|A|−|V|+ 1, y tal que las siguientes desigualdades inducen facetas: Desigualdades triviales: xij ≥1∀(i, j)∈A, y xij, xji ≥0∀a= (i, j)∈E, Desigualdades de paso (por una arista) (3.10). Desigualdades de corte impar (3.6) . Desigualdades k-rueda propuestas por Win [48]. Desigualdades de zigzag impar [10]. Comparaci´on de las formulaciones Es f´acil ver que las formulaciones (enteras) F1 y F2 son equivalentes, pero ¿qu´e podemos decir acerca de sus relajaciones en programaci´on lineal? Recordemos que las restricciones (3.4) no son lineales, y que no es posible una expresi´on de ellas sin usar variables enteras. Por tanto, estas restricciones no pueden ser eliminadas, y las desigualdades de corte impar (3.7) se a˜nadir´an a F1. Por otro lado, cabe se˜nalar que una vez que hayamos eliminado las condiciones de que las variables sean enteras de F2, las condiciones de simetr´ıa solas no nos garantizan la paridad de los v´ertices. Por lo que las restricciones (3.13) tambi´en se a˜nadir´an a F2. Por consiguiente, denominaremos a la relajaci´on lineal de F1 reforzada con (3.7), 49 3. El Problema del Cartero Chino para grafos dirigidos, mixtos y windy xij ≥1,∀(i, j)∈A, xa≥1,∀a∈E, x(δ+(S)) −x(δ−(S)) ≤x(δ(S)),∀S⊂V, (3.5) x(δ∗(S)) ≥ |δ∗(S)|+ 1,∀S⊂Vcon |δ∗(S)|impar,(3.7) e igualmente la relajaci´on lineal de F2 reforzada con (3.7), xij ≥1,∀(i, j)∈A, xij, xji ≥0,∀(i, j)∈E, xij +xji ≥1,∀(i, j)∈E, (3.10) x(δ∗(S)) ≥ |δ∗(S)|+ 1,∀S⊂Vcon |δ∗(S)|impar,(3.7) x(δ+(S)) −x(δ−(S)) + P(i,j)∈δ(i)(xij −xji) = 0,∀vi∈V, (3.11) Como las restricciones (3.5) y (3.7) en PLF1y (3.7) en PLF2son exponenciales, solo un subconjunto de ellas pueden ser a˜nadidas de forma expl´ıcita a PL para ser resuelto. Sin embargo, dichas desigualdades pueden separarse en tiempo polinomial. Se ha probado, adem´as, en [8] que ambas relajaciones producen la misma cota. Existen varios procedimientos exactos propuestos para hallar la soluci´on ´optima del PCCM, entre ellos el algoritmo de Ramificaci´on y Acotaci´on de Christofides, [6]. 3.3. Problema del Cartero windy El PCW puede definirse de la siguiente manera. Dado un grafo no dirigido y conexo G= (V, E) con dos costes no negativos asociados con cada arista (i, j)∈E tal que: cij se corresponde al coste de atravesarla desde vihasta vj cji se corresponde al coste de atravesarla desde vjhasta vi 50 3. El Problema del Cartero Chino para grafos dirigidos, mixtos y windy El PCW consiste en encontrar una ruta de coste m´ınimo en Gque pase por cada arista una vez. Fue propuesto por Minieka [39], quien le puso tal nombre debido a que el coste de ir de un punto a otro puede depender de si el viento sopla a favor o en contra. El PCW contiene el PCCM como caso especial cuando, para cada arista (i, j)∈E, o cij =cji, o max{cij, cji}=∞. Por tanto, es f´acil ver que PCW es NP-duro, aunque puede resolverse en tiempo polinomial si Ges par [?], si el coste de los dos sentidos opuestos de cada ciclo en Ges el mismo [29], o si Ges un grafo serie paralelo [53]. Si Gsatisface que el coste en los dos posibles sentidos de cada uno de los ciclos es el mismo, el PCW puede resolverse como el PCC no dirigido donde cada arista (i, j) tiene coste (cij +cji)/2. Vamos a describir a continuaci´on el algoritmo propuesto por Win [?] para encontrar una ruta en un grafo par (y Euleriano) G= (V, E). Este ser´a la base para desarrollar otros algoritmos para grafos generales. Algoritmo de Win para grafos Eulerianos: 1. Para cada arista (i, j)∈E, si cij ≤cji, entonces orientamos (i, j) desde vj hacia vi. De esta forma obtenemos un grafo dirigido DG= (V, A). 2. Construimos un grafo dirigido D0= (V, A0) con conjunto de arcos A0, costes y capacidades de arcos, y demanda en los nodos definida de la siguiente manera: Para cada arco (i, j)∈A, hay tres arcos en A0: una copia de (i, j) con coste cij y capacidad infinita, una copia de (j, i), denotada por (j, i)0, con coste (cij −cji)/2 y capacidad dos (estos arcos se llaman arcos artificiales). Para cada nodo vi∈V, la demanda es di=d+(i)−d−(i) en DG(las demandas negativas son interpretadas como suministros). 3. Encontramos un flujo de coste m´ınimo en D0satisfaciendo las demandas y suministros de los v´ertices. 4. Denotamos por y∗ ij,y∗ ji yy∗ (ji)0a los valores del flujo en los arcos (i, j), (j, i), y (j, i)0, respectivamente. Para cada arco (i, j),(j, i),(j, i)0∈A0, hacemos lo siguiente: 51 3. El Problema del Cartero Chino para grafos dirigidos, mixtos y windy Si y∗ (ji)0= 0, entonces ponemos y∗ ij + 1 copias de (i, j) (y ninguna copia de (j, i)) en A00 Si y∗ (ji)0= 2, ponemos y∗ ji + 1 copias de (j, i) (y ninguna copia de (i, j)) en A00. D00 = (V, A00) es Euleriano, y cualquier camino Euleriano dirigido en D00 es una ruta ´optima del PCW en G. 3.3.1. Algoritmos heur´ısticos Al igual que ocurr´ıa en el PCCM, el algoritmo anterior para grafos pares es la base para un procedimiento heur´ıstico para el caso general (Win [?]). Consiste en transformar primero el grafo original en uno par, y despu´es aplicar el algoritmo anterior para grafos Eulerianos. Algoritmo de Win para grafos generales: 1. Transformamos Gen un grafo Euleriano. Para cada arista a= (i, j)∈E, definimos ce= (cij +cji)/2. Identificamos los nodos impares de G, y calculamos las distancias del camino m´as corto entre cada par de ellos usando las distancias ce. Encontramos un emparejamiento perfecto de coste m´ınimo de los nodos impares. A˜nadimos a Euna copia adicional de cada arista que est´a en el camino m´as corto uniendo dos nodos impares emparejados (!!!!!!!). El grafo resultante G0= (V, E0), es Euleriano. 2. Aplicamos el algoritmo de Win a los grafos Eulerianos de G0con la funci´on de coste original ce. Este algoritmo tiene una cota para el peor de los casos de dos veces el valor del ´optimo. Win [48] propuso otra heur´ıstica que implicaba el redondeo de las soluciones ´optimas de la relajaci´on lineal de la formulaci´on del PCW que veremos a continuaci´on. Este algoritmo est´a basado en el siguiente resultado: Los valores de las variables en cualquier soluci´on ´optima PL son enteros o 0.5, y xij = 0,5 si y solo si xji = 0,5 ([33], [48]). Entonces, si imponemos que xij =xji = 1 podemos demostrar que es posible alcanzar una soluci´on factible del PCW. 52 3. El Problema del Cartero Chino para grafos dirigidos, mixtos y windy 3.3.2. Formulaci´on del problema Sea G= (V, E) el grafo donde hemos hallado la ruta de coste m´ınimo para el PCW. Para S1, S2⊆V, (S1:S2) denota el conjunto de aristas con v´ertices uno en S1, y el otro en S2. Dado S⊆V, consideramos: δ(S) = (S:V\S) E(S) = (S:S) Sea xij el n´umero de veces que una arista (i, j) es atravesada desde vihacia vjen una ruta del PCW. Definimos as´ı: Para cada F⊆E, consideramos x(F) = P(i,j)∈F(xij +xji) Para S1, S2⊂V, consideramos: •x(S1, S2) = Pvi∈S1,vj∈S2xij •x(S1:S2) = x(S1, S2) + x(S2, S1) La formulaci´on PLE (Programaci´on Lineal y Entera) del PCW es la siguiente [48], [28]: (PCW) min P(i,j)∈E(cijxij +cjixji)(3.14) s.t. xij +xji ≥1,∀(i, j)∈E, (3.15) P(i,j)∈δ(i)(xij −xji)=0,∀vi∈V, (3.16) xij, xji ≥0 y entero,∀(i, j)∈E, (3.17) donde las condiciones (3.15) implican que cada arista ser´a atravesada al menos una vez, y las condiciones (3.16) obligan a que el grafo (dirigido) representado por la ruta sea sim´etrico. Adem´as, el sistema anterior incluye una ecuaci´on asociada a cada v´ertice. Nos referiremos as´ı a estas |V|ecuaciones (3.16) como ecuaciones de simetr´ıa, y cualquier conjunto que tomemos con |V| − 1 de ellas son linealmente independientes. Sea PCW(G)⊆Z2|E|la envolvente convexa de los vectores que satisfacen las condiciones (3.15) a la (3.17). PCW(G) es un poliedro no acotado con dimensi´on 2|E|−|V|+ 1, y est´a demostrado que las desigualdades triviales inducen facetas ([27],[48]). Adem´as de estas desigualdades, cabe se˜nalar dos familias de desigualdades m´as que no est´an presentes en la formulaci´on anterior pero de gran importancia: 53 3. El Problema del Cartero Chino para grafos dirigidos, mixtos y windy Desigualdades de corte impar Inducen facetas para el PCW(G) y se basan en el hecho de que cualquier arista de un conjunto de corte debe ser atravesada un n´umero par de veces. Tienen la forma siguiente: x(δ(S)) ≥ |δ(S)|+ 1, ∀S⊂V,|δ(S)|impar. Desigualdades k-rueda Supongamos una rueda formada por un ciclo (la llanta), con cada nodo incidente con un nodo com´un (el centro). A las aristas que unen los nodos de la llanta con el centro las llamaremos radios. As´ı, una k-rueda (denotada como Wk), es una rueda con una llanta de knodos. Por ejemplo, una 3-rueda tendr´ıa la forma siguiente: Y una desigualdad 3-rueda ser´ıa de la forma: x12 +x13 +x14 +x32 +x42 +x43 ≥3 la cual es v´alida e induce facetas para el poliedro de PCW correspondiente. Adem´as, es generalizable reemplazando cada v´ertice por un subgrafo conexo y cada arco por un subconjunto de arcos paralelos con la misma direcci´on: 54 3. El Problema del Cartero Chino para grafos dirigidos, mixtos y windy Consideramos as´ı una partici´on del conjunto de v´ertices Ven cuatro subconjuntos, M1,M2,M3yM4, donde cada Micontiene un n´umero impar de v´ertices impares, y cada subgrafo G(Mi) est´a conectado. Consideramos tambi´en x(A0) como el conjunto de variables correspondientes al paso por las aristas en la direcci´on que aparece en el gr´afico anterior. La desigualdad 3-rueda es cuando: x(A0)≥1 2(|(M1:M3)|+|(M2:M4)|+|(M1:M4)|+|(M2:M3)|)+1 Las desigualdades 3-rueda pueden extenderse a las k-rueda, mucho m´as generales, que contienen un n´umero impar kde nodos en la llanta [48]. Se˜nalar finalmente acerca de la existencia de algoritmos exactos, que en Corber´an et al. [9] se presenta el algoritmo de ramificaci´on y acotaci´on para el PCW. Este usa la heur´ıstica y procedimientos exactos para separar las desigualdades de corte impar violadas e incorporar los algoritmos de separaci´on para todas las familias de desigualdades de zigzag. Adem´as, como est´a demostrado que todas las desigualdades de zigzag son desigualdades de Chv´atal-Gomory de rango a lo sumo 2, se a˜nade un algoritmo en tiempo polinomial para identificar las desigualdades de m´odulo k violadas. B´asicamente, el m´etodo consiste en resolver un sistema de congruencias donde el sistema est´a compuesto de todas las desigualdades obligatorias del ´ultimo PL m´as una desigualdad para cada ecuaci´on de simetr´ıa. Una aproximaci´on completamente diferente a la soluci´on del PCW fue el propuesto por Yan y Thompson [50], quienes modificaron la formulaci´on del PCW para obtener un problema de cobertura de conjuntos. Teniendo en cuenta esta transformaci´on, se propone un algoritmo exacto y un algoritmo heur´ıstico que produce buenos resultados para casos con hasta 90 v´ertices y 180 aristas. Ambos m´etodos est´an basados en la ramificaci´on y acotaci´on, previamente dise˜nados para dar soluci´on a problemas de cubrimiento de conjuntos, divisi´on y problemas packing. 55 4 Aplicaciones En este cap´ıtulo, nos centraremos en ciertos casos para los cuales aplicaremos los resultados vistos anteriormente para el PCC no dirigido, el PCC dirigido, el PCC mixto y el Problema del Cartero windy. Para la obtenci´on de soluciones utilizaremos un programa en Xpress, en el que iremos introduciendo los datos respectivos a cada caso. 4.1. Ejemplo del Problema del Cartero Chino no dirigido Consideremos la siguiente red de carreteras de la Pen´ınsula Ib´erica: 57 4. Aplicaciones La ruta a seguir ser´ıa: [1,2,7,5,4,10,8,9,8,10,9,10,4,3,4,5,6,5,7,6,7,8,7,2,1,3,1] 64 Conclusiones Como conclusi´on general del trabajo, podemos decir que los problemas de rutas por arcos son de gran importancia en la vida real. Vivimos en un mundo en el que se busca continuamente la optimizaci´on de los recursos, as´ı como del tiempo empleado a la hora de realizar cualquier tarea. Esto es crucial especialmente en el ´ambito de la log´ıstica y el transporte, cada vez m´as desarrollado para satisfacer mayor volumen de demanda en el menor tiempo posible. La manera de obtener mayores ganancias es aplicar ciertas t´ecnicas de la investigaci´on operativa, y aqu´ı es donde entra en juego lo que hemos estudiado en este trabajo, usando herramientas de Teor´ıa de Grafos y diversos modelos de Programaci´on Matem´atica. Si nos centramos ´unicamente en el problema de recorrer una red de calles o carreteras eficientemente, es indispensable el uso de los resultados derivados del estudio del Problema del Cartero Chino, donde debemos aplicar una u otra versi´on dependiendo del tipo de grafo que represente el problema en el que estamos trabajando. Existen as´ı infinidad de variantes, todas ellas con diversas formas propuestas de abordarlas. A pesar de que el PCC tuvo su origen en la forma de repartir cartas a lo largo de unas determinadas calles, su aplicaci´on va mucho m´as all´a. Ha sido utilizado a la hora de dise˜nar rutas de autobuses y camiones de mercanc´ıas, ha ayudado a reducir notablemente el coste de la recogida de basuras, de limpieza de calles y de lectura de contadores. Ha mejorado la retirada de nieve en carreteras y calles, y ha sido indispensable en el dise˜no de las rutas de tren y metro. Incluso se ha utilizado para minimizar el coste total de una gr´ua, ya que esta debe, a partir de 65 Conclusiones una posici´on de partida, realizar una serie de movimientos y volver a su posici´on inicial. Lo mismo ocurre con los movimientos de ciertas m´aquinas de producci´on en serie. Por otro lado es imprescindible considerar el problema windy en las trayectorias de aviones y barcos, donde la intensidad y la direcci´on del viento son determinantes a la hora de optimizar el combustible. Por los motivos precedentes, los problemas abordados en este trabajo no solo resultan muy interesantes, sino que tienen una importancia indiscutible tanto en el mundo empresarial e industrial como en la vida cotidiana. 66 Bibliograf´ıa [1] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti- Spaccamela, and M. Protasi,Complexity and Aproximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, New York, 1999. [2] R. Bellman y K. L. Cooke,The Konigsberg bridges problem generalized, Jl. of Math. Anal. and Appl., 25 (1969), p. 1. [3] E. Benavent y D. Soler,The directed rural postman problem with turn penalties, Transportation Science, 33 (1999), pp. 408-418. [4] R. G. Busacker y T. L. Saaty,Finite graphs and networks, McGraw- Hill, New York (1965). [5] N. Christofides,The optimum traversal of a graph, Omega - The Int. Jl. of Management Science, 1 (1973), p. 1. [6] N. Christofides, E. Benavent, V. Campos, ´ A. Corber´ an, y E. Mota,An optimal method for the mixed postman problem, in System Modelling and Optimization, P. Thoft-Christensen, ed., Lecture Notes in Control and Information Sciences 59, Springer, Berlin, 1984, pp. 641-649. [7] ´ A. Corber´ an, R. Mart´ ı, y J. M. Sanchis,A GRASP heuristic for the mixed Chinese postman problem, European Journal of Operational Research, 142 (2002), pp. 70-80. 67 [8] ´ A. Corber´ an, R. Mart´ ı, y J. M. Sanchis,A comparison of two different formulations for arc routing problems on mixed graphs, Computers and Operations Research, 33 (2006), pp. 3384-3402. [9] ´ A. Corber´ an, M. Oswald, I. Plana, G. Reinelt, y J. M. Sanchis, New results on the windy postman problem, Mathematical Programming, 132 (2012), pp. 309-332. [10] ´ A. Corber´ an, I. Plana, y J. M. Sanchis,Zigzag inegualities: A new class of facet-inducing inequalities for arc routing problems, Mathematical Programming, 108 (2006), pp. 79-96. [11] ´ A. Corber´ an, A. Romero, y J. M. Sanchis,The mixed general routing polyhedron, Mathematical Programming, 96 (2003), pp. 103-137. [12] E. W. Dijkstra,A note on two problems in connection with graphs, Numerische Mathematik, 1 (1959), p. 269. [13] R.G. Downey y M.R. Fellows,Fundamentals, Chinese Mathematics, 1 (1962), pp. 237-277. [14] M. Dror y M. Haquari,Generalized Steiner problems and other variants, Journal of Combinatorial Optimization, 4 (2000), pp. 415-436. [15] J. Edmonds,Paths, trees and flowers, Canadian Journal of Mathematics, 17 (1965), pp. 449-467. [16] J. Edmonds,The Chinese postman’s problem, Bulletin of the Operations Research Soc. of America, 13, Supplement 1 (1965), p. B-73. [17] J. Edmonds,The Chinese’s Postman Problem, Operations Research Bulletin, 13 (1965), pp. B73-B77. [18] J. Edmonds y E.L. Johnson,Matching, Euler tours and the Chinese postman, Mathematical Programming, 5 (1973), pp. 88-124. [19] L. Euler,Solutio problemais ad geometriam situs pertinentis, Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8 (1736), pp. 128-140. [20] M.R. Fellows, B.M.P. Jansen, y F.A. Rosamond,Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity, European Journal of Combinatorics, 34 (2013), pp. 541- 566. 68 [21] C.G. Fernandes, 0. Lee, y Y. Wakabayashi,Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width, Discrete Applied Mathematics, 157 (2009), pp. 272-279. [22] M. Fleury,Deux probl`emes de ge´om´etrie de situation, Journal de Math´ematiques ´ El´ementaires, 2 (1883), pp. 257-261. [23] J. Flum and M. Grohe,Parametrized Complexity Theory, Springer, New York, 2006. [24] L.R. Ford y D.R. Fulkerson,Flows in Networks, Princeton University Press, Princeton, NJ, 1962. [25] G.N. Frederickson,Approximation algorithms for some postman problems, Journal of the ACM, 26 (1979), pp. 538-554. [26] B.L. Golden y R.T. Wong,Capacitated arc routing problems, Networks, 11 (1981), pp. 305-315. [27] M. Gr¨ otschel y Z. Win,On the windy postman polyhedron, Technical report 75, University of Augsburg, Augsburg, Germany, 1988. [28] M. Gr¨ otschel y Z. Win,A cutting plane algorithm for the windy postman problem, Mathematical Programming, 55 (1992), pp. 339-358. [29] M. G. Guan,On the windy postman problem, Discrete Applied Mathematics, 9 (1984), pp. 41-46. [30] M.G. Guan,Graphic programming using odd or even points, Chinese Mathematics, 1 (1962), pp. 237-277. [31] M.G. Guan,Paths, trees and flowers, Canadian Journal of Mathematics, 17 (1965), pp. 449-467. [32] C. Hierholzer,¨ Uber die M¨oglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfabren, Mathematische Annalen, 6 (1873), pp. 30-32. [33] C. H. Kappauf y G. J. Koehler,The mixed postman problem, Discrete Applied Mathematics, 1 (1979), pp. 89-103. 69 [34] D. K¨ onig,Theorie der endlichen und unendlichen Graphen, Akademische Verlagsgessellschaft, Leipzig, 1936. [35] G. Laporte y A. Corber´ an,Arc Routing: Problems, Methods and Applications, Society for Industrial and Applied Mathematics, 2014. [36] T. M. Liebling,Graphentheorie in Planungs- und Tourenproblemen, Lecture Notes in Operations Research and Mathematical Systems 21, Springer, Berlin, 1970. [37] J.B. Listing,Vorstudien zur Topologie, Vandenhoeck und Ruprecht, G¨ottingen, 1847. [38] E. Minieka,Optimization Algorithms for Networks and Graphs, Marcel Dekker, New York, 1979. [39] E. Minieka,The Chinese postman problem for mixed networks, Management Science, 25 (1979), pp. 643-648. [40] R. Niedermeier,Invitation to Fixed-Parameter Algorithms, Oxford University Press, Oxford, UK, 2006. [41] M. W. Padberg y M. R. Rao,Odd minimum cut-sets and b-matchings, Mathematics of Operations Research, 7 (1982), pp. 67-80. [42] L. Poinsot,M´emoire sur les polygones et les poly`edres, Journal de l’´ Ecole Polytechnique, 4 (1810), pp. 16-49. [43] B. Raghavachari and J. Veerasamy,A 3/2-approximation algorithm for the mixed postman problem, SIAM Journal on Discrete Mathematics, 12 (1999), pp. 425-433. [44] B. Raghavachari y J. Veerasamy,Approximation algorithms for the asymmetric postman problem, in Proceedings of the 10th Annual ACMSIAM Symposium on Discrete Algorithms (SODA ’99), SIAM, Philadelphia, 1999, pp. 734-741. [45] V.V. Vazirani,Approximation Algorithms, Springer, New York, 2001. [46] O. Vleben,An application of modular equations in analysis situs, Annals of Mathematics, 2 (1913), pp. 86-94. 70 [47] D.P. Williamson y D.B. Shmoys,The Design of Approximation Algorithms, Cambridge University Press, Cambridge, UK, 2011. [48] Z. Win,Constributions to Routing Problems, Ph.D. thesis, University of Augsburg, Augsburg, Germany, 1987. [49] Z. Win,On the windy postman problem on Eulerian graphs, Mathematical Programming, 44 (1989), pp. 97-112. [50] H. Yan y G. Thompson,Finding postal carrier walk paths in mixed graphs, Computational Optimization and Applications, 9 (1998), pp. 229- 247. [51] F. J. Zaragoza Mart´ ınez,Complexity of the mixed postman problem with restrictions on the edges, in Proceedings of the Seventh Mexican International Conference on Computer Science (ENC’06), IEEE, Washington, DC, 2006, pp. 3-10. [52] F. J. Zaragoza Mart´ ınez,Postman Problems on Mixed Graphs, Ph.D. thesis, University of Waterloo, Waterloo, Ontario, Canada, 2003. [53] F. J. Zaragoza,Series-parallel graphs are windy postman perfect, Discrete Mathematics, 308 (2008), pp. 1366-1374. 71