<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>

In this thesis we consider three challenging vehicle routing problems representing specific aspects of complex real-world problems: (i) the vehicle routing problem with unit demands, (ii) the preemptive stacker crane problem and (iii) a multi-period vehicle and technician routing problem. For the vehicle routing problem with units demands we continue research on the exponential multi-insertion neighborhood, investigate its properties and propose heuristic solution methods utilizing the neighborhood. For the preemptive stacker crane problem we study structural properties and provide bounds on the benefits of preemption and the benefits of so-called explicit drop nodes that are used exclusively to facilitate preemption. We propose construction heuristics that improve on the state-of-the-art in computational time and solution quality. The multi-period vehicle and technician routing problem is the subject of the VeRoLog Solver Challenge 2019. We develop a solution method that adapts to the limited computational budget and the given instance parameters. In summary, this thesis contributes to the structural analysis of the considered problems and proposes efficient heuristic solution methods that are effective even on large-scale instances and under tight restrictions of the computational budget. The methods combine global and local search approaches and take the available computational budget into account to realize an adaptive best-effort allocation of the resources.

[pt] Na atualidade, as organizações públicas e privadas buscam otimizar seus processos de modo que, estes garantam a qualidade dos serviços e o retorno sobre o capital investido nas diversas operações que estão envolvidas. Com isso, as organizações que não se preocupam em desenhar seus processos com eficácia e eficiência, estarão sujeitas a falhas, onerando assim os custos de operação. O estudo em questão propõe uma política de atendimento às demandas de manutenção e a utilização de uma ferramenta de roteirização diária no desempenho das operações do setor de manutenção de uma universidade pública do estado de Minas Gerais. O Problema de Roteirização de Veículos (PRV), do inglês Vehicle Routing Problem (VRP), como é conhecido na literatura, é definido como o atendimento a pontos de demanda geograficamente dispersos, por intermédio de uma frota de veículos disponíveis que, em geral, partem e retornam a um depósito central. O PRV tem como objetivo encontrar rotas viáveis com um menor custo que respeite as restrições operacionais, como duração da jornada de trabalho, capacidade dos veículos, duração das rotas, entre diversas outras. No trabalho será proposta uma metodologia que sugere uma nova política de distribuição de profissionais e materiais necessários para realização dos atendimentos às demandas de manutenção das unidades internas e externas da universidade e faz uso de um software de solução do PRV para verificar o desempenho das políticas propostas. Os resultados do estudo para as estratégias propostas apresentaram reduções significativas, variando de 17,86 porcento a 66,27 porcento do custo mensal, além de oportunidades de ganhos operacionais frente ao cenário atual. Espera-se que o software de PRV seja utilizado na programação diária dos roteiros dos veículos do setor. / [en] Currently, public and private organizations seek to optimize their process-es in order to guarantee the quality of services and the return on capital invested in the various operations that are involved. As a result, organizations that are not concerned with designing their processes effectively and efficiently, will be sub-ject to failures, thus increasing operating costs. The study in question proposes a policy to meet maintenance demands and the use of a daily routing tool in the performance of operations in the maintenance sector of a public university in the state of Minas Gerais. The Problema de Roteamento de Veículos (PRV), from the English Vehicle Routing Problem (VRP), as it is known in the literature, is defined as the service to meet geographically dispersed demand points, through a fleet of available vehicles that, in general, depart and return to a central depot. The VRP aims to find viable routes at a lower cost that respects operational re-strictions, such as working hours, vehicle capacity, duration of routes, among others. In the work, a methodology will be proposed that suggests a new policy for the distribution of professionals and materials needed to fulfill the demands of maintenance of the university s internal and external units and makes use of a VRP solution software to verify the performance of the proposed policies. The results of the study for the proposed strategies showed significant reductions, varying from 17.86 percent to 66.27 percent of the monthly cost, in addition to opportunities for operational gains compared to the current scenario. It is expected that the VRP software will be used in the daily programming of the routes for vehicles in the sector.

No description available.

The vehicle routing problem is an optimisation problem with a high computational complexity that can be solved using heuristics methods to achieve near-optimal solutions in a reasonable amount of time. The work done in this study aims to compare the execution time and distance of different routing engines when using VROOM, as well as evaluate different implementations of the k-means algorithm by looking at the rand- and adjusted rand index. The results show a difference in the distance and execution time depending on which routing engine is used and it is unclear if there is a difference in the k-means implementations. Investigating the cause behind the observed results would be interesting in future works.

The thesis addresses the 'algorithm configuration problem,' focusing on optimizing algorithm parameters to enhance performance across various domains, such as electricity auctions, production, and transportation. Efficiently solving multiple instances of the same optimization problem is crucial, and the algorithms' performance is significantly influenced by their parameter settings. Research into algorithm configuration has grown substantially over the past two decades, with techniques such as ParamILS, SMAC, and racing algorithms emerging to find optimal parameter configurations. These methods often use a 'one-size-fits-all' approach, which may not be effective for heterogeneous problem instances requiring different configurations. Therefore, the first research question (RQ1) investigates how to mathematically define and formulate the multi-objective, instance-specific algorithm configuration problem. An advanced approach is 'instance-specific configuration,' which optimizes parameters based on the unique features of each problem instance. This leads to the second research question (RQ2): assessing the current state of research in algorithm configuration, identifying research gaps, and structuring the field. The thesis proposes a new framework called MO-SMAC that integrates multiple objectives and instance features into the algorithm configuration process. This framework aims to move beyond generic solutions by providing tailored configurations for each instance. A case study involving the Capacitated Vehicle Routing Problem (CVRP) and Genetic Algorithms (GAs) explores this approach. This leads to the third research question (RQ3): applying the generic configuration formulation to a concrete case study and defining the corresponding instance and configuration spaces. The thesis also emphasizes the need for a systematic experimental methodology. The fourth research question (RQ4) addresses this by proposing a Design of Experiments (DoE) approach to identify the most influential configuration parameters and their interactions with instance features. RQ5 specifically investigates the most influential factors in the algorithm configuration process and examines whether interactions exist between these factors. The DoE methodology aims to systematically assess the impact of individual parameters and instance features on algorithm performance, using screening to identify significant factors, ranking to determine their importance, and exploring interactions. Another key focus is understanding the trade-offs between competing performance objectives (RQ6), such as solution quality versus runtime. This question explores how specific configuration parameters impact these trade-offs and provides insights into balancing multiple objectives to achieve optimal performance for specific problem instances. RQ7 examines the benefits of incorporating instance features into the algorithm configuration process. It seeks to determine whether considering these features leads to better-performing configurations by tailoring them to each instance's unique characteristics, thereby improving performance and robustness compared to generalized approaches. Finally, RQ8 explores the generalizability of results from offline training and assesses how well various configurators perform in online scenarios. It investigates whether configurations optimized offline can maintain their effectiveness when applied to new, unseen instances, addressing the need for unbiased evaluation and emphasizing the importance of generalizability to prevent overfitting and overspecialization. In conclusion, the thesis aims to develop a multi-objective, instance-specific algorithm configuration framework that balances competing performance goals and leverages instance features for improved results. It challenges the 'one-size-fits-all' approach by offering tailored configurations for specific problem instances and highlights the need for systematic experimentation to understand trade-offs and ensure generalizability in the configuration process.:List of Figures List of Tables List of Abbreviations List of Symbols I Problem description 1 Introduction 2 The multi-objective instance-specific algorithm configuration problem 2.1 Formal statement 2.2 Excursus: possible algorithm performance metrics 2.3 Conclusion 3 Literature review 3.1 Algorithm selection 3.2 Parameter tuning and parameter control 3.2.1 Non-iterative parameter-tuning strategies 3.2.2 Iterative parameter-tuning strategies 3.2.3 Parameter control strategies 3.3 Gaining insights into instance hardness and algorithm performance 3.4 Benchmark generation 3.5 Conclusion II Case study 4 Case study 4.1 Formal statement of the optimization problem 4.2 The CVRP instance feature space F 4.3 The GA configuration space Θ 4.4 Conclusion 5 Experimental planning 5.1 Design of experiments 5.1.1 Practical methodology for DoE 5.1.2 Experimental designs 5.2 Instance space 5.2.1 Starting from a state-of-the-art benchmark set 5.2.2 Investigated instance features 5.2.3 Instance generation 5.3 Configuration space 5.4 Conclusion III Instance-oblivious algorithm configuration 6 Generalist 6.1 General methodology 6.2 Non-parametric tests 6.2.1 Single-objective ranking 6.2.2 Multi-objective ranking 6.3 Surrogate models 6.3.1 Linear regression 6.3.2 Shrinkage methods 6.3.3 Regression trees 6.4 Conclusion 7 Experiment: generalist 7.1 Planning 7.1.1 Instance space 7.1.2 Configuration space 7.2 Designing 7.2.1 Instance space 7.2.2 Configuration space 7.3 Conducting 7.4 Analyzing: non-parametric statistics 7.4.1 Single-objective parameter level rankings 7.4.2 Multi-objective rankings of configuration 7.5 Analyzing: Surrogate models 7.5.1 Data pre-processing 7.5.2 Performance metrics 7.5.3 Linear forward regression 7.5.4 Shrinkage 7.5.5 Regression tree 7.5.6 Pareto fronts 7.6 Evaluation 7.7 Conclusion IV Instance-specific algorithm configuration 8 Specialist 8.1 Bayesian optimization 8.2 Multi-Objective Instance-Specific Model-based algorithm configuration 8.2.1 General outline 8.2.2 Clustering 8.2.3 Acquisition function: expected hypervolume improvement 8.2.4 Candidate selection 8.2.5 Intensification 8.3 Surrogate models 8.3.1 Random forest 8.3.2 Gaussian process regression 8.4 Conclusion 9 Experiment: specialist 9.1 Planning 9.1.1 Initialization phase 9.1.2 Improvement phase 9.2 Designing 9.3 Conducting 9.4 Analyzing 9.4.1 Performance metrics 9.4.2 Surrogate models 9.5 Evaluation 9.6 Conclusion V Conclusion 10 Conclusion Bibliography

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire. / Many practical problems arising in real-world applications in the field of logistics can be modeled as vehicle routing problems (VRP). In broad terms, VRPs deal with designing optimal routes for delivering goods or services to a number of geographically scattered customers in a context in which, routing costs are minimized. Depending on the type of problem, one or several depots may be present. Routing problems are among the most difficult combinatorial optimization problems. In this dissertation we study a special combinatorial optimization problem, belonging to the class of the vehicle routing problem that is strongly linked to the context of the transportation networks. We introduce a new problem setting, which is mainly inspired by the activities of collecting milk from production farms and distributing the collected product to processing plants in Quebec. Two different variants of this problem setting are considered. The first variant seeks a tactical routing plan for the milk collection-distribution problem over a given planning horizon assuming that the production level over the considered horizon is fixed. The second variant aims to provide a more accurate plan by taking into account potential variations in terms of production level, which may occur during the course of a horizon. This thesis is cast into three main parts, as follows: In the first part, we describe an exact algorithm for the first variant of the problem, which is characterized by the presence of time windows, multiple depots, and a heterogeneous fleet of vehicles, where the objective is to minimize the routing cost. To this end, the problem is modeled as a multi-attribute vehicle routing problem. The exact algorithm proposed is based on the column generation approach, coupled with an elementary shortest path algorithm with resource constraints. In the second part, we design an exact framework to address the second variant of the problem. To this end, the problem is modeled as a multi-period vehicle routing problem, which explicitly takes into account potential production level variations over a horizon. New strategies are proposed to tackle the particular structure of the multi-period elementary shortest path algorithm with resource constraints. To solve realistic instances of the second variant of the problem in reasonable computation times, a heuristic approach is required. In the third part of this thesis, we propose an adaptive large neighborhood search, where various new exploration and exploitation strategies are proposed to improve the performance of the algorithm in terms of solution quality and computational efficiency.

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire. / Many practical problems arising in real-world applications in the field of logistics can be modeled as vehicle routing problems (VRP). In broad terms, VRPs deal with designing optimal routes for delivering goods or services to a number of geographically scattered customers in a context in which, routing costs are minimized. Depending on the type of problem, one or several depots may be present. Routing problems are among the most difficult combinatorial optimization problems. In this dissertation we study a special combinatorial optimization problem, belonging to the class of the vehicle routing problem that is strongly linked to the context of the transportation networks. We introduce a new problem setting, which is mainly inspired by the activities of collecting milk from production farms and distributing the collected product to processing plants in Quebec. Two different variants of this problem setting are considered. The first variant seeks a tactical routing plan for the milk collection-distribution problem over a given planning horizon assuming that the production level over the considered horizon is fixed. The second variant aims to provide a more accurate plan by taking into account potential variations in terms of production level, which may occur during the course of a horizon. This thesis is cast into three main parts, as follows: In the first part, we describe an exact algorithm for the first variant of the problem, which is characterized by the presence of time windows, multiple depots, and a heterogeneous fleet of vehicles, where the objective is to minimize the routing cost. To this end, the problem is modeled as a multi-attribute vehicle routing problem. The exact algorithm proposed is based on the column generation approach, coupled with an elementary shortest path algorithm with resource constraints. In the second part, we design an exact framework to address the second variant of the problem. To this end, the problem is modeled as a multi-period vehicle routing problem, which explicitly takes into account potential production level variations over a horizon. New strategies are proposed to tackle the particular structure of the multi-period elementary shortest path algorithm with resource constraints. To solve realistic instances of the second variant of the problem in reasonable computation times, a heuristic approach is required. In the third part of this thesis, we propose an adaptive large neighborhood search, where various new exploration and exploitation strategies are proposed to improve the performance of the algorithm in terms of solution quality and computational efficiency.

Dans ce mémoire, nous présentons un nouveau type de problème de confection de tour- née pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement. Cette variante est motivée par des problèmes similaires rapportés dans la littérature. Le véhi- cule en question contient plusieurs piles où des colis de hauteurs différentes sont empilés durant leur transport. La hauteur totale des items contenus dans chacune des piles ne peut dépasser une certaine hauteur maximale. Aucun déplacement n’est permis lors de la li- vraison d’un colis, ce qui signifie que le colis doit être sur le dessus d’une pile au moment d’être livré. De plus, tout colis i ramassé avant un colis j et contenu dans la même pile doit être livré après j. Une heuristique à grand voisinage, basé sur des travaux récents dans le domaine, est proposée comme méthode de résolution. Des résultats numériques sont rapportés pour plusieurs instances classiques ainsi que pour de nouvelles instances. / In this work, we consider a new type of pickup and delivery routing problem with last- in-first-out loading constraints for a single vehicle with multiple stacks. This problem is motivated by similar problems reported in the literature. In the problem considered, items are collected and put on top of one of multiple stacks inside the vehicle, such that the total height of the items on each stack does not exceed a given threshold. The loading constraints state that if items i and j are in the same stack and item i is collected before item j, then i must be delivered after j. Furthermore, an item can be delivered only if it is on the top of a stack. An adaptive large neighborhood heuristic, based on recent studies in this field, is proposed to solve the problem. Numerical results are reported on many classical instances reported in the literature and also on some new ones.

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.