Dissertação
{en_GB=Optimization of Order Assignment to Couriers for On-demand Delivery} {} EVALUATED
{pt=A economia on-demand tem moldado hábitos dos consumidores, que exigem entregas mais rápidas. As entregas instantâneas ganharam popularidade no transporte de refeições para áreas urbanas, e o espetro de produtos disponíveis para encomendar tem-se expandido. As plataformas que disponibilizam estes serviços dependem de estafetas crowdsourced, que usam veículos pessoais, originando frotas heterogéneas. Verifica-se uma intensa concorrência para reter consumidores e estafetas. Assim, é vital desenvolver modelos de otimização que integrem múltiplos tipos de veículos, capazes de produzir atribuições em tempo real para satisfazer expetativas de consumidores e estafetas. É desenvolvido um modelo de otimização para resolver o problema de atribuição com restrições de veículos, recorrendo aos algoritmos Jonker-Vogenant e Branch-and-Cut. O modelo matemático é inserido num framework dinâmico, que continuamente o resolve, enquanto controla chegadas de pedidos, turnos e atualiza posicionamentos. O modelo contempla o trânsito e limites de velocidade para diferentes tipos de veículos. Para além deste modelo, é investigada a implementação de políticas – política de atribuição e política de bicicletas – para melhorar o desempenho em diferentes métricas. Com base em instâncias reais, o modelo proposto considerando a política de atribuição alcança uma redução no tempo de entrega de, aproximadamente, 4,5% e um aumento de 9,6% na utilização equilibrada de estafetas em comparação com a atribuição real, melhorando a solução na perspetiva dos consumidores e estafetas. A política de bicicletas melhora a utilização equilibrada de estafetas em 4pp, à custa de um aumento de 0,3% no tempo de entrega em comparação com o modelo base., en=The on-demand economy has shaped the habits of consumers, who now expect faster deliveries. Instant deliveries gained popularity for carrying meals to urban areas, and the spectrum of products available to order has broadened. The platforms that provide these services rely on crowdsourced couriers, who use their personal vehicles, resulting in a heterogeneous fleet. Companies experience intense competition to retain both customers and couriers. Hence, it is vital to develop superior optimization models integrating multiple types of vehicles, capable of producing assignments in real-time to meet customers and couriers’ expectations. An optimization model is developed to solve the assignment problem with vehicle restrictions using the Jonker-Vogenant and Branch-and-Cut algorithms. The mathematical model is inserted into a dynamic framework that continuously solves it, while controlling the arrivals of orders, couriers’ shifts and performing position updates. The model also contemplates dynamic congestion and regional speed limits for different types of vehicles. Besides a myopic assignment approach, the implementation of policies is investigated – extended assignment policy and bicycle policy – in order to improve performance along different metrics. Based on real-world instances, the proposed model with the extended assignment policy achieves a decrease in total delivery time of approximately 4.5% and an increase of 9.6% in balanced courier utilization when compared with the real assignment, thus improving the solution from the customer and couriers’ perspectives. The bicycle policy achieves an increase in balanced courier utilization of 3pp, at the expense of a 0.3% increase in delivery time compared to the baseline model.}
dezembro 5, 2022, 15:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
Departamento de Engenharia e Gestão (DEG)
Professor Associado