Diversity control mechanisms in iterated local search to solve vehicle routing problems
Data
2021-08-30
Autores
Máximo, Vinícius Rosa [UNIFESP]
Orientadores
Rosset, Mariá Cristina Vasconcelos Nascimento [UNIFESP]
Tipo
Tese de doutorado
Título da Revista
ISSN da Revista
Título de Volume
Resumo
Métodos heurísticos têm sido amplamente usados para resolver problemas difíceis de otimização para os quais métodos de solução exatos são impraticáveis. O Problema de Roteamento de Veículos (PRV) é um exemplo desses problemas. Meta-heurísticas baseadas em busca local foram aplicadas com sucesso no PRV clássico, denominado Problema de Roteamento de Veículos Capacitado (PRVC), do inglês Capacitated Vehicle Routing Problem (CVRP). O CVRP visa encontrar um conjunto de rotas que minimizem o custo de trajeto usando uma frota de veículos idênticos para atender todos os clientes, respeitando as capacidades dos veículos. Apesar do bom desempenho, a maioria das heurísticas e meta-heurísticas aplicadas ao CVRP ficam presas em ótimos locais, mesmo com os mecanismos de hill-climbing existentes, como as estratégias de diversificação incorporadas nos métodos de solução para evitar esse fenômeno. Esta tese visa investigar mecanismos de diversificação a serem incorporados à Iterated Local Search, que é uma das meta-heurísticas mais utilizadas para resolver problemas de roteamento. O algoritmo proposto é denominado Adaptive Iterated Local Search (AILS). Como uma primeira contribuição, apresentamos uma hibridização de AILS com Path-Relinking (PR) para o CVRP. No método apresentado, sugerimos um mecanismo automático para controlar a etapa de diversidade na meta-heurística, permitindo que ela escape dos ótimos locais mais facilmente. Os experimentos computacionais com instâncias de benchmark para o CVRP indicam que a estratégia proposta teve um desempenho melhor do que as meta-heurísticas da literatura. Tendo em vista os excelentes resultados obtidos pelo AILS-PR para o CVRP, aplicamos o AILS ao Heterogeneous Fleet Vehicle Routing Problem (HFVRP) que é uma generalização do CVRP. No HFVRP, os veículos podem ter capacidades e custos operacionais diferentes, proporcionando um cenário mais realista para diversas aplicações. Algumas mudanças foram necessárias para adaptar o AILS a esse problema, que não era um método de solução híbrido. A análise comparativa do AILS aplicado ao HFVRP com metaheurísticas de última geração sugere um excelente desempenho do AILS. Apesar dos excelentes resultados alcançados pelo AILS-PR para o CVRP, notamos que principalmente por causa do PR, o AILS-PR não conseguia ter um desempenho tão bom para instâncias grandes quanto nas instâncias de pequeno e médio porte. Para resolver esse problema, outra contribuição desta tese é o desenvolvimento de um AILS mais adequado para instâncias de grande escala, denominado AILS-II. O AILS-II tem duas fases, a primeira é o mesmo processo de pesquisa do AILS, enquanto a segunda utiliza soluções de elite como novas soluções de referência. O AILS-II para o CVRP apresentou bom desempenho para instâncias grandes, com até 30000 vértices, em comparação ao AILS-PR.
Heuristic methods have been widely used to solve hard optimization problems for which exact solution methods are impractical. The Vehicle Routing Problem (VRP) is an example of these problems. Local search-based meta-heuristics have been successfully applied to the classic VRP, called the Capacitated Vehicle Routing Problem (CVRP). The CVRP aims to find a set of routes that minimize the cost of travel using a fleet of identical vehicles to serve all customers while respecting vehicle capacities. Despite the good performance, most of the CVRP heuristics and metaheuristics get trapped in local optima, even with the existing hill-climbing mechanisms, such as the diversification strategies incorporated in the solution methods to avoid this phenomenon. This thesis aims at investigating diversification mechanisms to incorporate into the Iterated Local Search, which is one of the most commonly used metaheuristics to solve routing problems. The proposed algorithm is called Adaptive Iterated Local Search (AILS). As a first contribution, we present a hybridization of AILS with Path-Relinking (PR) to the CVRP. In the introduced method, we suggest an automatic mechanism to control the diversity step in the metaheuristic, allowing it to escape from local optima more easily. The computational experiments with CVRP benchmark instances indicate that the proposed strategy performed better than the literature metaheuristics. Bearing in mind the excellent results AILS-PR achieved to the CVRP, we applied AILS to the Heterogeneous Fleet Vehicle Routing Problem (HFVRP), a generalization of the CVRP. In HFVRP, vehicles may have different capacity and operating costs, providing a more realistic scenario to several applications. Some changes were necessary to adapt AILS to this problem, which was not a hybrid solution method. The comparative analysis of AILS applied to HFVRP with state-of-the-art metaheuristics suggests an excellent performance of AILS. Despite the outstanding results achieved by AILS-PR to the CVRP, we noticed that mainly because of PR, AILS-PR could not perform as well as in small- and medium-sized in large-sized instances. To address this issue, another contribution of this thesis is the development of an AILS more suitable for large-scale instances, named AILS-II. AILS-II has two phases, the first is the same search process as AILS, while the second uses elite solutions as new reference solutions. AILS-II to the CVRP presented a good performance for large instances, with up to 30000 vertices, in comparison to AILS-PR.
Heuristic methods have been widely used to solve hard optimization problems for which exact solution methods are impractical. The Vehicle Routing Problem (VRP) is an example of these problems. Local search-based meta-heuristics have been successfully applied to the classic VRP, called the Capacitated Vehicle Routing Problem (CVRP). The CVRP aims to find a set of routes that minimize the cost of travel using a fleet of identical vehicles to serve all customers while respecting vehicle capacities. Despite the good performance, most of the CVRP heuristics and metaheuristics get trapped in local optima, even with the existing hill-climbing mechanisms, such as the diversification strategies incorporated in the solution methods to avoid this phenomenon. This thesis aims at investigating diversification mechanisms to incorporate into the Iterated Local Search, which is one of the most commonly used metaheuristics to solve routing problems. The proposed algorithm is called Adaptive Iterated Local Search (AILS). As a first contribution, we present a hybridization of AILS with Path-Relinking (PR) to the CVRP. In the introduced method, we suggest an automatic mechanism to control the diversity step in the metaheuristic, allowing it to escape from local optima more easily. The computational experiments with CVRP benchmark instances indicate that the proposed strategy performed better than the literature metaheuristics. Bearing in mind the excellent results AILS-PR achieved to the CVRP, we applied AILS to the Heterogeneous Fleet Vehicle Routing Problem (HFVRP), a generalization of the CVRP. In HFVRP, vehicles may have different capacity and operating costs, providing a more realistic scenario to several applications. Some changes were necessary to adapt AILS to this problem, which was not a hybrid solution method. The comparative analysis of AILS applied to HFVRP with state-of-the-art metaheuristics suggests an excellent performance of AILS. Despite the outstanding results achieved by AILS-PR to the CVRP, we noticed that mainly because of PR, AILS-PR could not perform as well as in small- and medium-sized in large-sized instances. To address this issue, another contribution of this thesis is the development of an AILS more suitable for large-scale instances, named AILS-II. AILS-II has two phases, the first is the same search process as AILS, while the second uses elite solutions as new reference solutions. AILS-II to the CVRP presented a good performance for large instances, with up to 30000 vertices, in comparison to AILS-PR.
Descrição
Citação
@article{Maximo2021, title={Diversity Control Mechanisms in Iterated Local Search to Solve Vehicle Routing Problems}, author={Maximo, Vinicius Rosa}, year={2015}, publisher={Universidade Federal de S{\~a}o Paulo (UNIFESP)} }