Στην παρούσα μεταπτυχιακή διπλωματική εργασία μελετήθηκε το πρόβλημα Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου (VRPTW) κάτω από ένα φιλικό προς το περιβάλλον πρίσμα που απαιτεί την δημιουργία ισορροπημένων και συμπαγών συστάδων. Παρουσιάζεται μια νέα ευρετική προσέγγιση που αποτελείται από τρεις φάσεις: (i) συσταδοποίηση των πελατών με συμβατά παράθυρα χρόνου, (ii) συσταδοποίηση των πελατών που βρίσκονται γεωγραφικά κοντά χρησιμοποιώντας διάφορες μεθόδους (φυσικές αποκοπές, KaHIP, τετραδικά δένδρα), (iii) μια φάση εκλέπτυνσης που είτε χωρίζει μια συστάδα σε μικρότερες, είτε συγχωνεύει συστάδες δημιουργώντας μια συμπαγή μεγαλύτερη συστάδα. Η νέα προσέγγιση αποδίδει πολύ καλά όταν χρησιμοποιείται σε δυναμικά σενάρια στα οποία ζητούνται αλλαγές στην αρχικά υπολογισμένη διαδρομή (προσθήκη μιας νέας παραγγελίας ή ακύρωση κάποιας παραγγελίας). Η νέα μέθοδος αποτελεί ένα πολύ καλό σημείο εκκίνησης για επανεξέταση και περαιτέρω βελτιστοποίηση της λύσης του προβλήματος Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου. Πειράματα που έγιναν με πραγματικά σύνολα δεδομένων δείχνουν ότι η νέα προσέγγιση υπερέχει σε σχέση με τις συνήθεις προσεγγίσεις που ξεκινούν από μία βασική λύση. / We investigate the Vehicle Routing Problem with Time Windows (VRPTW) under a new approach, consisting of three major phases: (i) a first clustering of customers with compatible time windows; (ii) a second clustering of customers with close geographic proximity based on various methods (natural cuts, KaHIP, quad trees); (iii) a refinement phase that either splits a cluster into smaller ones, or merges clusters to form a bigger compact cluster. Our approach turns out to be beneficial when used in an on-line environment, where changes to the initial tour are requested (add a new customer to the tour or drop some customers). The new method serves as a warm starting point for re-evaluating and further optimizing the solution of VRPTW. Experiments with real data sets demonstrate that our approach compares favorably with standard approaches that start from a basic (cold) solution.

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2015-10-19T19:19:50Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Approved for entry into archive by Elizabete Silva (elizabete.silva@ufes.br) on 2015-11-03T19:59:38Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Made available in DSpace on 2015-11-03T19:59:38Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) Previous issue date: 2015 / O turismo é um importante setor para economia mundial e vem crescendo consistentemente nos últimos anos. Porém, um fator determinante para escolha do destino de um turista é a existência de pontos de interesse que ele deseja visitar na região e, para tanto, as informações dos pontos de interesse de uma região devem estar disponíveis. Dada às limitações de tempo do turista, não é possível para ele visitar todos os atrativos e, por essa razão, se faz necessário a criação de roteiros turísticos. Muito embora existam diversos pacotes de viagens com destinos predefinidos, contemplando locais mais populares, nos últimos anos tem crescido a procura por soluções que criem roteiros personalizados voltados às necessidades de cada turista. Para suprir essa nova demanda, Van Oudheusden e Vansteenwegen (2007) propuseram o Tourist Trip Design Problem (TTDP) e sugeriram o uso do Orienteering Problem (OP) e suas extensões para resolução do TTDP. Esta dissertação tem por objetivo o desenvolvimento de um modelo matemático e de uma meta-heurística Simulated Annealing (SA) para resolução do TTDP. O objetivo considerado consiste em gerar roteiros que maximizem a soma das notas atribuídas aos atrativos em função do grau de interesse do turista, levando em conta o período que ele tem disponível na localidade e o horário que cada atrativo está disponível para ser visitado. / Tourism is an important sector for the world economy and has been growing steadily over recent years. However, a decisive factor for the choice of a tourist destination is the existence of points of interest in the region he wants to visit and, therefore, the information from points of interest in a region should be available. Given the tourist time constraints, it is not possible for him to visit all the attractions and, therefore, it is necessary the creation of tourist routes. Although there are several packages with predefined destinations contemplating most popular locations in recent years has increased the demand for solutions that create custom tours for the needs of each tourist. To meet this new demand Van Oudheusden and Vansteenwegen (2007) proposed the Tourist Trip Design Problem (TTDP) and they suggested that the use of the Orienteering Problem (OP) and its extensions is the best approach to the TTDP. This thesis proposes the development of a mathematical model and a Simulated Annealing (SA) metaheuristic to solve the TTDP. The objective considered is to generate routes that maximize the sum of scores awarded to the attractions based on the degree of interest of the tourist taking into account the time that he has in the locality and the time that each attraction is available to be visited.

abstract: This thesis presents a successful application of operations research techniques in nonprofit distribution system to improve the distribution efficiency and increase customer service quality. It focuses on truck routing problems faced by St. Mary’s Food Bank Distribution Center. This problem is modeled as a capacitated vehicle routing problem to improve the distribution efficiency and is extended to capacitated vehicle routing problem with time windows to increase customer service quality. Several heuristics are applied to solve these vehicle routing problems and tested in well-known benchmark problems. Algorithms are tested by comparing the results with the plan currently used by St. Mary’s Food Bank Distribution Center. The results suggest heuristics are quite completive: average 17% less trucks and 28.52% less travel time are used in heuristics’ solution. / Dissertation/Thesis / Masters Thesis Industrial Engineering 2015

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2015-10-19T19:19:50Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Approved for entry into archive by Elizabete Silva (elizabete.silva@ufes.br) on 2015-11-03T19:59:38Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Made available in DSpace on 2015-11-03T19:59:38Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) Previous issue date: 2015 / Modelo Matemático e Meta-Heurística Simulated Annealing para Elaboração de Roteiros Turísticos com base no Tourist Trip Design Problem / Modelo Matemático e Meta-Heurística Simulated Annealing para Elaboração de Roteiros Turísticos com base no Tourist Trip Design Problem

This thesis demonstrates practical using of vehicle routing problem with time windows (VRPTW) and its solution by heuristic method. There are described teoretical principles of integer models, mathematical definitions of VRP with one or more vehicles, VRPTW and some heuristics for VRP. The practical part is solution of VRP by heuristic nearest neighbor. Product distribution is planed according to the firm settings in Prague. I compare existing situation and computed solution that show benefits of using described methods in conclusion.

O transporte rodoviário é uma das atividades econômicas do homem que mais contribuem para a emissão de Gases de Efeito Estufa (GEE) na atmosfera. Sabe-se que a emissão de CO2 está diretamente vinculada ao consumo de combustível. Por isso, é possível encontrar uma série de trabalhos que objetivam diminuir as emissões por meio da redução do consumo de combustível dos veículos. A otimização de rotas é uma importante ferramenta para essa redução e, consequentemente, possibilita minimizar as emissões dos veículos. Esta pesquisa tem como objetivo aplicar em uma empresa líder na distribuição de revistas no país o PRP, que é um modelo de minimização do consumo de combustível/emissão de GEE por meio de ajustes das variáveis como velocidade média, quantidade de carga transportada, distância percorrida e inclinações das vias. Como a maioria das metodologias de estimativa de combustível existentes na literatura não considera a inclinação das vias nos seus cálculos, neste trabalho foi necessário desenvolver uma metodologia para incluí-la no modelo. Testes foram efetuados com variações nas janelas de tempo, e o modelo mostrou-se sensível a cada uma das variáveis analisadas, gerando economias em 100% das rotas estudadas. / Road transport is one of the biggest contributors of Greenhouse Gases emissions of all humans economic activities. It is known that CO2 emissions are directly related to fuel consumption, so that is why it is possible to find a series of studies that aims to reduce emissions by reducing vehicles fuel consumption. Route optimization is an important tool for reducing fuel consumption and hence emissions. This research aims to implement the PRP model in a leading company in the country, which is a model that minimizes fuel consumption/GHG emissions through adjustments of variables such as average speed, pay load, distance traveled and slopes of the road. Most existing fuel estimation methodologies found in the literature does not consider the slope of the roads in their calculations. So in this research it was necessary to develop a methodology to include it in the model. Tests were performed with variations in the time windows and the model was sensitive to each of the variables analyzed, generating savings on 100% of the studied routes.

Um tema pouco estudado na literatura, mas frequentemente encontrado por empresas prestadoras de serviço, é o Problema de Escalonamento de Técnicos de Campos (Field Technician Scheduling Problem). O problema consiste em associar um número de tarefas - em diversos locais, com diferentes prioridades e com janelas de tempo - a uma quantidade de técnicos - com diferentes horários de expediente e com habilidades distintas - que saem no início do horário de trabalho da sede da empresa, para onde devem retornar antes do fim do expediente. Cada tarefa é atendida por um único técnico. Esse problema é estudado neste trabalho. A primeira parte do trabalho apresenta um modelo de programação linear inteira mista (PLIM) e, dada a complexidade do problema, heurísticas construtivas e meta-heurísticas foram desenvolvidas. Na função objetivo, procura-se principalmente maximizar o número ponderado de tarefas executadas em um dia de trabalho, de acordo com as suas prioridades. Em linhas gerais, as heurísticas construtivas ordenam as tarefas de acordo com um critério pré-estabelecido e, em seguida, designam cada uma a um dos técnicos capazes de realiza-la sem violar as restrições do problema. Tendo em conta o bom desempenho obtido em outros problemas semelhantes, foi adotado um Algoritmo Genético denominado Biased Random-Key Genetic Algorithms (BRKGA), que utiliza chaves aleatórias para codificar e decodificar as soluções. Codificadores e decodificadores adaptados ao problema foram desenvolvidos e testes computacionais são apresentados. As soluções obtidas em problemas de pequenas dimensões são comparadas com as soluções ótimas conhecidas e, para aprimorar a avaliação do desempenho nas instâncias médias e grandes, quatro procedimentos para obter limitantes superiores foram propostos. Testes computacionais foram realizados em 1040 instâncias. O BRKGA encontrou 99% das 238 soluções ótimas conhecidas e, nas 720 instâncias de dimensões médias e grandes, ficou em média a 3,8% dos limitantes superiores. As heurísticas construtivas superaram uma heurística construtiva da literatura em 90% das instâncias. A segunda parte do trabalho apresenta uma nova abordagem para o Problema de Escalonamento de Técnicos de Campo: um modelo biobjetivo, onde uma segunda função objetivo buscará que as tarefas prioritárias sejam realizadas o mais cedo possível. Uma versão multiobjectivo do BRKGA foi desenvolvida, considerando diversas estratégias para classificar a população do algoritmo e escolher as melhores soluções (estratégias de elitismo). Codificadores e decodificadores foram criados para o problema multiobjectivo. Os resultados computacionais obtidos são comparados com os resultados de um Algoritmo Genético conhecido na literatura, o Nondominated Sorting Genetic Algorithm II (NSGA II). Para instâncias de pequenas dimensões, os resultados da meta-heurística proposta também são comparados com a fronteira ótima de Pareto de 234 instâncias, obtidas por enumeração completa. Em média, o BRKGA multiobjectivo encontrou 94% das soluções da fronteira ótima de Pareto e, nas instâncias médias e grandes, superou o desempenho do NSGA-II nas medidas de avaliação adotadas (porcentagem de soluções eficientes, hipervolume, indicador epsílon e cobertura). / An important topic in service companies, but little studied until now, is the field technician scheduling problem. In this problem, technicians have to execute a set of jobs or service tasks. Technicians have different skills and working hours. Tasks are in different locations within a city, with different time windows, priorities, and processing times. Each task is executed by only one technician. This problem is addressed in this thesis. The first part of the research presents the mixed integer linear programming model (MILP) and, due to the complexity of this problem, constructive heuristics and metaheuristics were proposed. The objective function is to maximize the sum of the weighted performed tasks in a day, based on the priority of tasks. In general terms, in the proposed constructive heuristics, jobs are ordered according to a criterion and, after that, tasks are assigned to technicians without violating constraints. A Genetic Algorithm (the Biases Randon Key Genetic Algorithm - -RKGA) is applied to the problem, based on its success in similar problems; the BRKGA uses random keys and a decoder transforms each chromosome of the Genetic Algorithm into a feasible solution of the problem. Decoders and encoders adapted to the problem were developed and computational tests are presented. A comparison between the solutions of the heuristic methods and optimal solutions values was also conducted for small instances and, to analyze medium and large instances, four upper bound models were proposed. Computational experiments with 1040 instances were carried out. The BRKGA reached 99% of the 238 optimal solutions and, for 720 medium and large instances, the average upper bound gap was 3,8%. Constructive heuristics overcame a heuristic of the literature in 90% of the instances. The second part of this research presents a new approach of the Field Technician Scheduling Problem: a multiobjective model, with a second objective function to execute the priority tasks as soon as possible. A multiobjective BRKGA was developed, with different strategies to classify the Genetic Algorithm population and to select the elite solutions (elite strategies). Decoders and encoders were developed for the multiobjective problem too. The results were compared with a known Genetic Algorithm, the Nondominated Sorting Genetic Algorithm II (NSGA II). For 234 small instances, the results were compared with the Pareto optimal solutions, obtained by complete enumeration. On average, the BRKGA found 94% of the Pareto optimal solutions and, for 720 medium and large instances, outperformed the NSGA-II by means of the measures adopted (percentage of efficient solutions, hypervolume, epsilon and coverage).

Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.

Autonomy in multi-robot systems is bounded by coordination among its agents. Coordination implies simultaneous task decomposition, task allocation, team formation, task scheduling and routing; collectively termed as task planning. In many real-world applications of multi-robot systems such as commercial cleaning, delivery systems, warehousing and inventory management: spatial & temporal constraints, variable execution time, and energy limitations need to be integrated into the planning module. Spatial constraints comprise of the location of the tasks, their reachability, and the structure of the environment; temporal constraints express task completion deadlines. There has been significant research in multi-robot task allocation involving spatio-temporal constraints. However, limited attention has been paid to combine them with team formation and non- instantaneous task execution time. We achieve team formation by including quota constraints which ensure to schedule the number of robots required to perform the task. We introduce and integrate task activation (time) windows with the team effort of multiple robots in performing tasks for a given duration. Additionally, while visiting tasks in space, energy budget affects the robots operation time. We map energy depletion as a function of time to ensure long-term operation by periodically visiting recharging stations. Research on task planning approaches which combines all these conditions is still lacking. In this thesis, we propose two variants of Team Orienteering Problem with task activation windows and limited energy budget to formulate the simultaneous task allocation and scheduling as an optimization problem. A complete mixed integer linear programming (MILP) formulation for both variants is presented in this work, implemented using Gurobi Optimizer and analyzed for scalability. This work compares the different objectives of the formulation like maximizing the number of tasks visited, minimizing the total distance travelled, and/or maximizing the reward, to suit various applications. Finally, analysis of optimal solutions discover trends in task selection based on the travel cost, task completion rewards, robot's energy level, and the time left to task inactivation.

Le problème de routage de véhicules avec fenêtres de temps et routes multiples (MTVRPTW) est une généralisation du problème de routage de véhicules avec fenêtres de temps (VRPTW). Dans le MTVRPTW, on autorise un véhicule à effectuer plusieurs routes durant une période de planification, ce qui permet d'optimiser les transports lorsque le nombre de véhicules est limité et peu élevé. Nous proposons dans cette thèse la première méthode exacte permettant de résoudre ce problème. Notre modélisation prend la forme d'un problème de couverture des clients dont les variables sont des routes. Des contraintes d'exclusion mutuelle expriment la disponibilité des véhicules. Nous utilisons la Génération de Colonnes, avec un sous-problème effectuant, par programmation dynamique, une recherche de plus court chemin élémentaire contraint en ressources. Notre méthode de programmation dynamique tient compte des dépendances de plusieurs ressources grâce à la notion de label représentatif, et est ainsi plus efficace qu'une approche classique. La méthode de Génération de Colonnes est incluse dans un schéma de Branch and Price composé de deux types de branchement, l'un basé sur les arcs, l'autre sur la résolution d'un VRPTW. Nous avons mis en place diverses méthodes accélératrices spécifiques du MTVRPTW. Nous donnons les résultats de l'algorithme sur les instances de Solomon. Des résultats issus de méthodes exactes étaient disponibles dans la littérature pour le MTVRPTW avec durée limite sur les routes. Nous avons proposé un nouvel algorithme plus performant, et basé sur nos méthodes, pour cette variante du problème. / The multi-trip vehicle routing problem with time windows (MTVRPTW) is a generalization of the vehicle routing problem with time windows (VRPTW). In the MTVRPTW, one vehicle can perform several trips during a planning period. This allows optimizing the transport when the number of vehicles is limited and small.We propose here the first exact method for solving this problem.Our model is designed as a coverage problem for customers where the variables are trips. Mutual exclusion constraints express the availability of vehicles. We use a column generation scheme in which the sub-problem is an elementary shortest path problem with resource constraints (ESPPRC). Our dynamic programming method for ESPPRC takes into account dependencies of several resources through the concept of representative label. It is thus more efficient than a conventional approach. The column generation method is included in a Branch and Price scheme with two types of branching. One is based on arc selection, and the other on solving a VRPTW. We have implemented various accelerating methods which are specific to MTVRPTW. We give the results of our algorithm on Solomon instances.Results from exact methods were available in the literature for the MTVRPTW with time limit on the trips. We proposed a new and more efficient algorithm, based on our methods, to solve this variant of the problem.