Scatter Search para problemas de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas (2006)
- Authors:
- Autor USP: BELFIORE, PATRÍCIA PRADO - EP
- Unidade: EP
- Sigla do Departamento: PRO
- Subjects: ROTEIRIZAÇÃO; PESQUISA OPERACIONAL; HEURÍSTICA; VAREJO
- Language: Português
- Abstract: Esta tese estuda a implementação de heurísticas e da metaheurística busca dispersa (scatter search) em um problema de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas (Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries - HFVRPTWSD). O HFVRPTWSD é uma combinação do problema de roteirização com frota heterogênea (HFVRP), problema de roteirização de veículos com janelas de tempo (VRPTW) e problema de roteirização com entregas fracionadas (VRPSD). O problema é baseado em um único depósito, a demanda dos clientes pode ser maior que a capacidade dos veículos e, além das restrições de janelas de tempo, há também restrições de capacidade dos veículos e restrições quanto ao tipo de veículo. O VRPSD foi introduzido na literatura por Dror e Trudeau em 1989. No problema de roteirização de veículos com entregas fracionadas, cada cliente pode ser abastecido por mais de um veículo, enquanto no problema clássico de roteirização de veículos (VRP), cada cliente é atendido por um único veículo. Desta forma, para o VRPSD, além dos roteiros de entrega, deve-se determinar a quantidade entregue a cada cliente em cada veículo. Todos os problemas de roteirização com entregas fracionadas encontrados na literatura (VRPSD e suas extensões) têm como característica frota homogênea. O problema estudado neste trabalho difere, portanto, de todos os problemas de roteirização com entregas fracionadas da literatura, poistem, como característica, frota heterogênea. O mesmo raciocínio vale para problemas de roteirização de veículos com frota heterogênea. Os modelos são aplicados em uma rede de varejo no Brasil que é abastecida a partir de um centro de distribuição. A rede compõe um total de 519 lojas distribuídas em 12 estados do país. ) As heurísticas e a metaheurística busca dispersa também são aplicadas em três conjuntos de problemas encontrados na literatura (SOLOMON, 1987; HO E HAUGLAND, 2004; LIU E SHEN, 1999), com o objetivo de avaliar o desempenho dos algoritmos para cada problema. O problema consiste em determinar, a cada dia, como alocar os caminhões às lojas, a quantidade de carga em cada caminhão a ser entregue em cada uma das lojas, qual o melhor roteiro e o tempo de início de atendimento do primeiro cliente da rota, de forma a minimizar o custo total de distribuição e o tempo total de viagem, garantindo que a demanda das lojas seja atendida e as demais restrições do problema sejam respeitadas. Para a resolução do VRPSD e suas extensões, a única metaheurística encontrada na literatura foi busca tabu. Para o problema de roteirização com frota heterogênea e suas extensões, foram implementadas apenas as metaheurísticas busca tabu e BATA (Back-Tracking Adaptative Threshold Accepting). As estratégias de solução propostas no presente trabalho consistem na implementação de heurísticas construtivas e da metaheurística busca dispersa (BD). As soluções iniciais de BD são obtidasatravés da implementação de quatro heurísticas construtivas: heurística de economias, heurística de inserção seqüencial baseada nas idéias de Solomon (1987), heurística de inserção seqüencial baseada nas idéias de Ho e Haugland (2004) e adaptação da heurística de inserção seqüencial de Dullaert et al. (2002). Para o caso real, foi possível uma redução no custo total da frota comparado com a solução atual da empresa. Para algumas instâncias dos três conjuntos de problemas da literatura, os algoritmos apresentaram resultados similares ou superiores às melhores soluções encontradas
- Imprenta:
- Data da defesa: 03.03.2006
-
ABNT
BELFIORE, Patrícia Prado. Scatter Search para problemas de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas. 2006. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2006. Disponível em: http://www.teses.usp.br/teses/disponiveis/3/3136/tde-05092006-145756/. Acesso em: 24 abr. 2024. -
APA
Belfiore, P. P. (2006). Scatter Search para problemas de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/3/3136/tde-05092006-145756/ -
NLM
Belfiore PP. Scatter Search para problemas de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas [Internet]. 2006 ;[citado 2024 abr. 24 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3136/tde-05092006-145756/ -
Vancouver
Belfiore PP. Scatter Search para problemas de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas [Internet]. 2006 ;[citado 2024 abr. 24 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3136/tde-05092006-145756/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
