Enrutamiento de arco

Categoría de problema de enrutamiento que minimiza la distancia y el tiempo totales

Los problemas de enrutamiento de arco (ARP) son una categoría de problemas de enrutamiento general (GRP), que también incluye problemas de enrutamiento de nodos (NRP). El objetivo en ARP y NRP es atravesar los bordes y nodos de un gráfico, respectivamente. ^[1] El objetivo de los problemas de enrutamiento de arco implica minimizar la distancia y el tiempo totales, lo que a menudo implica minimizar el tiempo muerto , el tiempo que lleva llegar a un destino. Los problemas de enrutamiento de arco se pueden aplicar a la recolección de basura , planificación de rutas de autobuses escolares , entrega de paquetes y periódicos, deshielo y remoción de nieve con vehículos de servicio invernal que rocían sal en la carretera, ^[2] entrega de correo , mantenimiento de redes, barrido de calles , policía y seguridad. patrullaje de guardias, ^[1] y quitanieves . ^{[3] [4]} Los problemas de enrutamiento de arco son NP difíciles , a diferencia de los problemas de inspección de rutas que se pueden resolver en tiempo polinomial .

Para un ejemplo del mundo real de resolución de problemas de enrutamiento de arcos, Cristina R. Delgado Serna y Joaquín Pacheco Bonrostro aplicaron algoritmos de aproximación para encontrar las mejores rutas de autobuses escolares en el sistema de escuelas secundarias de la provincia española de Burgos . Los investigadores minimizaron la cantidad de rutas que tardaron más de 60 minutos en recorrerse primero. También minimizaron la duración de la ruta más larga con un número máximo fijo de vehículos. ^[5]

Existen generalizaciones de problemas de enrutamiento de arco que introducen a múltiples carteros, por ejemplo, el problema del cartero chino (KCPP).

Fondo

La programación y rutas eficientes de los vehículos pueden ahorrarle a la industria y al gobierno millones de dólares cada año. ^{[2] [6]} Los problemas de enrutamiento de arcos tienen aplicaciones en la planificación de autobuses escolares, recolección de basura y desperdicios en las ciudades, entrega de correo y paquetes por parte de carteros y servicios postales, aplicación de sal en invierno para mantener las carreteras seguras en invierno, nieve arado y remoción, lectura de medidores, incluida tecnología de lectura de medidores de identificación remota por radiofrecuencia, mantenimiento y barrido de calles, planificación de rutas de patrullas de policía y más.

Base

El problema básico de enrutamiento es: dado un conjunto de nodos y/o arcos que serán atendidos por una flota de vehículos, encontrar rutas para cada vehículo que comiencen y terminen en un depósito. Una ruta de vehículo es una secuencia de puntos o nodos que el vehículo debe atravesar en orden, comenzando y terminando en un depósito. ^[2]

Problema del cartero chino

El problema del cartero chino (CPP) tiene como objetivo encontrar la duración mínima del ciclo para un solo cartero. El CPP requiere que todos los bordes se atraviesen una vez, el problema del cartero rural (RPP) requiere que se atraviese un subconjunto de los bordes con el ciclo de longitud mínima. ^[1]

Problemas de rutas de vehículos/VRP

Los problemas de enrutamiento de arco impactan las decisiones de planificación estratégica, táctica y operativa. El papel estratégico del lugar donde se ubica un depósito depende de la ruta de arco más eficiente disponible. La decisión sobre el tamaño de la flota de vehículos y los tipos de vehículos con diferentes especificaciones se relaciona con el aspecto táctico de los problemas de enrutamiento de arco en la investigación de operaciones. Las decisiones de enrutamiento y programación son decisiones de planificación operativa en problemas de enrutamiento de arco. Las decisiones de planificación operativa también incluyen el tiempo que los vehículos son utilizados por los trabajadores con decisiones de personal. ^[2] Las decisiones de ruta de vehículos para la ubicación de un depósito dependen del costo de transporte de materiales a lo largo de una región geográfica. Bodino y otros. Al aplicar rutas de vehículos al problema de marcar un viaje. ^[7]

Problema del cartero rural

En algunas situaciones, el conjunto de aristas que se requieren es diferente de las aristas del gráfico. Esto está modelado por el problema del cartero rural (RPP), ^[1] donde las aristas requeridas son un subconjunto del sistema de aristas.

Algoritmos

Encontrar una solución eficiente con grandes cantidades de datos al problema del cartero chino (CPP), al problema del cartero ventoso (WPP), al problema del cartero rural (RPP), al problema del cartero k -chino (KCPP), al problema mixto del cartero chino (MCPP) ), el problema del cartero chino dirigido (DCPP), ^[8] el problema del arado cuesta abajo (DPP), el problema del arado con precedencia (PPP), el problema del cartero rural con viento (WRPP) y el problema de ruta general con viento (WGRP) requieren el uso Conceptos matemáticos reflexivos, incluidos métodos de optimización heurística , métodos de ramificación y unión , programación lineal entera y aplicaciones de algoritmos de problemas de viajante , como el algoritmo de Held-Karp, mejoran de a a . ^[9] Además de estos algoritmos, estas clases de problemas también se pueden resolver con el algoritmo del plano de corte , optimización convexa , cascos convexos , multiplicadores de Lagrange y otros métodos de programación dinámica . En los casos en los que no sea factible ejecutar el algoritmo de Held-Karp debido a su alta complejidad computacional, se pueden utilizar algoritmos como este para aproximar la solución en un período de tiempo razonable. ^[10] ${\displaystyle O(n!)}$ ${\displaystyle O(2^{n}n^{2})}$

circuitos eulerianos

La primera referencia documentada al área de los problemas de trazado de arcos es el clásico desafío de los puentes de Königsberg , que Euler demostró ser imposible. ^[4] El residente de Konigsberg , ahora parte de Kaliningrado , quería encontrar una manera de cruzar los siete puentes sobre el río Pregel sin retroceder ni volver sobre sus pasos, es decir, cruzar cada puente una vez y sólo una vez. En 1736, Euler redujo el problema a una cuestión de nodos y aristas y demostró que el problema era imposible. En 1873, Hierholzer trabajó más sobre la cuestión de los circuitos cerrados. ^[4]

El trabajo sobre los circuitos eulerianos fue popularizado por Scientific American el 1 de julio de 1953. ^[11] Este trabajo fue ampliado por Meigu Guan, también conocido como Kwan Mei-Ko en Shangtun Normal College. Meigu Guan estaba interesada en una pregunta diferente en lugar de determinar un circuito cerrado. Guan trabajó para encontrar una caminata de longitud mínima que atravesara cada borde del gráfico al menos una vez. Guan describió su objetivo en 1962: "Un cartero tiene que recorrer el tramo asignado antes de regresar a la oficina de correos. El problema es encontrar la distancia más corta a pie para el cartero". ^[4]

tipos de problemas

Los problemas de enrutamiento de arco (ARP) difieren en su objetivo y heurística. Sin embargo, se sabe que todos ellos son NP-hard .

Problema del cartero rural no dirigido

Este problema lleva el nombre del cartero y su desafío de entregar el correo en el orden que elija, pero minimizando sus costos como el tiempo o la distancia del viaje. A veces también se le llama el problema del cartero chino no dirigido . El problema del cartero rural no dirigido (URPP) tiene como objetivo minimizar el costo total de una ruta que mapea toda la red o, en casos más específicos, una ruta que mapea cada borde que requiere un servicio. Si se debe mapear toda la red, la ruta que mapea toda la red se llama recorrido de cobertura . En el caso de que solo se necesiten mapear ciertos bordes, el problema apunta a resolver la ruta que optimice las demandas, cruzando rutas no requeridas un número mínimo de veces. ^[12]

Problema de enrutamiento de arco capacitado no dirigido

El problema del enrutamiento del arco capacitado no dirigido consiste en demandas impuestas a los bordes, y cada borde debe satisfacer la demanda. Un ejemplo es la recolección de basura, donde cada ruta puede requerir tanto una recolección de basura como una recolección de materiales reciclables. Pueden surgir problemas en aplicaciones de la vida real si hay problemas de tiempo, como el caso en el que ciertas rutas no pueden ser atendidas debido a conflictos de tiempo o programación, o restricciones, como un período de tiempo limitado. Las heurísticas descritas en este artículo ignoran cualquier problema que surja debido a restricciones de la aplicación. ^[12]

Historia

El URPP se introdujo por primera vez en 1974 y Lenstra y Kan demostraron que era un problema NP-difícil . El UCARP puede derivarse del URPP y, por tanto, también es NP-duro. En 1981, otro par de informáticos, Golden y Wong, lograron demostrar que incluso derivar una aproximación de 0,5 al URPP era NP-difícil. En 2000, Dror publicó un libro que describe diferentes problemas de enrutamiento de arco.

Problema del cartero ventoso y variantes.

El problema del cartero ventoso propuesto por Minieka es una variante del problema de inspección de ruta en el que la entrada es un gráfico no dirigido, pero donde cada arista puede tener un coste diferente para atravesarlo en una dirección que para atravesarlo en la otra dirección. ^[13] A diferencia de las soluciones para gráficos dirigidos y no dirigidos, es NP-completo . ^{[14] [15]} El costo de viajar en una dirección es mayor cuando el viento sopla en tu cara que cuando el viento está en tu espalda, y este es el origen del nombre problema del cartero ventoso. El trabajo que se necesita para atravesar la calle en una dirección es diferente al trabajo que se necesita para atravesar la calle en otra dirección en un día ventoso. ^[8]

El problema del cartero ventoso es un problema de enrutamiento de arco (ARP) que contiene el problema mixto del cartero chino MCPP como caso especial. ^[dieciséis]

El problema se puede definir de la siguiente manera: "Dado un grafo no dirigido y conexo G=(V,E) con dos costos no negativos y asociado a cada arista correspondiente al costo de recorrerlo de i a j y de j a i, respectivamente, el WPP debe encontrar un recorrido de costo mínimo en G atravesando cada borde al menos una vez." ^[16] Este problema fue introducido por Minieka. El WPP es NP-completo en general y puede resolverse en tiempo polinomial si G es eulerian, si el costo de dos orientaciones opuestas de cada ciclo en G es el mismo o si G es un gráfico serie-paralelo. El problema del cartero rural ventoso (WRPP) es una generalización del WPP en el que no es necesario atravesar todos los bordes del gráfico, sino solo aquellos en un subconjunto determinado de bordes requeridos. Por ejemplo, algunos caminos rurales no son necesarios para que el cartero los cruce y algunos caminos en colinas empinadas tardan más en subir que en bajar. ^[10] ${\displaystyle c_{i,j}}$ ${\displaystyle c_{j,i}}$ ${\displaystyle \{i,j\}\in E}$

El problema del cartero rural ventoso (WRPP) es una generalización del WPP en el que no es necesario atravesar todos los bordes del gráfico, sino solo aquellos en un subconjunto determinado de bordes requeridos. Por ejemplo, algunos caminos rurales no son necesarios para que el cartero los cruce y algunos caminos en colinas empinadas tardan más en subir que en bajar. ^[10] Considere un gráfico no dirigido con dos costos y asociado con el costo de atravesar el borde a partir de i y j, respectivamente. G es el gráfico ventoso y nos interesa el subconjunto de aristas, o los símbolos matemáticos . ${\displaystyle G=\{E,V\}}$ ${\displaystyle c_{ij}}$ ${\displaystyle c_{ji}}$ ${\displaystyle (i,j)}$ ${\displaystyle E_{R}\subseteq E}$

Si el WRPP incluye la restricción adicional de que se debe visitar un determinado conjunto de vértices , el problema se convierte en el problema de enrutamiento general de Windy (WGRP). Benavent propuso una formulación de programación lineal entera y diferentes heurísticas y límites inferiores para el WRPP. ^[9] ${\displaystyle V_{R}\subseteq V}$

Benavent et al publicaron una evaluación de varios métodos heurísticos utilizados para resolver el WRPP en unos pocos segundos con una desviación no mayor al 1% del límite inferior en gráficos de tamaño mediano. Mejoraron esto con un algoritmo de búsqueda dispersa que redujo la diferencia al 0,5%. Scatter Search encontró soluciones que se desviaron en menos del 2 % cuando se implementaron en redes con cientos de nodos y miles de bordes. ^[9]

En aplicaciones del mundo real, hay varios vehículos que pueden moverse, lo que lleva a la generalización denominada Problema del cartero rural ventoso de vehículos K Min-Max (MM K-WRPP). El problema del cartero rural ventoso de K vehículos min-max (MM K-WRPP) se define de la siguiente manera: dado un gráfico ventoso , un vértice distinguido, que representa el depósito, un subconjunto de bordes requeridos y un número fijo K de vehículos, El MM K-WRPP consiste en encontrar un conjunto de K recorridos para los vehículos de tal manera que cada recorrido comience y termine en el depósito y cada borde requerido sea atendido por exactamente un vehículo. El objetivo es minimizar la duración del recorrido más largo para encontrar un conjunto de rutas equilibradas para los vehículos. Algunas aplicaciones en la vida real de problemas de enrutamiento con objetivos mínimo-máximo son el enrutamiento de autobuses escolares (Delgado y Pacheco 2001), la entrega de periódicos a los clientes (Applegate et al. 2002) y la recolección de residuos (Lacomme et al. 2004). ^[10] ${\displaystyle G=\{V,E\}}$ ${\displaystyle 1\in V}$ ${\displaystyle E_{R}\subseteq E}$

El mejor algoritmo MM K_WRPP estuvo muy cerca de la solución mínima con 2 y 3 vehículos, menos del 0,4% en promedio. La diferencia aumenta hasta aproximadamente el 1,00% y el 1,60% en 4 y 5 vehículos.

Según Dussault et al y Benavent et al, un algoritmo metaheurístico de recocido de simulación multiobjetivo (MOSA) puede resolver las diferentes restricciones impuestas al WRPP. El WRPP es un importante problema de enrutamiento del arco que generaliza muchos de los problemas de enrutamiento del arco de vehículos individuales. En aplicaciones reales de matemáticas, es preferible una solución que minimice los costos totales de la ruta de todos los vehículos y la duración del recorrido más largo. Es difícil estar en un lugar donde su paquete siempre llega con horas de retraso. ^[8] Deberíamos comenzar con el supuesto de que varios vehículos con una capacidad mensurable específica para atender a los clientes es más realista que un vehículo con una capacidad infinita no mensurable. Rabbani y otros. al midieron el rendimiento de los algoritmos y modelos MOSA utilizando un desarrollo multiobjetivo de búsqueda Cuckoo, desarrollado por Yang et al, ^[17] también conocido como búsqueda Cuckoo multiobjetivo y abreviado como MOCS. ^[8] Llegaron a la conclusión de que los métodos MOSA eran más eficientes que los métodos MOCS. En el futuro, se podrían investigar comparaciones con otros métodos metaheurísticos, incluido el algoritmo genético de clasificación no dominado (NSGA-), el algoritmo de optimización de enjambre de partículas multiobjetivo (MOPSO) y el algoritmo competitivo imperialista multiobjetivo.

En el modelo del problema del cartero ventoso (WPP), el costo de ir en una dirección es diferente del costo que se necesita para ir en la otra dirección. Por ejemplo, si el viento sopla por la calle se necesita más tiempo y energía para ir en contra que con el viento. Otro ejemplo del WPP es que el costo de arar cuesta arriba es mayor que el costo de arar cuesta abajo. ^[3] Esto está modelado por una variante estudiada por Dussault et al, el Downhill Ploughing Problem (DPP). ^[3]

Ángel Corberán publicó un algoritmo de rama y corte para el problema del cartero ventoso. El algoritmo se basa en métodos heurísticos y exactos para manipular violaciones de desigualdades impares. ^[dieciséis]

Aplicaciones

Varios problemas combinatorios se han reducido al problema del cartero chino, incluido encontrar un corte máximo en un gráfico plano y un circuito de longitud media mínima en un gráfico no dirigido. ^[18]

Quitanieves

En invierno, una pregunta común es ¿qué conjunto de rutas tiene la longitud máxima de ruta más pequeña (mínima)? Normalmente, esto se evalúa como un problema de trazado de arco con un gráfico. El tiempo que se tarda en recorrer una calle, conocido como tiempo muerto, es más rápido que el tiempo que se tarda en quitar la nieve de las calles (o entregar el correo o dejar paquetes). Otro aspecto que se debe considerar al aplicar el trazado en arco para quitar la nieve es el hecho de que en calles empinadas es difícil o imposible quitar la nieve cuesta arriba. El objetivo es una ruta que evite arar cuesta arriba en calles empinadas y que complete el trabajo más rápido al maximizar el tiempo muerto para llegar a la ubicación. Esto fue modelado con un algoritmo heurístico que se aproxima a un límite inferior de Dussault, Golden y Wasil. ^[3] Este es el problema del arado cuesta abajo (DPP). Los equipos de nieve prefieren arar cuesta abajo y cuesta arriba. Este problema supone que las condiciones son lo suficientemente graves como para que las calles estén cerradas y no haya tráfico.

El problema del arado cuesta abajo ignora el problema del arado con prioridad (PPP), que se basa en la suposición razonable de que si la nieve es demasiado profunda, el quitanieves no puede cortar una calle sin arar. El DPP supone que el nivel de nieve es lo suficientemente bajo como para que las calles que no se limpian puedan quedar muertas, pero que la nieve es lo suficientemente profunda como para que no haya tráfico. Si hay tráfico en las carreteras, ya no se puede asumir que es imposible arar cuesta arriba. La simulación para el DPP dejó sin arar una calle sin arar aproximadamente el 5% del tiempo, lo cual es un tema para futuras investigaciones sobre teoría de grafos y enrutamiento de arcos.

Considerando un grafo no dirigido donde es el conjunto de vértices y nodos y es el conjunto de arcos. Cada arco representado por tiene cuatro costos: , definido como el costo de arar de a , el costo de arar de a , el costo de arar de a y , el costo de arar de a . La configuración supone que tiene una elevación más alta , lo que lleva a la afirmación: . En la práctica, el tiempo de arado cuesta abajo es dos veces más eficiente que el de arado cuesta arriba y el tiempo de arado muerto es dos veces más eficiente que el de arado. El algoritmo encuentra que las rutas comenzarán y terminarán en el depósito y recorrerán el arco dos veces porque el lado izquierdo y el lado derecho de la calle requieren dos pasadas para abrirse. ${\displaystyle G=\{V,A\}}$ ${\displaystyle V}$ ${\displaystyle A}$ ${\displaystyle (v_{i},v_{j})}$ ${\displaystyle c_{ij}^{+}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle c_{ji}^{+}}$ ${\displaystyle v_{j}}$ ${\displaystyle v_{i}}$ ${\displaystyle c_{ij}^{-}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle c_{ji}^{-}}$ ${\displaystyle v_{j}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle v_{i}}$ ${\displaystyle c_{ij}^{+}\gg c_{ji}^{+}\gg c_{ij}^{-}\geq c_{ji}^{-}}$ ${\displaystyle k}$ ${\displaystyle v_{0}}$

La mejor solución minimizará la longitud máxima de la ruta. Dussault, Golden y Wasil encontraron un algoritmo que no excedía el límite inferior en un 5,5% en más de 80 ejecuciones de prueba. La desviación aumentó a medida que aumentó la complejidad del modelo porque hay más aproximaciones no optimizadas que optimizadas a medida que crece el modelo. Una mejora con respecto a Dussault et. El algoritmo DPP de Al podría tener penalizaciones por hacer giros en U y giros a la izquierda, o cruzar una intersección en línea recta, lo que lleva tiempo adicional y empuja la nieve hacia el centro de la intersección, respectivamente. (consulte El problema del cartero rural dirigido con penalizaciones por giro, a menudo denominado DRPP-TP a continuación).

k -Problema del cartero chino ( k -CPP)

El k -cartero chino se puede afirmar de la siguiente manera: "dado un gráfico G ponderado por aristas conectado y números enteros p y k , decida si hay al menos k caminos cerrados tales que cada arista de G esté contenida en al menos uno de ellos y el peso total de los bordes en los paseos es como máximo p ?" El proceso de obtención de la solución al k -CPP es NP completo. Gutin, Muciaccia y Yeo demostraron en 2013 que el k -CPP es manejable con parámetros fijos. ^[19] Los autores demuestran que el k -CPP admite un núcleo con vértices y que la versión dirigida del k -CPP es NP completo. ${\displaystyle O(k^{2}\log(k))}$

Problema del cartero rural (RPP) y generalizaciones.

El problema del cartero rural (RPP) hace que algunas rutas sean obligatorias y absolutas, pero la persona que atraviesa el gráfico no tiene que ir en una dirección particular. El RPP es NP duro y completo, de la misma manera que el kCPP, el DPP, el PPP, son NP duro. Benevant estudió una generalización de este problema denominado Problema dirigido del cartero rural con penalizaciones por giro (DRPP-TP). ^[20] El algoritmo de Benevant se aproximó a la solución transformando el DRPP-TP en un problema del viajante asimétrico (ATSP).

Heurísticas y algoritmos.

La mayoría de los algoritmos requieren un preprocesamiento del gráfico, lo que simplifica el gráfico inicial eliminando todos los bordes que no están en el camino más corto entre dos bordes requeridos. Otra simplificación que agrega el preprocesamiento es que transforma el camino más corto entre 2 bordes requeridos en un solo borde no requerido, independientemente del número de bordes en el camino, siempre que no haya bordes requeridos en el camino.

Una vez realizado el preprocesamiento, el problema se puede generalizar a un problema de casco convexo , siendo los bordes las puntas del casco. El problema del casco convexo se puede resolver mediante programación lineal o mediante algoritmos de casco convexo, pero el proceso de encontrar el casco convexo es un problema exponencial.

Los métodos para resolver el URPP después de realizar el preprocesamiento consisten en el algoritmo del plano de corte y la metodología de rama y corte . ^[21]

Complejidad

Esta es una lista de complejidades computacionales para diferentes problemas de enrutamiento de arco.

Lista de variantes de enrutamiento de arco

enlaces externos

• Página de búsqueda de problemas de enrutamiento de arco en la Universidad de Lancaster
• Tendencias en el enrutamiento de arco

Ver también

• Problema del cartero chino
• Problema de ruta de vehículos
• Problema del vendedor ambulante
• camino euleriano
• Problema de enrutamiento del arco capacitado
• Lista de problemas de teoría de grafos
• Problema de ruta del quitanieves
• Lista de complejidad de los problemas del cartero chino

Referencias

1. Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2 de enero de 2018). "Un diseño de ruta equilibrada para el problema del cartero rural de depósitos múltiples mínimo-máximo (MMMDRPP): un caso de patrullaje policial". Revista Internacional de Ciencia de la Información Geográfica . 32 (1): 169-190. doi : 10.1080/13658816.2017.1380201 . ISSN  1365-8816. S2CID  29526595.
2. Omer, Masoud (2007). "Ruteo eficiente del recorrido de nieve de vehículos quitanieves".
3. Dussault, Benjamín; Dorado, Bruce; Wasil, Edward (octubre de 2014). "El problema del arado cuesta abajo con arados múltiples". Revista de la Sociedad de Investigación Operativa . 65 (10): 1465-1474. doi :10.1057/jors.2013.83. ISSN  0160-5682. S2CID  36977043.
4. Eiselt, HA; Gendreau, Michel; Laporte, Gilbert (abril de 1995). "Problemas de enrutamiento de arco, parte I: el problema del cartero chino". La investigación de operaciones . 43 (2): 231–242. doi : 10.1287/opre.43.2.231 . hdl : 11059/14013 . ISSN  0030-364X.
5. Delgado Serna, Cristina R.; Pacheco Bonrostro, Joaquín (2001), Voß, Stefan; Daduna, Joachim R. (eds.), "Problemas de rutas de vehículos Minmax: aplicación al transporte escolar en la provincia de Burgos", Programación del transporte público asistida por computadora , Berlín, Heidelberg: Springer, págs. 297–317, doi :10.1007 /978-3-642-56423-9_17, ISBN 978-3-642-56423-9, consultado el 1 de mayo de 2022
6. Bodino, Lawrence; Dorado, Bruce (1981). "Clasificación en ruteo y programación de vehículos". Redes . 11 (2): 97-108. doi :10.1002/net.3230110204.
7. Bodin, Lawrence D.; Sexton, Thomas R. (febrero de 1983). El problema de Dial-A-Ride para suscriptores de varios vehículos (informe técnico). Escuela de Postgrado Naval. hdl :10945/63226. NPS55-83-002.
8. Rabbani, Masoud; Alamdar, familia Safoura; Farrokhi-Asl, Hamed (1 de febrero de 2016). "Problema del cartero rural ventoso capacitado con varios vehículos: un algoritmo híbrido de recocido simulado multiobjetivo" (PDF) . Revista internacional de gestión de operaciones y suministros . 2 (4): 1003–20. doi :10.22034/2015.4.03. ISSN  2383-1359.
9. Benavent, E.; Corberán, A.; Piñana, E.; Plana, I.; Sanchis, JM (diciembre de 2005), "Nuevos algoritmos heurísticos para el problema del cartero rural con viento", Computers and Operations Research , 32 (12): 3111–28, doi :10.1016/j.cor.2004.04.007, hdl : 10251/ 94488
10. Benavent, Enrique; Corberán, Ángel; Sanchis, José M. (julio de 2010). "Una metaheurística para el problema del cartero rural con viento mínimo-máximo con vehículos K". Ciencia de la gestión computacional . 7 (3): 269–287. doi :10.1007/s10287-009-0119-2. hdl : 10251/100790 . ISSN  1619-697X. S2CID  41426793.
11. "Leonhard Euler y los puentes de Koenigsberg". Científico americano . Consultado el 30 de abril de 2022 .
12. HA, Eiselt; Michel, Gendreau (1995). "Problemas de enrutamiento de arco, parte II: el problema del cartero rural". La investigación de operaciones . 43 (3): 399–414. doi : 10.1287/opre.43.3.399 .
13. Minieka, Edward (julio de 1979). "El problema del cartero chino para redes mixtas". Ciencias de la gestión . 25 (7): 643–648. doi :10.1287/mnsc.25.7.643.
14. Guan, Meigu (1984), "Sobre el problema del cartero ventoso", Matemáticas aplicadas discretas , 9 (1): 41–46, doi : 10.1016/0166-218X(84)90089-1 , SEÑOR  0754427.
15. Lenstra, JK; Rinnooy Kan, AHG (1981), "Complejidad de los problemas de programación y rutas de vehículos" (PDF) , Networks , 11 (2): 221–7, doi :10.1002/net.3230110211
16. Corberán, Ángel; Osvaldo, Marco; Plana, Isaac; Reinelt, Gerhard; Sanchis, José M. (abril de 2012). "Nuevos resultados sobre el problema del cartero ventoso". Programación Matemática . 132 (1–2): 309–332. doi :10.1007/s10107-010-0399-x. ISSN  0025-5610. S2CID  12808962.
17. Yang, Xin-She (2010). "Optimización de ingeniería mediante Cuckoo Search". Revista Internacional de Modelado Matemático y Optimización Numérica . 1 (4): 330–343. arXiv : 1005.2908 . doi :10.1504/IJMMNO.2010.035430. S2CID  34889796.
18. A. Schrijver, Optimización combinatoria, poliedros y eficiencia, Volumen A, Springer. (2002).
19. Gutin, Gregorio; Muciaccia, Gabriele; Sí, Anders (18 de noviembre de 2013). "Complejidad parametrizada del problema del cartero k-chino". Informática Teórica . 513 : 124-128. arXiv : 1308.0482 . doi : 10.1016/j.tcs.2013.10.012 . ISSN  0304-3975. S2CID  2867281.
20. Benavent, Enrique; Soler, David (noviembre de 1999). "El problema del cartero rural dirigido con sanciones por giro". Ciencia del transporte . 33 (4): 408–418. doi :10.1287/trsc.33.4.408. ISSN  0041-1655.
21. Hertz, Alain. "Tendencias recientes en el enrutamiento de arco" (PDF) . Escuela Politécnica — GERAD.
22. Edmonds, Jack; Johnson, Ellis L. (1973). "Matching, giras de Euler y el cartero chino". Programación Matemática . 5 (1): 88-124. doi :10.1007/bf01580113. ISSN  0025-5610. S2CID  15249924.
23. Yaxiong, Lin; Yongchang, Zhao (enero de 1988). "Un nuevo algoritmo para el problema del cartero chino dirigido". Investigación de operaciones y computadoras . 15 (6): 577–584. doi :10.1016/0305-0548(88)90053-6. ISSN  0305-0548.
24. Papadimitriou, Christos H. (julio de 1976). "Sobre la complejidad del recorrido de bordes". Revista de la ACM . 23 (3): 544–554. doi : 10.1145/321958.321974 . ISSN  0004-5411. S2CID  8625996.
25. Raghavachari, Balaji; Veerasamy, Jeyakesavan (enero de 1999). "Un algoritmo de aproximación 3/2 para el problema del cartero mixto". Revista SIAM de Matemática Discreta . 12 (4): 425–433. doi :10.1137/s0895480197331454. ISSN  0895-4801.
26. Gutin, Gregorio; Jones, Marcos; Sheng, Bin (2014), "Complejidad parametrizada del problema del cartero chino k-Arc", Algoritmos - ESA 2014 , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 530–541, arXiv : 1403.1512 , doi : 10.1007/978-3 -662-44777-2_44, ISBN 978-3-662-44776-5, S2CID  3472348 , consultado el 9 de mayo de 2022
27. Fernández, Cristina G.; Lee, Orlando; Wakabayashi, Yoshiko (enero de 2009). "Cobertura de ciclo mínima y problemas del cartero chino en gráficos mixtos con ancho de árbol acotado". Matemática Aplicada Discreta . 157 (2): 272–279. doi : 10.1016/j.dam.2007.10.032 . ISSN  0166-218X.
28. Guan, Meigu (septiembre de 1984). "Sobre el problema del cartero ventoso". Matemática Aplicada Discreta . 9 (1): 41–46. doi : 10.1016/0166-218x(84)90089-1 . ISSN  0166-218X.
29. Gana, Zaw (mayo de 1989). "Sobre el problema del cartero ventoso en gráficos eulerianos". Programación Matemática . 44 (1–3): 97–112. doi :10.1007/bf01587080. ISSN  0025-5610. S2CID  206800125.
30. Veerasamy, Jeyakesavan (1999). Algoritmos de aproximación para problemas de Postman (tesis doctoral). Universidad de Texas en Dallas.
31. Dror, Moshé; Popa, Helman; Trudeau, Pierre (1987). "Recorrido del cartero sobre un gráfico con relación de precedencia sobre arcos". Redes . 17 (3): 283–294. doi :10.1002/net.3230170304. ISSN  0028-3045.
32. "12º congreso mundial de informática: congreso IFIP'92". Computadoras en la Industria . 20 (1): 124-126. Enero de 1992. doi : 10.1016/0166-3615(92)90137-c . ISSN  0166-3615.
33. Thomassen, Carsten (junio de 1997). "Sobre la complejidad de encontrar una cobertura de ciclo mínima de un gráfico". Revista SIAM de Computación . 26 (3): 675–677. doi :10.1137/s0097539794267255. ISSN  0097-5397.
34. Corberán, Ángel (2015).Enrutamiento de arco: problemas, métodos y aplicaciones. ISBN 978-1-61197-366-2.
35. Frederickson, Greg N.; Hecht, Mateo S.; Kim, Chul E. (mayo de 1978). "Algoritmos de aproximación para algunos problemas de enrutamiento". Revista SIAM de Computación . 7 (2): 178-193. doi :10.1137/0207017. ISSN  0097-5397. S2CID  7562375.
36. Eiselt, H (mayo de 1995). "Problemas de enrutamiento de arco, parte II: El problema del cartero rural". pag. 399. ProQuest219174102  .
37. Guan, Meigu (1962). "Programación gráfica mediante puntos pares o impares". Matemáticas chinas .
38. Dussault, Benjamín; Dorado, Bruce; Groër, Chris; Wasil, Edward (1 de abril de 2013). "Arar con prioridad: una variante del problema del cartero ventoso". Investigación de operaciones y computadoras . 40 (4): 1047–1059. doi :10.1016/j.cor.2012.10.013. ISSN  0305-0548.
39. Dussault, Benjamín; Dorado, Bruce; Wasil, Edward (1 de octubre de 2014). "El problema del arado cuesta abajo con arados múltiples". Revista de la Sociedad de Investigación Operativa . 65 (10): 1465-1474. doi :10.1057/jors.2013.83. ISSN  1476-9360. S2CID  36977043.
40. Dussault, Benjamín; Dorado, Bruce; Wasil, Edward (1 de octubre de 2014). "El problema del arado cuesta abajo con arados múltiples". Revista de la Sociedad de Investigación Operativa . 65 (10): 1465-1474. doi :10.1057/jors.2013.83. ISSN  1476-9360. S2CID  36977043.
41. Dussualt, Benjamín (2012). "Modelado y resolución de problemas de enrutamiento de arco en barrido de calles y quitanieves". ProQuest .
42. Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2 de enero de 2018). "Un diseño de ruta equilibrada para el problema del cartero rural de depósitos múltiples mínimo-máximo (MMMDRPP): un caso de patrullaje policial". Revista Internacional de Ciencia de la Información Geográfica . 32 (1): 169-190. doi : 10.1080/13658816.2017.1380201 . ISSN  1365-8816. S2CID  29526595.
43. Ghiani, Gianpaolo; Improta, Gennaro (1 de abril de 2000). "Una transformación eficiente del problema generalizado de rutas de vehículos". Revista europea de investigación operativa . 122 (1): 11-17. doi :10.1016/S0377-2217(99)00073-9. ISSN  0377-2217.