DECISÕES SOBRE TRANSPORTES (PARTE III)

Mayara Condé Rocha Murça

TRA-53 – Logística e Transportes Agosto/2013

Problemas de roteirização e programação de veículos (RPV)

Objetivo geral: Determinar rotas de distribuição de produtos a partir de armazéns que atendam a demanda de clientes, satisfaçam restrições operacionais e minimizem o custo global de transporte

Componentes do problema:

Rede de transporte

Conjunto de clientes

Conjunto de armazéns

Frota de veículos

Disponibilidade de mão-de-obra (motoristas)

Problemas de roteirização e programação de veículos (RPV)

Problemas clássicos:

Capacitated VRP

Distance-constrained VRP

VRP with Time Windows

VRP with Backhauls

VRP with Pickup and Delivery

Problemas de roteirização e programação de veículos (RPV)

Problemas clássicos

Problemas de roteirização e programação de veículos (RPV)

A exemplo do que ocorre com o problema do caixeiro viajante, para problemas reais de grandes dimensões, a obtenção de soluções ótimas através de métodos exatos torna-se proibitiva em termos de tempo computacional

Em geral, são utilizadas heurísticas, combinação de heurísticas (construção, refinamento e meta-heurística) e até mesmo combinação de heurísticas com métodos exatos para obter soluções

Exemplo – CVRP

Determinar um conjunto de rotas que minimize o custo total do problema de entrega de produtos da empresa Chemtech 1 armazém único 13 clientes A política da empresa determina que os veículos não

podem viajar distâncias superiores a 60 milhas entre dois clientes sucessivos

Toda a demanda deve ser entregue por um único veículo Disponibilidade de veículos com capacidade de 10 ton Cada veículo tem um custo fixo de $100 por dia e um custo

variável de $1 por milha

Exemplo – CVRP

Configuração da rede:

0 Depot

11

10

12

1 2

3

4

5

6

9

8

7

13

Exemplo – CVRP

Matriz de distâncias do problema

1 2 3 4 5 6 7 8 9 10 11 12 13

0 45 31 47 34 19 30 32 35 20 42 16 19 50

1 21 43 55 58 x 49 x x 35 24 54 23

2 27 29 38 56 48 x 50 44 21 45 21

3 33 50 x x x x x 52 x 22

4 19 36 x x 45 x 47 56 45

5 18 56 50 25 x 41 40 56

6 59 44 17 x 55 41 x

7 30 41 18 43 18 x

8 25 50 48 17 x

9 56 42 23 x

10 24 35 56

11 29 38

12 x

Exemplo – CVRP

Demanda dos clientes

Customer 1 2 3 4 5 6 7 8 9 10 11 12 13

Demand (ton)

3 5 5 4 2 2 6 8 3 3 7 4 3

Exemplo – CVRP

1 – Obter solução utilizando heurística de construção (vizinho mais próximo)

2 – Obter solução utilizado uma combinação de heurística de construção com meta-heurística (algoritmo genético)

3 – Obter solução utilizando uma combinação de heurística com método exato (programação linear)

OBS: Realizar apenas 1 iteração para obter cada solução.

Exemplo – CVRP

1 – Obter solução utilizando heurística de construção (vizinho mais próximo)

Exemplo – CVRP

Solução 1

0 Depot

11

10

12

1 2

3

4

5

6

9

8

7

13

Custo total = 1306

Rota Clientes Custo Ton

1 0-10-11-0 182 10

2 0-5-6-9-0 174 7

3 0-12-7-0 169 10

4 0-2-1-0 197 8

5 0-4-3-0 214 9

6 0-8-0 170 8

7 0-13-0 200 3

Critério: O primeiro cliente de cada rota é o cliente ainda não atendido que está mais próximo do

depósito

Exemplo – CVRP

Solução 1’

0 Depot

11

10

12

1 2

3

4

5

6

9

8

7

13

Custo total = 1324

Rota Clientes Custo Ton

8 0-13-3-5-0 241 10

9 0-1-2-6-0 252 10

10 0-10-7-0 192 9

6 0-8-0 170 8

11 0-4-9-0 199 7

12 0-12-0 138 4

13 0-11-0 132 7

Critério: O primeiro cliente de cada rota é o cliente ainda não atendido que está mais distante do

depósito

Exemplo – CVRP

2 – Obter solução utilizado uma combinação de heurística de construção com meta-heurística (algoritmo genético)

Exemplo – CVRP

Solução 2

0 Depot

11

10

12

1 2

3

4

5

6

9

8

7

13

Custo total = 1193

Exemplo – CVRP

3 – Obter solução utilizando uma combinação de heurística com método exato (programação linear)

Metodologia de Otimização Unificada

Combinação de métodos matemáticos com heurísticas Quebra de um problema de programação matemática

de grande escala em vários subproblemas mais fáceis de otimizar

Soluções geradas por heurísticas constituem input para os subproblemas

É possível obter uma boa solução, dentro de uma faixa aceitável de variação em relação à solução ótima

Como sabemos se a solução é boa se não conhecemos a solução ótima? O método computa limites inferiores para a solução ótima

Metodologia de Otimização Unificada

Monolithic MIP

LP Master Model

IP Master Model

Lagrangean Submodels

Heuristics

Feasible Plans Lower Bounds on

Optimal Plans

Demonstrably Good Plan

Shadow Prices

Feasible Subplans

Subplans

Exemplo – CVRP

Solução 3

0 Depot

11

10

12

1 2

3

4

5

6

9

8

7

13

Custo total = 1213

(1ª iteração)

Exemplo – CVRP

Solução 3

0 Depot

11

10

12

1 2

3

4

5

6

9

8

7

13

Custo total = 1147

(14ª iteração)

Roteirização de aeronaves

Principais decisões de planejamento de uma companhia aérea:

Planejamento da frota

(Fleet Planning)

Planejamento da estrutura de rotas

(Route Planning)

Desenvolvimento da programação de voos

(Schedule Development)

Precificação (Pricing)

Gerenciamento de receita (Revenue Management)

Programação de voos (Schedule Design)

Alocação de frota (Fleet Assignment)

Roteirização de aeronaves (Aircraft Routing)

Programação de tripulação (Crew Scheduling)

Roteirização de aeronaves

Programação de voos

•Definida preliminarmente no 1º estágio do planejamento a partir de análise da demanda, do comportamento do mercado, da estrutura de rede,...

Requisitos de manutenção das aeronaves

•As aeronaves devem receber serviços de manutenção em aeroportos específicos (bases de manutenção) com certa frequência

• Inspeções visuais são realizadas a cada 3 ou 4 dias

Ciclos de roteirização

•São cumpridos por cada aeronave

•Reduzem o número de possibilidades de roteirização

•Comumente são utilizados ciclos de 3 a 7 dias

Problema: Como determinar quais voos serão realizados por cada aeronave da frota diariamente?

Roteirização de aeronaves

Exemplo:

Voo Origem Hora de partida

Destino Hora de chegada

Horas de voo

122 JFK 07:35 LAX 10:05 5.5

137 JFK 07:40 BOS 09:10 1.5

134 JFK 10:35 MIA 13:35 3

138 JFK 12:30 BOS 14:00 1.5

123 JFK 16:00 LAX 18:30 5.5

124 JFK 19:00 LAX 21:30 5.5

139 JFK 21:30 BOS 23:00 1.5

116 BOS 06:15 JFK 07:45 1.5

117 BOS 10:00 JFK 11:30 1.5

118 BOS 15:00 JFK 16:30 1.5

101 LAX 05:00 JFK 13:30 5.5

102 LAX 09:45 JFK 18:15 5.5

103 LAX 15:20 JFK 23:50 5.5

115 MIA 18:15 JFK 21:15 3

Ciclos de 3 dias

Base de manutenção: JFK

Turnaround time: 45 minutos

Roteirização de aeronaves

Exemplo:

MIA JFK

JFK BOS JFK

JFK MIA

115

138 118

134

DIA 1

DIA 2

DIA 3

Roteirização de aeronaves

1º passo – Determinar ciclos de roteirização viáveis: Pelo menos 1 pernoite da aeronave em JFK

Garantir um tempo mínimo de 45 minutos entre dois voos (turnaround)

2º passo – Determinar quais ciclos de roteirização devem ser realizados: Todos os voos da programação devem ser realizados diariamente

Cada voo só pode ser realizado por uma e somente uma aeronave

Minimizar custos ou quantidade de aeronaves necessárias / Maximizar oportunidades de manutenção

Roteirização de aeronaves

Objetivo: determinar qual ciclo será realizado por cada aeronave de forma a

minimizar os custos operacionais

Parâmetros:

: custo da rota j

: 1, se o voo i pertencer à rota j; 0, caso contrário

: número total de aeronaves na frota

Variável de decisão:

se a rota j for selecionada

caso contrário

1,

0,jx

jc

ija

N

Objetivo: determinar qual ciclo será realizado por cada aeronave de forma a minimizar os custos operacionais

Objetivo: determinar qual ciclo será realizado por cada aeronave de forma a

minimizar os custos operacionais

Sujeito a:

para qualquer voo i

para todas as rotas j

para qualquer rota j

Roteirização de aeronaves

Min j j

j

c x

1ij j

j

a x

j

j

x N

0,1jx

Objetivo: determinar qual ciclo será realizado por cada aeronave de forma a minimizar os custos operacionais