Una de las tareas de optimización más comunes es el enrutamiento de vehículos, en el que el objetivo es encontrar las mejores rutas para una flota de vehículos que visita un conjunto de ubicaciones. Por lo general, "mejor" se refiere a las rutas con la menor distancia o costo total. Estos son algunos ejemplos de problemas relacionados con el enrutamiento:
- Una empresa de entrega de paquetes quiere asignar rutas para que los conductores realicen las entregas.
- Una empresa de TV por cable quiere asignar rutas para que los técnicos realicen llamadas de servicio residencial.
- Una empresa de transporte privado con conductor desea asignar rutas para que los conductores recojan y dejen pasajeros.
El problema de enrutamiento más famoso es el Problema del vendedor que viaja (TSP): encuentra la ruta más corta para un vendedor que necesita visitar clientes en diferentes ubicaciones y volver al punto de partida. Una TSP se puede representar con un gráfico, en el que los nodos corresponden a las ubicaciones, y los bordes (o arcos) denotan el viaje directo entre ubicaciones. Por ejemplo, el siguiente gráfico muestra un TSP con solo cuatro ubicaciones, etiquetadas como A, B, C y D. La distancia entre dos ubicaciones cualesquiera se obtiene mediante el número que se encuentra junto al borde que las une.
Cuando calculas las distancias de todas las rutas posibles, puedes ver que la ruta más corta es ACDBA, cuya distancia total es 35 + 30 + 15 + 10 = 90.
El problema se vuelve más difícil cuando hay más ubicaciones. En el ejemplo anterior, solo hay seis rutas. Pero si hay diez ubicaciones (sin contar el punto de partida), la cantidad de rutas es 362,880. Para 20 ubicaciones, el número salta a 2432902008176640000. Se garantiza que una búsqueda exhaustiva de todas las rutas posibles encontrará la más corta, pero es intratable desde el punto de vista informático para todos los conjuntos de ubicaciones, excepto los pequeños. Para problemas más grandes, se necesitan técnicas de optimización para buscar de forma inteligente el espacio de la solución y encontrar una solución óptima (o casi óptima).
Una versión más general del TSP es el problema de ruta del vehículo (VRP), en el que hay varios vehículos. En la mayoría de los casos, los VRP tienen restricciones: por ejemplo, los vehículos pueden tener capacidades para el peso o el volumen máximos de artículos que pueden llevar, o es posible que los conductores deban visitar ubicaciones durante períodos específicos solicitados por los clientes.
Las herramientas O pueden resolver muchos tipos de VRP, incluidos los siguientes:
- Problema del vendedor de viajes: Es el problema clásico de las rutas en el que solo hay un vehículo.
- Problema de ruta del vehículo, una generalización del TSP con varios vehículos
- VRP con restricciones de capacidad, en el que los vehículos tienen las capacidades máximas para los elementos que pueden transportar.
- VRP con períodos, en el que los vehículos deben visitar las ubicaciones en intervalos de tiempo especificados.
- VRP con restricciones de recursos, como espacio o personal para cargar y descargar vehículos en el depósito (el punto de partida de las rutas)
- VRP con visitas descartadas, en el que no es necesario que los vehículos visiten todas las ubicaciones, pero deben pagar una penalización por cada visita que se descarta.
Limitaciones para resolver problemas relacionados con las rutas de los vehículos
Los problemas relacionados con las rutas de vehículos son intrínsecamente intratables: el tiempo que se tarda en resolverlos aumenta de manera exponencial con el tamaño del problema. En el caso de problemas lo suficientemente grandes, podría tardar años en encontrar la solución óptima con las Herramientas de OR (o cualquier otro software de enrutamiento). Como resultado, las herramientas OR a veces muestran soluciones que son buenas, pero no óptimas. Para encontrar una mejor solución, cambia las opciones de búsqueda de la herramienta. Consulta Cambia la estrategia de búsqueda para ver un ejemplo.