Contributions to the single and multiple vehicle routing problems with deliveries and selective pickups

• Ano de defesa: 2012
• Autor(a) principal: Bruck, Bruno Petrato
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal de Viçosa
• Palavras-chave em Português: Pesquisa operacional; Otimização combinatória; Logística; Otimização matemática; Ciência da Computação
• Link de acesso: http://www.locus.ufv.br/handle/123456789/7685

The Single Vehicle Routing Problem with Deliveries and Selective Pickups (SVR- PDSP) is a variation of the classical Vehicle Routing Problem (VRP) that has received limited attention. It has many practical applications in reverse logistic contexts, such as in drink factories, which besides having to supply stores and supermarkets with full bottles, have to pickup empty bottles, returning them to the factory in order to be clean and refilled. There is also the Multiple Vehicle Routing Problem with Deliv- eries and Selective Pickups (MVRPDSP), which shares the same applications of the SVRPDSP. It is even more practical, since in real world cases it is commom having multiple vehicles. However, regarding the MVRPDSP, to our knowledge, there is not a single approach in the literature. In the present work, for the SVRPDSP, in terms of heuristic approaches, we propose a Hybrid Evolutionary Algorithm (EA) which makes use of a data mining strategy in its crossover and mutation phases; and a Variable Neighborhood Descent Algorithm (VND). In addition we also propose a Branch&Cut algorithm for an exact formulation of the literature and a novel formulation. Regarding the MVRPDSP we propose two formulations based on the ones of the single vehicle version of this problem and a hybrid cluster-first constructive heuristic. Experimental results show that the proposed formulation for the SVRPDSP outperforms by far the others from the literature, finding optimal solutions for more than half the instances of the benchmark used in the literature. For the MVRPDSP we created a benchmark of instances and report several good solutions, including some optimals.