Bi-objective robust optimization for the pollution-routing problem under uncertainty in travel time and demand

Abstract

Nos últimos anos, o problema de roteamento de veículos e o seu impacto ambiental tornou-se um ponto de interesse para as empresas logísticas e investigadores, que continuam a propor novas e mais completas formulações para este problema para melhor refletir o contexto real da operação logísticaO interesse das empresas em ter modelos e algoritmos prontos a utilizar e dedicados a problemas de planeamento de rotas é triplo: não só podem otimizar o seu sistema de transporte, reduzindo a mão-de-obra necessária, melhorando a satisfação do cliente e reduzindo os custos, mas também reduzir as preocupações causadas pela gestão de complexas redes de veículos e clientes. Contudo, a maioria dos modelos assume que a informação é perfeita, ou seja, que os dados fornecidos ao modelo se materializarão exatamente, quer sejam as exigências do cliente, velocidades de viagem, tempos de viagem, consumo de combustível (entre outros). As soluções fornecidas pelos modelos e algoritmos refletem essa suposição, mas as soluções dadas só têm garantia de funcionar se o mundo real se comportar exatamente como o esperado, o que raramente acontece. Essa incerteza inerente aos dados levou ao aumento da investigação em abordagens capazes de lidar com dados incertos, uma vez que estes refletem melhor as condições do mundo real, e fornecem resultados mais utilizáveis. Nesta dissertação, estudamos o Problema de Rotas com Poluição, e propomos dois modelos que consideram a incerteza nos tempos de viagem e na procura, para os casos em que os custos ambientais e operacionais são uma preocupação, e estudamos os compromissos entre estes dois aspetos de avaliação. Verificamos que os atrasos na rota têm um impacto muito mais pronunciado nas emissões de veículos, nos custos operacionais, e nos tempos de resolução de problemas do que o aumento da procura. Mostramos também o impacto que os sistemas start-stop têm nos custos de operação, e como os reduzem sem esforço computacional extra. A interação entre o aumento da procura e os atrasos raramente é pronunciada, e, enquanto o aumento da procura tende apenas a piorar o desempenho ambiental, os atrasos conduzem a custos mais elevados e pior desempenho, devido ao aumento do salário do condutor, e ao aumento da velocidade dos veículos, o que leva a um aumento emissões.

In recent years, the Vehicle Routing Problem and its environmental impact have become a point of interest for logistic companies and researchers, that propose newer and more complete formulations to better reflect the real context of logistic operation. The interest of companies in having off-the-shelf models and algorithms devoted to route planning problems is three-fold: not only can they optimize their transport system, reducing necessary manpower, improving customer satisfaction, and reducing costs, but also reduce the concerns caused by managing such complex networks of vehicles and customers. However, most models assume the information is perfect, that is, that the data provided to the model will materialize exactly, be it customer demands, travel speeds, travel times, fuel consumption (among others). The solutions provided by the models and algorithms reflect that assumption, but the solutions given are only guaranteed to work if the real world behaves exactly as expected, which is seldom the case. That inherent uncertainty in the data has led to increasing research in approaches able to cope with uncertain data, as they better reflect real world conditions, and provide more usable results. In this dissertation, we study the Pollution Routing Problem and propose two models that consider uncertainty in travel times and demand, for cases where environmental and operational costs are a concern and study the tradeoffs between the two. We study the impact that uncertain conditions have on solutions, and what trade-offs may exist between minimizing costs and minimizing emissions.We find delays in route have a much more pronounced impact in vehicle emissions, operation costs, and in problem solving times than increase in demand. We also show the impact start-stop systems have on operation costs, and how they reduce them without requiring additional computational effort. The interaction between demand increase and delays is rarely pronounced, and, while demand increase tends to only worsen environmental performance, delays drive higher costs and worse performance, due to increase in driver pay, and increase in vehicle speeds, which leads to more emissions.