Pesquisa Operacional na prática: ideias simples que resultamapolo.dps.uminho.pt/eventos/semana_IO_2016/semana_IO_apdio2.pdf · Investigação Operacional na prática: ideias simples

Investigação Operacional na prática:ideias simples que resultam

José Fernando OliveiraMaria Antónia Carravilla

U.Minho, 11 de março de 2016

Sistema de Apoio à Afectação de Reservas a Veículos numa Empresa de Rent‐a‐Car

HERMES

free saleveículos que existem em quantidades grandesdistribuídos por todas as estações de aluguersempre disponíveis ‐> reserva imediata

veículos especiaispelo custo (gamas média alta e alta)pelas características(monovolumes de 7 lugares, carrinhas de 9 lugares, veículos de carga, veículos todo‐o‐terreno – jipes ou “pick‐ups”).

As frotas das Rent‐a‐Car

O problema dos veículos especiaisGrande dificuldade em emparelhar reservas e veículos

porque há poucos veículosveículos não estão localizados nas estações em que são necessáriosnecessidade de transportes em vazio

Problema:Dados

um conjunto de reservasum conjunto de veículos

Determinar a afectação dos veículos às reservasMaximizando os proveitos

Data de saída 1 de Junho @ 12h00Data de entrada 5 de Junho @ 16h00Estação de saída FaroEstação de entrada Faro



Data de saída 7 de Junho @ 10h00Data de entrada 8 de Junho @ 18h00Estação de saída LisboaEstação de entrada Porto

Transfer:DuraçãoCusto

Data de saída >5 de Junho @ 16h00Data de entrada <7 de Junho @ 10h00Estação de saída FaroEstação de entrada Lisboa

Importaçãode Dados

1

UTILIZADORValidaçãode Soluções

3

MODELOGeração

de Soluções

2

Exportaçãode Soluções

4

ReservasGrupo Data de saída Estação de saídaData de entrada Estação de entradaProveito

ViaturasGrupoData de entrada Estação de entrada

Transfers entre estaçõesDuraçãoCusto


1


3

MODELOGeração

de Soluções

2


4

Dados Reservas

a 10 a

c 11 b

a 9 c

c 8 b

d 7 a

a 6 d

c 5 b

d 4 d

b 3 b

b 2 a

d 1 c


1


3

MODELOGeração

de Soluções

2


4

tempo

Dados Viaturas

V1

V2

V3

V4 d

a

c

a


1


3

MODELOGeração

de Soluções

2


4

tempo

SoluçãoReservas atribuídas a viaturasReservas não atribuídas a viaturasTransfers para as viaturas

ObjectivoMaximizar proveitoPROVEITO = receitas reservas – custos transfers

RestriçõesTemporaisViaturasReservas


1


3

MODELOGeração

de Soluções

2


4

Geração de Soluções duas fases

a 10 a

c 11 b

a 9 c

c 8 b

d 7 a

a 6 d

c 5 b

d 4 d

b 3 b

b 2 a

d 1 c

FASE 1Optimização


1


3

MODELOGeração

de Soluções

2


4

tempo

Geração de Soluçõesduas fases

a 10 a

c 11 b

a 9 c

c 8 b

d 7 a

a 6 d

c 5 b

d 4 d

b 3 b

b 2 a

d 1 c

FASE 1Optimização


1


3

MODELOGeração

de Soluções

2


4

tempo


a 10 a

c 11 b

a 9 c

c 8 b

d 7 a

a 6 d

c 5 b

d 4 d

b 3 b

b 2 a

d 1 c

FASE 1Optimização

FASE 2Heurística


1


3

MODELOGeração

de Soluções

2


4

tempo


a 10 a

c 11 b

a 9 c

c 8 b

d 7 a

a 6 d

c 5 b

d 4 d

b 3 b

b 2 a

d 1 c

FASE 1Optimização

FASE 2Heurística


1


3

MODELOGeração

de Soluções

2


4

tempo

Modelo MIP

Modelo MIP

Modelo MIP

Geração de Soluçõesoptimização

c 11 b

a 9 c

d 7 a

a 6 d

c 5 b

b 3 b

V1

V2

V3

V4 d

a

c

a

tempo


c 11 b

a 9 c

d 7 a

a 6 d

c 5 b

b 3 b

V1

V2

V3

V4 d

a

c

a

tempo


c 11 b

a 9 c

d 7 a

a 6 d

c 5 b

b 3 b

V1

V2

V3

V4 d

a

c

a

tempo


c 11 b

d 7 a a 9 c

b 3 b

a 6 d c 5 b

V1

V2

V3

V4 d

a

c

a

d b

dc

ad

Proveito viatura 2:

‐ Custo transfer ad+ Proveito reserva 7+ Proveito reserva 9

tempo

Geração de Soluçõesheurística

Ordenar lista de reservas por:Data de início crescente

Proveito decrescente

Para cada reserva seleccionar as viaturas com:Data‐in + duração transfer < Data‐out reservaOrdenar lista de viaturas por:

Custo transfer crescenteData‐out reserva – (Data‐in + duração transfer) crescente


V1

V2

V3

V4 b

c

b

b

a 10 ac 8 b

d 4 db 2 a

d 1 c

tempo


V1

V2

V3

V4 b

c

b

b

d 4 dbd

a 10 ac 8 b

d 4 db 2 a

d 1 c

tempo


V1

V2

V3

V4 b

c

b

b a 10 a

d 4 d

b a

bd

a 10 ac 8 b

d 4 db 2 a

d 1 c

tempo


V1

V2

V3

V4 b

c

b

b a 10 a c 8 b

d 4 dbd

acb a

a 10 ac 8 b

d 4 db 2 a

d 1 c

tempo


V1

V2

V3

V4 b

c

b

b a 10 a c 8 b

d 4 d

b 2 a

bd

ac

cb

b a

a 10 ac 8 b

d 4 db 2 a

d 1 c

tempo


V1

V2

V3

V4 b

c

b

b a 10 a c 8 b

d 4 d

b 2 a

d 1 cbd

bd

ac

cb

b a

a 10 ac 8 b

d 4 db 2 a

d 1 c

tempo

Resultados

Um funcionário superior da empresa disponível para outras tarefas.Mais reservas aceitesMenores custos de transfer

SAD trata várias gamas de veículos em simultâneo.SAD trata “upgrades” e “downgrades”

REDI

Um SAD para a Racionalização da Ocupação dos EDIfícios da CMP

Porque foi necessário o Projecto REDI?

A ocupação dos edifícios da CMP pelas Direcções Municipais evoluiu gradualmente em função de novas necessidades de espaços que surgiram ao longo dos anos.

Essa evolução gradual fez com que a ocupação de espaços nunca fosse tratada globalmente, tendo em conta: •as necessidades das Direcções Municipais•os edifícios disponíveis e as suas características.

Porque foi necessário o Projecto REDI?

A ocupação dos edifícios da CMP pelas Direcções Municipais evoluiu gradualmente em função de novas necessidades de espaços que surgiram ao longo dos anos.

Essa evolução gradual fez com que a ocupação de espaços nunca fosse tratada globalmente, tendo em conta: •as necessidades das Direcções Municipais•os edifícios disponíveis e as suas características.

Quais os resultados do Projecto REDI?

$$$$$$

$$$$$$

Quais os resultados do Projecto REDI?

Definição dos edifícios onde localizar cada unidade da CMP, por forma a racionalizar a sua ocupação.

Edifícios e terrenosRecolha

de DadosMODELOGeração

de soluções

UTILIZADORAvaliação e escolha de

solução

DirecçõesMunicipais

Recolhade Dados

Edifícios e terrenos da CMP


Edifício dos Paços do Concelho



• Plantas: Piso 0 Piso 1 Piso 2

• Plantas: Piso 3 Piso 4 Piso 5



Presidência; Vice – Presidência; Assembleia Municipal; Gabinete de Auditoria e Controlo Interno; Gabinete de Comunicação e Imagem; Salões Nobres

3

Pelouro da Educação, Desporto, Juventude Inovação; Pelouro da Cultura e Turismo; Pelouro da Habitação e Acção Social; Pelouro das Actividades Económicas, Protecção Civil e Recursos Humanos;CDU; Gabinete de Auditoria e Controlo Interno; Gabinete de Comunicação e Imagem

4

Departamento Municipal de Finanças e Património; Divisão Municipal de Cadastro e Gestão do Património

2

Direcção Municipal de Finanças e Património; Gabinete de Auditoria e Controlo Interno; Divisão Municipal de Protocolo e Relações Públicas; Gabinete de Comunicação e Imagem; Divisão Municipal de Secretariado e Apoio Administrativo

Divisão Municipal de Arquivo Geral; Divisão Municipal de Protocolo e Relações Públicas; Gabinete de Auditoria e Controlo Interno; Gabinete de Comunicação e Imagem

Entidade

1

0

Piso

Presidência; Vice – Presidência; Assembleia Municipal; Gabinete de Auditoria e Controlo Interno; Gabinete de Comunicação e Imagem; Salões Nobres

3

Pelouro da Educação, Desporto, Juventude Inovação; Pelouro da Cultura e Turismo; Pelouro da Habitação e Acção Social; Pelouro das Actividades Económicas, Protecção Civil e Recursos Humanos;CDU; Gabinete de Auditoria e Controlo Interno; Gabinete de Comunicação e Imagem

4

Departamento Municipal de Finanças e Património; Divisão Municipal de Cadastro e Gestão do Património

2

Direcção Municipal de Finanças e Património; Gabinete de Auditoria e Controlo Interno; Divisão Municipal de Protocolo e Relações Públicas; Gabinete de Comunicação e Imagem; Divisão Municipal de Secretariado e Apoio Administrativo

Divisão Municipal de Arquivo Geral; Divisão Municipal de Protocolo e Relações Públicas; Gabinete de Auditoria e Controlo Interno; Gabinete de Comunicação e Imagem

Entidade

1

0

Piso





Museu Romântico da Quinta da Macieirinha


Armazéns na cidadeda Maia



Edifícios e terrenos da CMPCasa - Oficina António

Carneiro

Edifícios e terrenos da CMPCasa - Oficina António

Carneiro

• Ocupação de espaços• Departamento de Museus e Património Cultural - Divisão de

Museus• Edifício municipal, doado à CMP em 1966 com condição de

habitação própria para a esposa do Sr. Carneiro• Casa abre ao público em 1973 e encerra para obras em 1996

(situação que se mantém)• Residente faleceu em 2001 • Local usado como residência considerado inviável para fins gerais/

administrativos devido à precariedade da construção• Área total de 509 m2, composta por 3 fracções (151, 235 e 123 m2,

respectivamente.



Edifícios e terrenos da CMPCentro de Recursos EducativosConservatório de MúsicaEdifício Adm. E Casa dos Jardineiros no Parque da CidadeEdifício da Rua de CedofeitaEdifício da Rua do Bolhão IEdifício da Rua do Bolhão IIEdifício de S.DinisEdifício de S.RoqueEdifício de SalgueirosEdifício do parque de S.RoqueEdifício dos CorreiosEdifício EntreparedesFundação Maria Guerra JunqueiroGabinete de AmbienteGabinete de ProjectosGabinete do MunícipeLegado D. Marta SampaioMatadouro Municipal

Estaleiro de BonjóiaEstaleiro do Monte AventinoEstaleiro de Martins SarmentoArrecadação da ErvilhaArrecadação do BonjardimArrecadação da Ponte NovaArrecadação da FontinhaArrecadação Largo 1º de DezembroEstaleiro do FreixoAbrigo do BonjardimTerreno das AreiasEstaleiro de BonjóiaEstaleiro do Monte AventinoEstaleiro de Martins SarmentoArrecadação da ErvilhaArrecadação do BonjardimArrecadação da Ponte NovaArrecadação da Fontinha

Mercado Ferreira BorgesMuseu Ciência e IndústriaMuseu da ImprensaMuseu do Vinho do PortoMuseu Romântico da Quinta da MacieirinhaNúcleo Rural do Parque da CidadeOficinas Gerais do CarvalhidoOrdem dos ArquitectosPaços do ConcelhoPalacete Viscondes de BalsemãoPalácio do BolhãoParque da PasteleiraParque Urbano da Quinta do CoveloQuartel dos BSBReservas dos Museus da CidadeSolar do Vinho do PortoMercado Ferreira BorgesMuseu Ciência e Indústria

Armazém Bom SucessoArmazém BonjardimArmazém de S.BentoArmazéns do MatadouroArmazéns na cidade da MaiaBiblioteca Almeida GarrettBiblioteca InfantilBiblioteca MunicipalCasa - Museu Guerra JunqueiroCasa - Oficina António CarneiroCasa de SerrúbiaCasa do InfanteCasa do RoseiralCasa TaitCasa Vitorino RibeiroCaves do Palácio de CristalCemitério de AgramonteCemitério do Prado do Repouso


Identificação de espaços mínimos de alocação (EmA)

Área útil de cada EmACaracterísticas de cada EmA

Proximidade entre EmA0 - mesmo espaço1 - mesmo edifício e pisos diferentes2 - edifícios próximos3 - outros

Necessidades de espaço dasDirecções Municipais

Defin

ição

de

unid

ades

mín

imas

de

aloc

ação

(Um

A)

Informação de Recursos Humanos

NomeNúmero mecanográficoIdentificação da UmA a que pertenceCategoria profissional

Agregação de categorias

Tabela com área útil por pessoa de uma determinada categoria


Identificação de unidades mínimas de alocação (UmA)Espaço ocupado por cada UmAÁrea útil ocupada por cada UmACaracterísticas especiais dos espaços a ocupar pela UmANecessidades de proximidade de munícipesNecessidades de proximidade de equipamentos municipais

Interacções entre UmA1 interacção muito baixa3 interacção “normal”5 interacção forte

(uma unidade com ela própria)


Impossibilidade de alocação de uma unidade a um espaço

Obrigatoriedade de alocação de uma unidade a um espaço

Unidades e Espaços

Modelo MIP

Modelo MIP

Modelo MIP

Geração de SoluçõesAlgoritmos genéticos

Representação de uma soluçãoAlocação da unidade A ao espaço X

Unidade 1 alocada ao espaço 5….Unidade 39 alocada ao espaço 7….

Um espaço X pode ter 0 ou mais unidades alocadas(exemplo: espaço 5 tem unidades 1 e 38 alocadas )

Uma unidade A tem que ser alocada a um e um só espaço

Unidade 1 2 3 4 5 6 … 37 38 39 40 41 A

Espaço 5 4 10 23 45 51 … 2 5 7 10 12 X

Geração de SoluçõesPopulação inicial (pais)

½ da população = solução inicial½ da população = gerada aleatoriamente

Geração de filhosCrossover

MutaçãoUnidade escolhida aleatoriamente (unidade 4)Novo espaço escolhido aleatoriamente (espaço 30)

Unidade 1 2 3 4 5 6 … 37 38 39 40 41 A

Espaço 5 4 10 23 45 51 … 2 5 7 10 12 X

Unidade 1 2 3 4 5 6 … 37 38 39 40 41 A

Espaço 5 4 10 30 45 51 … 2 5 7 10 12 X

Geração de SoluçõesEvolução da população








Avaliação de uma solução

Número de mudanças face à solução inicial(custos de mudança)

Interacção entre unidades proximidade de espaços(custos de interacção)

Sobre-ocupação(custos de sobre-ocupação)

Violação de restrições de alocação(alocação actual pode não ser admissível)

ExemploEspaços

YX

Z

Q

X Y Z Q KX 0 1 2 3 3Y 1 0 2 3 3Z 2 2 0 3 3Q 3 3 3 0 3K 3 3 3 3 0

Área útil(m2)

100 120 150 200 150

Proximidades entre espaços

Níveis de proximidade:0 mesmo espaço1 mesmo edifício e pisos diferentes2 edifícios próximos3 outros

K

ExemploUnidades<->Espaços

X Y Z Q KA 80 0 0 0 0B 0 70 0 0 0C 0 50 0 0 0D 0 0 0 50 0E 0 0 0 140 0F 0 0 0 0 60G 0 0 0 0 90

Áreas úteis ocupadas (m2)YB C

X AZ

Q D E

K F G

YX

Z

Q

K

X Y Z Q KA 1 1 0 1 0B 0 1 1 0 0C 1 0 0 1 0D 0 0 1 1 0E 0 0 0 1 0F 0 0 1 0 1G 0 1 0 0 1

Unidades <-> espaços

ExemploUnidades<->Espaços

ExemploInteracções entre Unidades

A B C D E F GA 5 1 1 1 1 1 1B 1 5 1 5 1 3 1C 1 1 5 1 1 1 1D 1 5 1 5 1 5 3E 1 1 1 1 5 1 1F 1 3 1 5 1 5 1G 1 1 1 3 1 1 5

Interacções entre unidades

F G

D E

AB C

ExemploAlgumas Soluções

F

G D

E

AB

C

F G

D E

AB

C

Grande custo nas interacções

Grande custo nas mudanças

ResultadosCMP passou a ter registo de Edifícios e Terrenos

Unidades mudaram de instalações

Espaços arrendados foram libertados

Edifícios foram vendidos

$$$$$$

$$$

$$$

Documents

Pesquisa Operacional na prática: ideias simples que resultamapolo.dps.uminho.pt/eventos/semana_IO_2016/semana_IO_apdio2.pdf · Investigação Operacional na prática: ideias simples