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
• Data de Início da vigência: 01 de maio de 2018
• Data de Término da vigência: 30 de setembro de 2018
• Área de 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
• Instituição Anfitriã: É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.

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., 2023-02-28. (18/01523-0, 19/23596-2, 16/01860-1, 15/14582-7, 17/06434-3)