Problema de enrutamiento de quitanieves

El problema de enrutamiento de quitanieves es una aplicación de la estructura de los problemas de enrutamiento de arcos (ARP, por sus siglas en inglés) y los problemas de enrutamiento de vehículos (VRP, por sus siglas en inglés) a la remoción de nieve , que considera las carreteras como aristas de un grafo.

El problema es un problema de enrutamiento simple cuando no se especifican los tiempos de llegada. ^{[ 1 ]} Los problemas de quitanieves consideran restricciones como el costo de quitar la nieve cuesta abajo en comparación con quitarla cuesta arriba. ^{[ 2 ]} El problema del cartero chino mixto es aplicable a rutas de nieve donde las aristas dirigidas representan calles de un solo sentido y las aristas no dirigidas representan calles de doble sentido. ^{[ 3 ]}

El enrutamiento y la programación de vehículos quitanieves es un tema importante para los planificadores de transporte y los investigadores de operaciones ^{[ 4 ].} Este conjunto de problemas forma parte de un campo más amplio de problemas denominados Problemas de Enrutamiento de Arcos , que a su vez es un subconjunto de un campo más amplio llamado Problemas de Enrutamiento de Vehículos . El enrutamiento y la programación de vehículos incluyen la remoción de nieve, la entrega de correo por parte de un cartero, la lectura de medidores para recaudar dinero para la ciudad, el enrutamiento de autobuses escolares, la recolección de basura y desechos, y el mantenimiento de calles. ^{[ 1 ]}

El problema de la remoción de nieve consiste en despejar un conjunto de carreteras en el menor tiempo posible. La planificación de rutas para vehículos de nieve implica salarios elevados para los conductores, altos costos de combustible y altos costos de compra y mantenimiento de dichos vehículos. En el sector público, el objetivo suele ser menos minimizar costos y más maximizar la seguridad y la comodidad, por ejemplo, reduciendo el número de giros a la izquierda en carreteras principales que resultan peligrosos para los vehículos.