Dissertação
{en_GB=Bi-Objective Districting and Routing Problems: A Comparison of Models} {} EVALUATED
{pt=Sectorização e roteamento são cruciais na otimização de sistemas de transporte e complexas operações logísticas. Ao combinar essas estratégias, as empresas são capazes de eficientemente entregar mercadorias numa escala global, reduzindo os custos e melhorando os níveis de serviço. A relevância do estudo está na proposta de um método exato para resolver um problema bi-objectivo que envolve decisões de sectorização e roteamento. O problema abordado nesta tese envolve a divisão de um conjunto de clientes em distritos e a determinação das rotas para satisfazer as procuras. Este problema é designado Capacitated Vehicle Routing and Districting problem (CVRDP), combinando o Capacitated Vehicle Routing problem (CVRP) com distritos. Cada distrito está associado a uma rota, que começa e termina no único depósito, visitando os clientes do distrito. Os veículos transportam mercadoria, respeitando as restrições de capacidade. O problema bi-objectivo visa minimizar o tempo total de viagem e a dispersão dos distritos. Quatro modelos MILP são propostos, diferindo na sua abordagem para evitar as subtours. Esses modelos incluem o Improved Miller-Tucker-Zemlin (MTZ) e Single Commodity Flow (SCF), tanto desagregados como agregados. O estudo utiliza o augmented ε-constraint para encontrar soluções não dominadas da frente de Pareto (Almeida et al., 2022). Instâncias adaptadas da literatura são usadas numa análise de quatro fases, onde o número de distritos é pré-determinado. O modelo SCF-Desagregado consistentemente supera os demais em instâncias com tamanhos maiores. Considerando um problema uni-objectivo, este modelo também se destaca, especificamente em termos de alcançar distritos compactos e minimizar o tempo total de viagem., en=Districting and routing are crucial components in optimising transportation systems and complex logistics operations. Combining these components helps companies efficiently deliver goods worldwide, reducing costs and improving service levels. The present study contributes to the field by proposing an exact solution method for addressing a bi-objective problem, involving both districting and routing decisions. The problem tackled in this thesis involves partitioning a set of customers into districts and determining routes to meet their demands. It is known as the Capacitated Vehicle Routing and Districting Problem (CVRDP), which combines the Capacitated Vehicle Routing Problem (CVRP) with districting. There is one route per district. Every route starts and ends at a single depot, visiting the customers of the district exactly once. Vehicles must meet customer demands while respecting capacity constraints. The bi-objective problem aims to minimise the total travel time and district's dispersion. Four MILP models are proposed, differing in their approach to prevent subtours. These models include the Improved Miller-Tucker-Zemlin (MTZ) and Single Commodity Flow (SCF) models, with both the disaggregated and aggregated versions. The study applies the augmented ε-constraint method to find non-dominated solutions of the Pareto front (Almeida et al., 2022). In the computational experiments, adapted instances from the literature are used in a four-phase analysis, where the number of districts is predetermined. Overall, the disaggregated SCF model outperforms the other models. This model also stands out as the best option for optimising a single-objective problem, specifically in terms of achieving compact districts and minimising the total travel time.}
outubro 23, 2023, 10:30
Orientação
ORIENTADOR
Departamento de Engenharia e Gestão (DEG)
Professor Catedrático
