Exact and heuristic algorithms for covering routing problems = Algoritmos exatos e heurísticos para problemas de roteamento por cobertura
Lucas Porto Maziero
TESE
Inglês
T/UNICAMP M457e
[Algoritmos exatos e heurísticos para problemas de roteamento por cobertura]
Campinas, SP : [s.n.], 2023.
1 recurso online (105 p.) : il., digital, arquivo PDF.
Orientadores: Fábio Luiz Usberti, Celso Cavellucci
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação
Resumo: Os problemas de roteamento possuem diversas aplicações no mundo real, cada uma com restrições particulares como janelas de tempo, logística verde, disponibilidade de recursos e acessibilidade aos clientes. Quando se trata de disponibilidade de recursos e acessibilidade aos clientes,...
Ver mais
Resumo: Os problemas de roteamento possuem diversas aplicações no mundo real, cada uma com restrições particulares como janelas de tempo, logística verde, disponibilidade de recursos e acessibilidade aos clientes. Quando se trata de disponibilidade de recursos e acessibilidade aos clientes, problemas de roteamento por cobertura são propostos para lidar com cenários reais em que regiões de difícil acesso possuem clientes que precisam ser atendidos, mas não podem ser visitados in loco. Os problemas de roteamento por cobertura visam encontrar rotas de custo mínimo cujas demandas dos clientes são atendidas servindo-os localmente ou remotamente com um veículo. Nesta tese, são propostas metodologias computacionais para dois problemas de roteamento por cobertura: Covering Salesman Problem (CSP) e Multi-Depot Covering Tour Vehicle Routing Problem (MDCTVRP). Além disso, dois novos problemas de roteamento por cobertura são introduzidos: Capacitated Covering Salesman Problem (CCSP) e Electric Capacitated Covering Tour Problem (ECCTP). O CSP é uma generalização do Problema do Caixeiro Viajante em que o objetivo é encontrar um ciclo de custo mínimo tal que todos os vértices sejam visitados ou cobertos pelo ciclo. Nesta tese, desigualdades válidas da literatura são adaptadas para o CSP. Além disso, é proposto um novo conjunto de desigualdades válidas que se utilizam de aspectos únicos do problema. O primeiro branch-and-cut framework, com rotinas exatas e heurísticas para separar as desigualdades válidas, é proposto para resolver o CSP. Experimentos computacionais realizados em um benchmark de instâncias mostram que o framework proposto foi capaz de superar metodologias do estado-da-arte da literatura, além de obter soluções ótimas para diversas instâncias anteriormente não resolvidas. O CCSP é introduzido nesta tese com a intenção de abordar restrições de cobertura em problemas de roteamento de veículos capacitados. O objetivo do CCSP é atender os clientes usando uma frota de veículos, minimizando a distância percorrida pelos veículos. Os veículos podem atender os clientes localmente ou remotamente. Metodologias computacionais baseadas em Programação Linear Inteira (PLI) e na meta-heurística Biased Random-Key Genetic Algorithm (BRKGA) são propostas para resolver o CCSP. Além disso, uma formulação de PLI oriunda do CCSP é estendida para resolver o MDCTVRP. Os resultados dos experimentos computacionais mostram que a nova formulação para o MDCTVRP superou a melhor abordagem exata existente até então. Especificamente, soluções ótimas foram obtidas para vários instâncias anteriormente não resolvidas. No intuito de abordar um cenário real envolvendo logística verde, o ECCTP é introduzido nesta tese. O ECCTP é uma nova variante do problema de roteamento de veículos onde as demandas dos clientes podem ser atendidas por veículos elétricos com autonomia limitada e os veículos elétricos podem recarregar em postos de recargas alternativos. Os veículos podem atender os clientes localmente ou remotamente. Uma formulação de PLI mista e uma meta-heurística (BRKGA) são propostas para resolver o ECCTP. Com um benchmark de instâncias adaptadas da literatura, foram realizados experimentos computacionais com o objetivo de avaliar a eficácia da formulação e da meta-heurística
Ver menos
Abstract: Routing problems have several real-world applications, each with particular constraints such as time windows, green logistics, resources availability and customers accessibility. When it comes to resources availability and customers accessibility, covering routing problems are proposed to...
Ver mais
Abstract: Routing problems have several real-world applications, each with particular constraints such as time windows, green logistics, resources availability and customers accessibility. When it comes to resources availability and customers accessibility, covering routing problems are proposed to deal with real-world scenarios in which there are hard-to-reach regions containing customers that need to be served, but cannot be visited on site. The covering routing problems aim to find minimum cost routes such that the demands of the customers are satisfied by serving them locally or remotely with a vehicle. In this thesis, computational methodologies are proposed for two known covering routing problems: the Covering Salesman Problem (CSP) and the Multi-Depot Covering Tour Vehicle Routing Problem (MDCTVRP). Furthermore, two new covering routing problem are introduced: the Capacitated Covering Salesman Problem (CCSP) and the Electric Capacitated Covering Tour Problem (ECCTP). The CSP is a generalization of the Traveling Salesman Problem in which the objective is to find a minimum cost tour such that every vertex is visited or covered by the tour. In this thesis, valid inequalities from the literature are adapted to the CSP. In addition, a novel set of valid inequalities is proposed, which make use of unique aspects of the problem. The first branch-and-cut framework, with exact and heuristic routines to separate the valid inequalities, is proposed to solve the CSP. Computational experiments conducted on benchmark of instances show that the proposed framework was able to outperform state-of-the-art methodologies from literature, in addition to having proven optimal solutions for several previously unresolved instances. The CCSP is introduced in this thesis with the intention of addressing covering constraints in capacitated vehicle routing problems. The objective of the CCSP is to serve customers using a fleet of vehicles, minimizing the distance traversed by the vehicles. The vehicles can serve customers locally or remotely. Computational methodologies based on Integer Linear Programming (ILP) and Biased Random-Key Genetic Algorithm (BRKGA) metaheuristic are proposed to solve the CCSP. Moreover, a CCSP ILP formulation is extended to solve the MDCTVRP. The results of the computational experiments show that the new formulation for the MDCTVRP outperformed the best existing exact approach so far. Specifically, optimal solutions were obtained for several previously unsolved instances. In order to tackle a real-world scenario involving green logistics, the ECCTP is introduced in this thesis. The ECCTP is a new variant of the vehicle routing problem where customers demands can be served by a electric vehicles with limited autonomy and the electric vehicles can recharge at alternative fuel stations. The vehicles can serve customers locally or remotely. A mixed ILP formulation and a (BRKGA) metaheuristic are proposed to solve the ECCTP. With a benchmark of instances adapted from the literature, computational experiments were conducted with the purpose of evaluating the effectiveness of the formulation and metaheuristic
Ver menos
Aberto
Usberti, Fábio Luiz, 1982-
Orientador
Cavellucci, Celso, 1951-
Coorientador
Castellucci, Pedro Belin
Avaliador
Hokama, Pedro Henrique Del Bianco, 1986-
Avaliador
Oliveira, Washington Alves de, 1977-
Avaliador
Poldi, Kelly Cristina, 1979-
Avaliador
Exact and heuristic algorithms for covering routing problems = Algoritmos exatos e heurísticos para problemas de roteamento por cobertura
Lucas Porto Maziero
Exact and heuristic algorithms for covering routing problems = Algoritmos exatos e heurísticos para problemas de roteamento por cobertura
Lucas Porto Maziero