Métodos Branch-price-and-cut de pontos interiores para variantes do problema de roteamento de veículos

• Processo: 14/00939-8
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Vigência: 01 de abril de 2014 - 31 de março de 2016
• Área do conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Pedro Augusto Munari Junior
• Beneficiário: Pedro Augusto Munari Junior
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Pesquisadores associados: Douglas José Alem Junior
• Auxílios(s) vinculado(s): 14/50228-0 - Formulations and solution methods for vehicle routing problems with data uncertainty, AP.R
• Assunto(s): Problemas de roteamento de veículos Otimização combinatória Métodos de geração de colunas Branch-price-and-cut Algoritmos
• Palavra(s)-Chave do Pesquisador: branch-price-and-cut | Geração de Colunas | Pontos Interiores | roteamento de veículos | Otimização

Resumo

Neste projeto, pretende-se desenvolver métodos branch-price-and-cut (BPC) para a resolução de duas variantes práticas do problema de roteamento de veículos. A primeira delas considera o uso de múltiplos entregadores em cada rota e, assim, busca determinar o número de trabalhadores que devem ser alocados a cada veículo, além das decisões usuais de roteamento. O número de entregadores tem influência direta no tempo de serviço em cada cliente e, consequentemente, no número de clientes que podem ser visitados ao dia. A segunda variante a ser abordada envolve requisições de coleta e entrega de produtos e, assim, modela situações urbanas relevantes como a entrega de pedidos e o transporte de pessoas sob demanda. Métodos BPC são atualmente o estado-da-arte na resolução exata de problemas de roteamento de veículos. Entretanto, esses métodos ainda podem levar um tempo razoavelmente alto na prática e, assim, a pesquisa por técnicas para a melhoria desses métodos é bastante ativa. Sendo assim, pretende-se propor um método BPC de pontos interiores para cada variante, o qual usa o algoritmo primal-dual de pontos interiores com o intuito de melhorar a eficiência da geração de colunas e desigualdades válidas. Também, as técnicas de ramificação forte (strong branching) e ramificação antecipada (early branching) deverão ser exploradas neste BPC. Até o momento, não se tem conhecimento do uso destas estratégias na solução dos problemas abordados. Além disso, pretende-se tratar as incertezas sobre dados, uma característica comumente observada em situações reais, mas ainda pouco explorada nos modelos e métodos de solução existentes na literatura de roteamento de veículos. Os métodos propostos serão implementados e avaliados usando exemplares de teste da literatura, bem como pretende-se usar dados reais coletados de empresas. (AU)

Publicações científicas

(6)

(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)

MARIA GABRIELA S. FURTADO; PEDRO MUNARI; REINALDO MORABITO. O problema de coleta e entrega com janelas de tempo na indústria petrolífera: modelos e métodos branch-and-cut. Gestão & Produção, v. 24, n. 3, p. 501-513, 2017-10-09. (14/00939-8, 14/22542-2)

ALDAIR ÁLVAREZ; PEDRO MUNARI. Abordagens metaheurísticas para o problema de roteamento de veículos com janelas de tempo e múltiplos entregadores. Gestão & Produção, v. 23, n. 2, p. 279-293, 2016-06-14. (14/00939-8)

FURTADO, MARIA GABRIELA S.; MUNARI, PEDRO; MORABITO, REINALDO. Pickup and delivery problem with time windows: A new compact two-index formulation. OPERATIONS RESEARCH LETTERS, v. 45, n. 4, p. 334-341, JUL 2017. (10/10133-0, 14/22542-2, 14/00939-8)

ALVAREZ, ALDAIR; MUNARI, PEDRO. An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen. Computers & Operations Research, v. 83, p. 1-12, JUL 2017. (14/00939-8)

GONDZIO, JACEK; GONZALEZ-BREVIS, PABLO; MUNARI, PEDRO. Large-scale optimization with the primal-dual column generation method. MATHEMATICAL PROGRAMMING COMPUTATION, v. 8, n. 1, p. 47-82, MAR 2016. (14/50228-0, 14/00939-8)

MUNARI, PEDRO; MORABITO, REINALDO. A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen. Top, v. 26, n. 3, p. 437-464, OCT 2018. (16/01860-1, 14/00939-8)