This thesis identifies some problems, the genetic algorithm (GA) is facing in the area of vehicle routing and proposes various methods to address those problems. Those problems arise from the unavailability of suitable chromosomal representation and evaluation schemes of GA for the Vehicle Routing Problem (VRP). The representation and evaluation schemes already in use have problems of high computational cost, illegal chromosomes (chromosomes not representing a legal tour) and wrong fitness assignment (fitness not truly representing chromosome genetic makeup). These problems are addressed by several proposed new schemes, namely the Self Imposed Constraints Evaluation scheme, the Contour and Reverse Contour Evaluation schemes and the Order Skipping Evaluation scheme, which are specifically tailored for various objectives, problems and situations. Apart from this, a methodology, which has previously being used in other meta-heuristics, is incorporated into GA i.e., the independent application of GA on various sub-localities of the problem. We call this GA, a Localized Genetic Algorithm (LGA). LGA is an iterative procedure between optimization and controlled de-optimization. The procedure of controlled de-optimization is also novel. It brings the solution into a new search space while controlling its cost effectively. LGA is introduced with various search techniques, i.e. intensive, extensive and selective, the use of which depends on the problem size and the availability of computational resources. Furthermore, search reduction techniques (Fitness Approximation Methods) are also introduced into the LGA, which has enabled the LGA to be applied to large scale problems. Due to the implementation of those proposals, LGA is the first GA-driven approach to be applied to very large scale CVRP problems of up to 1200 customers, i.e. datasets presented by Feiyue in 2005 and large scale VRPTW problems of up to 1000 customers, datasets presented by Gehring and Homberger in 1999. Lastly, a standard unit for computational comparison, i.e., Bellman's Evaluation Units BEUs, is also introduced to facilitate computational comparisons for future researchers. LGA has shown promising results on CVRP and VRPTW problems. It is flexible and also has the potential to be extended to not only other vehicle routing problems, but also to other ordering problems.

Submitted by Filipe dos Santos (fsantos@pucsp.br) on 2018-10-19T11:51:51Z No. of bitstreams: 1 Rafael Emídio Murata Rodrigues.pdf: 1071545 bytes, checksum: 468e0f7e27e278e12eed0dd52f4198cc (MD5) / Made available in DSpace on 2018-10-19T11:51:51Z (GMT). No. of bitstreams: 1 Rafael Emídio Murata Rodrigues.pdf: 1071545 bytes, checksum: 468e0f7e27e278e12eed0dd52f4198cc (MD5) Previous issue date: 2018-08-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In our lives, we constantly move in streets and neighborhoods. In general, we consider time and (or distance) when planning the route. However, their solutions may face complex problems arising from the different possibilities of solutions. Similar to route planning, the Vehicle Routing Problem was introduced by George B. Dantzig and John H. Ramser in 1959 and consists of delivering gasoline to several fuel stations; at first a mathematical proposal, later became an algorithmic approach, for planning of routes of delivery of products in an optimized way (searching the "shortest path"). Although, during the search of shortest path, they are limited to the use of the streets. In this context emerges the Human Routing Problem, such an approach is not limited to streets, but makes use of all possible paths, by vehicles and humans. Such a problem can be observed in route planning at airports, museums and a supply chain company that wants to optimize the route of delivery of its products and increase customer satisfaction. Based on the Vehicle Routing Problem, the Human Routing Problem will be proposed. Its problematic will be demonstrated in a prototype, capable of assisting in the planning of human routes and three use cases. Ideas of Human Routing Problem had inspiration in the collective foraging insects / Na nossa vida, nos locomovemos constantemente em ruas e bairros. Em geral, consideramos o tempo e (ou a distância), ao planejar a rota. Contudo, suas soluções podem enfrentar problemas complexos, decorrentes das diversas possibilidades de soluções. Semelhante a planejamento de rotas, o Problema de Roteamento de Veículos foi introduzido por George B. Dantzig, e John H. Ramser em 1959 e consiste em entregar gasolina diversos postos de combustível; a princípio uma proposta matemática, mais tarde tornou-se uma abordagem algorítmica, para planejamento de rotas de entrega de produtos de forma otimizada (buscando o “menor caminho”). Embora, durante a busca de menor caminho, limitam-se ao uso de ruas. Neste contexto emerge o Problema de Roteamento Humano, tal abordagem não se limita a ruas, mas faz uso de todos os caminhos possíveis, por veículos e humanos. Tal problemática, pode ser observada nos planejamentos de rotas em aeroportos, museus e em uma empresa de supply chain que deseja otimizar a rota de entrega dos seus produtos, e aumentar a satisfação dos seus clientes. Tomando como base central, o Problema de Roteamento de Veículos será proposto o Problema de Roteamento Humano. Sua problemática, será demonstrado em um protótipo, capaz de auxiliar no planejamento de rotas humanas e três casos de uso. As ideias do Problema de Roteamento Humano tiveram inspiração no forrageamento dos insetos coletivos

<p> Orbital Debris is a growing challenge for the Space Industry. The increasing density of derelict objects in high-value orbital regimes is resulting in more conjunction warnings and break-up events with cascading repercussions on active satellites and spacecraft. The recent rapid growth of the commercial space industry, in particular proliferated satellite constellations, has placed orbital debris remediation at the forefront of Space Industry efforts. The need to remove existing debris, combined with a growing demand for active satellite life extension services, has created an emerging market for space logistics, in particular spacecraft capable of rendezvous and docking, orbital refueling, debris deorbiting, or object relocation. This market has seen numerous companies emerge with multi-purpose on-orbit servicing platforms. This ecosystem poses technological, economical, and policy questions to decision-makers looking to acquire platforms or invest in technologies and requires a System-of-Systems approach to determine mission and system concepts of merit. An open-source modeling, analysis, and simulation software toolbox has been developed which enables rapid early-stage analysis and design of diverse fleets of on-orbit servicing platforms, with a specific emphasis on active debris removal applications. The toolbox provides fetching and processing of real-time orbital catalog data, clustering and scoring of high-value debris targets, flexible and efficient multi-vehicle multi-objective time-varying routing optimization, and fleet-level lifecycle cost estimation. The toolbox is applied to a diverse sample of promising commercial platforms to enable government decision-makers to make sound investment and acquisition decisions to support the development of ADR technologies, missions, and companies. </p>

El sector de servicio de mantenimiento demuestra un crecimiento continuo desde la incorporación de máquinas para el desarrollo de operaciones. En el Perú, este sector tiene un crecimiento lento, a pesar de ello, algunas empresas de mantenimiento han encontrado oportunidades en nichos poco explorados, como los mantenimientos a cajeros automáticos. Sin embargo, el tipo de servicio que brindan no cumplen ciertos aspectos esenciales para satisfacer la demanda, debido al exceso de tiempo en la atención del servicios y llegada a destiempo para la atención. Es por ello, que el objetivo principal del proyecto es reducir el lead time para el cumplimiento del cronograma anual, ya que se presencia una pérdida del 33.44% de la facturación del servicio de mantenimiento en el año 2019. Por esta razón, se diseña un modelo de gestión de servicio de mantenimiento que comprende la asignación de ruta por el vehicle routing problem mediante la distancia euclidiana y la estandarización de procesos mediante el estudio de tiempos que será validado mediante la simulación del software Arena. Asimismo, se analiza un flujo de caja económico del cual se obtiene un índice de rendimiento (RBC) de S/. 2.31. Finalmente, ha sido posible la reducción del lead time y el cumplimiento del cronograma de mantenimiento. / The maintenance service sector shows continuous growth since the incorporation of machines for the development of operations. In Peru, this sector has a slow growth, despite this, some maintenance companies have found opportunities in little-explored niches, such as maintenance of ATMs. However, the type of service they provide does not meet certain essential aspects to satisfy the demand, due to the excess time in the service and arrival at the wrong time for the service. That is why the main objective of the project is to reduce the lead time for compliance with the annual schedule, since there is a 33.44% loss of the maintenance service billing in 2019. For this reason, a Maintenance service management model that includes the route assignment for the vehicle's routing problem using the standard Euclidean distance and the laization of processes through the study of times that will be validated through the simulation of the Arena software. Likewise, an economic cash flow is analyzed from which a performance index (RBC) of S /. 2.31. Finally, it has been possible to reduce lead time and meet the maintenance schedule. / Trabajo de investigación

The purpose of this thesis is to investigate how tractor swapping can be implemented in Vehicle Routing Problems (VRP) with electric heavy goods vehicles, and to evaluate how a model that allows for tractor swapping performs, in terms of schedule cost, against a model that does not. Hence, this thesis introduces a new rich VRP variant which includes tractor swapping, as well as time windows, pickup and delivery, and electric vehicles. The model is named Electric Tractor Swap Vehicle Routing Problem (E-TSVRP) and is formulated as a mixed integer linear program. As for the solver, Gurobi is used. The results show that utilizing tractor swapping can reduce the total cost of serving customers significantly by reducing en-route charging and utilizing drivers more efficiently. Specifically, it is shown that the cost reduction comes mainly from reducing driver work time. By demonstrating how tractor swapping works and how the results can be visualized on smaller cases, this thesis aims to serve as a foundation for future research within the field. To be able to fully implement the model for large logistics problem instances however, alternative solution methods such as heuristics or metaheuristics should be developed so that the problems can be solved in a reasonable amount of time. / Syftet med denna uppsats är att undersöka hur traktorbyten kan implementeras i "Vehicle Routing Problem" (VRP) med tunga, elektriska lastfordon, och att utvärdera hur en modell som tillåter traktorbyten presterar mot en modell som inte tillåter det, med avseende på den totala schemakostnaden. I uppsatsen introduceras därför en ny och generell VRP som har stöd för traktorbyten, men som också modellerar energikonsumtion och laddning av elektriska lastbilar, samt tillåter tidsfönster för när leveranser kan levereras och hämtas upp på godtyckliga platser. Modellen kallas för "Electric Tractor Swap Vehicle Routing Problem" (E-TSVRP) och formuleras som ett linjärt, blandat heltalsprogram. Programmet löses sedan med lösaren Gurobi. Resultaten visar att utnyttjandet av traktorbyten kan märkbart minska den totala kostnaden av att leverera varor till kunder genom att minska tiden som föraren väntar på att traktorn laddar. Mer specifikt tillåts möjligheten att byta till en ny traktor när den tidigare får slut på energi, vilket möjliggör en högre utnyttjandegrad av förarna, och den fakturerade tiden associerad till förarna kan minskas. Detta sker genom en avvägning mellan å ena sidan högre hårdvarukostnader för fler traktorer och å andra sidan lägre förarkostnader. Genom att demonstrera hur traktorbyten fungerar och hur resultaten kan visualiseras på mindre transportproblem, strävar denna uppsats efter att verka som en grund för framtida forskning. För att modellen ska kunna användas för stora logistikproblem bör dock alternativa lösningsmetoder som till exempel lösningsheuristiker eller metaheuristiker utvecklas så att problemen kan lösas inom en rimlig tid.