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
Linha de fomento: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 no Exterior: 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

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.