The Capacitated Arc Routing Problem has many applications in real life. The aim of this problem is to minimize the total cost at fulfilment of the requirements of arcs. The Capacitated Arc Routing Problem is an extension of the Chinese Postman Problem, which is a special type of the Vehicle Routing Problems. In this thesis is explained the issue of the Chinese Postman Problem and its extensions at first. Subsequently the applications of mathematical models are illustrated on a model example. However these mathematical models, which are searching the optimal solution, do not use so much in reality. Therefore the randomized heuristic algorithm for solving these problems is suggested and programmed in this thesis. Subsequently this heuristic was applied to case study of garbage collection in Podebrady city.

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-09T05:57:31Z (GMT). No. of bitstreams: 1 Usberti_FabioLuiz_M.pdf: 37565259 bytes, checksum: cddb8b852bd82318a8c784f1f223a076 (MD5) Previous issue date: 2007 / Resumo: Esse trabalho se dedicou ao estudo dos algoritmos para roteamento de leituristas, incluindo propostas de alteração que resultem na melhoria da qualidade dos resultados. A motivação é proveniente da alta demanda por soluções computacionais para esse problema, ainda pouco estudado devido às peculiaridades que lhe são inerentes. Encontram-se na literatura duas heurísticas, de estratégias distintas e antagônicas para esse problema. Uma das heurísticas procura construir a rota ignorando a restrição de capacidade, para posterior particionamento dessa rota em subrotas, cada qual destinada a um leiturista (¿route first, cluster second¿). A outra heurística, em uma abordagem inversa, primeiramente subdivide a região de trabalho dos leituristas, para posterior roteamento dessas partições (¿cluster first, route second¿). Essas duas heurísticas foram testadas exaustivamente, tornando possível localizar aspectos sujeitos à melhoria, dando origem a duas novas heurísticas. Foi gerada uma base de testes contendo 144 instâncias que simulam as condições reais de trabalho dos leituristas, classificadas de acordo com o tamanho e dificuldade. A partir das soluções provenientes dos quatro algoritmos foi possível analisá-los comparativamente, avaliando o melhor em um âmbito geral (envolvendo todos os algoritmos) e específico (algoritmos de mesmo tipo, ¿route first cluster second¿ ou ¿cluster first route second¿), segundo critérios de qualidade pré-definidos: número de rotas, tempo de percurso, violação da carga horária e tempo computacional. Os resultados revelam que os novos algoritmos foram melhores tanto na comparação específica quanto na comparação geral / Abstract: This work¿s main study object consists on algorithms for routing meter readers, from which proposals towards solution¿s improvement are made. The demand for computational results concerning this problem, added to literature little attention due to its inherited peculiarities, has been the outmost motivation. Two preexisting heuristics from literature, with distinct and antagonic strategies, are pointed out. One of these heuristics atempt to create a single route, dismissing the capacity restriction, and then partitionates this route into subroutes, each of them destinated to one meter reader (route first, cluster second). The other heuristic, in an inverse approach, first splits the meter reader¿s working area, and only then routes each of these partitions (cluster first, route second). The two heuristics were tested to exaustion, allowing enumeration of weak aspects subject to improvement. Therefore, two new heuristics were developed, based upon the originals, however adapted in order to outperform solution¿s quality. A testing base containing 144 instances was generated, simulating meter readers realistic labor¿s conditions, classified by size and difficulty. Through solutions provided by the four algorithms, comparison analyses have taken place, evaluating in a general (involving all algorithms) and specific manner (same kind algorithms, i.e., route first, cluster second or cluster first, route second), considering four predefined quality criteria: number of routes, deadheading time, violation of shiftwork time and computational time. Results revealed that the new algorithms achieved better solutions on specific and general comparisons / Mestrado / Automação / Mestre em Engenharia Elétrica

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

This master's thesis deals with mathematical model building for routing problems and ways to solve them. There are discussed and implemented deterministic and heuristic approaches that are suitable to be utilized. A big effort is put into building of the mathematical model describing a real world problem from the field of waste management. Appropriate algorithms are developed and modified to solve a particular problem effectively. An original graphical environment is created to illustrate acquired results and perform testing computations.

Le problème de tournées de véhicules est un des problèmes d’optimisation combinatoire les plus connus et les plus difficiles. Il s’agit de déterminer les tournées optimales pour une flotte de véhicules afin de servir un ensemble donné de clients. Dans les problèmes classiques de transport, chaque client est normalement servi à partir d’un seul nœud (ou arc). Pour cela, on définit toujours un ensemble donné de nœuds (ou arcs) obligatoires à visiter ou traverser, et on recherche la solution à partir de cet ensemble de nœuds (ou arcs). Mais dans plusieurs applications réelles où un client peut être servi à partir de plus d’un nœud, (ou arc), les problèmes généralisés qui en résultent sont plus complexes. Le but principal de cette thèse est d’étudier trois problèmes généralisés de tournées de véhicules. Le premier problème de la tournée sur arcs suffisamment proche (CEARP), comporte une application réelle intéressante en routage pour le relevé des compteurs à distance ; les deux autres problèmes, problème de tournées couvrantes multi-véhicules (mCTP) et problème généralisé de tournées sur nœuds (GVRP), permettent de modéliser des problèmes de conception des réseaux de transport à deux niveaux. Pour résoudre ces problèmes, nous proposons une approche exacte ainsi que des métaheuristiques. Pour développer la méthode exacte, nous formulons chaque problème comme un programme mathématique, puis nous construisons des algorithmes de type branchement et coupes. Les métaheuristiques sont basées sur le ELS (ou Evolutionary Local Search) et sur le GRASP (ou Greedy Randomized Adaptive Search Procedure). De nombreuses expérimentations montrent la performance de nos méthodes. / The Routing Problem is one of the most popular and challenging combinatorial optimization problems. It involves finding the optimal set of routes for fleet of vehicles in order to serve a given set of customers. In the classic transportation problems, each customer is normally served by only one node (or arc). Therefore, there is always a given set of required nodes (or arcs) that have to be visited or traversed, and we just need to find the solution from this set of nodes (or arcs). But in many real applications where a customer can be served by from more than one node (or arc), the generalized resulting problems are more complex. The primary goal of this thesis is to study three generalized routing problems. The first one, the Close-Enough Arc Routing Problem(CEARP), has an interesting real-life application to routing for meter reading while the others two, the multi-vehicle Covering Tour Problem (mCTP) and the Generalized Vehicle Routing Problem(GVRP), can model problems concerned with the design of bilevel transportation networks. The problems are solved by exact methods as well as metaheuristics. To develop exact methods, we formulate each problem as a mathematical program, and then develop branch-and-cut algorithms. The metaheuristics are based on the evolutionary local search (ELS) method et on the greedy randomized adaptive search procedure (GRASP) method. The extensive computational experiments show the performance of our methods.

This thesis explores the use of a column generation method, a subgradient method, and a logic-based Benders decomposition method on a minimized makespan K-rural postman problem. The K-rural postman problem here describes a search and rescue mission using multiple identical unmanned aerial vehicles (UAVs) to cover an area, represented as a complete graph. Each decomposition method has a separate problem for each UAV. In the subgradient and column generation case, a heuristic is used to find an improved upper bound for the makespan. This upper bound can in turn be used to decrease the feasible regions of the subproblems. Moreover, because the subproblems are slow to solve, a maximum calculation time is used, resulting in a feasible solution and a lower bound for each subproblem. These two modifications to the decomposition methods result in a non-standard behaviour.  Multiple fictional problem instances of different sizes and numbers of UAVs were generated and used for evaluating the methods. A maximal time limit is used in these instances. We conclude that solving the original, non-decomposed, problem for smaller instances with a standard solver is faster and gives better results than the decomposition methods. For larger instances, solving the non-decomposed model led to memory issues on several occasions. However, the suggested subgradient and column generation methods can solve every problem. The logic-based Benders decomposition method performed best on instances with multiple UAVs, but had issues when fewer UAVs are utilized. / Den här masteruppsatsen utforskar användningen av en kolumngenereringsmetod, en subgradientmetod och en logikbaserad Benders dekompositionsmetod på en variant av lantbrevbärarproblemet. Vårat brevbärarprolem beskriver sök- och räddningsuppdrag där $K$ drönare används för att avsöka ett område med målfunktionen att minimera flygtiden för den långsammaste drönaren. Varje dekompositionsmetod använder sig av ett problem för varje drönare. I subgradient- och kolumngenereringsmetoden användes en heuristik för att hitta en bättre övre begränsning till drönarnas flygtid. Den förbättrade övre begränsningen kunde sedan användas för att minska det tillåtna området för de mindre problemen. Eftersom de mindre problem var svårlösta, användes en maximal beräkningstid vilket resulterade i att en tillåten lösning och undre gräns gavs för varje mindre problem. Dessa två modifikationer resulterade i icke typiska beteenden.  Metoderna utvärderades på flera fiktiva testinstanser av olika storlekar där antalet drönare varierar. En tidsbegränsning används på varje probleminstans. Slutsatserna från uppsatsen är de original brevbärare problemet ger bäst lösning och snabbast lösningstid i de mindre instanserna. Vid lösning av större probleminstanser, gav original problemet flerfaldiga gånger minnesproblem. Subgradient- och kolumngenereringsmetoden kunde däremot lösa varje probleminstans inom tidsbegränsningen, vilket gjorde de mer pålitliga. Logikbaserade Benders dekompositionsmetoden presterade bättre i instanser med flera drönare, men stötte på problem i instanser med färre drönare.

The multiple constant multiplication (MCM) operation is a fundamental operation in digital signal processing (DSP) and digital image processing (DIP). Examples of the MCM are in finite impulse response (FIR) and infinite impulse response (IIR) filters, matrix multiplication, and transforms. The aim of this work is minimizing the complexity of the MCM operation using common subexpression elimination (CSE) technique and redundant number representations. The CSE technique searches and eliminates common digit patterns (subexpressions) among MCM coefficients. More common subexpressions can be found by representing the MCM coefficients using redundant number representations. A CSE algorithm is proposed that works on a type of redundant numbers called the zero-dominant set (ZDS). The ZDS is an extension over the representations of minimum number of non-zero digits called minimum Hamming weight (MHW). Using the ZDS improves CSE algorithms' performance as compared with using the MHW representations. The disadvantage of using the ZDS is it increases the possibility of overlapping patterns (digit collisions). In this case, one or more digits are shared between a number of patterns. Eliminating a pattern results in losing other patterns because of eliminating the common digits. A pattern preservation algorithm (PPA) is developed to resolve the overlapping patterns in the representations. A tree and graph encoders are proposed to generate a larger space of number representations. The algorithms generate redundant representations of a value for a given digit set, radix, and wordlength. The tree encoder is modified to search for common subexpressions simultaneously with generating of the representation tree. A complexity measure is proposed to compare between the subexpressions at each node. The algorithm terminates generating the rest of the representation tree when it finds subexpressions with maximum sharing. This reduces the search space while minimizes the hardware complexity. A combinatoric model of the MCM problem is proposed in this work. The model is obtained by enumerating all the possible solutions of the MCM that resemble a graph called the demand graph. Arc routing on this graph gives the solutions of the MCM problem. A similar arc routing is found in the capacitated arc routing such as the winter salting problem. Ant colony optimization (ACO) meta-heuristics is proposed to traverse the demand graph. The ACO is simulated on a PC using Python programming language. This is to verify the model correctness and the work of the ACO. A parallel simulation of the ACO is carried out on a multi-core super computer using C++ boost graph library.