Problema mixto del cartero chino

Problema en matemáticas

El problema del cartero chino mixto (MCPP o MCP) es la búsqueda del recorrido más corto de un grafo con un conjunto de vértices V, un conjunto de aristas no dirigidas E con pesos racionales positivos y un conjunto de arcos dirigidos A con pesos racionales positivos que cubra cada arista o arco al menos una vez con un costo mínimo. ^[1] Papadimitriou ha demostrado que el problema es NP-completo . ^[2] El problema del cartero chino mixto surge a menudo en problemas de enrutamiento de arcos como la limpieza de nieve, donde algunas calles son demasiado estrechas para atravesarlas en ambas direcciones mientras que otras son bidireccionales y se pueden limpiar en ambas direcciones. Es fácil verificar si un grafo mixto tiene un recorrido del cartero de cualquier tamaño verificando si el grafo está fuertemente conectado. El problema es NP-completo si restringimos el recorrido del cartero para atravesar cada arco exactamente una vez o si lo restringimos para atravesar cada arista exactamente una vez, como lo demostró Zaragoza Martínez. ^{[3] [4]}

Definición matemática

La definición matemática es:

Entrada: Un gráfico mixto fuertemente conectado con un costo para cada arista y un costo máximo . ${\displaystyle G=(V,E,A)}$ ${\displaystyle c(e)\geq 0}$ ${\displaystyle e\subset E\cup A}$ ${\displaystyle c_{max}}$

Pregunta: ¿existe un recorrido (dirigido) que recorra cada arista en y cada arco en al menos una vez y tenga un costo como máximo ? ^[5] ${\displaystyle E}$ ${\displaystyle A}$ ${\displaystyle c_{max}}$

Complejidad computacional

La principal dificultad para resolver el problema del Cartero Chino Mixto radica en elegir las orientaciones de las aristas (no dirigidas) cuando tenemos un presupuesto ajustado para nuestro viaje y sólo podemos permitirnos recorrer cada arista una vez. Entonces tenemos que orientar las aristas y añadir algunos arcos más para obtener un grafo euleriano dirigido, es decir, para hacer que cada vértice esté equilibrado. Si hay múltiples aristas incidentes en un vértice, no es una tarea fácil determinar la orientación correcta de cada arista. ^[6] El matemático Papadimitriou analizó este problema con más restricciones: "EL CARTERO CHINO MIXTO es NP-completo, incluso si el grafo de entrada es plano, cada vértice tiene un grado de tres como máximo y cada arista y arco tiene un costo de uno". ^[7]

Gráfico euleriano

El proceso de comprobar si un grafo mixto es euleriano es importante para crear un algoritmo que resuelva el problema del cartero chino mixto. Los grados de un grafo mixto G deben ser pares para tener un ciclo euleriano, pero esto no es suficiente. ^[8]

Aproximación

El hecho de que el Cartero Chino Mixto sea NP-duro ha llevado a la búsqueda de algoritmos de tiempo polinomial que se acerquen a la solución óptima con un umbral razonable. Frederickson desarrolló un método con un factor de 3/2 que podría aplicarse a grafos planares, ^[9] y Raghavachari y Veerasamy encontraron un método que no tiene por qué ser planar. ^[10] Sin embargo, el tiempo polinomial no puede determinar el costo de la eliminación de obstáculos, el tiempo que tarda una máquina quitanieves en llegar a las calles que limpiará o una barredora en llegar a las calles que barrerá. ^{[11] [12]}

Definición formal

Dado un gráfico mixto fuertemente conectado con un conjunto de vértices , un conjunto de aristas , un conjunto de arcos y un coste no negativo para cada uno , la MCPP consiste en encontrar un recorrido de coste mínimo que pase por cada enlace al menos una vez. ${\displaystyle G=(V,E,A)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle A}$ ${\displaystyle c_{e}}$ ${\displaystyle e\in E\cup A}$ ${\displaystyle e\in E\cup A}$

Dado , , , denota el conjunto de aristas con exactamente un punto final en , y . Dado un vértice , (grado de entrada) denota el número de arcos que entran en , (grado de salida) es el número de arcos que salen de , y (grado) es el número de enlaces incidentes con . ^[13] Nótese que . Un grafo mixto se llama par si todos sus vértices tienen grado par, se llama simétrico si para cada vértice , y se dice que está equilibrado si, dado cualquier subconjunto de vértices, la diferencia entre el número de arcos dirigidos desde a , , y el número de arcos dirigidos desde a , , no es mayor que el número de aristas no dirigidas que unen y , . ${\displaystyle S\subset V}$ ${\displaystyle \delta ^{+}(S)=\{(i,j)\in A:i\in S,j\in V\backslash S\}}$ ${\displaystyle \delta ^{-}(S)=\{(i,j)\in A:i\in V\backslash S,j\in S\}}$ ${\displaystyle \delta (S)}$ ${\displaystyle S}$ ${\displaystyle \delta ^{\star }=\delta (S)\cup \delta ^{+}(S)\cup \delta ^{-}}$ ${\textstyle i}$ ${\displaystyle d_{i}^{-}}$ ${\displaystyle i}$ ${\displaystyle d_{i}^{+}}$ ${\textstyle i}$ ${\displaystyle d_{i}}$ ${\displaystyle i}$ ${\displaystyle d_{i}=|\delta ^{\star }(\{{i}\})|}$ ${\displaystyle G=(V,E,A)}$ ${\displaystyle d_{i}^{-}=d_{i}^{+}}$ ${\textstyle i}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle V\backslash S}$ ${\displaystyle |\delta ^{+}(S)|}$ ${\displaystyle V\backslash S}$ ${\displaystyle S}$ ${\displaystyle |\delta ^{-}(S)|}$ ${\displaystyle S}$ ${\displaystyle V\backslash S}$ ${\displaystyle |\delta (S)|}$

Es un hecho bien conocido que un grafo mixto es euleriano si y solo si es par y equilibrado. ^[14] Nótese que si es par y simétrico, entonces G también es equilibrado (y euleriano). Además, si es par, se puede resolver exactamente en tiempo polinomial. ^[15] ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle MCPP}$

Algoritmo MCPP uniforme

1. Dado un grafo mixto par y fuertemente conexo , sea el conjunto de arcos obtenidos asignando aleatoriamente una dirección a las aristas en y con los mismos costos. Calcule para cada vértice i en el grafo dirigido . Un vértice con se considerará como una fuente (sumidero) con oferta y demanda . Nótese que como es un grafo par, todas las ofertas y demandas son números pares (cero se considera un número par). ${\displaystyle G=(V,E,A)}$ ${\displaystyle A_{1}}$ ${\displaystyle E}$ ${\displaystyle s_{i}=d_{i}^{-}-d_{i}^{+}}$ ${\displaystyle (V,A\cup A_{1})}$ ${\textstyle i}$ ${\displaystyle s_{i}>0(s_{i}<0)}$ ${\displaystyle s_{i}(-s_{i})}$ ${\displaystyle G}$
2. Sea el conjunto de arcos en dirección opuesta a los de y con los costos de esas aristas correspondientes, y sea el conjunto de arcos paralelos a con costo cero. ${\displaystyle A_{2}}$ ${\displaystyle A_{1}}$ ${\displaystyle A_{3}}$ ${\displaystyle A_{2}}$
3. Para satisfacer las demandas de todos los vértices, resuelva un problema de flujo de costo mínimo en el grafo , en el que cada arco en tiene capacidad infinita y cada arco en tiene capacidad 2. Sea el flujo óptimo. ${\displaystyle s_{i}}$ ${\displaystyle (V,A\cup A_{1}\cup A_{2}\cup A_{3})}$ ${\displaystyle A\cup A_{1}\cup A_{2}}$ ${\displaystyle A_{3}}$ ${\displaystyle x_{ij}}$
4. Para cada arco en do: Si , entonces orientar el borde correspondiente en de a (la dirección, de a , asignada al borde asociado en el paso 1 era "incorrecta"); si , entonces orientar el borde correspondiente en de a (en este caso, la orientación en el paso 1 era "correcta"). Nótese que el caso es imposible, ya que todos los valores de flujo a través de arcos en son números pares. ${\displaystyle (i,j)}$ ${\displaystyle A_{3}}$ ${\displaystyle x_{ij}=2}$ ${\displaystyle G}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle x_{ij}=0}$ ${\displaystyle G}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle x_{ij}=1}$ ${\displaystyle A_{3}}$
5. Aumenta agregando copias de cada arco en . El gráfico resultante es par y simétrico. ${\displaystyle G}$ ${\displaystyle x_{ij}}$ ${\displaystyle A\cup A_{1}\cup A_{2}}$

Algoritmos heurísticos

Cuando el gráfico mixto no es par y no todos los nodos tienen grado par, el gráfico puede transformarse en un gráfico par.

• Sea un grafo mixto fuertemente conectado . Encuentre los nodos de grado impar ignorando las direcciones de los arcos y obtenga una correspondencia de costo mínimo. Aumente el grafo con los bordes de la correspondencia de costo mínimo para generar un grafo par . ${\displaystyle \mathrm {G=\{V,E,A\}} }$ ${\displaystyle \mathrm {G'=\{V',E',A'\}} }$
• El gráfico es par pero no es simétrico y un gráfico euleriano mixto es par y simétrico. Resuelva un problema de flujo de costo mínimo en para obtener un gráfico simétrico que puede no ser par . ${\displaystyle G'}$ ${\displaystyle G''}$
• El paso final consiste en hacer que el gráfico simétrico sea par. Etiquete los nodos de grado impar como . Encuentre ciclos que alternen entre líneas en el conjunto de arcos y líneas en el conjunto de aristas que comiencen y terminen en los puntos en . Los arcos en deben considerarse como aristas no dirigidas, no como arcos dirigidos. ${\displaystyle G''}$ ${\displaystyle V_{O}}$ ${\displaystyle A''\backslash A}$ ${\displaystyle E''}$ ${\displaystyle V_{O}}$ ${\displaystyle A''\backslash A}$

Algoritmo genético

En un artículo publicado por Hua Jiang et al., se presentó un algoritmo genético para resolver el problema del cartero chino mixto mediante la operación sobre una población. El algoritmo tuvo un buen desempeño en comparación con otros algoritmos de aproximación para el MCPP. ^[16]

Véase también

• Problema de enrutamiento del arco capacitivo

Referencias

1. Minieka, Edward (julio de 1979). "El problema del cartero chino para redes mixtas". Management Science . 25 (7): 643–648. doi :10.1287/mnsc.25.7.643. ISSN  0025-1909.
2. Papadimitriou, Christos H. (julio de 1976). "Sobre la complejidad del recorrido de aristas". Revista de la ACM . 23 (3): 544–554. doi : 10.1145/321958.321974 . ISSN  0004-5411. S2CID  8625996.
3. Zaragoza Martinez, Francisco (septiembre de 2006). "Complejidad del problema del cartero mixto con restricciones en los arcos". 2006 3rd International Conference on Electrical and Electronics Engineering . IEEE. págs. 1–4. doi :10.1109/iceee.2006.251877. ISBN 1-4244-0402-9.
4. Zaragoza Martinez, Francisco (2006). "Complejidad del problema del cartero mixto con restricciones en los bordes". 2006 Séptimo Congreso Internacional Mexicano de Ciencias de la Computación . IEEE. pp. 3–10. doi :10.1109/enc.2006.9. ISBN 0-7695-2666-7. Número de identificación del sujeto  17176905.
5. Edmonds, Jack; Johnson, Ellis L. (diciembre de 1973). "Matching, Euler tours and the Chinese cartero". Programación matemática . 5 (1): 88–124. doi :10.1007/bf01580113. ISSN  0025-5610. S2CID  15249924.
6. Corberán, Ángel (2015).Enrutamiento de arcos: problemas, métodos y aplicaciones. ISBN 978-1-61197-366-2.
7. Papadimitriou, Christos H. (julio de 1976). "Sobre la complejidad del recorrido de aristas". Revista de la ACM . 23 (3): 544–554. doi : 10.1145/321958.321974 . ISSN  0004-5411. S2CID  8625996.
8. Randolph, Ford, Lester (2016). Flujos en redes. Princeton University Press. ISBN 978-1-4008-7518-4. OCLC  954124517.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
9. Frederickson, Greg N. (julio de 1979). "Algoritmos de aproximación para algunos problemas de Postman". Revista de la ACM . 26 (3): 538–554. doi : 10.1145/322139.322150 . ISSN  0004-5411. S2CID  16149998.
10. Raghavachari, Balaji; Veerasamy, Jeyakesavan (enero de 1999). "Un algoritmo de aproximación 3/2 para el problema del cartero mixto". Revista SIAM de Matemáticas Discretas . 12 (4): 425–433. doi :10.1137/s0895480197331454. ISSN  0895-4801.
11. Zaragoza Martinez, Francisco (2006). "Complejidad del problema del cartero mixto con restricciones en los bordes". 2006 Séptimo Congreso Internacional Mexicano de Ciencias de la Computación . IEEE. pp. 3–10. doi :10.1109/enc.2006.9. ISBN 0-7695-2666-7. Número de identificación del sujeto  17176905.
12. Zaragoza Martinez, Francisco (septiembre de 2006). "Complejidad del problema del cartero mixto con restricciones en los arcos". 2006 3rd International Conference on Electrical and Electronics Engineering . IEEE. págs. 1–4. doi :10.1109/iceee.2006.251877. ISBN 1-4244-0402-9.
13. Corberán, Ángel (2015).Enrutamiento de arcos: problemas, métodos y aplicaciones. ISBN 978-1-61197-366-2.
14. Ford, LR (1962). Flujos en redes . Princeton, Nueva Jersey: Princeton University Press.
15. Edmonds, Jack; Johnson, Ellis L. (diciembre de 1973). "Matching, Euler tours and the Chinese cartero". Programación matemática . 5 (1): 88–124. doi :10.1007/bf01580113. ISSN  0025-5610. S2CID  15249924.
16. Jiang, Hua; Kang, Lishan; Zhang, Shuqi; Zhu, Fei (2010), Cai, Zhihua; Hu, Chengyu; Kang, Zhuo; Liu, Yong (eds.), "Algoritmo genético para el problema mixto del cartero chino", Avances en Computación e Inteligencia , Lecture Notes in Computer Science, vol. 6382, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 193–199, doi :10.1007/978-3-642-16493-4_20, ISBN 978-3-642-16492-7, consultado el 25 de octubre de 2022