Ingeniero

Se requiere encontrar un plan óptimo de rutas para atender con una flota de vehículos al conjunto de viajes señalados en la tabla a continuación. Cada viaje tiene una posición de salida (el sitiodonde el vehículo recoge al cliente), una posición de llegada (el sitio hacia donde el cliente debe ser transportado) y una ventana de tiempo para el inicio del viaje. Las posiciones espaciales estándadas por coordenadas cartesianas en el plano.

|Viaje |Posición de salida |Posición de llegada |Ventanas de tiempo |
|A |(1,1) |(2,3)|[07;09] |
|B |(0,2) |(1,4) |[08;09] |
|C |(1,0)|(0,3) |[07;08] |
|D |(3,2) |(5,0) |[14;15] |
|E |(1,2)|(5,6) |[12;13] |
|F |(6,6) |(6,3) |[17;21] |
|G|(5,4) |(0,4) |[21;23] |

Deben tomarse en cuenta las siguientes restricciones:

a) Cada vehículo puede atender un sóloviaje a la vez.
b) Los vehículos se desplazan únicamente en los sentidos horizontal y vertical.
c) Esto significa que al moverse de la posición [pic] a la posición [pic], un vehículo recorre ladistancia

d) [pic]

(Este tipo de distancia suele conocerse como métrica de Manhattan, debido a la geometría regular que presentan las calles en ese barrio de Nueva York)


e) Todos losvehículos se mueven con velocidad unitaria, recorren una unidad de distancia por cada unidad de tiempo.
f) El depósito de los vehículos está en la posición (0, 0). Todas las rutas deben empezar y...