El Problema del Ruteo Vehicular con Ventanas de Tiempo

Share:



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 [aibi], 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;

No hay comentarios