Busca avançada
Ano de início
Entree

Benders-branch-and-cut para o problema de roteamento de veículos com múltiplos entregadores e demanda estocástica

Processo: 18/01523-0
Modalidade de apoio:Bolsas no Exterior - Estágio de Pesquisa - Doutorado
Vigência (Início): 01 de maio de 2018
Vigência (Término): 30 de setembro de 2018
Área do conhecimento:Engenharias - Engenharia de Produção - Pesquisa Operacional
Pesquisador responsável:Reinaldo Morabito Neto
Beneficiário:Jonathan Justen de La Vega Martínez
Supervisor: Michel Gendreau
Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
Local de pesquisa: École Polytechnique de Montréal, Canadá  
Vinculado à bolsa:15/14582-7 - Programação Estocástica e Otimização Robusta para Variantes do Problema de Roteamento de Veículos: Formulações e Métodos Exatos, BP.DR
Assunto(s):Programação estocástica   Otimização estocástica   Problemas de roteamento de veículos
Palavra(s)-Chave do Pesquisador:Algoritmo benders-branch-and-cut | Programação Estocástica | roteamento de veículos | Otimização estocástica

Resumo

Nesse projeto de pesquisa, pretende-se melhorar o algoritmo benders-branch-and-cut desenvolvido no projeto BEPE do processo 2017/06434-3 a fim de resolver efetivamente instâncias de tamanhos razoáveis do problema de roteamento de veículos com janelas de tempo, múltiplos entregadores e demanda estocástica. O problema foi formulado como um programa dois estágios com recurso. No primeiro estágio, um conjunto de rutas é definido. No segundo estágio, decisões de recurso ou ações contingenciais são tomadas de modo a mitigar o impacto das incertezas da demanda nas rotas definidas a priori. Um método de solução exato baseado no algoritmo benders-branch-and-cut foi proposto para resolver o problema. Experimentos computacionais foram realizados usando as bem conhecidas instâncias de Solomon a fim de avaliar o desempenho computacional do algoritmo proposto. Resultados computacionais revelaram a dificuldade do algoritmo benders-branch-and-cut para resolver instâncias de tamanhos razoáveis do problema. De fato, o algoritmo não provou otimalidade, durante um tempo de execução de 3600 segundos, em instâncias com mais de 25 clientes e 20 cenários. Por essa razão, o presente projeto de pesquisa visa melhorar o desempenho computacional do algoritmo benders-branch-and-cut desenvolvido no projeto BEPE do processo 2017/06434-3 para resolver efetivamente instâncias práticas do problema.

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Publicações científicas
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
DE LA VEGA, JONATHAN; GENDREAU, MICHEL; MORABITO, REINALDO; MUNARI, PEDRO; ORDONEZ, FERNANDO. An integer L-shaped algorithm for the vehicle routing problem with time windows and stochastic demands. European Journal of Operational Research, v. 308, n. 2, p. 20-pg., . (18/01523-0, 19/23596-2, 16/01860-1, 15/14582-7, 17/06434-3)

Por favor, reporte erros na lista de publicações científicas utilizando este formulário.