The thesis deals with application of models of routing problems on a real problem, beer distribution in Jesenicko region provided by Viden plus, a.s. The goal of the thesis is to optimize daily distributional routes for two vehicles with different capacities. Total distance has to be minimized respecting time and capacity limits. In case the optimal solution is not found, sub-optimal solution will be accepted. Solutions are calculated with use of the optimization software LINGO and some heuristic methods. Models of travelling salesman problem and vehicle routing problem are used to find the solutions. Results are compared to the current state of distributional routes in conclusion of the thesis.

This thesis deals with the optimization of distribution of bakery products. Firstly there are the fundamental types of vehicle routing problems and their optimization models introduced. Next part is dedicated to heuristic algorithms. The heuristic methods are introduced in general, then there are the chosen methods described. Later there are two chosen algorithms formulated. First one based on the nearest neighbour method and another one based on the savings algorithm. Both of algorithms were programmed in the Visual Basic of Applications MS Excel 2010. These algorithms were applied for the solution of the real problem dealing with the distribution of goods. The bakery company has provided the data about its customers for this purpose. The last part of this thesis is dedicated to the summary and comparison of the solution of the assigned problem that was gained by the proposed algorithms with the solution that the bakery company has put into practice.

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2015-07-17T16:00:19Z No. of bitstreams: 1 Stanley Jefferson de Araujo Lima.pdf: 1500605 bytes, checksum: 2aec7d5c11c9781ce7f70eb2019c01f4 (MD5) / Made available in DSpace on 2015-07-17T16:00:19Z (GMT). No. of bitstreams: 1 Stanley Jefferson de Araujo Lima.pdf: 1500605 bytes, checksum: 2aec7d5c11c9781ce7f70eb2019c01f4 (MD5) Previous issue date: 2015-01-27 / In recent years, the Vehicle Routing Problem (VRP) has attracted an increasing attention from researchers due to the great difficulty of its solution and its presence in various practical situations. As consequence, there has been great effort to develop more robust, agile and flexible algorithms that can be modeled according to the scenario that describes the problem. The Capacitated Vehicle Routing Problem (CVRP) is a version of VRP and consists in determining a set of routes to be followed by a fleet of homogeneous vehicles, which must serve a set of customers. The objective is to minimize the total cost of the routes subject to the following restrictions: i) routes must start and end in the same distribution center; ii) each customer must be visited once and its demand must be met in full by only one vehicle and iii) the sum of customers' demands included in a route cannot exceed the vehicle capacity. The CVRP belongs to the class of NP-hard problems, that is, problems whose the solution usually requires non-polynomial complexity time algorithms and because of this are usually resolved with the use of heuristic and metaheuristics algorithms. In this work, it was investigated the optimization of CVRP using Genetic Algorithm (GA) with alternative chromosome representations and heuristics. To this end, three strategies, each one employing a different model of chromosome representation for encoding solution in AG were proposed. In addition, the heuristics of Gillett and Miller to generate solutions that are included in the initial population of GA and Hill-climbing for refinement of GA solutions, after a number of generations without improvement, were adopted. In the performed experiments, the results obtained by the proposed strategies were compared with each other and also with the best results found in the literature for a set of known instances. These experiments showed that the proposed strategies provided good results with respect to quality of solutions well as the computational cost. In addition, it was possible to evaluate the viability of each employed chromosome representation and the contribution of the heuristics in the convergence process of GA. / Nos últimos anos o Problema de Roteamento de Veículos (PRV) tem atraído cada vez mais a atenção de pesquisadores devido à grande dificuldade de solução e sua presença em várias situações do cotidiano. Em decorrência disso, tem havido um grande esforço para desenvolver algoritmos cada vez mais robustos, ágeis e flexíveis e que possam ser modelados com base no cenário que descreve o problema. O Problema de Roteamento de Veículos Capacitado (PRVC) é uma versão do PRV e consiste em encontrar um conjunto de rotas a serem seguidas por uma frota de veículos homogêneos, os quais devem atender a um conjunto de clientes. O objetivo é minimizar o custo total das rotas respeitando as seguintes restrições: i) as rotas devem iniciar e terminar no mesmo centro de distribuição; ii) cada cliente deve ser visitado uma única vez e sua demanda deve ser atendida integralmente por apenas um veículo e iii) a soma das demandas dos clientes incluídos em uma rota não pode exceder a capacidade do veículo. Problemas desta natureza podem ser classificados como NP-Hard, ou seja, possuem ordem de complexidade não polinomial e normalmente são resolvidos com uso de algoritmos heurísticos e meta-heurísticos. Neste trabalho investigou-se a otimização do PRVC usando Algoritmo Genético (AG) com representações cromossômicas e heurísticas alternativas. Para tanto, foram propostas três estratégias, cada uma delas empregando um modelo diferente de representação cromossômica para codificação da solução no AG. Além disso, foram empregadas as heurísticas de Gillett e Miller para gerar soluções que são incluídas na população inicial do AG e Subida/Descida de Encosta para refinamento das soluções, após um certo número de gerações sem melhoria. Nos experimentos realizados, os resultados obtidos pelas estratégias propostas foram comparados entre si e também com os melhores resultados encontrados na literatura para um conjunto de instâncias conhecidas. Pode-se constatar, a partir desses experimentos, que as estratégias apresentaram bons resultados tanto no que tange a qualidade das soluções quanto ao tempo computacional dispendido. Em adição, foi possível avaliar a viabilidade de cada uma das representações cromossômicas empregadas, além da contribuição das heurísticas no processo de convergência do ag.

This thesis deals with an optimization of waste collection in a mid-sized town. The model is formulated based on requirements from a real process. To deal with this problem, the original memetic algorithm was developed and implemented in C++.

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.

Les prestataires de service réseau doivent faire face à la demande croissante des besoins des utilisateurs, en particulier vers une plus grande flexibilité et toujours plus de capacité. La "softwerisation" et la "cloudification" des composants du réseau offrent une solution prometteuse pour obtenir l'agilité nécessaire afin de répondre dynamiquement à l'exigence au niveau de la consommation des ressources. Cette vision se traduit par le déploiement de la Virtualisation des Fonctions Réseau (NFV) où les Fonctions de Réseau Virtuels (VNFs) peuvent être associées pour créer des services réseau. Cette thèse étudie la problématique de l'allocation de ressources dans un système NFV afin de minimiser son coût sous contraintes sur l'interconnectivité entre les VNF, les ressources du système et les exigences de service. La principale considération est la réduction du coût global du déploiement en ressources informatiques. Nous étudions également d'autres objectifs à satisfaire tels que la migration des fonctions réseau et la gestion de la congestion. Notre premier objectif est d'augmenter notre compréhension de la performance d'un système NFV en étudiant le placement et le routage des fonctions réseau. Nous formalisons le problème dans une approche globale en tenant compte d'un large ensemble de paramètres pertinents. Nous prendrons en compte les cas statiques (Hors Ligne) et dynamiques (En Ligne) du problème. Nous proposons et analysons trois algorithmes heuristiques: deux sont conçus pour traiter de grandes dimensions du scenario "Hors Ligne" et le dernier est conçu pour résoudre le scénario "En Ligne". Les résultats montrent que notre solution surpasse l'état de l'art par rapport à l'indicateur de performance critique. Nous évaluons également l'impact de la migration d'une série de demandes simultanées et proposons une technique de migration simple pour ce système dynamique. A la lumière de ces premiers résultats, nous étendons notre étude afin d'améliorer l'efficacité de notre solution en proposant un modèle plus simple. La seconde partie de notre étude se concentre sur l'optimisation de l'utilisation des ressources d'un système NFV. La principale distinction est que nous pouvons appliquer le modèle à un système dynamique avec de grandes instances. De plus, nous fournissons également une méthode originale pour engendrer de fortes inégalités afin d'améliorer la résolution de la programmation linéaire (LP) dans un espace de dimension supérieur. Les résultats obtenus n'améliorent pas seulement le modèle, mais promettent aussi de pouvoir être utiliser efficacement dans d'autres modèles. Une troisième contribution de notre travail concerne le problème de routage dans NFV. En effet, une évolution importante des besoins des utilisateurs est représentée par la demande d'accès croissante aux ressources réseau, de stockage et de calcul afin de combiner dynamiquement le niveau de consommation de ressources avec leurs besoins de service. Par conséquent, nous nous intéressons au routage efficace d'une demande utilisateur à travers les noeuds qui traitent les fonctions impliquées dans une chaîne de services donnée. Nous proposons une formulation originale de ce problème basée sur la construction d'un réseau étendu. Nous formulons une solution mathématique exacte et proposons plusieurs algorithmes approximatifs tenant compte les principaux paramètres du système. Nous conclurons en soulignant les contributions principales de notre travail et proposons quelques pistes pour des travaux futurs. / Network service providers have to cope with the growing on-demand need from end-users as well as the diversity of usage. The "softwerization" and "loudification" of the network components offer a promising solution to achieve the agility necessary to dynamically match the servcice requirements with the level of resource consumption. Cloud-based solutions promises an economy of scale and simpler management. Virtualizing the many network appliances offers the flexibility to adapt to the varying service demand. This materializes with the deployment of Network Functions Virtualization (NFV) where Virtual Network Functions (VNFs) may be chained together to create network services. This dissertation studies the resource allocation problem in an NFV system for minimizing its cost under constraints on interconnectivity among VNFs, system resources, and service requirements. The main consideration is the reduction of the overall deployment cost while efficiently utilizing the available resources. In addition, a number of other important constraints are considered such as migration and congestion. Our first goal is to increase our understanding of the performance of an NFV system with respect to network functions placement and routing. We formalize the problem in a comprehensive maner taking into account a broad set of relevant parameters. The static (OFFLINE) and dynamic (ONLINE) cases are considered. We propose and analyze three heuristic algorithms: two for handling large dimensions of the OFFLINE problem and one designed to address the ONLINE scenario. The results show that our solution outperforms the state of the art with respect to critical performance index. We also evaluate the impact of migrating a set of running demands, and propose a simple migration technique for the dynamic system. We extend this work by proposing a simpler model to improve the performance of our solution. The second part of our work focuses on minimizing the resource utilization of an NFV system. The main distinctive point is that we can apply the model to a dynamic system with large instances. Moreover, we also provide an interesting method for generating some strong inequalities to improve the Linear Programming (LP) solving in a higher dimensional space. The obtained results are not only making the model easier but also can be used efficiently in other models. A third contribution focuses specifically on the routing problem in NFV. An important evolution of the users’ needs is represented by the dynamic on-demand access to network, vstorage and compute resources. Therefore, routing efficiently a demand across nodes handling the functions involved in a given service chain constitutes the a novel problem that we address in this last section. We provide an original formulation of this problem based on the construction of an expanded network. We derive the exact mathematical formulation and propose several approximate algorithms taking into account the main system’s parameters. We conclude by deriving some interesting insights both about the algorithms and the network performance. We finally conclude with our main findings and highlight many avenues for future work.

This thesis deals with stochastic location routing problem. Multiple stochas- tic and deterministic models are formulated and it is discussed that it is difficult to solve these problems via exact integer programming methods. It is necessary to develop heuristic methods to find a solution of these problems. Multiple ver- sions of these problems are formulated and their properties and possibilities how to solve them are discussed. Therefore, the brand new Blockchain metaheuristic is developed and later used for solving stochastic location routing problem ap- plied on a waste collection problem. As a part of Blockchain metaheuristic we develop the new application of Greedy algorihtm that is used for finding initial solution. The quality of the heuristic algorithm developed by us is presented in a numerical study. 1

The e-commerce market has developed massively since the 1990ies. In addition to a general change of shopping behavior, the COVID-pandemic increased the importance of online shopping. This study is about the transportation of e-commerce parcels on the last mile in urban areas, so called last-mile delivery. Special focus is put on innovative last mile solutions that reduce the externalities related to last-mile delivery. There are several factors that complicate the delivery on the last mile such as congestion, driving restrictions and meeting time-windows for customers. This study investigates to what extent the route planning for a fleet of vehicles can account for these various requirements and restrictions. The route planning was conducted in the GIS software ArcGIS Pro using the vehicle routing problem. The routes could be successfully planned and consider most of the relevant factors for last-mile delivery operations. The results indicate that traffic and congestion in cities can be accounted for which results in an average driving speed of 20km/h. The planned routes also indicate that not even 20% of the vehicle’s cargo capacity was used and that 60-65% of the total time is spent driving between orders. The study and its results are relevant to businesses and researchers in the field of last-mile delivery as the analysis of a real-world scenario highlights the possibilities and limitations of route planning on the last mile.

京都大学 / 新制・課程博士 / 博士(工学) / 甲第24219号 / 工博第5047号 / 新制||工||1788(附属図書館) / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 藤井 聡, 教授 山田 忠史, 准教授 QURESHI Ali Gul / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DGAM

[pt] Nos últimos anos as empresas varejistas começaram a investir em modelos menores de lojas, voltando-se para o atendimento de conveniência, que busca atender os novos hábitos de consumo da população. No entanto, esse modelo de loja representa um grande desafio logístico para as empresas, uma vez que por serem pequenas essas lojas normalmente não possuem espaço para estoque, necessitando de abastecimentos frequentes. A logística urbana apresenta alguns obstáculos como as restrições de circulação por tipo de veículo e as janelas de tempo, tornando a roteirização adequada fundamental para entregar o produto correto, no momento correto e na quantidade correta, garantindo assim a redução de veículos, distância percorrida e custos logísticos. Desta forma, este trabalho busca contribuir para o reabastecimento ótimo de lojas de conveniência localizadas em grandes centros urbanos através da otimização de rotas, considerando restrições de circulação e janelas de tempo disponíveis para abastecimento. Para isto, um estudo de caso foi feito em uma empresa do setor varejista utilizando uma ferramenta de código aberto baseada no Excel para resolver a variante do problema de roteirização de veículos. A ferramenta utilizada para resolver casos reais da empresa em estudo, considera o planejamento médio da demanda diária assim como a capacidade e disponibilidade dos veículos, tempos de descarga e restrições de horário para recebimento e circulação de veículos. Os resultados do estudo para os cenários discutidos apresentam uma redução de até 32 por cento no frete da empresa, além de oportunidades de ganhos operacionais frente à atual operação da empresa. / [en] In recent years retail companies have begun to invest in smaller store models, turning to the convenience service, which seeks to meet the new consumption habits of the population. However, this store model represents a major logistical challenge for companies, once they are small, usually do not have space for inventory and need frequent replenishments. City Logistics presents some obstacles such as traffic restrictions by vehicle type and time windows, making proper routing essential to deliver the right product at the right time and in the right amount, thus ensuring vehicle reduction, distance traveled and logistics costs. In this way, the objective of this paper is to contribute to the optimal replenishment of convenience stores located in large urban centers through an optimization of the routes, considering the traffic restrictions and the time windows available for supply. For this, a case study was done in a retail company using an Excel open source tool to solve the variant of the vehicle routing problem. The tool is used to solve real cases of the company under study, considering the average planning of daily demand as well as the capacity and availability of vehicles, unloading times and time constraints for receiving and circulating vehicles. The study results for the scenarios discussed present a reduction of up to 32 per cent in the company s freight as well as opportunities for operating gains against the company s current operation.