Instituto de Computação - UNICAMP (Universidade Estadual de Campinas)
Alunos: Eduardo Barros Innarelli (170161) e Felipe Lopes de Mello (171119)
Orientador: Eduardo Candido Xavier
Neste trabalho estudamos um problema de roteamento de veículos estocástico (do inglês Stochastic Vehicle Routing Problem - SVRP) no qual os clientes e suas demandas são incertos. No problema clássico, o VRP, temos um depósito de onde m caminhões devem sair para fazer entregas para n clientes. Deve-se construir m rotas disjuntas nos clientes iniciando e terminando no depósito, tal que cada cliente seja visitado exatamente uma vez, com o objetivo de minimizar o custo total. Na versão estocástica do problema, alguns clientes são já conhecidos e para um outro conjunto de clientes temos apenas suas probabilidades de ocorrência, o que significa que devem ser atendidos por alguma rota caso sua ocorrência se realize. Nessa versão as demandas dos clientes não são fixas, podendo variar conforme uma distribuição probabilística. Neste caso, o objetivo é computar m rotas de custo esperado mínimo tal que a demanda de todos clientes sejam atendidas e a capacidade C dos veículos não seja excedida.
O objetivo no primeiro estágio é projetar m rotas (uma para cada veículo) de custo esperado mínimo saindo e voltando para o depósito, tal que cada cliente esteja em exatamente uma rota e a demanda esperada de cada rota seja no máximo C.
Códigos:
Referência:
Códigos:
- Fluxo de execução
- Construção de solução e estruturas iniciais
- Avaliação de soluções a partir de movimentos entre vizinhos
- Atualização de estruturas, parâmetros e melhor solução conforme a viabilidade da solução corrente
- Custos aproximados
Referência:
No segundo estágio, após serem realizados os eventos aleatórios, são aplicadas as políticas de recurso sob uma rota, que podem incorrer em novos custos. O objetivo é otimizar o custo de transporte esperado, que consiste no custo da viagem mais o custo esperado das políticas de recurso levando em conta todas as possíveis realizações.
Códigos:
Referência: