Vehicle routing problem with delivery and pickup

Abstract

This project, on Vehicle Routing Problem with Delivery and Pickup (VRPDP) aimed at determining the factors that contribute to the quality of a solution and checking the effect of varying the relative sizes of delivery demands to the size of pickup demands. This work was done with a dataset generated by a random uniform distribution of complete graphs with 15, 20, and 25 nodes, with varying relative sizes of the demands at each node to create four scenarios, Indifferent relative sizes of delivery to pickup, Large delivery demand relative to pickup demand, small delivery relative to pickup demand and delivery demand relatively equal to pick up demand at each customer. Three distinct problems were created using these scenarios. A model was created using flow formulation on the GurobiPy solver. The three problems were solved using the model and the result was tabulated. Observations on the table were thoroughly examined and relevant inferences were made on the factors that influence the quality of the VRPDP solution and the effect of varying the relative sizes of the demands.

Este projeto, sobre Problema de Planeamento de Rotas de Veículos com Entrega e Recolha (VRPDP), teve como objetivo estudar e determinar diversos fatores que possam contribuir para a qualidade de uma solução do problema, houve particular atenção em verificar o efeito que a variação nas quantidades de procura (quantidades a entregar) e de recolha têm nas soluções. Este trabalho foi realizado usando um conjunto de dados gerados aleatoriamente, através de uma distribuição uniforme, que permitiu construir grafos completos com 15, 20 e 25 vértices, gerar os seus custos de ligações e também gerar diferentes quantidades de procura e de recolha de forma a criar quatro cenários diferentes. Um cenário tem quantidades de procura e recolha sem qualquer relacionamento, outro cujos valores de procura s˜ao sempre superiores aos da recolha, outro cujos valores de recolha são sempre superiores aos da procura e, finalmente, o quarto cenário no qual os valores para entrega e recolha são iguais. São propostas formulações em Programação Inteira Mista para o Problema de Planeamento de Rotas de Veículos com Entrega e Recolha (VRPDP) usando diferentes conjuntos de restrições para formulações de fluxos. Um modelo foi construído, em Gurobipy, para ser usado no solver Gurobi. Os problemas que foram resolvidos utilizando o modelo e os resultados obtidos para os diversos cenários foram resumidos em tabelas. As tabelas foram examinadas minuciosamente e inferências relevantes foram realizadas sobre os fatores que influenciam a qualidade da solução VRPDP e o efeito da variação das quantidades relativas das procuras e das recolhas.