Esta dissertação trata do planejamento do abastecimento de última milha em centros urbanos, propondo métodos para agrupar pedidos de clientes em programação de entregas. Neste estudo, é considerado que o frete pago ao transportador em uma rota é definido pela distância direta do ponto de entrega mais distante do depósito em contraposição à distância total da rota que é usual na literatura sobre problemas de roteirização de veículos. Além disso, também são consideradas categorias, conjunto de produtos similares, que não podem ser transportadas juntas por não serem compatíveis entre si. O objetivo do problema proposto é determinar o agrupamento e sequenciamento de pedidos em roteiros de veículos de acordo com as características operacionais descritas acima, utilizando uma frota homogênea de veículos capacitados que parte de um depósito, de tal forma que toda a demanda seja atendida com o menor frete possível. Para resolução desse problema são propostas uma formulação matemática para obtenção de soluções exatas e a implementação da heurística \"Multi Start Perturbation Tabu\" (MSPT) que é composta das metaheurísticas \"Greedy Randomized Adaptive Search Procedure\" (GRASP), \"Tabu Search\" (TS) e \"Iterated Local Search\" (ILS) para obtenção de soluções heurísticas. Os resultados experimentais indicam que a MSPT é competitiva com os resultados do método exato com até 5 horas de processamento utilizando os recursos computacionais de alto desempenho do Laboratório de Computação Científica Avançada (LCCA) da Universidade de São Paulo. / This dissertation addresses the planning of the last mile supply in urban centers and proposes methods to group customer orders into shipments. In this study, freight paid to the carrier on a route is defined as the direct distance from the point of delivery that is furthest from the depot as opposed to be defined as the total distance of the route which is commonly found in the literature on vehicle routing problems. In addition, it is also considered categories, a set of similar products, which cannot be transported together because they are not compatible with each other. The objective of the proposed problem is to determine the grouping and sequencing of orders into vehicle shipments according to the operational characteristics described above, using a homogeneous fleet of capacitated vehicles that is located in a depot, in such a way that all the demand is delivered with the lowest freight possible. To solve this problem, it is proposed a mathematical formulation to obtain exact solutions and the implementation of the Multi Start Perturbation Tabu (MSPT) heuristic that is composed of the Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search (TS) and \"Iterated Local Search\" (ILS) for heuristic solutions. Finally, the experimental results indicate that the MSPT is competitive with the outcomes of the exact method with up to 5 hours of processing using the high performance computational resources of the Advanced Scientific Computation Laboratory (LCCA) of the University of São Paulo (USP).

Apesar de serem utilizados com sucesso em problemas de roteirização clássicos como o do caixeiro-viajante e o de roteirização de veículos com janelas de tempo, os algoritmos genéticos não apresentavam bons resultados nos problemas de roteirização de veículos sem janelas de tempo. Utilizando-se de uma tendência recente de hibridização de algoritmos genéticos, Prins (2004) elaborou um algoritmo para o problema de roteirização de veículos sem janelas de tempo, monoperíodo, e que obrigatoriamente atenda a todos os clientes cujos resultados, quando aplicado a instâncias de Christofides et al. (1979) e de Golden et al. (1998), são comparáveis aos melhores códigos elaborados com base na busca tabu. Diferentemente da maioria dos algoritmos genéticos apresentados para solução de problemas de roteirização de veículos, no método desenvolvido por Prins (2004) o cromossomo é composto apenas pelos pontos a serem atendidos, não contendo delimitadores de rotas. Estas são definidas a partir de um método de particionamento do cromossomo. Este trabalho implementa o algoritmo descrito por Prins (2004) e propõe a este melhorias em diversas de suas etapas, como inicialização, operação de crossover, operação de mutação, reinicialização e particionamento do cromossomo. As alterações implantadas são aplicadas às instâncias de Christofides et al. (1979) e comparadas com o algoritmo inicial em termos de qualidade de solução e tempo de processamento. Finalmente, é elaborado um algoritmo genético que contempla as alterações que obtiveram resultados positivos. / In the Vehicle Routing Problem (VRP) we seek for a set of minimum-cost vehicle routes for a fleet of identical vehicles, each starting and ending at a depot, such that each customer is visited exactly once and the total demand of any route does not exceed the vehicle capacity. Several families of heuristics have been proposed for the VRP. They can be broadly classified into two main classes: classical heuristics developed between 1960 and 1990, and, more recently, metaheuristics. Among them, tabu search plays an key role, being acknowledged by most authors as the most successful approach for the VRP. In the literature some successful implementations of metaheuristic Genetic Algorithm (GA) can be found for classic routing problems such as the traveling salesman and vehicle routing problems with time windows. However, until recently, the same did not apply for the VRP. In this thesis we develop a genetic algorithm without trip delimiters, and hybridized with a local search procedure, for the solving the VRP, which is based on the work of Prins (2004). At any time, a chromosome can be converted into an optimal VRP solution (subject to chromosome sequence) by means of a splitting procedure, in which the chromosome sequence, representing a giant tour, is partitioned into feasible routes in terms of vehicle capacities. Starting with the procedure originally proposed Prins (2004), we then introduce new improvements in terms of the different components of the GA, aiming to obtain improved solutions. These include how we determine the initial population, different partitioning approaches, alternative reproduction (crossover) processes, a granular tabu mechanism similar to the one proposed by Toth and Vigo (2003 and, finally, in changes in the reinitialization process, aiming to reestablish diversity. Computational experiments are presented, based on the 14 classical Christofides instances for the VRP. The results show that the proposed improved versions of the GA allow us to obtain better solutions when compared to the original approach by Prins (2004).

Modelos de simulação usados para representar uma malha ferroviária com a circulação de trens percorrendo nela um ciclo fechado, estão sujeitos a diversas interferências. Essas interferências são representadas pela circulação de outros trens, bem como pelas filas que são formadas junto aos terminas de carga e descarga, que alteram a programação inicialmente idealizada. A validação desses modelos de simulação é prejudicada por essas interferências, e a busca por um correto procedimento de validação deve ter como base o adequado direcionamento e alocação dos trens. A carência de estudos sobre a validação de simulações aplicadas a sistemas ferroviários, que considerem a característica especifica de trens de ciclo e as interferências citadas, possibilitou a elaboração desta tese, a qual sinaliza que o desenvolvimento de algoritmos que representam o processo de movimentação dos trens em nível de detalhe suficiente, e a adoção de um método de direcionamento adequado, permitem a validação do modelo para esse tipo de sistema. Das três alternativas avaliadas para representar o direcionamento: escolha aleatória entre diversos pontos de carregamento para atender um destino final ou realizado por rotina com a mesma finalidade inserida no próprio simulador, e por modelo otimizador acessado externamente pelo simulador, foi selecionada a segunda opção por permitir uma validação do modelo mais próxima da realidade e realizar experimentos com menor tempo computacional. Uma vez programado o modelo de simulação com o direcionamento de trens escolhido, foi possível conduzir experimentos para medir a sensibilidade com relação as principais variáveis que permitem o dimensionamento de sistemas ferroviários brasileiros. / The rail network simulation models considering trains on closed loop may have many disturbances. These disturbances are caused by the railnet traffic, or queues at the load/unload stations, that changes the movement previously planned. The validation of these simulation models can be problematic because of these disturbances, and the search for the right validation procedure must count with a good train destination choosing process. The lack of studies about the validation of simulations applied to rail networks, considering the specific features of the closed loop trains and the disturbances, have leaded this thesis development, which proves that the development of algorithms that represent the movement process of the trains under sufficient detailing level, and the adoption of a correct destination choosing process, reaches the model validation. From the three options evaluated to represent this destination choosing procedure: random choosing between many loading points to one unloading point, or an internal model routine to do this same task, or an external optimization model called from the simulation model, was choosen the second option, because it validates the model and runs the simulation experiment faster. Once prepared the model with the destination choosing process selected, was possible to conduct experiments to measure the model sensitivity to the main parameters at the design of brazilian rail networks.

Esta dissertação trata do problema do agrupamento de cargas fracionadas na distribuição de cimento ensacado partindo de um depósito central. O problema consiste em definir quais entregas de cimento serão carregadas juntas em um determinado veículo, de modo a aproveitar ao máximo sua capacidade e ao mesmo tempo reduzir o custo com o frete pago aos transportadores que farão sua distribuição. Em especial, o método de resolução proposto pode ser dividido em três fases. Na primeira fase, as entregas pertencentes a um mesmo cliente são agrupadas prioritariamente. Na segunda fase, são agrupadas as entregas de clientes dentro de uma mesma cidade. Neste caso, uma simplificação necessária é considerar que todas as entregas de uma mesma cidade estão localizadas em um único ponto. Com isso, a distância entre os clientes se torna irrelevante e é proposto um método baseado em um algoritmo genético para resolução de problemas de bin-packing (BPP). Para a terceira fase, é considerado o agrupamento para pontos de entrega pertencentes a cidades diferentes, onde as distâncias rodoviárias são consideradas. Nesta etapa, é proposta uma variação do método anterior, incorporando ao modelo algumas heurísticas para resolução de problemas de roteirização de veículos, como o algoritmo de Clarke & Wright e o algoritmo do Vizinho Mais Próximo. / This thesis deals with the problem of merging less-than-truckload deliveries in bagged cement distribution from a central depot. The problem consists in defining which cement deliveries shall be loaded in each given vehicle, in order to maximize the vehicle full capacity as well as reduce carriers freights. Particularly, the solution method can be divided hierarchically in three stages. In the first stage, the deliveries from the same client are merged with priority. In the second stage, the deliveries from the same city are merged. In this case, a necessary assumption is to consider the deliveries from the same city as located in a single destination point. Consequently, the distances among deliveries can be assumed as irrelevant and a heuristic method is proposed, which relies on a genetic algorithm for the bin-packing problem (BPP). In the third stage, merging of different delivery points that are apart from each other is considered. For this step, a variation of the previous method is proposed, incorporating some heuristics to solve the vehicle routing problem, like the Clarke & Wrights savings algorithm and the Nearest Neighbor algorithm.

This work is to develop a computer system and with the help of Geo-routing for application in the delivery of charge, with a focus on food distribution segment of poultry production. The region used for the development of this work was the middle region west of Santa Catarina, with poultry company Aurora Foods. The project was divided into five modules: data collection in the field, issue of roads, adding relief, routing and data transmission. The first three modules were needed to structure the road network, "raw material" for routing. In the routing module, emphasis of this project, the system with features designed routing itself. It was created by sequential logic of 06 (six) algorithms for closing phase loads and also tools with automatic functions of spatial data in the auxiliary lock phase loads (manual phase) following defined parameters. For each load was verified the logic of filling the compartments of the transport vehicle of diet for proper distribution of load on it. The system had features on the map as plot aviaries projection clickable route between points on the road network and visualization of spatial filters. This project enabled us to verify that, using geo linked to the development of a custom computer system, you can perform the routing and closing loads optimized, with management control and reduce the possibility of errors due to human interference. / Este trabalho consistiu em desenvolver um sistema computacional contando com o auxílio de Geotecnologias para aplicação na roteirização de entrega de cargas, com foco na distribuição de ração do segmento avicultura de corte. A região utilizada para o desenvolvimento do trabalho foi a mesorregião Oeste Catarinense com avicultores da empresa Aurora Alimentos. O projeto foi dividido em cinco módulos: coleta de dados a campo, edição de estradas, adição do relevo, roteirização e transmissão de dados. Os três primeiros módulos foram necessários para a estruturação da rede viária, matéria-prima para a roteirização. No módulo roteirização, ênfase deste projeto, o sistema com as funcionalidades de roteirização foi desenvolvido propriamente dito. Foi criada a lógica sequencial de 06 (seis) algoritmos para fechamento de cargas na fase automática e também ferramentas com funções de espacialização de dados na fase auxiliar do fechamento de cargas (fase manual), seguindo parâmetros definidos. Para cada carga foi verificada a lógica de enchimento dos compartimentos do veículo de transporte de ração para distribuição adequada da carga no mesmo. O sistema dispõe de funcionalidades no mapa como plotagem de aviários, projeção de percurso entre pontos clicáveis sobre a rede viária e visualização de filtros espaciais. Este projeto possibilitou verificar que, utilizando geotecnologias atreladas ao desenvolvimento de um sistema computacional personalizado, é possível realizar a roteirização e fechamento de cargas otimizadas, com controle gerencial e reduzir a possibilidade de erros devido à interferência humana.

Submitted by Aelson Maciera (aelsoncm@terra.com.br) on 2017-05-22T20:04:01Z No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-05-31T13:43:27Z (GMT) No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-05-31T13:43:34Z (GMT) No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) / Made available in DSpace on 2017-05-31T13:52:08Z (GMT). No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) Previous issue date: 2017-03-07 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Vehicle routing problems occur in many practical situations where the distribution of goods and / or services to different demand points is necessary. In this context, this research aims to study a ship routing and scheduling problem that arises at the collection and delivery operations of different types of crude oil from offshore platforms to coastal terminals. In the paradigm adopted for the representation of the problem, the transportation is largely the result of the need to maintain inventories at each supply point (platforms) between minimum and maximum levels, considering production rates on these operating points and the demand attendance of each product in the coastal terminals. The routing and scheduling of the fleet aims to achieve minimum variable cost solutions, and considers various operational constraints, such as the maximum cargo volume transported on each ship, the ships mooring in the operational points ports, the simultaneous unloading of the ships in terminals with more than one berth, among many others. In this research, Inventory Constrained Routing Problem (ICRP) models in the maritime context have been modified and extended for appropriately representating and solving real problems based on data collected in a case study performed on a Brazilian oil company, involving relatively short distances and time horizons. Small sized instances are solved by a mathematical programming software. Given the difficulties of solving larger examples, this study proposes a multistart heuristic method that includes a metaheuristic GRASP and improvement procedures, and also a rolling horizon heuristic. Both methods provide feasible good quality solutions in reasonable computing times. In order to improve the quality of the solutions found by these constructive methods, it is also discussed a procedure that combines the mathematical programming software and local search heuristic methods (matheuristic). The results show the potential of the proposed models and solution methods to tackle the problem and produce competitive solutions. / Problemas de roteirização de veículos ocorrem em diversas situações práticas onde se faz necessária a distribuição de bens e/ou serviços a pontos dispersos de demanda. Nesse contexto, a presente pesquisa visa o estudo de um problema de roteirização e programação de navios presente em operações de coleta e entrega de diferentes tipos de óleo cru de diversas plataformas offshore para vários terminais costeiros. No paradigma adotado para representação do problema, o transporte dos produtos é em grande parte o resultado da necessidade de manutenção dos estoques em cada ponto de suprimento (plataformas) entre níveis mínimos e máximos, considerando-se as taxas de produção nesses pontos operacionais, assim como o atendimento da demanda de cada produto nos terminais costeiros para abastecer as refinarias. A roteirização e programação da frota visa a obtenção de soluções de mínimo custo variável e considera várias restrições operacionais, tais como o volume máximo de carga transportada em cada navio, a viabilidade de atracação de navios em portos dos pontos operacionais, os descarregamentos simultâneos de navios em terminais com mais de um berço, dentre várias outras. Nesse sentido, modelos de otimização da literatura de roteirização veículos com restrições de estoque (Inventory Constrained Routing Problem – ICRP) no contexto marítimo foram modificados e estendidos para representação do problema e resolução de exemplares de uma situação real, definidos a partir de dados coletados em um estudo de caso realizado em uma empresa petrolífera nacional, envolvendo distâncias relativamente curtas e com horizontes de planejamento de curto prazo (poucas semanas). Exemplares de pequeno porte são resolvidos por meio da utilização de um software de programação matemática. Dada a dificuldade de resolução dos exemplos de maior porte, é proposto um método heurístico de múltiplos reinícios composto por uma metaheurística GRASP e procedimentos de melhoria, além de uma heurística de horizonte rolante, que proporcionaram a obtenção de soluções factíveis de boa qualidade em tempos computacionais aceitáveis. Com intuito de melhorar a qualidade das soluções encontradas pelos métodos construtivos, é também discutido um procedimento que combina o software de programação matemática e métodos heurísticos com busca local (mateheurística). Os resultados mostram o potencial dos modelos e métodos de solução aqui desenvolvidos e propostos para abordar o problema e produzir soluções competitivas em relação às soluções da empresa.

O ônibus é o principal modo de transporte público de passageiros das grandes cidades brasileiras. Ultimamente as redes de transporte público vêm sofrendo modificações estruturais importantes, visando sua melhoria. Esta Dissertação descreve a pesquisa de mestrado que teve como objetivo o estudo de métodos racionais de Roteirização de Ônibus Urbano para a escolha de um método adequado à aplicação nas grandes cidades brasileiras. A revisão bibliográfica dá mais ênfase aos métodos que atendem a esse objetivo e que possibilitam sua aplicação imediata com ou sem modificação. Para se conhecer as diferenças locais em termos de planejamento dos itinerários nas maiores capitais brasileiras, apresenta-se um levantamento feito junto a 11 (onze) órgãos gestores. Comparam-se os procedimentos adotados no Brasil com os adotados nos Estados Unidos e Canadá e escolhe-se o melhor método com base em critérios existentes na literatura. O objetivo principal foi alcançado: o método indicado pode ser aplicado, com algumas modificações concernentes principalmente à coleta de dados. Espera-se que esta pesquisa contribua para a divulgação das técnicas de roteirização baseadas em modelos matemáticos de modo a auxiliar o especialista: (a) na alteração e/ou concepção das rotas (b) na completa reformulação de complexos sistemas de transporte público. / Bus transit is the main urban public transportation mode available in large-size Brazilian cities. Brazilian transit networks have held important structural modifications lately, seeking their improvement. This dissertation describes a master’s research that had as the main objective the study of rational bus transit routing methods. The goal is to choose the best of these methods for application in large-size Brazilian cities. The literature review focused on methods which are addressed to this objective, and that could be used with or without changes for this purpose. A total of 11 (eleven) transit agencies answered a national survey made to identify local differences in the planning techniques used in the largest Brazilian capitals. Procedures adopted in Brazil were compared with the ones applied in the United States and in Canada and one method was then chosen, taken into account evaluation criteria found in the literature. The main objective of this research was reached: the method selected can be applied with some minor modifications concerning mainly the data collection procedure. This research shall contribute for the popularization of mathematical models as routing techniques that could help planners: (a) to design a new bus route and/or to redesign an existing one (b) to completely redesign complex transit systems.

O objetivo deste trabalho é apresentar os conceitos da logística, em especial a logística de serviços, e algumas de suas ferramentas, como a roteirização de veículos e previsão de demanda por serviços, aplicadas aos serviços urbanos, neste caso o serviço de remendos em pavimentos, visando aumentar a eficiência desse serviço. O serviço de remendos, muitas vezes chamado de tapa-buracos, é uma atividade de manutenção comum nas cidades. Para observar a aplicação das ferramentas foi elaborado um estudo de caso na cidade de São Carlos. Dados sobre o serviço de remendos em pavimentos foram coletados e, com a ajuda de um sistema de informações geográficas – SIG, foram gerados roteiros que foram comparados com os dados originais. As rotas simuladas pelo SIG foram mais eficientes do que as praticadas na realidade, mostrando a utilidade dos conceitos da logística e também a utilidade do SIG na gerência da infra-estrutura urbana. A previsão de demanda por serviços de remendos não pôde ser observada devido à falta de dados históricos, fundamentais a essa etapa do trabalho. / The objective of this work is to introduce the concepts of logistics, especially the service logistics and some of its tools as the vehicle routing and the demand forecast for services, applied to the urban services, in this case the patching service in pavements in order to increase the efficiency of this service. The patching service, many times called tapa-buracos (in Brazil), is a common activity of maintenance in the cities. To observe the application of the tools one case study was elaborated in the city of São Carlos. Data about the patching service in pavements were collected and, helped by the geographic information system – GIS, routes were created and compared to the original data. The paths simulated by the GIS were more efficient than the real ones, showing the utility of the logistics concepts and also the utility of the GIS on the management of the urban infrastructure. The demand forecast for services of patching could not be observed due of the lack of historical data, essential to this part of the work.

A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.

As localizações dos terminais e as rotas de entrega que partem desses terminais são decisões importantes que surgem na concepção de redes de transporte de carga fracionada. Nesses casos, dois problemas independentes precisam ser tratados: o problema da localização de instalações (LAP) e o problema da roteirização dos veículos (VRP). Este trabalho apresenta um modelo matemático para resolver o LAP e o VRP de forma integrada, ou seja, para a resolução do problema de Localização/Roteirização (Location Routing Problem - LRP). De acordo com a literatura, a abordagem integrada do LRP fornece melhores resultados do que a solução do LAP e do VRP separadamente. O modelo foi testado e aplicado em um caso real de Many-to-Many com Multiplos elos LRP, respeitou as restrições e o nível de serviço exigido e propiciou melhoria nos resultados para a empresa de transporte no qual foi aplicado. Os resultados do modelo também foram melhores do que os resultados apresentados por um software líder de mercado. / In the Less Than Truck Load (LTL) operations both the location of facilities and the routing of vehicles are important decisions for the optimal design of the related logistics network. Two interdependent problems arise: the Location Allocation Problem (LAP) and the Vehicle Routing Problem (VRP). This paper presents a mathematical model to solve the LAP and the VRP simultaneously on an integrated way, such as the so-called Location-Routing Problem (LRP). According to the literature the LRP integrated approach provides better results than considering the LAP and the VRP separately. The model was tested and applied to a real case of Many-to-Many with Multi-Echelons LTL Location-Routing Problem respecting the constraints and the required service level standard and provided better results for the company in which it was tested. The model results also were better than the results presented by market-leading software.