Στόχος της παρούσας εργασίας, είναι η σχεδίαση και η υλοποίηση ενός προγράμματος, το οποίο θα υπολογίζει την βέλτιστη διαδρομή μεταξύ δύο σημείων στην πόλη της Πάτρας, το οποία συνδέονται με αστική συγκοινωνία. Στα πλαίσια της εργασίας αυτής, συγκεντρώθηκαν τα δεδομένα που αφορούν τις διαδρομές των λεωφορείων, τα δρομολόγια και οι χρόνοι μετάβασης. Στη συνέχεια, τα δεδομένα αυτά κωδικοποιήθηκαν κατάλληλα και δημιουργήθηκε πρόγραμμα το οποίο θα τα χρησιμοποιεί για να υπολογίζει την βέλτιστη δρομολόγηση μεταξύ δύο σημείων που θα επιλέγει ο χρήστης. Το πρόγραμμα παρέχεται και ως ανεξάρτητη εκτελέσιμη εφαρμογή αλλά και ως υπηρεσία web, με δυνατότητα εγκατάστασης στον web server του εργαστηρίου. / The main purpose of this Diploma Thesis is the development of a computer program, that is going to estimate the best route between two city points in the city of Patras. These two places are accessible by Patras public transportation system. For this project, we gathered all the appropriate data that are related with the bus routes, the routes, and the time between subsequent bus stop. Furthermore, these data were encoded in such a way, that they are accessible by our program, which calculates the best route between two points chosen by a user. This program was developed as an independent executable application but also as a web service, with the ability to be uploaded in the laboratory’s web server.

[pt] Com a era da globalização e a introdução da filosofia de Gestão da Cadeia de Suprimentos, os clientes têm se tornado cada vez mais exigentes no que diz respeito à qualidade e prazos de entrega, gerando uma competitividade crescente e uma busca por serviços cada vez mais customizados que, para as empresas de distribuição de produtos, tem se tornado um fator cada vez mais importante na obtenção de vantagem competitiva e conquista de fatias cada vez maiores do mercado. Nesse sentido, muitas empresas de transporte têm tentado dar maior confiabilidade, mais velocidade e flexibilidade, buscando obter maior eficiência e pontualidade nas tarefas de entrega e/ou coleta; um melhor aproveitamento da frota e dos motoristas; menores tempos de ciclo; melhor planejamento das rotas, gerando assim sensíveis reduções de custos operacionais, melhoria da imagem da empresa no mercado e, em função disso, uma conquista cada vez maior de mercado. Nesse sentido, de modo a obter excelência nos processos de distribuição física, muitas empresas têm adquirido os chamados sistemas de roteirizarão e programação de veículos ou, simplesmente, roteirizadores. Dado o crescimento na utilização de roteirizadores para redução de custos operacionais e a possibilidade por parte do autor de participar da implementação dessa tecnologia em uma empresa, os objetivos dessa dissertação são: Descrever a operação da Empresa Alfa onde foi realizada a implementação do roteirizador de veículos e a apresentação do processo de implementação do roteirizador na operação. Como o autor fez parte da implementação do roteirizador na Empresa Alfa, a metodologia utilizada para a elaboração desse trabalho incluiu: pesquisa bibliográfica, visitas in loco e entrevistas não estruturadas junto aos envolvidos na operação. O resultado desta dissertação é uma análise da operação da Empresa Alfa durante a implementação do roteirizador, mostrando seus pontos positivos e suas dificuldades extraídos apos finalizado o processo de implementação. / [en] Nowadays with the globalization and the introduction of the Supply chain management philosophy, the customers become more demanding in order to get better quality in delivery time, increasing competitiveness and a search for customized services that, for distribution companies, it has become the most important factor in order to get competitive advantage and to increase the market share. In accordance with these ideas, many distribution companies have tried to improve the reliability, speed and flexibility, in order to get higher efficiency and punctuality in the deliveries; better fleet and drivers utilization; lower time to planning routes, generating cost reduction, improvements of the company`s image in the market, and higher market share. Trying to get excellence in distribution process, many companies have acquired the routing and scheduling systems. Due to the growth of routing systems use and the possibility for the author to participate in an implementation of this technology in a company, the objectives of this work are: to describe the operation of the Alpha Company`s where the implementation has been done; and present the routing system implementation process. Since the author was part of the team in the implementation of routing system in the Alpha Company, the methodology used for the elaboration of this work included: bibliographical research, visits in loco to the Alpha Company`s operations and non structuralized interviews with the involved parts in the operation. As a result of this work, we have an analysis of the operation during the implementation of the Routing System in line with the main results getting after finished the implementation process.

[pt] O Problema de Roteirização de Veículos (Vehicle Routing Problem - VRP) é um problema clássico combinatório bem conhecido. Este trabalho apresenta um novo fator no modelo de otimização matemática de otimização do VRP, considerando restrições que abordam a probabilidade de roubo de cargas nas regiões visitadas, além das restrições tradicionais, tais como o número de veículos, janelas de tempo, a capacidade do veículo e tempo de ciclo dos veículos. O modelo desenvolvido é testado em um estudo de caso real, considerando uma empresa de distribuição de produtos farmacêuticos do Rio de Janeiro. As soluções de rota com e sem risco de roubo de carga são comparadas. O modelo é resolvido usando o software AIMMS, para análises com instância pequenas, e resolvidas executando a Metaheurística Simulated Annealing, para o estudo de caso, onde se utiliza de duas instâncias. / [en] The Vehicle Routing Problem (VRP) is a classic well-known combinatorial problem. This paper introduces a new factor in the VRP mathematical optimization model, considering restrictions that address the probability of cargo theft in the regions visited, beyond the traditional constraints such as the number of vehicles, time windows, the capacity of the vehicle and the vehicle s cycle time. The paper proposes a mixed integer linear model that minimizes total transportation costs and cargo theft costs. The model is tested in a real-life case study, a company that distributes pharmaceutical products in Rio de Janeiro. The route solutions with and without cargo theft risk are compared. The model is solved using AIMMS software for analysis with small instance, and resolved by running the Simulated Annealing Metaheuristic, for the case study, which uses two instances.

[pt] Esta pesquisa trata de duas variantes do conhecido Problema de Roteirização de Veículos com Estoque (do inglês Inventory Routing Problem – IRP). O problema nasce num contexto de um sistema de Vendor Managed Inventory (VMI) no qual o fornecedor é responsável pela gestão de estoques do cliente. Tal problema é a junção dos problemas de transporte e gestão de estoques, que correspondem aos maiores custos em uma operação logística. Destarte este trabalho apresenta um modelo matemático para uma variante do IRP que considera que o fornecedor tem clientes dentro e fora do sistema de VMI. Este caso surge quando para alguns clientes não é interessante a realização do controle de seus estoques dentro do sistema de VMI, somente o atendimento de suas demandas. Além disto, o modelo contempla três diferentes tipos de políticas de gestão de estoques e é capaz de lidar com casos contendo vários períodos e vários veículos. Após sua elaboração, o modelo foi validado em instâncias do IRP, do Problema de Roteamento de Veículos (do inglês Capacitated Vehicle Routing Problem - CVRP) e instâncias próprias para a variante. Foram realizados também estudos sobre os impactos das diferentes políticas de gestão de estoques. Além do modelo matemático, foi desenvolvida uma meta-heurística híbrida que resolve uma variante do IRP considerando vários períodos e vários veículos. Cada movimento considerado durante a meta-heurística é divido em duas etapas, a primeira sendo a modificação da posição de um ou mais clientes nos veículos e períodos e uma segunda etapa que resolve de forma exata um Problema de Fluxo Máximo a Custo Mínimo para a atribuição ótima do volume de carga transportada para cada cliente por cada veículo em cada período. Esta abordagem é então testada em instâncias clássicas para esta variante do IRP, obtendo resultados que comprovam a eficiência do algoritmo. / [en] This research deals with two variants of the Inventory Routing Problem (IRP). This problem comes from the context of a Vendor Managed Inventory (VMI) system in which the vendor is responsible for managing the customer s inventory. It is the combination of transportation and inventory management problems, which correspond to the higher costs in a logistics operation. Hence, this paper presents a mathematical model for an IRP variant, in which the vendor has customers inside and outside the VMI system. This situation is presented when it is not interesting to manage the inventories of some clients within the VMI system, resulting only in meeting their demands. In addition, the model considers three different types of stock management policies and it can comprehend multiple periods and multiple vehicles. After its modelling, the model was validated using IRP instaces, the Vehicle Routing Problem (CVRP) and specific instances for this variant. The impacts of different inventory management policies were also analyzed. In addition to the mathematical model, a hybrid meta-heuristic was developed, which solves an IRP variant considering several periods and several vehicles. Each iteration of the metaheuristic is divided into two stages: the first is modifying the position of one or more customers attended by the vehicles and periods, and a second step that solves a Maximum Flow at Minimum Cost problem, to optimally assign the load volumes transported to each customer in each vehicle in each period. Then, this approach is tested in classical instances for this IRP variant, obtaining results that prove the efficiency of the algorithm.