Author(s): Toscano, Micaela Dinis Costa da Cruz
Date: 2017
Persistent ID: http://hdl.handle.net/10400.5/14686
Origin: Repositório da UTL
Subject(s): Problemas com procura nos arcos; problemas com procura nos arcos e restrições de capacidade; rotas periódicas; modelos de programação linear inteira mista; Arc Routing Problems; Capacitated Arc Routing Problems; periodic routes; mixed integer linear programming models
Mestrado em Métodos Quantitativos para a Decisão Económica e Empresarial
Este projeto, inicialmente sugerido pela Junta de Freguesia de Alvalade, visa a identificação de rotas para recolha periódica de resíduos de papeleiras. O modelo apresentado tem como objetivo minimizar o tempo total das rotas, tendo em conta a capacidade do veículo e a duração dos turnos dos trabalhadores, considerando ainda um horizonte de planeamento predefinido. As rotas são planeadas para cinco dias de trabalho com dois turnos diários. Foram estudados os problemas com procura nos arcos (ARP - Arc Routing Problems), uma vez que as papeleiras se encontram dispostas ao longo da rua, dando especial destaque aos problemas com restrições de capacidade (CARP - Capacitated Arc Routing Problems), tendo em atenção a capacidade limitada do veículo. O problema é formulado numa rede orientada, em que os nodos representam os cruzamentos ou entroncamentos e as ruas ou troços de ruas são representados pelos arcos, a cada um dos quais está associado o número de papeleiras a recolher. Os dados foram tratados no Microsoft Excel 2016 e o modelo foi testado com o Open Solver. Foram feitos testes com um exemplo de pequena dimensão e com instâncias de maior dimensão, utilizando dados reais.
This project, which was initially suggested by the Alvalade Parish Council, aims at identifying the routes for the periodic collection of litter bin waste. The model we present seeks to minimize the total routing time, according to the vehicles' capacity and the duration of the work shifts, during a predefined time horizon. The routes were planned considering five work days and two daily work shifts. Due to the fact that the litter bins are spread along the streets, we have studied Arc Routing Problems (ARP), with a special focus on Capacitated Arc Routing Problems (CARP), always keeping the vehicles' capacity in mind. The problem was formulated over a directed graph, where the nodes represent the intersections or junctions, and the arcs represent the streets or street segments. The number of litter bins demanding collection is associated to each arc. The data were processed on Microsoft Excel 2016 and the model was tested on the Open Solver. In order to assess the model, we first conducted tests using a small array of data, which then led us into further tests, where bigger instances based on real data were used.
