| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 4.24 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
Nos últimos anos, o problema da last-mile delivery sofreu uma transformação notável,
impulsionada principalmente pelo crescimento exponencial do comércio online. O aumento das
compras online e a comodidade que estas oferecem impulsionaram o sector da logística a entrar
numa nova era onde a criação e desenvolvimento de soluções inovadoras de otimização de rotas
é imperativo. Atualmente, a última etapa da cadeia de abastecimento tornou-se um ponto fulcral
para as empresas que pretendem satisfazer as altas expectativas dos clientes quanto a opções de
entrega. À medida que o ecossistema global de comércio online continua a evoluir, a capacidade
de simplificar as operações da last-mile delivery e de proporcionar experiências positivas aos
clientes torna-se cada vez mais um fator diferenciador crítico para as empresas.
Esta dissertação tem como objetivo colmatar a lacuna existente entre as rotas programadas e as
rotas efetivamente percorridas pelos condutores, que são muitas vezes obrigados a efetuar
mudanças em tempo real para se adaptarem às realidades da estrada. Esta questão foi destacada
pelo Amazon Last-Mile Routing Research Challenge 2021, que visava estimular os investigadores a
melhorar a qualidade dos itinerários programados, tornando-os mais realistas.
A solução para esta temática foi conseguida através do desenvolvimento de uma abordagem
híbrida que explora algoritmos de machine learning e otimiza automaticamente os seus
hiperparâmetros. Esta solução aprende as combinações ótimas das zonas com base em padrões
extraídos de sequências históricas. Além disso, a solução demonstra a capacidade de aplicar
eficazmente este conhecimento a rotas desconhecidas, melhorando significativamente o
planeamento e a adaptação de rotas a cenários reais.
O principal objetivo desta solução é prever sequências de zonas em vez de paragens individuais.
Só depois da sequência de zonas ter sido determinada é que o algoritmo procede ao
sequenciamento das paragens dentro de cada zona. Foi utilizado um processo sistemático,
começando com o pré-processamento do conjunto de dados com o objetivo de o preparar para as
fases subsequentes. A etapa seguinte recorreu a um algoritmo de Prediction by Partial Matching
para identificar as combinações de zonas ótimas. Na fase subsequente, o conhecimento obtido foi
utilizado para calcular sequências de zonas para rotas inexploradas, utilizando um algoritmo de
Rollout. Finalmente, foi implementado o Lin-Kernighan-Helsgaun solver para efetuar o
sequenciamento zona a zona, assegurando a integridade da sequência de zonas. Todas estas
etapas críticas estão perfeitamente integradas num pipeline repetível que ajusta
automaticamente os valores do hiperparâmetro do algoritmo Prediction by Partial Matching.
Os resultados obtidos são muito satisfatórios e indicam que a solução desenvolvida é eficaz na
previsão de rotas efetivamente percorridas. A avaliação global foi de 0,0727, demonstrando um
desempenho robusto. A otimização do hiperparâmetro resultou em melhorias em 85% dos casos,
que variam entre 0,0001 e 0,0006 e possuem uma média de 0,00021, confirmando ainda mais a
sua eficácia. Estes resultados realçam a capacidade da solução tirar partido do conhecimento dos
condutores, salientando o seu valor prático e estabelecendo-a como uma ferramenta fiável na
geração de previsões de elevada qualidade.
In recent years, the landscape of last-mile delivery has undergone a remarkable transformation, driven primarily by the exponential growth of e-commerce. The surge in online shopping and the convenience it offers have propelled the logistics industry into a new era of innovation and adaptation. Today, the last leg of the supply chain has become a pivotal focal point for businesses aiming to meet customer expectations for faster, more reliable, and flexible delivery options. This transformation fueled the necessity of advanced route optimization algorithms, real-time tracking solutions, and novel approaches. As the global e-commerce ecosystem continues to evolve, the ability to streamline last-mile delivery operations and provide seamless customer experiences becomes a critical differentiator for businesses. This dissertation aims to address a common gap between programmed routes and the routes drivers take. Drivers are often forced to make on-the-fly adjustments to accommodate the dynamic realities of the road. This pressing issue was mainly highlighted by the 2021 Amazon Last Mile Routing Research Challenge, which aimed to stimulate researchers to improve the quality of programmed routes by making them more realistic. The solution to this problem has been achieved by developing a sophisticated hybrid approach that harnesses the power of machine learning algorithms and automatically optimizes its hyperparameters. These algorithms can learn optimal zone combinations based on patterns extracted from historical routes. Furthermore, the solution demonstrates the ability to effectively apply this learned knowledge to previously unknown routes, significantly improving route planning and adaptation in real-world scenarios. The main principle of this solution is to predict zone sequences rather than individual stops. Only after the zone sequence has been determined does the algorithm proceed to intra-zone routing. A systematic process was used to achieve this approach, starting with pre-processing the dataset to prepare it for the subsequent phases. The following step used a Prediction by Partial Matching algorithm to identify the most optimal zone combinations. In the subsequent phase, using a Rollout Algorithm the accumulated knowledge was used to compute zone sequences for previously unexplored routes. Finally, a Lin-Kernighan-Helsgaun solver was implemented to perform zone-to-zone routing, ensuring the integrity of the zone sequence. All these critical steps are seamlessly integrated into a repeatable pipeline that automatically fine-tunes the hyperparameter values of the Prediction by Partial Matching algorithm. The results obtained are very promising, demonstrating the effectiveness of the solution in predicting real-world routes. The overall score was 0.0727, demonstrating its robust performance. The hyperparameter optimization resulted in improvements in 85% of the cases, with improvements ranging from 0.0001 to 0.0006 and an average improvement of 0.00021, further confirming the strength of the solution. These results underscore the solution's ability to leverage the expertise of the drivers, underscoring its practical value and establishing it as a reliable tool for generating high-quality insights and predictions across multiple domains.
In recent years, the landscape of last-mile delivery has undergone a remarkable transformation, driven primarily by the exponential growth of e-commerce. The surge in online shopping and the convenience it offers have propelled the logistics industry into a new era of innovation and adaptation. Today, the last leg of the supply chain has become a pivotal focal point for businesses aiming to meet customer expectations for faster, more reliable, and flexible delivery options. This transformation fueled the necessity of advanced route optimization algorithms, real-time tracking solutions, and novel approaches. As the global e-commerce ecosystem continues to evolve, the ability to streamline last-mile delivery operations and provide seamless customer experiences becomes a critical differentiator for businesses. This dissertation aims to address a common gap between programmed routes and the routes drivers take. Drivers are often forced to make on-the-fly adjustments to accommodate the dynamic realities of the road. This pressing issue was mainly highlighted by the 2021 Amazon Last Mile Routing Research Challenge, which aimed to stimulate researchers to improve the quality of programmed routes by making them more realistic. The solution to this problem has been achieved by developing a sophisticated hybrid approach that harnesses the power of machine learning algorithms and automatically optimizes its hyperparameters. These algorithms can learn optimal zone combinations based on patterns extracted from historical routes. Furthermore, the solution demonstrates the ability to effectively apply this learned knowledge to previously unknown routes, significantly improving route planning and adaptation in real-world scenarios. The main principle of this solution is to predict zone sequences rather than individual stops. Only after the zone sequence has been determined does the algorithm proceed to intra-zone routing. A systematic process was used to achieve this approach, starting with pre-processing the dataset to prepare it for the subsequent phases. The following step used a Prediction by Partial Matching algorithm to identify the most optimal zone combinations. In the subsequent phase, using a Rollout Algorithm the accumulated knowledge was used to compute zone sequences for previously unexplored routes. Finally, a Lin-Kernighan-Helsgaun solver was implemented to perform zone-to-zone routing, ensuring the integrity of the zone sequence. All these critical steps are seamlessly integrated into a repeatable pipeline that automatically fine-tunes the hyperparameter values of the Prediction by Partial Matching algorithm. The results obtained are very promising, demonstrating the effectiveness of the solution in predicting real-world routes. The overall score was 0.0727, demonstrating its robust performance. The hyperparameter optimization resulted in improvements in 85% of the cases, with improvements ranging from 0.0001 to 0.0006 and an average improvement of 0.00021, further confirming the strength of the solution. These results underscore the solution's ability to leverage the expertise of the drivers, underscoring its practical value and establishing it as a reliable tool for generating high-quality insights and predictions across multiple domains.
Description
Keywords
Last-mile delivery VRP TSP Machine Learning Hybrid Solutions PPM Rollout Algorithm