Hispanopedia Wiki
Articulo de referencia

Enrutamiento de arco

Los problemas de enrutamiento de arcos ( ARP ) son una categoría de problemas de enrutamiento general (GRP), que también incluye problemas de enrutamiento de nodos (NRP). El obj...

Hispanopedia WikiContenido en espanolLectura gratuita

Los problemas de enrutamiento de arcos ( ARP ) son una categoría de problemas de enrutamiento general (GRP), que también incluye problemas de enrutamiento de nodos (NRP). El objetivo en los ARP y NRP es recorrer las aristas y los nodos de un grafo, respectivamente. [ 1 ] El objetivo de los problemas de enrutamiento de arcos implica minimizar la distancia y el tiempo totales, lo que a menudo implica minimizar el tiempo de viaje en vacío , el tiempo que se tarda en llegar a un destino. Los problemas de enrutamiento de arcos 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 esparcen sal en la carretera, [ 2 ] la entrega de correo , el mantenimiento de redes, 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 arcos son NP-difíciles , a diferencia de los problemas de inspección de rutas que se pueden resolver en tiempo polinomial .

Como ejemplo práctico 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 educación secundaria de la provincia española de Burgos . Los investigadores minimizaron primero el número de rutas que tardaban más de 60 minutos en recorrerse. 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 los problemas de enrutamiento de arcos que introducen múltiples carteros, por ejemplo, el problema del cartero chino de k personas (KCPP).

Fondo

La programación y el enrutamiento eficientes de vehículos pueden ahorrar 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, la recolección de basura y desechos en las ciudades, la entrega de correo y paquetes por carteros y servicios postales, el esparcimiento de sal en invierno para mantener las carreteras seguras, el arado y la remoción de nieve, la lectura de medidores, incluida la tecnología de lectura de medidores por identificación de 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 consiste en: dado un conjunto de nodos y/o arcos que deben ser atendidos por una flota de vehículos, encontrar rutas para cada vehículo que comiencen y terminen en un depósito. Una ruta vehicular es una secuencia de puntos o nodos que el vehículo debe recorrer en orden, comenzando y terminando en un depósito. [ 2 ]

El problema del cartero chino

El problema del cartero chino (PCC) tiene como objetivo encontrar el ciclo de longitud mínima para un solo cartero. El PCC requiere que todas las aristas se recorran una vez, mientras que el problema del cartero rural (PCR) requiere que un subconjunto de las aristas se recorra con el ciclo de longitud mínima. [ 1 ]

Problemas de enrutamiento de vehículos/VRP

Los problemas de enrutamiento de arcos impactan las decisiones de planificación estratégica, táctica y operativa. El rol estratégico de la ubicación de un depósito depende de la ruta de arco más eficiente disponible. La decisión del tamaño de la flota de vehículos y los tipos de vehículos con especificaciones variables se relaciona con el aspecto táctico de los problemas de enrutamiento de arcos en la investigación operativa. 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 con decisiones de 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 viaje a demanda. [ 7 ]

Problema del cartero rural

En algunas situaciones, el conjunto de aristas requeridas es diferente de las aristas del grafo. 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 chino k (KCPP), el problema del cartero chino mixto (MCPP), el Problema del Cartero Chino Dirigido (DCPP), [ 8 ] el Problema del Arado Cuesta Descendente (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, como el algoritmo de Held-Karp, que supone una mejora deO(norte¡){\displaystyle O(n!)}aO(2nortenorte2){\displaystyle O(2^{n}n^{2})}[ 9 ] Además de estos algoritmos, estas clases de problemas también pueden resolverse con el algoritmo del plano de corte , la optimización convexa , las envolventes convexas , los multiplicadores de Lagrange y otros métodos de programación dinámica . En los casos en 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 tiempo razonable. [ 10 ]

circuitos eulerianos

La referencia documentada más antigua al área de problemas de enrutamiento de arcos es el clásico desafío de los puentes de Königsberg , que Euler demostró que era imposible. [ 4 ] Los habitantes de Königsberg , ahora parte de Kaliningrado , querían encontrar una manera de cruzar los siete puentes sobre el río Pregel sin retroceder ni desandar sus pasos, es decir, cruzar cada puente una sola vez. En 1736, Euler redujo el problema a una cuestión de nodos y aristas y demostró que era imposible. En 1873, Hierholzer continuó trabajando en 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 el Colegio Normal de Shangtun. Meigu Guan estaba interesado en una cuestión diferente en lugar de determinar un circuito cerrado. Guan trabajó para encontrar un recorrido de longitud mínima que atravesara cada arista 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 más corta que debe recorrer el cartero". [ 4 ]

Tipos de problemas

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

Problema del cartero rural sin dirección

Este problema recibe su nombre del cartero y su desafío de entregar el correo en el orden que elija, minimizando sus costos, como el tiempo o la distancia recorrida. También se le conoce como el problema del cartero chino no dirigido . El problema del cartero rural no dirigido (URPP) busca minimizar el costo total de una ruta que mapee toda la red o, en casos más específicos, una ruta que mapee cada arista que requiera un servicio. Si se debe mapear toda la red, la ruta que la mapea se denomina recorrido de cobertura . En el caso de que solo se necesiten mapear ciertas aristas, el problema busca resolver la ruta que optimice las demandas, cruzando a rutas no requeridas un número mínimo de veces. [ 12 ]

Problema de enrutamiento de arcos con capacidad no dirigidos

El problema de enrutamiento de arcos con capacidad no dirigidos consiste en demandas impuestas a las aristas, y cada arista debe satisfacer la demanda. Un ejemplo es la recolección de basura, donde cada ruta puede requerir tanto la recolección de basura como la de materiales reciclables. En aplicaciones reales, pueden surgir problemas si existen problemas de sincronización, como cuando ciertas rutas no pueden ser atendidas debido a conflictos de tiempo o de 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 las 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 se puede derivar del URPP y, por lo tanto, también es NP-difícil. En 1981, otro par de científicos 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 arcos.

El problema del cartero ventoso y sus variantes

El problema del cartero ventoso propuesto por Minieka es una variante del problema de inspección de rutas en la que la entrada es un grafo no dirigido, pero donde cada arista puede tener un costo diferente para recorrerla en una dirección que para recorrerla en la otra. [ 13 ] A diferencia de 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 la cara que cuando el viento está a la espalda, y este es el origen del nombre Problema del cartero ventoso. El trabajo que se requiere para recorrer la calle en una dirección es diferente al trabajo que se requiere para recorrer la calle en otra dirección en un día ventoso. [ 8 ]

El problema del cartero ventoso es un problema de enrutamiento de arcos (ARP) que contiene el problema del cartero chino mixto (MCPP) como caso especial. [ 16 ]

El problema se puede definir de la siguiente manera: "Dado un grafo no dirigido y conexo G=(V,E) con dos costos no negativosdoi,j{\displaystyle c_{i,j}}ydoj,i{\displaystyle c_{j,i}}asociado con cada borde{i,j}∈mi{\displaystyle \{i,j\}\in E}correspondiente al costo de recorrerlo de i a j y de j a i, respectivamente, el WPP consiste en encontrar un recorrido de costo 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 costo 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 la que no todas las aristas del grafo tienen que ser recorridas, sino solo aquellas en un subconjunto dado de aristas requeridas. Por ejemplo, algunas carreteras rurales no son necesarias para que el cartero las cruce y algunas carreteras en colinas empinadas tardan más en subir que en bajar. [ 10 ]

El problema del cartero rural ventoso (WRPP, por sus siglas en inglés) es una generalización del problema del cartero rural ventoso (WPP, por sus siglas en inglés) en la que no es necesario recorrer todas las aristas del grafo, sino solo aquellas de un subconjunto determinado de aristas requeridas. Por ejemplo, algunas carreteras rurales no son necesarias para que el cartero las cruce, y algunas carreteras en pendientes pronunciadas tardan más en subir que en bajar. [ 10 ] Consideremos un grafo no dirigido.GRAMO={mi,V}{\displaystyle G=\{E,V\}}con dos costosdoij{\displaystyle c_{ij}}ydoji{\displaystyle c_{ji}}asociado al costo de atravesar el borde(i,j){\displaystyle (i,j)}comenzando desde i y j, respectivamente. G es el grafo sinuoso y estamos interesados ​​en el subconjunto de aristas, o en símbolos matemáticos,miR⊆mi{\displaystyle E_{R}\subseteeq E}.

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

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

En aplicaciones del mundo real, existen múltiples vehículos que pueden moverse, lo que lleva a la generalización denominada Problema del cartero rural ventoso con K vehículos y mínimo-máximo (MM K-WRPP). El Problema del cartero rural ventoso con K vehículos y mínimo-máximo (MM K-WRPP) se define de la siguiente manera: Dado un gráfico ventosoGRAMO={V,mi}{\displaystyle G=\{V,E\}}, un vértice distinguido,1∈V{\displaystyle 1\in V}, que representa el depósito, un subconjunto de aristas requeridas miR⊆mi{\displaystyle E_{R}\subseteeq E}Con 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 reales de problemas de enrutamiento con objetivos min-max 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 ]

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

Según Dussault et al y Benavent et al, un algoritmo metaheurístico de recocido simulado multiobjetivo (MOSA) puede resolver las diferentes restricciones impuestas al WRPP. El WRPP es un importante problema de enrutamiento de arcos que generaliza muchos de los problemas de enrutamiento de arcos de un solo vehículo. En aplicaciones matemáticas reales, se prefiere una solución que minimice los costos totales de todas las rutas de los vehículos y la longitud del recorrido más largo. Es difícil estar en un lugar donde tu paquete siempre llega con horas de retraso. [ 8 ] Deberíamos comenzar con la suposición de que varios vehículos con una capacidad específica y medible para atender a los clientes es más realista que un solo vehículo con capacidad infinita no medible. Rabbani et al midieron el rendimiento de los algoritmos y modelos MOSA utilizando un desarrollo multiobjetivo de la búsqueda del cuco, desarrollado por Yang et al, [ 17 ] también conocido como búsqueda del cuco multiobjetivo y abreviado 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 (WPP), el costo de ir en una dirección es diferente al costo de ir en la dirección opuesta. Por ejemplo, si el viento sopla a favor del viento, se requiere más tiempo y energía para ir contra el viento que a favor. Otro ejemplo del WPP 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 de Arado Cuesta Descendente (DPP). [ 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 violaciones de desigualdades de corte impares. [ 16 ]

Aplicaciones

Diversos problemas combinatorios se han reducido al problema del cartero chino, incluyendo encontrar un corte máximo en un grafo planar y un circuito de longitud media mínima en un grafo 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 enrutamiento de arcos con un grafo. El tiempo que se tarda en recorrer una calle, conocido como tiempo de inactividad, es más rápido que el tiempo que se tarda en quitar la nieve de las calles (o entregar correo o dejar paquetes). Otro aspecto que debe considerarse al aplicar el enrutamiento de arcos al quitanieves 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 quitar la nieve cuesta arriba en calles empinadas que complete el trabajo más rápido al maximizar el tiempo de inactividad para llegar a la ubicación. Esto fue modelado con un algoritmo heurístico que aproxima una cota inferior por Dussault, Golden y Wasil. [ 3 ] Este es el Problema del Quitanieves Cuesta Abajo (DPP). Los equipos de nieve prefieren quitar la nieve cuesta abajo y cuesta arriba en caso de inactividad. 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 cuesta abajo ignora el problema de arado con precedencia (PPP), que se basa en la suposición razonable de que si la nieve es demasiado profunda, la quitanieves no puede despejar una calle sin limpiar. El DPP parte de la suposición de que el nivel de nieve es lo suficientemente bajo como para que las calles sin limpiar puedan despejarse, 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 arar cuesta arriba ya no se sostiene. La simulación para el DPP despejó calles sin limpiar aproximadamente el 5% de las veces, lo que constituye un tema para futuras investigaciones sobre teoría de grafos y enrutamiento de arcos.

Considerando un grafo no dirigidoGRAMO={V,A}{\displaystyle G=\{V,A\}}dóndeV{\displaystyle V}es el conjunto de vértices y nodos yA{\displaystyle A}es el conjunto de arcos. Cada arco está representado por(vi,vj){\displaystyle (v_{i},v_{j})}tiene cuatro costos:doij+{\displaystyle c_{ij}^{+}}, definido como el costo de arar desdevi{\displaystyle v_{i}}avj{\displaystyle v_{j}},doji+{\displaystyle c_{ji}^{+}}, el costo de arar desdevj{\displaystyle v_{j}}avi{\displaystyle v_{i}},doij−{\displaystyle c_{ij}^{-}}, el costo de desviar los trenes en vacío desdevi{\displaystyle v_{i}}avj{\displaystyle v_{j}}, ydoji−{\displaystyle c_{ji}^{-}}, el costo de desviar los trenes en vacío desdevj{\displaystyle v_{j}}avi{\displaystyle v_{i}}. La configuración asume quevj{\displaystyle v_{j}}tiene mayor altitudvi{\displaystyle v_{i}}lo cual lleva a la siguiente afirmación:doij+≫doji+≫doij−≥doji−{\displaystyle c_{ij}^{+}\gg c_{ji}^{+}\gg c_{ij}^{-}\geq c_{ji}^{-}}En la práctica, el tiempo de arado cuesta abajo es dos veces más eficiente que el arado cuesta arriba y el desbroce es dos veces más eficiente que el arado. El algoritmo encuentrak{\displaystyle k}Cada ruta comenzará y terminará en el depósito.v0{\displaystyle v_{0}}, arar el arco dos veces porque el lado izquierdo y el lado derecho de la calle requieren dos pasadas para ararse.

La mejor solución minimizará la longitud máxima de la ruta. Dussault, Golden y Wasil encontraron un algoritmo que no superó 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, ya que hay más aproximaciones no optimizadas que optimizadas a medida que el modelo crece. Una mejora del algoritmo DPP de Dussault et al. podría incluir penalizaciones por realizar giros en U y giros a la izquierda, o por cruzar una intersección en línea recta, lo que consume tiempo adicional y empuja la nieve hacia el centro de la intersección, respectivamente. (Véase el problema del cartero rural dirigido con penalizaciones por giro, a menudo denominado DRPP-TP más adelante).

Problema del cartero chino k ( k -CPP)

El problema del cartero chino k se puede plantear de la siguiente manera: "dado un grafo conexo ponderado por aristas G y enteros p y k , decidir si existen al menos k caminos cerrados tales que cada arista de G esté contenida en al menos uno de ellos y el peso total de las aristas en los caminos sea como máximo p ?". El proceso de obtención de la solución al problema del cartero chino k es NP-completo. Gutin, Muciaccia y Yeo demostraron en 2013 que el problema del cartero chino k es tratable con parámetros fijos. [ 19 ] Los autores demuestran que el problema del cartero chino k admite un núcleo conO(k2registro⁡(k)){\displaystyle O(k^{2}\log(k))}vértices y la versión dirigida del k -CPP es NP-completa.

El problema del cartero rural (PCR) 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 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, denominado 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 del viajante asimétrico (ATSP).

Heurísticas y algoritmos

La mayoría de los algoritmos requieren un preprocesamiento del grafo, que simplifica el grafo inicial eliminando todas las aristas que no forman parte del camino más corto entre dos aristas requeridas. Otra simplificación que aporta 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 mismo.

Una vez realizado el preprocesamiento, el problema puede generalizarse a un problema de envolvente convexa , donde los bordes son los puntos de la envolvente. El problema de la envolvente convexa puede resolverse mediante programación lineal o mediante algoritmos de envolvente convexa, pero el proceso de hallar la envolvente convexa es un problema exponencial.

Los métodos para resolver el URPP después del preprocesamiento consisten en el algoritmo de planos 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 arcos

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

Véase también

Referencias

  1. 1 2 3 4 5 Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2018-01-02). "Un diseño de ruta equilibrado para el problema del cartero rural con múltiples depósitos min-max (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. 1 2 3 4 Omer, Masoud (2007). "Enrutamiento eficiente de vehículos quitanieves" .
  3. 1 2 3 4 Dussault, Benjamin; Golden, Bruce; Wasil, Edward (octubre de 2014). "El problema del arado cuesta abajo con múltiples arados" . Journal of the Operational Research Society . 65 (10): 1465– 1474. doi : 10.1057/jors.2013.83 . ISSN 0160-5682 . S2CID 36977043 .  
  4. 1 2 3 4 Eiselt, HA; Gendreau, Michel; Laporte, Gilbert (abril de 1995). "Problemas de enrutamiento de arcos, parte I: El problema del cartero chino" . Operations Research . 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), "Problemas de enrutamiento de vehículos minmax: Aplicación al transporte escolar en la provincia de Burgos" , en Voß, Stefan; Daduna, Joachim R. (eds.), Planificación asistida por ordenador del transporte público , 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 el enrutamiento y la programación de vehículos" . Networks . 11 (2): 97– 108. doi : 10.1002/net.3230110204 .
  7. ↑ Bodin, Lawrence D.; Sexton, Thomas R. (febrero de 1983). El problema del servicio de transporte a demanda con múltiples vehículos (Informe técnico). Escuela Naval de Posgrado. hdl : 10945/63226 . NPS55-83-002.
  8. 1 2 3 4 Rabbani, Masoud; Alamdar, Safoura Famil; Farrokhi-Asl, Hamed (2016-02-01). "Problema del cartero rural con viento y capacidad limitada 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. 1 2 3 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. 1 2 3 4 Benavent, Enrique; Corberán, Ángel; Sanchis, José M. (julio de 2010). "Una metaheurística para el problema min–max del cartero rural ventoso 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. 1 2 H. A., Eiselt; Michel, Gendreau (1995). "Problemas de enrutamiento de arcos, parte II: El problema del cartero rural" . Investigación operativa . 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", Matemáticas Aplicadas Discretas , 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. 1 2 3 Corberán, Angel; Oswald, Marcus; 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 . hdl : 10251/150344 . ISSN 0025-5610 . S2CID 12808962 .  
  17. ↑ Yang, Xin-She (2010). "Optimización de ingeniería mediante búsqueda del cuco". Revista internacional de modelado matemático y optimización numérica . 1 (4) 35430: 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 " . Theoretical Computer Science . 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. 1 2 3 Edmonds, Jack; Johnson, Ellis L. (1973). "Matching, Euler tours and the Chinese postman" . Mathematical Programming . 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" . Journal of the 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" . SIAM Journal on Discrete Mathematics . 12 (4): 425– 433. doi : 10.1137/s0895480197331454 . ISSN 0895-4801 . 
  26. 1 2 Gutin, Gregory; Jones, Mark; Sheng, Bin (2014), "Complejidad parametrizada del problema del cartero chino de k arcos" , Algorithms - ESA 2014 , Berlín, Heidelberg: Springer Berlin Heidelberg, pp. 530–541 , arXiv : 1403.1512 , doi : 10.1007/978-3-662-44777-2_44 , ISBN  978-3-662-44776-5, S2CID 3472348 , consultado el 09-05-2022 
  27. ↑ Fernandes, Cristina G.; Lee, Orlando; Wakabayashi, Yoshiko (enero de 2009). "Problemas de cobertura de ciclo mínimo y 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. 1 2 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" . Mathematical Programming . 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). "Recorrido del cartero en un grafo con relación de precedencia en arcos" . Networks . 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 ciclos mínima de un grafo" . SIAM Journal on Computing . 26 (3): 675– 677. doi : 10.1137/s0097539794267255 . ISSN 0097-5397 . 
  34. ↑ Corberán, Ángel (2015).Enrutamiento de arcos: problemas, métodos y aplicacionesISBN​ 978-1-61197-366-2.
  35. 1 2 Frederickson, Greg N.; Hecht, Matthew S.; Kim, Chul E. (mayo de 1978). "Algoritmos de aproximación para algunos problemas de enrutamiento" . SIAM Journal on Computing . 7 (2): 178– 193. doi : 10.1137/0207017 . ISSN 0097-5397 . S2CID 7562375 .  
  36. ↑ Eiselt, H (mayo de 1995). "Problemas de enrutamiento de arcos, parte II: El problema del cartero rural" . pág. 399. ProQuest 219174102 .  
  37. ↑ Guan, Meigu (1962). "Programación gráfica usando puntos pares o impares". Matemáticas chinas .
  38. ↑ Dussault, Benjamin; Golden, Bruce; Groër, Chris; Wasil, Edward (1 de abril de 2013). "Arando 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. 1 2 Dussault, Benjamin; Golden, Bruce; Wasil, Edward (2014-10-01). "El problema del arado cuesta abajo con múltiples arados" . Journal of the Operational Research Society . 65 (10): 1465– 1474. doi : 10.1057/jors.2013.83 . ISSN 1476-9360 . S2CID 36977043 .  
  40. ↑ Dussualt, Benjamin (2012). "Modelado y resolución de problemas de enrutamiento de arcos en barrido de calles y arado de nieve" . ProQuest .
  41. ↑ Ghiani, Gianpaolo; Improta, Gennaro (2000-04-01). "Una transformación eficiente del problema generalizado de enrutamiento de vehículos" . European Journal of Operational Research . 122 (1): 11– 17. doi : 10.1016/S0377-2217(99)00073-9 . ISSN 0377-2217 . 
Lecturas relacionadas
6 articulos
Recogida de residuosRecogida de residuosLa recolección de residuos es parte del proceso de gestión de residuos . Es el traslado de residuos sólidos desde el punto de uso y eliminación has...Icono del globo.Autobús escolarUn autobús escolar es cualquier tipo de autobús que pertenece, es arrendado, contratado u operado por una escuela o distrito escolar . Se utiliza h...DeshieloDeshieloEl deshielo es el proceso de eliminar la nieve , el hielo o la escarcha de una superficie. El antihielo es la aplicación de productos químicos que ...Remoción de nieveRemoción de nieveLa remoción o limpieza de nieve es la tarea de retirar la nieve después de una nevada para que viajar sea más fácil y seguro. Esto lo llevan a cabo...Vehículo de servicio de inviernoVehículo de servicio de inviernoUn vehículo de servicio de invierno ( WSV ), o vehículo de remoción de nieve , es un vehículo especialmente diseñado o adaptado para limpiar las ví...SalSalSal de roca (halita) En el uso común, la sal es un mineral compuesto principalmente de cloruro de sodio (NaCl). Cuando se usa en alimentos, especia...