El problema del transporte con ventanas de tiempo, VRPTW (por sus siglas en inglés, Vehicle Routing Problem with Time Windows), es un modelo que se aplica a cadena de suministros y transporte escolar.
El problema se puede plantear como sigue:
Un vendedor (viajero por cierto) necesita visitar n puntos de la ciudad, sin importar el orden en que lo haga, cada uno exactamente una vez y en el menor tiempo posible.
En el contexto de lo que se verá más adelante, podríamos decir que el vendedor viajero es asociable a un operador de un servicio puerta a puerta que debe atender a la demanda ubicada en la posición de cada uno de los n nodos que debe visitar.
A continuación se presenta el modelo de programación lineal entera que representa al problema:
La función objetivo presentada en (1), representa el costo total, el cual se puede interpretar como el tiempo de viaje o distancia recorrida total. Se requiere encontrar la mínima distancia de recorrido total utilizando el menor número de vehículos. La variable xijk, toma valor de uno cuando el vehículo k atiende la ruta que va del cliente i al cliente j. El depósito se representa como i = 0 ó i = 1 + n. Las restricciones que se deben cumplir se presentan de (2) a (11).
Restricciones en (2), restringen la asignación de cada cliente a una sola ruta vehicular, esto es, el cliente es atendido por un sólo vehículo.
Restricciones de (3) a (5), dan las características de la ruta a seguir por cada vehículo k.
Restricciones en (3), definen el número de clientes j que son directamente alcanzables desde el depósito 0 utilizando el vehículo k, esto es, para cada vehículo k, sólo un cliente j se puede alcanzar partiendo del deposito.
Restricciones en (4), indica para cada unidad vehicular que, la diferencia del número de clientes i desde los cuales el cliente j es directamente alcanzable, con respecto del número de clientes i que son directamente alcanzables desde el cliente j, es cero, esto es, el número de vehículos que llegan a un cliente es el mismo número de vehículos que sale.
Restricciones en (5), indica para cada unidad vehicular que, el número de clientes i desde los cuales el deposito n + 1 es directamente alcanzable, es sólo uno, esto es, cada ruta vehicular tiene un sólo cliente que conecta al depósito.
Restricciones (6) a (8) y (9), garantizan la factibilidad de la secuencia con respecto a condiciones de tiempo y aspectos de capacidad respectivamente.
Restricciones en (6), indica para cada unidad vehicular y cada arco entre par de clientes, que la suma del tiempo inicial del servicio wik para el cliente i más su tiempo de servicio dado al cliente i más su tiempo de recorrido desde el cliente i al cliente j, menos el tiempo inicial del servicio wik es menor o igual que (1 - xijk ) = Mij, esto es, no se puede iniciar un servicio en j si el cliente i no ha sido atendido y el vehículo no ha llegado al cliente j. Aquí M es una constante muy grande.
Restricciones en (7), indican para cada unidad vehicular y cada cliente i, que el tiempo inicial del servicio wik debe iniciar dentro de la ventana de tiempo [ai, bi], donde ai es el tiempo más temprano posible que puede iniciar el servicio en el cliente i y bi es el tiempo más tarde posible que puede iniciar el servicio en el cliente i.
Restricciones en (8), indican para cada unidad vehicular y en el depósito 0, que el tiempo inicial del servicio wik debe iniciar dentro de la ventana de tiempo [E, L], esto es, el vehículo k, debe tener una salida posible más temprana desde el depósito y una llegada posible más tarde al depósito.
Restricciones en (9), indican que para todo vehículo k, la suma de las demandas de todos los clientes atendidos no debe exceder la capacidad del vehículo.
Restricciones (10), son restricciones de no negatividad de las variables x.
Restricciones (11), son restricciones que definen al modelo lineal como un modelo lineal entero binario.
IMPLEMENTACION DE UN PROBLEMA DE RUTEO VEHICULAR CON VENTANA DE TIEMPO
A LA EMPRESA “FERNADES AGRO S.A”.
PLANTEAMIENTO DEL PROBLEMA A SOLUCIONAR:
Según el ministerio de economía La
Libertad estimó que este año 2015 en la región habrá una producción de más de
seis millones de toneladas de caña de azúcar, siendo en gran parte de este tonelaje
provenientes del valle Chicama. Si bien se sabe
en el valle Chicama está la
presencia de empresas azucareras como Cartavio, Casa Grande, Pucala que son las
que mayor producción aportan, también existe la presencia de pequeños
productores , agricultores que poseen algún terreno y producen caña de azúcar.
Como caso de estudio tomaremos
como referente a la Empresa FERNADES AGRO S.A, una pequeña empresa ubicada en
la localidad de Chiclin y que brinda
servicios de proveedor de recursos como abono, pesticidas, etc para los
agricultores dentro de su localidad.
Actualmente en la empresa se
maneja dos tipos de transporte, el primero es el primario que va desde el
centro de distribuciones en Lima, el cual se encarga de transportar todos los
productos al establecimiento de la empresa
y el transporte secundario que es nuestro motivo de estudio, va desde su
establecimiento hasta los clientes
finales que son los pequeños agricultores.
La sucursal donde nos enfocaremos
es la que está situada en la localidad
de Chiclin, donde trabaja con un solo camión propio de la empresa pero en la
actualidad realizan outsoutcing y cuentan con un camión de 5 toneladas que se encargan la entrega del producto final
a los clientes finales.
Para plantear este tipo de problemas
necesitamos “n” datos de la empresa y
trabajaremos con 4 destinos en los cuales se realizan la distribución de los
productos.
OBJETIVOS:
- Disminuir los tiempos de entrega de los
productos por parte de la empresa hacia los consumidores.
- Maximizar el nivel de servicio a los clientes,
optimizando la utilización de los recursos.
- Buscar la aplicación del objetivo general de la
logística la cual consiste en maximización de nivel del servicio, minimización
de costos.
- Elaboración de rutas de acuerdo al orden de los
pedidos por parte de los consumidores.
CONSIDERACIONES:
·
En el problema que plantearemos hemos
considerado las siguientes restricciones:
- Cada vehículo tiene una capacidad limitada (para
efectos de simplificación se concibe una flota de vehículos toda con igual
capacidad).
- Cada cliente debe ser visitado entro de una
determinada ventana de tiempo.
- El vehículo tiene la alternativa de llegar al
punto de entrega antes del inicio de la ventana de tiempo y esperar a que se
inicie.
RED CON LOS DATOS DEL PROBLEMA A SOLUCIONAR:
COORDENADAS DE LOS NODOS OBTENIDAS CON GOOGLE MAPS:
POSICIONAMIENTO DE LOS NODOS OBTENIDOS EN GOOGLE MAPS:
GRÁFICO GENERADO POR GLPK:
RESULTADOS OBTENIDOS
POR GLPK:
Como vemos en la red, los vehículos tendrán que realizar un
recorrido relativamente corto, optimizando de esta manera la entrega de
encomiendas.
IMPLEMENTACIÓN DEL MODELO EN GLPK
# Archivo de salida
param filename, symbolic := "vrptw.svg";
set N; # conjunto de nodos incluido el deposito
set K; # Conjunto de vehiculos
param xcoord {i in N} ;
param ycoord {j in N};
param VD:= 30; # Velocidad por defecto (MPH)
param f:= 90; # Flete em dolars
param dist{i in N, j in N:i != j} := sqrt((xcoord[i] - xcoord[j])^2 + (ycoord[i] - ycoord[j])^2); # Distancia
param c{i in N, j in N: i != j} := f * dist[i,j]/1000; # Costo de transporte en miles de soles
param conv{i in N, j in N: i !=j} := dist[i,j]*0.0003048; # Convertir distancia de feet em mile: mt = feet*0.0003048.
param t{i in N, j in N: i != j}:= (conv[i,j]*3600)/VD; # Tiempo de viaje en segundos.
param d{i in N}; # demanda de los clientes i = 1, 2, 3, 4, 5, 6.
param q{k in K}; # capacidad de los vehiculos k = v1, v2, v3.
#param t{i in N, j in N}; # tiempo entre los clientes
param a{i in N}; # Limite de tiempo inferior.
param b{i in N}; # Limite de tiempo superior.
var X{i in N, j in N, k in K}, binary; # Condiciones de acceso a una ruta, 1 - si puede hacer uso de la ruta y 0- si no puede hacer uso de la ruta.
var Y{i in N, k in K} integer ; # vehiculo k comienza el servicio al cliente.
minimize Z: sum {i in N, j in N, k in K: i != j and (i != 0 and j != 4) and j > 0 } c[i,j]*X[i,j,k];
s.t. R_1 {i in N: (i!= 0 and i != 4)}: sum{j in N, k in K: i !=j }X[i,j,k] = 1; # Un Cliente puede ser visitado unicamente por un vehiculo
s.t. R_2 {k in K}: sum{i in N, j in N: (i != 0 and i != 4 and i != j) }d[i]*X[i,j,k] < = q[k]; # Demanda no excede la capacidad del vehiculo
s.t. R_3 {k in K}: sum {i in N, j in N: i == 0 and i !=j } X[i,j,k] = 1; # Cada vehiculo deja el deposito
s.t. R_4 {h in N, k in K: (h != 0 and h != 4)}: sum{i in N: i != h} X[i,h,k] - sum{j in N: h != j}X[h,j,k] = 0; # Conservacion de flujo
s.t. R_5 {k in K}: sum{i in N, j in N: j == 4 and i!= j and i > =0 }X[i,j,k] = 1;
s.t. R_6{i in N, j in N, k in K: i != 0 and i != 4 and i != j }: Y[i,k] + t[i,j] - 10000*(1 - X[i,j,k]) < = Y[j,k]; # Llegar al cliente j.
s.t. R_7{i in N, k in K: i != 0 and i != 4}: Y[i,k] > = a[i]; # ventana de tiempo
s.t. R_8{i in N, k in K: i != 0 and i != 4 }: Y[i,k] < = b[i]; # ventana de tiempo
solve;
printf " < ?xml version=""1.0"" standalone=""no""? > \n" > filename;
printf " < !DOCTYPE svg PUBLIC ""-//W3C//DTD SVG 1.1//EN"" \n" > > filename;
printf """http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"" > \n" > > filename;
printf " < svg width=""1000\%"" height=""1000\%"" version=""1.0"" \n" > > filename;
printf "xmlns=""http://www.w3.org/2000/svg"" > \n" > > filename;
for{i in N}
{
printf " < text x=""%f"" y=""%f"" fill=""black"" > ""%s"" < /text > ",xcoord[i]*3, ycoord[i]*3,i > > filename;
printf " < circle cx=""%f"" cy=""%f"" r=""%f"" / > \n", xcoord[i]*3, ycoord[i]*3 ,3.5 > > filename;
}
# draw solid black lines for integer connections
for {i in N,j in N, k in K : i != j and X[i,j,k] == 1}
printf " < line x1=""%f"" y1=""%f"" x2=""%f"" y2=""%f""" &
" style=""stroke:blue;stroke-width:1""/ > \n",
xcoord[i] * 3, ycoord[i] * 3, xcoord[j] * 3, ycoord[j] * 3 > > filename;
printf " < /svg > \n" > > filename;
printf "\n" ;
printf " Costo y asignacion de vehiculos: %s\n",
sum {i in N, j in N, k in K: i != j and (i != 0 and j != 4) and j > 0} c[i,j]*X[i,j,k];
printf(" Arco Vehiculo \n");
printf "\n" ;
printf {i in N, j in N, k in K: X[i,j,k] } " %1s %2s %10s \n", i, j, k;
data;
set N := 0 1 2 3 4 ;
set K := 'v1';
param: xcoord ycoord :=
0 10 15
1 82 76
2 96 44
3 50 5
4 49 8;
param d :=
0 0
1 10
2 30
3 10
4 10;
param q :=
'v1' 200;
param a :=
0 0400
1 0700
2 0000
3 0000
4 0700;
param b :=
0 1500
1 2400
2 2400
3 0700
4 2400;
end;
