| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 6.09 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
Districting can reduce the complexities of delivery problems by segmenting its dimensions while facilitating drivers’ familiarity with their work areas, fostering personal connections with customers, and enhancing satisfaction. This dissertation presents and evaluates multiple heuristics for route creation intending to identify the most efficient method for intra- and inter-district routing. Three types of distances, two TSP-to-SHPP converters, and three types of interdistrict connectors were tested, resulting in a total of 18 distinct variants from the combination of these components. Out of 18 tested variants, the best-performing developed approach used a LinKhernigan-based heuristic, later converting it to a Shortest Hamiltonian Path in each district, creating inter-district connections to a hypothetical medoid in the next district to visit and utilizing asymmetric road distances. The obtained results were satisfactory, and the best components for route creation were identified,
allowing for the continuation of the analysis of the model’s adaptability to day-to-day implementation in a further project. The models were developed and tested using real-world data from a parcel delivery company operating in the Porto metropolitan area of Portugal.
O processo de districting pode reduzir a complexidade de problems de parcel delivery, particularmente problemas de Last-Mile Routing, ao segmentar suas dimensões, facilitando a familiaridade dos motoristas com suas áreas de trabalho, fomentando conexões pessoais com os clientes e aumentando a satisfação. Esta dissertação apresenta e avalia múltiplas heurísticas de criação de rotas com o objetivo de identificar o método mais eficiente para roteamento intra e inter-district. Foram testados três tipos de distâncias, dois conversores TSP-para-SHPP e três tipos de conectores inter-districts, tendo a combinação desses componentes resultado num total de 18 variantes distintas. Das 18 variantes testadas, a abordagem desenvolvida com melhor desempenho utilizou uma heuristica Lin-Kernighan, posteriormente convertida num Shortest Hamiltonian Path em cada distrito, criando conexões inter-district com um medoide hipotético no próximo district a visitar e utilizando distâncias rodoviárias assimétricas. Os resultados obtidos foram satisfatórios, e os melhores componentes para a criação de rotas foram identificados, permitindo a continuidade da análise da adaptabilidade do modelo à implementação diária num projeto futuro. Os modelos foram desenvolvidos e testados usando dados práticos relativos às rotas de uma empresa de entrega de encomendas operando na área metropolitana do Porto, em Portugal.
O processo de districting pode reduzir a complexidade de problems de parcel delivery, particularmente problemas de Last-Mile Routing, ao segmentar suas dimensões, facilitando a familiaridade dos motoristas com suas áreas de trabalho, fomentando conexões pessoais com os clientes e aumentando a satisfação. Esta dissertação apresenta e avalia múltiplas heurísticas de criação de rotas com o objetivo de identificar o método mais eficiente para roteamento intra e inter-district. Foram testados três tipos de distâncias, dois conversores TSP-para-SHPP e três tipos de conectores inter-districts, tendo a combinação desses componentes resultado num total de 18 variantes distintas. Das 18 variantes testadas, a abordagem desenvolvida com melhor desempenho utilizou uma heuristica Lin-Kernighan, posteriormente convertida num Shortest Hamiltonian Path em cada distrito, criando conexões inter-district com um medoide hipotético no próximo district a visitar e utilizando distâncias rodoviárias assimétricas. Os resultados obtidos foram satisfatórios, e os melhores componentes para a criação de rotas foram identificados, permitindo a continuidade da análise da adaptabilidade do modelo à implementação diária num projeto futuro. Os modelos foram desenvolvidos e testados usando dados práticos relativos às rotas de uma empresa de entrega de encomendas operando na área metropolitana do Porto, em Portugal.
Description
Keywords
Districting Last-Mile Delivery Shortest Hamiltonian Path Problem Routing