Busca avançada
Ano de início
Entree

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

Processo: 14/00939-8
Linha de fomento: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
Pesq. 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 

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)
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. Citações Web of Science: 3.
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. Citações Web of Science: 14.
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. Citações Web of Science: 6.
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. -, Set. 2017.
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, Jun. 2016.
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. Citações Web of Science: 7.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.