Untitled

Ruteo de vehiculos

Problemas de Ruteo de Vehículos es el nombre genérico dado a una gran familia de problemas referentes a la distribución de mercancía o personal, búsqueda de información o prestación de servicios, a un conjunto de clientes mediante una flota de vehículos.

Los vehículos realizan sus movimientos a través de una red de rutas partiendo de puntos fijos, llamados depósitos. Cada tramo de esta red, que puede ser en una dirección o en ambas, tiene asociado un costo o tiempo de viaje que puede depender de muchos factores, como por ejemplo del tipo de vehículo o del periodo durante el cual el tramo es recorrido.

Diferentes variantes del problema, que incluyen restricciones adicionales y la incorporación de múltiples variables, son propuestas como una aproximación generalizada a problemas reales de enrutamiento de vehículos, así como también se han propuesto diferentes métodos para encontrar soluciones a estos problemas.

consiste en

se tiene

Metodos

El método de valoración de ahorros de Clarke-Wright

El método de valoración de ahorros de Clarke-Wright ha permanecido a través de los años por ser lo suficientemente flexible como para manejar un amplio rango de restricciones prácticas, siendo relativamente rápido de calcular en una computadora para problemas con número moderado de paradas y capaz de generar soluciones que están cerca de lo óptimo. El método puede manejar muchas restricciones prácticas, principalmente porque el es capaz de formar rutas y ordenar paradas en las rutas simultáneamente.

El objetivo del método de ahorros es minimizar la distancia total viajada por todos los vehículos y minimizar indirectamente el número de vehículos necesarios para atender todas las paradas

MÉTODO DE APROXIMACIÓN DE VOGEL

El método de aproximación de Vogel es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo produce mejores resultados iniciales que los mismos.

Algoritmo

El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la culminación del método.

PASO 1

Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas.

PASO 2

Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).

PASO 3

De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0).

PASO 4: DE CICLO Y EXCEPCIONES

- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.

- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de costos mínimos, detenerse.

- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine las variables básicas cero por el método del costo mínimo, detenerse.

- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y las demandas se hayan agotado.

Método del costo minimo

El método del costo mínimo o de los mínimos costos es un algoritmo desarrollado con el objetivo de resolver problemas de transporte o distribución, arrojando mejores resultados que métodos como el de la esquina noroeste, dado que se enfoca en las rutas que presentan menores costos.

El diagrama de flujo de este algoritmo es mucho más sencillo que los anteriores dado que se trata simplemente de la asignación de la mayor cantidad de unidades posibles (sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa de toda la matriz hasta finalizar el método.

Algoritmo

PASO 1:

De la matriz se elige la ruta (celda) menos costosa (en caso de un empate, este se rompe arbitrariamente) y se le asigna la mayor cantidad de unidades posible, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la cantidad asignada a la celda.

PASO 2:

En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del "Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso.

PASO 3:

Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es el caso se ha llegado al final el método, "detenerse".

La segunda es que quede más de un renglón o columna, si este es el caso iniciar nuevamente el "Paso 1".

Método de la esquina noroeste

El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas de transporte o distribución mediante la consecución de una solución básica inicial que satisfaga todas las restricciones existentes sin que esto implique que se alcance el costo óptimo total.

Este método tiene como ventaja frente a sus similares la rapidez de su ejecución, y es utilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muy elevado.

Su nombre se debe al génesis del algoritmo, el cual inicia en la ruta, celda o esquina Noroeste. Es común encontrar gran variedad de métodos que se basen en la misma metodología de la esquina Noroeste, dado que podemos encontrar de igual manera el método e la esquina Noreste, Sureste o Suroeste

Algoritmo

PASO 1:

En la celda seleccionada como esquina Noroeste se debe asignar la máxima cantidad de unidades posibles, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la cantidad asignada a la celda.

PASO 2:

En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del "Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso.

PASO 3:

Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es el caso se ha llegado al final el método, "detenerse".

La segunda es que quede más de un renglón o columna, si este es el caso iniciar nuevamente el "Paso 1".