Ruteo Vehicular

EII 450 Investigación Operacional II 1º semestre 2012
Capítulo III: Problemas de Ruteo Vehicular

Problemas de Ruteo Vehicular
Fuentes: Plantas, Proveedores, Puertos, etc. Plantas, puntos de almacenamiento. Almacenes de campo, puntos de almacenamiento. Clientes, Centros de Demanda.

Suminist ro

Demanda Suminist ro

Costos de Inventario, Almacenamiento y Operaciones Costos deProducción y Compras Costos de Transporte Costos de Inventario, Almacenamiento y Operaciones Costos de Transporte

•Estos problemas aparecen en diversas etapas del sistema de distribución o la CA

2

Problemas de Ruteo Vehicular

CD 2 Proveedor 2

CD 1

Planta

Proveedor 1

3

Problemas de Ruteo Vehicular

Localización de Instalaciones

Nivel Estratégico

Diseño de Flota, Zonas dereparto y Agrupación de Clientes

Planificación de Inventarios

Nivel Táctico

Ruteo Vehicular

Decisiones de Ordenamiento

Nivel Operativo

4

Problemas de Ruteo Vehicular • Los modelos o problemas de ruteo están enfocados principalmente en diseñar y operar sistemas logísticos de distribución, reparto y recolección • Algunas decisiones relevantes:
– Tamaño de flota y capacidadesde vehículos – Zonificación y asignación de clientes a zonas/vehículos – Secuenciación de visitas, re-asignación y carga de camiones

• Es posible encontrar otras problemas reales donde aplicar dichos modelos/metodologías
– Diseño de tarjetas electrónicas – Instalación de bodegas en proyectos de construcción – Operación naviera/aérea – Secuenciamiento de Tareas
5

Un primer problema ELPROBLEMA DEL VENDEDOR VIAJERO • Tenemos n ciudades o clientes • Un vendedor viajero debe visitarlas todas, comenzando en la ciudad 1 (para este problema, finalmente es irrelevante el inicio ¿por qué?). • La distancia en entre la ciudad i y la j es dij. • El vendedor debe buscar una secuencia de visitas de modo de no pasar dos veces por una misma ciudad (entra y sale una sola vez a cada ciudad) • Ladistancia total recorrida debe ser la mínima posible...
6

Un primer problema EL PROBLEMA DEL VENDEDOR VIAJERO
9 8 6 8 5 5 6,2 11 8,7 8,2 4 13 5,2 7,5 7 4 9 12 9 6 6,8 12 10 9 6 10 8 9 14 14 10 6,5 6 8 7 11 13 7 5 11 16 12 11,2 12,2 19 13 10 9 17 13,5 10,5 20

1 5

2

8,5 7,5

3

10

18 11

7

15

•¿Cuántas soluciones existen? •¿Importa realmente no pasar más de una vez? •¿Esesto siempre factible?

7

Un primer problema EL PROBLEMA DEL VENDEDOR VIAJERO Variable de decisión Yij : F.O
Restricciones: Desde cada ciudad se debe salir una vez A cada ciudad se debe llegar una vez Integralidad

1 si se utiliza el arco (i,j), 0 si no.

Min

∑∑d ⋅Y
i=1 j=1 ij

N

N

ij

s. a :

∑Y
j =1

N

ij

=1

∀i = 1,..., N

∑Y
j =1

N

ji

=1

∀i =1,..., N
∀i, j = 1,..., N
8

Yij ∈ {0,1}

Un primer problema EL PROBLEMA DEL VENDEDOR VIAJERO • ¿Son suficientes las restricciones presentadas? • Esto es una solución factible para dichas restricciones
j l

i

k

n

m

• Ejemplo: • ¿Es realmente útil esta solución? • ¿Qué debemos hacer a la formulación del PVV? • Veremos dos alternativas para evitar este problema
9

Unprimer problema EL PROBLEMA DEL VENDEDOR VIAJERO
2 5 2 5

1

3

7 2 5 6

1

3

7

6 1 3 7 2 4

4

2 5 6 4 1 3 7 1

5

3

7

6 4 4

6

• Debemos imponer que para conjunto de menos de n (2 a n-1) ciudades no se formen circuitos.

i , j∈S ,( i , j )∈ A

∑

X ij ≤ S − 1

∀S ⊆ N
10

Un primer problema EL PROBLEMA DEL VENDEDOR VIAJERO Ejemplo (arcosbi-direccionales)
2

i , j∈S ,( i , j )∈ A

∑

5

X ij ≤ S − 1 ∀S ⊆ N

1

3

7

Los casos de la figura…

6 4

( X 56 + X 65 ) + ( X 57 + X 75 ) + ( X 67 + X 76 ) ≤ 2

( X 12 + X 21 ) + ( X 23 + X 32 ) + ( X 34 + X 43 ) + ( X 14 + X 41 ) + ( X 31 + X 13 ) ≤ 3
•¿Cuántos subconjuntos de Nodos S existen?
– – – – – De De De De De a a a a a 3 4 5 6 7 nodos nodos nodos nodos nodos : 1-2-3,...