Document details

Planeamento de rotas de distribuição

Author(s): Silva, João Carlos Lopes da

Date: 2016

Persistent ID: http://hdl.handle.net/10451/24881

Origin: Repositório da Universidade de Lisboa

Subject(s): Algoritmos exactos; Traveling Salesman Problem; Vehicle Routing Problem; Time Windows; Teses de mestrado - 2016; Departamento de Estatística e Investigação Operacional; Departamento de Estatística e Investigação Operacional; Departamento de Estatística e Investigação Operacional


Description

Considerando um conjunto de clientes que necessitam de ser visitados num intervalo de tempo previamente conhecido, o Traveling Salesman Problem with Time Windows (TSPTW) consiste em determinar uma rota de custo mínimo, com início e fim num depósito, garantindo que todos os clientes sejam visitados na respetiva janela temporal. São conhecidos os clientes a servir, os custos e tempos de deslocação entre cada par de clientes e entre cada cliente e o depósito, os tempos de serviço e a janela temporal de cada cliente, bem como o tempo e distância máxima da rota. A rota tem associado um custo resultante da soma dos custos de deslocação. Existem diversas variantes do problema, pelo que nesta dissertação são estudadas as variantes do TSPTW com vista à minimização da distância total percorrida com tempos de espera, minimização da duração da rota com e sem possibilidade de tempos de espera, no caso de o veículo chegar ao cliente antes do início da respetiva janela temporal. Para cada problema, é considerado uma variação da amplitude das janelas temporais de cada cliente a ser visitado. O TSPTW pertence à classe de problemas NP-difícil, por ser uma extensão do clássico TSP. Na presente dissertação são propostos dois modelos para o TSPTW: um modelo baseado nas restrições de Miller-Tucker-Zemlin (MTZ) e um outro Modelo de Fluxo Agregado (MFA). Pretende-se comparar os modelos propostos na resolução de problemas para as diversas variantes em estudo, bem como a comparação da qualidade da correspondente relaxação linear. Para comparar os modelos propostos, foram utilizadas instâncias de referência da literatura. Com um número de clientes a variar entre 20 a 200 e com diferentes amplitudes de janelas temporais para cada problema, os métodos utilizados permitiram resolver os problemas, em que não era conhecido o seu valor ótimo.

Given a set of customers who need to be visited in a previously known time window, the Traveling Salesman Problem with Time Windows (TSPTW) is to determine a minimum cost route, starting and ending in a depot, ensuring that all customers are visited in the them time window. All customers to serve are known, cost and travel times between each pair of customers and between each customer and the depot, service times and the time window of each client, as well as the maximum time and route distance. The route has an associated cost, resulting from the sum of the travel costs. There are several variants of the problem, so this thesis is to studied TSPTW variants with goal to minimizing the total distance traveled with waiting times, minimizing the duration of the route with and without possibility of waiting times, in case of the vehicle reach the client before the start of respective time window. For each problem, it is considered a variation of the length of time windows of each client to be visited. The TSPTW belongs to the class of NP-hard problems, being an extension of the classic TSP. In this thesis two models are proposed for TSPTW: a model based on the constraints of Miller-Tucker-Zemlin (MTZ) and another Aggregated Flow Model (MFA). Aims to compare the formulations in getting the solutions of the several variants in study, as well as the quality of linear relaxation. To compare the models, it were used the literature reference instances. With a number of customers range from 20 to 200 with different ranges and time windows for each problem, the methods allow solving problems, that it was not known the optimal solution.

Tese de mestrado, Estatística e Investigação Operacional, Universidade de Lisboa, Faculdade de Ciências, 2016

Document Type Master thesis
Language Portuguese
Advisor(s) Gouveia, Luís, 1957-; Paias, Ana Maria Duarte Silva Alves, 1963-
Contributor(s) Silva, João Carlos Lopes da
facebook logo  linkedin logo  twitter logo 
mendeley logo

Related documents

No related documents