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 grafo, 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 de marcha en vacío , el tiempo que lleva llegar a un destino. Los problemas de enrutamiento de arco se pueden aplicar a la recolección de basura , la planificación de rutas de autobuses escolares , la entrega de paquetes y periódicos, el deshielo y la remoción de nieve con vehículos de servicio de invierno que rocían sal en la carretera, ^[2] la entrega de correo , el mantenimiento de la red, el barrido de calles , el patrullaje policial y de guardias de seguridad, ^[1] y el arado de nieve . ^{[3] [4]} Los problemas de enrutamiento de arco son NP duros , a diferencia de los problemas de inspección de ruta que se pueden resolver en tiempo polinomial .

Para un ejemplo real de resolución de problemas de rutas de arco, Cristina R. Delgado Serna y Joaquín Pacheco Bonrostro aplicaron algoritmos de aproximación para encontrar las mejores rutas de autobús escolar en el sistema de educación secundaria de la provincia española de Burgos . Los investigadores minimizaron el número de rutas que tardaban 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 múltiples carteros, por ejemplo, el problema del cartero chino k (KCPP).

Fondo

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

Base

El problema básico de enrutamiento es el siguiente: 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 el ciclo de longitud mínima para un solo cartero. El CPP requiere que se atraviesen todos los bordes una vez, mientras que 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 enrutamiento de vehículos/VRP

Los problemas de enrutamiento de arcos afectan las decisiones de planificación estratégica, táctica y operativa. El papel estratégico de la ubicación de 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 especificaciones variables se relacionan con el aspecto táctico de los problemas de enrutamiento de arcos en la investigación de operaciones. Las decisiones de enrutamiento y programación son decisiones de planificación operativa en los problemas de enrutamiento de arcos. Las decisiones de planificación operativa también incluyen el tiempo que los trabajadores utilizan los vehículos junto con las decisiones del personal. ^[2] Las decisiones de enrutamiento de vehículos para la ubicación de un depósito dependen del costo de transportar materiales en una región geográfica. Bodin et. al aplicaron el enrutamiento de vehículos al problema de dial-a-ride. ^[7]

Problema del cartero rural

En algunas situaciones, el conjunto de aristas que se requieren es diferente de las aristas del gráfico. Esto se modela mediante 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 para el problema del cartero chino (CPP), el problema del cartero ventoso (WPP), el problema del cartero rural (RPP), el problema del cartero k -chino (KCPP), el problema del cartero chino mixto (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 ventoso (WRPP) y el problema de enrutamiento general ventoso (WGRP) requiere el uso de conceptos matemáticos bien pensados, incluidos métodos de optimización heurística , métodos de ramificación y acotación , programación lineal entera y aplicaciones de algoritmos del problema del viajante de comercio, como el algoritmo Held-Karp, que mejora de a . ^[9] Además de estos algoritmos, estas clases de problemas también se pueden resolver con el algoritmo del plano de corte , la optimización convexa , las envolturas convexas , los multiplicadores de Lagrange y otros métodos de programación dinámica . En los casos en los que no es posible ejecutar el algoritmo Held-Karp debido a su alta complejidad computacional, se pueden utilizar algoritmos como este para aproximar la solución en un tiempo razonable. ^[10] ${\displaystyle O(n!)}$ ${\displaystyle O(2^{n}n^{2})}$

Circuitos eulerianos

La primera referencia documentada al área de problemas de trazado de arcos es el desafío clásico de los puentes de Königsberg , que Euler demostró que era imposible. ^[4] El residente de Königsberg , ahora parte de Kaliningrado , quería encontrar una forma de cruzar los siete puentes sobre el río Pregel sin retroceder ni desandar sus pasos, es decir, cruzar cada puente una y solo 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 realizó más trabajos sobre la cuestión de los circuitos cerrados. ^[4]

El trabajo sobre los circuitos eulerianos se popularizó en 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 interesado en una cuestión diferente en lugar de determinar un circuito cerrado. Guan trabajó para encontrar una longitud mínima de caminata que atravesara cada borde del grafo al menos una vez. Guan describió su objetivo en 1962: "Un cartero tiene que cubrir su segmento asignado antes de regresar a la oficina de correos. El problema es encontrar la distancia de caminata más corta para el cartero". ^[4]

Tipos de problemas

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

Problema del cartero rural sin dirección

Este problema recibe su nombre del cartero y su desafío de entregar el correo en cualquier orden que elija, pero minimizando sus costos, como el tiempo o la distancia de viaje. A veces también se lo 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 en que solo se necesiten mapear ciertos bordes, el problema tiene como objetivo resolver la ruta que optimiza las demandas, cruzando hacia rutas no requeridas un número mínimo de veces. ^[12]

Problema de enrutamiento de arco capacitado no dirigido

El problema de enrutamiento de arcos capacitativos no dirigidos 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 reciclables. Los problemas en aplicaciones de la vida real pueden surgir 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 de este tipo 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-hard . El UCARP se puede derivar del URPP y, por lo tanto, también es NP-hard. En 1981, otro par de científicos informáticos, Golden y Wong, lograron demostrar que incluso derivar una aproximación de .5 al URPP era NP-hard. En 2000, Dror publicó un libro que describe diferentes problemas de enrutamiento de arcos.

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 grafo no dirigido, pero donde cada arista puede tener un costo diferente para atravesarlo en una dirección que para atravesarlo en la otra dirección. ^[13] En contraste con las soluciones para grafos 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 sopla en tu espalda, y este es el origen del nombre de problema del cartero ventoso. El trabajo que se necesita para atravesar la calle en una dirección es diferente del 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 del cartero chino mixto (MCPP) como un caso especial. ^[16]

El problema puede definirse de la siguiente manera: "Dado un grafo no dirigido y conexo G=(V,E) con dos costes no negativos y asociado a cada arista correspondiente al coste de atravesarlo de i a j y de j a i, respectivamente, el WPP es encontrar un recorrido de coste mínimo en G recorriendo cada arista 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 euleriano, si el coste de dos orientaciones opuestas de cada ciclo en G es el mismo o si G es un grafo serie-paralelo. El Problema del Cartero Rural Ventoso (WRPP) es una generalización del WPP en el que no se deben atravesar todas las aristas del grafo sino sólo aquellas en un subconjunto dado de aristas requeridas. 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 se deben atravesar todos los bordes del grafo, sino solo aquellos en un subconjunto dado 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 grafo no dirigido con dos costos y asociados con el costo de atravesar el borde comenzando desde i y j, respectivamente. G es el grafo ventoso y estamos interesados ​​en el subconjunto de bordes, o en 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 grafos de tamaño medio. Mejoraron esto con un algoritmo Scatter Search 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 aristas. ^[9]

En aplicaciones del mundo real, hay múltiples vehículos que pueden moverse, lo que conduce a la generalización denominada Problema del Cartero Rural Ventoso de K-vehículos Mín-Máx (MM K-WRPP). El Problema del Cartero Rural Ventoso de K-vehículos Mín-Máx (MM K-WRPP) se define de la siguiente manera: Dado un grafo ventoso , un vértice distinguido, , que representa el depósito, un subconjunto de aristas requeridas , 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 arista requerida sea atendida por exactamente un vehículo. El objetivo es minimizar la longitud del recorrido más largo para encontrar un conjunto de rutas equilibradas para los vehículos. Algunas aplicaciones de la vida real de problemas de enrutamiento con objetivos mín-máx son el enrutamiento de autobuses escolares (Delgado y Pacheco 2001), la entrega de periódicos a 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 brecha aumenta a aproximadamente el 1,00 % y el 1,60 % con 4 y 5 vehículos.

Según Dussault et al y Benavent et al, un algoritmo de simulación de recocido multiobjetivo metaheurístico (MOSA) puede resolver las diferentes restricciones impuestas al WRPP. El WRPP es un importante problema de enrutamiento de arco que generaliza muchos de los problemas de enrutamiento de arco de un solo vehículo. 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 horas tarde. ^[8] Deberíamos comenzar con la suposición de que varios vehículos con una capacidad medible específica para atender a los clientes es más realista que un vehículo con una capacidad infinita no medible. Rabbani et. al midieron el rendimiento de los algoritmos y modelos MOSA utilizando un desarrollo multiobjetivo de la búsqueda Cuckoo, desarrollada por Yang et al, ^[17] también conocida como Búsqueda Cuckoo Multiobjetivo y abreviada como MOCS. ^[8] Concluyeron 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, incluidos el algoritmo genético de clasificación no dominada (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 (PPV), 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 calle abajo, se necesita más tiempo y energía para ir contra el viento que a favor del viento. Otro ejemplo del PPV es que el costo de arar cuesta arriba es mayor que el costo de arar cuesta abajo. ^[3] Esto se modela mediante una variante estudiada por Dussault et al, el Problema del Arado Cuesta Abajo (PPD). ^[3]

Angel Corberan publicó un algoritmo de ramificación y corte para el problema del cartero ventoso. El algoritmo se basa en métodos heurísticos y exactos para manipular las violaciones de la desigualdad de corte impar. ^[16]

Aplicaciones

Varios problemas combinatorios se han reducido al problema del cartero chino, incluido el hallazgo de 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). Por lo general, esto se evalúa como un problema de enrutamiento de arco con un gráfico. El tiempo que se tarda en recorrer una calle, conocido como tiempo de paso 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 enrutamiento de arco al arado de nieve es el hecho de que en calles empinadas es difícil o imposible arar 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 de paso muerto para llegar a la ubicación. Esto se modeló con un algoritmo heurístico que se aproxima a un límite inferior por 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 severas como para que las calles estén cerradas y no haya tráfico.

El problema de arado en pendiente descendente ignora el problema de arado con precedencia (PPP), que se basa en la suposición razonable de que si la nieve es demasiado profunda, el quitanieves no puede quitar la nieve muerta de una calle sin quitar. El DPP parte de la suposición de que el nivel de nieve es lo suficientemente bajo como para que las calles que no se limpian puedan quitarse la nieve muerta, pero que la nieve es lo suficientemente profunda como para que no haya tráfico. Si hay tráfico en las carreteras, la suposición de que es imposible quitar la nieve en pendiente ascendente ya no se puede mantener. La simulación para el DPP dejó la nieve muerta en una calle sin quitar alrededor del 5% del tiempo, lo que es un tema para futuras investigaciones sobre teoría de grafos y trazado 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 desde hasta , , el costo de arar desde hasta , , el costo de desbrozar desde hasta , y , el costo de desbrozar desde hasta . 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 arado cuesta arriba y el desbrozar es dos veces más eficiente que el arado. El algoritmo descubre que las rutas comenzarán y terminarán en el depósito , ara el arco dos veces porque el lado izquierdo y el lado derecho de la calle requieren dos pasadas para arar. ${\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 excedió el límite inferior en un 5,5 % en más de 80 ejecuciones de prueba. La desviación aumentó a medida que aumentaba la complejidad del modelo porque hay más aproximaciones no optimizadas que aproximaciones optimizadas a medida que el modelo crece. Una mejora en el algoritmo DPP de Dussault et. 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 requiere más tiempo y empuja la nieve hacia el medio de la intersección, respectivamente. (Vea el problema del problema del cartero rural dirigido con penalizaciones de giro, a menudo denominado DRPP-TP a continuación).

a-El problema del cartero chino (a-CPP)

El Cartero k -chino puede enunciarse de la siguiente manera: "dado un grafo conexo ponderado por aristas G y enteros p y k , decida si hay al menos k recorridos cerrados tales que cada arista de G esté contenida en al menos una de ellas y el peso total de las aristas en los recorridos sea como máximo p ?" El proceso de obtención de la solución del 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 completa. ${\displaystyle O(k^{2}\log(k))}$

Problema del cartero rural (PPR) y generalizaciones

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

Heurísticas y algoritmos

La mayoría de los algoritmos requieren un preprocesamiento del gráfico, que simplifica el gráfico inicial eliminando todas las aristas que no se encuentran en el camino más corto entre dos aristas requeridas. Otra simplificación que agrega el preprocesamiento es que transforma el camino más corto entre dos aristas requeridas en una única arista no requerida, independientemente del número de aristas en el camino, siempre que no haya aristas requeridas en el camino.

Una vez realizado el preprocesamiento, el problema se puede generalizar a un problema de envoltura convexa , en el que los bordes son los puntos de la envoltura. El problema de la envoltura convexa se puede resolver mediante programación lineal o mediante algoritmos de envoltura convexa, pero el proceso de encontrar la envoltura convexa 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 ramificación y corte . ^[21]

Complejidad

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

Lista de variantes de enrutamiento de arco

Enlaces externos

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

Véase también

• Problema del cartero chino
• Problema de ruta del vehículo
• Problema del viajante de comercio
• Camino euleriano
• Problema de enrutamiento del arco capacitivo
• Lista de problemas de teoría de grafos
• Problema de ruta de la máquina quitanieves
• Lista de complejidad del problema del cartero chino

Referencias

1. Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2018-01-02). "Un diseño de ruta equilibrada para el problema del cartero rural de múltiples depósitos mín-máx (MMMDRPP): un caso de patrullaje policial". Revista internacional de ciencias de la información geográfica . 32 (1): 169–190. Bibcode :2018IJGIS..32..169C. doi : 10.1080/13658816.2017.1380201 . ISSN  1365-8816. S2CID  29526595.
2. Omer, Masoud (2007). "Enrutamiento eficiente de vehículos quitanieves".
3. Dussault, Benjamin; Golden, 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". 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 ruteo de vehículos Minmax: aplicación al transporte escolar en la provincia de Burgos", Computer-Aided Scheduling of Public Transport , Berlín, Heidelberg: Springer, pp. 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. Bodin, Lawrence; Golden, Bruce (1981). "Clasificación en la planificación y el enrutamiento 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 la conexión telefónica entre abonados de varios vehículos (informe técnico). Naval Postgraduate School. hdl :10945/63226. NPS55-83-002.
8. Rabbani, Masoud; Alamdar, Safoura Famil; 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 suministros y operaciones . 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 K vehículos". Computational Management Science . 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 Königsberg". Scientific American . Julio de 1953. 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". 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". Management Science . 25 (7): 643–648. doi :10.1287/mnsc.25.7.643.
14. Guan, Meigu (1984), "Sobre el problema del cartero ventoso", Discrete Applied Mathematics , 9 (1): 41–46, doi : 10.1016/0166-218X(84)90089-1 , MR  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 búsqueda de cuco". 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, Gregory; Muciaccia, Gabriele; Yeo, Anders (18 de noviembre de 2013). "Complejidad parametrizada del problema del cartero chino k". Ciencias de la computación 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 penalizaciones por giro". Transportation Science . 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, Euler tours 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". Computers & Operations Research . 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 aristas". 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áticas Discretas . 12 (4): 425–433. doi :10.1137/s0895480197331454. ISSN  0895-4801.
26. Gutin, Gregory; Jones, Mark; Sheng, Bin (2014), "Complejidad parametrizada del problema del cartero chino de k-Arc", Algorithms - 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. Fernandes, Cristina G.; Lee, Orlando; Wakabayashi, Yoshiko (enero de 2009). "Cobertura de ciclo mínimo y problemas del cartero chino en grafos mixtos con ancho de árbol acotado". Matemáticas Aplicadas Discretas . 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áticas Aplicadas Discretas . 9 (1): 41–46. doi : 10.1016/0166-218x(84)90089-1 . ISSN  0166-218X.
29. Win, Zaw (mayo de 1989). "Sobre el problema del cartero ventoso en grafos 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, Moshe; Stern, Helman; Trudeau, Pierre (1987). "Gira del cartero en un grafo con relación de precedencia en arcos". Redes . 17 (3): 283–294. doi :10.1002/net.3230170304. ISSN  0028-3045.
32. "12º congreso mundial de informática— congreso IFIP'92". Computers in Industry . 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 grafo". Revista SIAM de Computación . 26 (3): 675–677. doi :10.1137/s0097539794267255. ISSN  0097-5397.
34. Corberán, Ángel (2015).Enrutamiento de arcos: problemas, métodos y aplicaciones. ISBN 978-1-61197-366-2.
35. Frederickson, Greg N.; Hecht, Matthew S.; Kim, Chul E. (mayo de 1978). "Algoritmos de aproximación para algunos problemas de enrutamiento". Revista SIAM de informática . 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". pág. 399. ProQuest  219174102.
37. Guan, Meigu (1962). "Programación gráfica utilizando puntos pares o impares". Matemáticas chinas .
38. Dussault, Benjamin; Golden, Bruce; Groër, Chris; Wasil, Edward (1 de abril de 2013). "Arar con precedencia: una variante del problema del cartero ventoso". Computers & Operations Research . 40 (4): 1047–1059. doi :10.1016/j.cor.2012.10.013. ISSN  0305-0548.
39. Dussault, Benjamin; Golden, Bruce; Wasil, Edward (1 de octubre de 2014). "El problema del arado en pendiente 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, Benjamin; Golden, Bruce; Wasil, Edward (1 de octubre de 2014). "El problema del arado en pendiente 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, Benjamin (2012). "Modelado y solución de problemas de trazado de arcos en el barrido de calles y la remoción de nieve". ProQuest .
42. Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2018-01-02). "Un diseño de ruta equilibrada para el problema del cartero rural de múltiples depósitos con mínimo y máximo (MMMDRPP): un caso de patrullaje policial". Revista internacional de ciencias de la información geográfica . 32 (1): 169–190. Código Bibliográfico :2018IJGIS..32..169C. 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 enrutamiento de vehículos". Revista Europea de Investigación Operativa . 122 (1): 11–17. doi :10.1016/S0377-2217(99)00073-9. ISSN  0377-2217.