Pesquisa Operacional II

Aula 36

Módulo 4.7 – Roteamento de Veículos:Modelo by A.A.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

0

Roteamento de Veículos

1

2

3

4

5

6

7

8

9

10

11

12

13

14

0

2

1

3

4

3

4

2

6

3

1

3

3

3

1

10

Roteamento de Veículos

1

2

3

4

5

6

7

8

9

10

11

12

13

14

0

2

1

3

4

3

4

2

6

3

1

3

3

3

1

10

10

10

10

Roteamento de Veículos

1

2

3

4

5

6

7

8

9

10

11

12

13

14

0

C = {1, ..., n}

Roteamento de Veículos

1

2

3

4

5

6

7

8

9

10

11

12

13

14

0

N = C∪{0, n+1}

Roteamento de Veículos

1

2

3

4

5

6

7

8

9

10

11

12

13

14

0

E = {(i,j): i, j∈N, i≠j,

i≠n+1, j≠0}

Roteamento de Veículos

1

2

3

4

5

6

7

8

9

10

11

12

13

14

n+1

E = {(i,j): i, j∈N, i≠j,

i≠n+1, j≠0}

Roteamento de Veículos

1

2

3

4

5

6

7

8

9

10

11

12

13

14

n+1

E = {(i,j): i, j∈N, i≠j, i ≠n+1, j≠0}

Roteamento de Veículos

i

j

x_ij

Variáveis de Decisão

X_ijk = 1 se o veículo k vai do nó i para o nó j.

x_{i jk}

Origem

(Cidade i)

Destino

(Cidade j)

Veículo k

Roteamento de Veículos

1

5

2

3

x₁₃₁

x₁₂₁

Variáveis de Decisão

x₁₅₁

4

X_ijk = 1 se o veículo k vai do nó i para o nó j.

x₁₄₁

x₄₁₁

x₃₁₁

x₂₁₁

x₅₁₁

Roteamento de Veículos

1

5

2

3

x₁₃₁

x₁₂₁

Dado o veículo 1 na cidade 1, qual será a próxima cidade?

x₁₅₁

4

x₁₄₁

x₁₂₁ + x₁₃₁ + x₁₄₁ + x₁₅₁

Veículo 1

Roteamento de Veículos

1

5

2

3

x₁₃₂

x₁₂₂

Dado o veículo 1 na cidade 1, qual será a próxima cidade?

x₁₅₂

4

x₁₄₂

x₁₂₂ + x₁₃₂ + x₁₄₂ + x₁₅₂

Veículo 2

Roteamento de Veículos

1

5

2

3

x₁₃₃

x₁₂₃

Dado o veículo 1 na cidade 1, qual será a próxima cidade?

x₁₅₃

4

x₁₄₃

x₁₂₃ + x₁₃₃ + x₁₄₃ + x₁₅₃

Veículo 3

Roteamento de Veículos

1

5

2

3

x₁₃₄

x₁₂₄

Dado o veículo 1 na cidade 1, qual será a próxima cidade?

x₁₅₄

4

x₁₄₄

x₁₂₄ + x₁₃₄ + x₁₄₄ + x₁₅₄= 1

Veículo 4

Roteamento de Veículos

i

5

2

3

x_ijk

4

Dado o veículo k na cidade i, qual será a próxima cidade j?

Roteamento de Veículos

MAS...

1

4

2

3

5

6

7

As restrições anteriores permitem a existência de sub-rotas !!

1

4

2

3

5

6

7

Roteamento de Veículos

1

5

2

3

x₂₁₁

Eliminação de sub-rotas com dois nós

4

x₁₂₁

x₁₂₁ + x₂₁₁ ≤ 1

Roteamento de Veículos

1

2

x₂₁₁

Eliminação de sub-rotas com dois nós

x₁₂₁

x₁₂₁ + x₂₁₁ ≤ 1

Roteamento de Veículos

1

2

x₂₁₁

Eliminação de sub-rotas com dois nós

x₁₂₁

x₁₂₁ + x₂₁₁ ≤ 1

1

2

x₂₁₁

x₁₂₁

ou

Roteamento de Veículos

1

2

x₂₁₁

Eliminação de sub-rotas com dois nós

x₁₂₁

x₁₂₁ + x₂₁₁ ≤ 1

1

2

x₂₁₁

x₁₂₁

1

2

x₂₁₁

x₁₂₁

ou

ou

Roteamento de Veículos

1

5

2

3

x₂₁₁

Eliminação de sub-rotas com dois nós

4

x₁₂₁

x₁₃₁

x₃₁₁

x₁₄₁

x₄₁₁

x₅₁₁

x₁₅₁

x_ijk + x_jik ≤ 1

Roteamento de Veículos

1

5

2

3

Eliminação de sub-rotas com três nós

4

x₁₂₁

x₂₃₁

x₃₁₁

x₁₂₁ + x₂₃₁ + x₃₁₁ ≤ 2

Roteamento de Veículos

1

5

2

3

Eliminação de sub-rotas com três nós

4

x_ijk + x_jtk + x_tik ≤ 2

Roteamento de Veículos

1

5

2

3

Eliminação de sub-rotas com três nós

4

Eliminação

sub-rotas

Roteamento de Veículos

A demanda total da rota não excede a capacidade do veículo k

1

2

3

4

0

2

1

3

4

10

x₃₀₁

x₀₄₁

x₄₂₁

x₂₁₁

x₁₃₁

d₀x₀₄₁ + d₄x₄₂₁ + d₂x₂₁₁ + d₁x₁₃₁ + d₃x₃₀₁ ≤ 10

Roteamento de Veículos

Problema de Designação

1

2

3

4

0

2

1

3

4

10

A demanda total da rota não excede a capacidade do veículo k

5

2

3

x₁₃₃

x₁₂₃

x₁₅₃

4

x₁₄₃

x₀₂₃ + x₀₃₃ + x₀₄₃ + x₀₅₃= 1

Veículo 3

0

Restrição de Fluxo em Redes: Veículo sai do depósito 1 só vez

Roteamento de Veículos

5

2

3

x₁₃₃

x₁₂₃

Restrição de Fluxo em Redes: Veículo sai do depósito 1 só vez

x₁₅₃

4

x₁₄₃

Veículo 3

0

Roteamento de Veículos

1

Restrição de Fluxo em Redes: Deixar o nó somente se entrou

x₂₁₃ + x₃₁₃ + x₄₁₃ + x₅₁₃= 0

x₂₁₃

x₃₁₃

x₄₁₃

x₅₁₃

Veículo 3

Roteamento de Veículos

1

Restrição de Fluxo em Redes: Deixar o nó somente se entrou

Roteamento de Veículos

5

2

3

x₁₃₃

x₁₂₃

x₁₅₃

4

x₁₄₃

X_2,n+1,3 + x_3,n+1,3 + x_4,n+1,3 + x_5,n+1,3= 1

Veículo 3

n+1

Restrição de Fluxo em Redes: Veículo sai do depósito 1 só vez

Roteamento de Veículos

Restrição de Fluxo em Redes: Retornar ao nó n+1 somente 1 vez

5

2

3

x_3,n+1,3

x_2,n+1,3

x_5,n+1,3

4

x_4,n+1,3

Veículo 3

n+1

Roteamento de Veículos

S.a.:

​

​

​

​

​

​

​

​

MODELO COMPLETO GERAL

Min

custo para realizar percorrer a rota i-j

Roteamento de Veículos

Pesquisa Operacional II

Aula 36

Módulo 4.7 – Roteamento de Veículos:Modelo by A.A.