Méthode de recherche à grand voisinage pour un problème de tournées de véhicules avec flotte privée et transporteur externe

Dans ce mémoire, nous étudions un problème de tournées de véhicules dans lequel une flotte privée de véhicules n’a pas la capacité suffisante pour desservir les demandes des clients. Dans un tel cas, on fait appel à un transporteur externe. Ce dernier n’a aucune contrainte de capacité, mais un coût est encouru lorsqu’un client lui est affecté. Il n’est pas nécessaire de mettre tous les véhicules de la flotte privée en service si cette approche se révèle plus économique. L’objectif consiste à minimiser le coût fixe des véhicules, puis le coût variable de transport et le coût chargé par le transporteur externe. Notre travail consiste à appliquer la métaheuristique de recherche adaptative à grand voisinage sur ce problème. Nous comparons nos résultats avec ceux obtenus précédemment avec différentes techniques connues sur les instances de Christofides et celles de Golden.

Host and Network Optimizations for Performance Enhancement and Energy Efficiency in Data Center Networks

Modern data centers host hundreds of thousands of servers to achieve economies of scale. Such a huge number of servers create challenges for the data center network (DCN) to provide proportionally large bandwidth. In addition, the deployment of virtual machines (VMs) in data centers raises the requirements for efficient resource allocation and find-grained resource sharing. Further, the large number of servers and switches in the data center consume significant amounts of energy. Even though servers become more energy efficient with various energy saving techniques, DCN still accounts for 20% to 50% of the energy consumed by the entire data center. The objective of this dissertation is to enhance DCN performance as well as its energy efficiency by conducting optimizations on both host and network sides. First, as the DCN demands huge bisection bandwidth to interconnect all the servers, we propose a parallel packet switch (PPS) architecture that directly processes variable length packets without segmentation-and-reassembly (SAR). The proposed PPS achieves large bandwidth by combining switching capacities of multiple fabrics, and it further improves the switch throughput by avoiding padding bits in SAR. Second, since certain resource demands of the VM are bursty and demonstrate stochastic nature, to satisfy both deterministic and stochastic demands in VM placement, we propose the Max-Min Multidimensional Stochastic Bin Packing (M3SBP) algorithm. M3SBP calculates an equivalent deterministic value for the stochastic demands, and maximizes the minimum resource utilization ratio of each server. Third, to provide necessary traffic isolation for VMs that share the same physical network adapter, we propose the Flow-level Bandwidth Provisioning (FBP) algorithm. By reducing the flow scheduling problem to multiple stages of packet queuing problems, FBP guarantees the provisioned bandwidth and delay performance for each flow. Finally, while DCNs are typically provisioned with full bisection bandwidth, DCN traffic demonstrates fluctuating patterns, we propose a joint host-network optimization scheme to enhance the energy efficiency of DCNs during off-peak traffic hours. The proposed scheme utilizes a unified representation method that converts the VM placement problem to a routing problem and employs depth-first and best-fit search to find efficient paths for flows.

Méthode de recherche à grand voisinage pour un problème de tournées de véhicules avec flotte privée et transporteur externe

Dans ce mémoire, nous étudions un problème de tournées de véhicules dans lequel une flotte privée de véhicules n’a pas la capacité suffisante pour desservir les demandes des clients. Dans un tel cas, on fait appel à un transporteur externe. Ce dernier n’a aucune contrainte de capacité, mais un coût est encouru lorsqu’un client lui est affecté. Il n’est pas nécessaire de mettre tous les véhicules de la flotte privée en service si cette approche se révèle plus économique. L’objectif consiste à minimiser le coût fixe des véhicules, puis le coût variable de transport et le coût chargé par le transporteur externe. Notre travail consiste à appliquer la métaheuristique de recherche adaptative à grand voisinage sur ce problème. Nous comparons nos résultats avec ceux obtenus précédemment avec différentes techniques connues sur les instances de Christofides et celles de Golden.

Distributed Large-scale Mixed-Integer Optimization with Application to Energy and Multi-robot Networks

Several decision and control tasks in cyber-physical networks can be formulated as large- scale optimization problems with coupling constraints. In these "constraint-coupled" problems, each agent is associated to a local decision variable, subject to individual constraints. This thesis explores the use of primal decomposition techniques to develop tailored distributed algorithms for this challenging set-up over graphs. We first develop a distributed scheme for convex problems over random time-varying graphs with non-uniform edge probabilities. The approach is then extended to unknown cost functions estimated online. Subsequently, we consider Mixed-Integer Linear Programs (MILPs), which are of great interest in smart grid control and cooperative robotics. We propose a distributed methodological framework to compute a feasible solution to the original MILP, with guaranteed suboptimality bounds, and extend it to general nonconvex problems. Monte Carlo simulations highlight that the approach represents a substantial breakthrough with respect to the state of the art, thus representing a valuable solution for new toolboxes addressing large-scale MILPs. We then propose a distributed Benders decomposition algorithm for asynchronous unreliable networks. The framework has been then used as starting point to develop distributed methodologies for a microgrid optimal control scenario. We develop an ad-hoc distributed strategy for a stochastic set-up with renewable energy sources, and show a case study with samples generated using Generative Adversarial Networks (GANs). We then introduce a software toolbox named ChoiRbot, based on the novel Robot Operating System 2, and show how it facilitates simulations and experiments in distributed multi-robot scenarios. Finally, we consider a Pickup-and-Delivery Vehicle Routing Problem for which we design a distributed method inspired to the approach of general MILPs, and show the efficacy through simulations and experiments in ChoiRbot with ground and aerial robots.

Analysis and optimisation of books flow among branches through simulation: the case of Trondheim’s Public Library

Il presente lavoro di tesi verte sull’analisi e l’ottimizzazione dei flussi di libri generati tra le diverse sedi della biblioteca pubblica, Trondheim folkebibliotek, situata a Trondheim, città del nord norvegese. La ricerca si inserisce nell’ambito di un progetto pluriennale, SmartLIB, che questa sta intraprendendo con l’università NTNU - Norwegian University of Science and Technology. L’obiettivo di questa tesi è quello di analizzare possibili soluzioni per ottimizzare il flusso di libri generato dagli ordini dei cittadini. Una prima fase di raccolta ed analisi dei dati è servita per avere le informazioni necessarie per procedere nella ricerca. Successivamente è stata analizzata la possibilità di ridurre i flussi andando ad associare ad ogni dipartimento la quantità di copie necessarie per coprire il 90% della domanda, seguendo la distribuzione di Poisson. In seguito, sono state analizzate tre soluzioni per ottimizzare i flussi generati dai libri, il livello di riempimento dei box ed il percorso del camion che giornalmente visita tutte le sedi della libreria. Di supporto per questo secondo studio è stato il Vehicle Routing Problem (VRP). Un modello simulativo è stato creato su Anylogic ed utilizzato per validare le soluzioni proposte. I risultati hanno portato a proporre delle soluzioni per ottimizzare i flussi complessivi, riducendo il delay time di consegna dei libri del 50%, ad una riduzione del 53% del flusso di box e ad una conseguente aumento del 44% del tasso di riempimento di ogni box. Possibili future implementazioni delle soluzioni trovate corrispondono all’installazione di una nuova Sorting Machine nella sede centrale della libreria ed all’implementazione sempre in quest’ultima di un nuovo schedule giornaliero.

Smart freight transport in urban areas: a crowd-shipping model using autonomous vehicles

L'avanzamento dell'e-commerce e l'aumento della densità abitativa nel centro città sono elementi che incentivano l'incremento della richiesta merci all'interno dei centri urbani. L'attenzione all'impatto ambientale derivante da queste attività operative è un punto focale oggetto di sempre maggiore interesse. Attraverso il seguente studio, l'obiettivo è definire attuali e potenziali soluzioni nell'ambito della logistica urbana, con particolare interesse alle consegne dell'ultimo miglio. Una soluzione proposta riguarda la possibilità di sfruttare la capacità disponibile nei flussi generati dalla folla per movimentare merce, pratica nota sotto il nome di Crowd-shipping. L'idea consiste nella saturazione di mezzi già presenti nella rete urbana al fine di ridurre il numero di veicoli commerciali e minimizzare le esternalità negative annesse. A supporto di questa iniziativa, nell'analisi verranno considerati veicoli autonomi elettrici a guida autonoma. La tesi è incentrata sulla definizione di un modello di ottimizzazione matematica, che mira a designare un network logistico-distributivo efficiente per le consegne dell'ultimo miglio e a minimizzare le distanze degli attori coinvolti. Il problema proposto rappresenta una variante del Vehicle Routing Problem con time windows e multi depots. Il problema è NP-hard, quindi computazionalmente complesso per cui sarà necessario, in fase di analisi, definire un approccio euristico che permetterà di ottenere una soluzione sub-ottima in un tempo di calcolo ragionevole per istanze maggiori. L'analisi è stata sviluppata nell'ambiente di sviluppo Eclipse, attraverso il risolutore Cplex, in linguaggio Java. Per poterne comprendere la validità, è prevista un'ultima fase in cui gli output del modello ottimo e dell'euristica vengono confrontati tra loro su parametri caratteristici. Bisogna tuttavia considerare che l' utilizzo di sistemi cyber-fisici a supporto della logistica non può prescindere da un costante sguardo verso il progresso.

The mu-way intersection problem for m-cycle systems

An m-cycle system of order upsilon is a partition of the edge-set of a complete graph of order upsilon into m-cycles. The mu -way intersection problem for m-cycle systems involves taking mu systems, based on the same vertex set, and determining the possible number of cycles which can be common to all mu systems. General results for arbitrary m are obtained, and detailed intersection values for (mu, m) = (3, 4), (4, 5),(4, 6), (4, 7), (8, 8), (8, 9). (For the case (mu, m)= (2, m), see Billington (J. Combin. Des. 1 (1993) 435); for the case (Cc,m)=(3,3), see Milici and Quattrochi (Ars Combin. A 24 (1987) 175. (C) 2001 Elsevier Science B.V. All rights reserved.

The effect of deforestation on the water cycle in the amazon basin: an attempt reformulate the problem

If widespread deforestation in Amazon results in reduced evaporative water flux, then either a decrease in evaporation is compensated locally by reduced rainfall,or else changed moisture balance expresses itself downwind in the yet undisturbed forest. The question of where rain will occur is crucial. It is suggested that the appearance of clouds and the occurrence of rainout is governed primarily by the interplay of local meteorologic and physical geography parameters with the atmospheric stability structure except for a few well-defined periods when rain is dominated by large scale atmospheric instability. This means that the study of these phenomena (local heat balances,studies on cloud formation mechanism, vertical atmospheric stability, etc.) must be made on the scale of the cloud size, a few tens of kilometers at most.

Determining departure times in dynamic and stochastic maritime routing and scheduling problem

In maritime transportation, decisions are made in a dynamic setting where many aspects of the future are uncertain. However, most academic literature on maritime transportation considers static and deterministic routing and scheduling problems. This work addresses a gap in the literature on dynamic and stochastic maritime routing and scheduling problems, by focusing on the scheduling of departure times. Five simple strategies for setting departure times are considered, as well as a more advanced strategy which involves solving a mixed integer mathematical programming problem. The latter strategy is significantly better than the other methods, while adding only a small computational effort.

Hybrid Algorithms for Routing and Assignment Wavelengths in Optical Networks

This paper presents a strategy for the solution of the WDM optical networks planning. Specifically, the problem of Routing and Wavelength Allocation (RWA) in order to minimize the amount of wavelengths used. In this case, the problem is known as the Min-RWA. Two meta-heuristics (Tabu Search and Simulated Annealing) are applied to take solutions of good quality and high performance. The key point is the degradation of the maximum load on the virtual links in favor of minimization of number of wavelengths used; the objective is to find a good compromise between the metrics of virtual topology (load in Gb/s) and of the physical topology (quantity of wavelengths). The simulations suggest good results when compared to some existing in the literature.

Fretting fatigue in overhead conductors: Rig design and failure analysis of a Grosbeak aluminium cable steel reinforced conductor

The performance optimisation of overhead conductors depends on the systematic investigation of the fretting fatigue mechanisms in the conductor/clamping system. As a consequence, a fretting fatigue rig was designed and a limited range of fatigue tests was carried out at the middle high cycle fatigue regime in order to access an exploratory S-N curve for a Grosbeak conductor, which was mounted on a mono-articulated aluminium clamping system. Subsequent to these preliminary fatigue tests, the components of the conductor/clamping system, such as ACSR conductor, upper and lower clamps, bolt and nuts, were subjected to a failure analysis procedure in order to investigate the metallurgical free variables interfering on the fatigue test results, aiming at the optimisation of the testing reproducibility. The results indicated that the rupture of the planar fracture surfaces observed in the external At strands of the conductor tested under lower bending amplitude (0.9 mm) occurred by fatigue cracking (I mm deep), followed by shear overload. The V-type fracture surfaces observed in some At strands of the conductor tested under higher bending amplitude (1.3 mm) were also produced by fatigue cracking (approximately 400 mu m deep), followed by shear overload. Shear overload fracture (45 degrees fracture surface) was also observed on the remaining At wires of the conductor tested under higher bending amplitude (1.3 mm). Additionally, the upper and lower Al-cast clamps presented microstructure-sensitive cracking, which was folowed by particle detachment and formation of abrasive debris on the clamp/conductor tribo-interface, promoting even further the fretting mechanism. The detrimental formation of abrasive debris might be inhibited by the selection of a more suitable class of as-cast At alloy for the production of clamps. Finally, the bolt/nut system showed intense degradation of the carbon steel nut (fabricated in ferritic-pearlitic carbon steel, featuring machined threads with 190 HV), with intense plastic deformation and loss of material. Proper selection of both the bolt and nut materials and the finishing processing might prevent the loss in the clamping pressure during the fretting testing. It is important to control the specification of these components (clamps, bolt and nuts) prior to the start of large scale fretting fatigue testing of the overhead conductors in order to increase the reproducibility of this assessment. (c) 2008 Elsevier Ltd. All rights reserved.

5-cycle systems of K-v-F with a hole

Recently the problem of the existence of a 5-cycle system of K-v with a hole of size u was completely solved. In this paper we prove necessary and sufficient conditions on v and u for the existence of a 5-cycle system of K-v - F, with a hole of size u.

Embeddings of m-cycle systems and incomplete m-cycle systems: m<=14

In this paper we completely settle the embedding problem for m-cycle systems with m less than or equal to 14. We also solve the more general problem of finding m-cycle systems of K-v - K-u when m is an element of {4,6,7,8,10,12,14}.

On the Hamilton-Waterloo problem

The Hamilton-Waterloo problem asks for a 2-factorisation of K-v in which r of the 2-factors consist of cycles of lengths a(1), a(2),..., a(1) and the remaining s 2-factors consist of cycles of lengths b(1), b(2),..., b(u) (where necessarily Sigma(i)(=1)(t) a(i) = Sigma(j)(=1)(u) b(j) = v). In thus paper we consider the Hamilton-Waterloo problem in the case a(i) = m, 1 less than or equal to i less than or equal to t and b(j) = n, 1 less than or equal to j less than or equal to u. We obtain some general constructions, and apply these to obtain results for (m, n) is an element of {(4, 6)1(4, 8), (4, 16), (8, 16), (3, 5), (3, 15), (5, 15)}.

A user-centered interface for scheduling problem definition

In this paper we present a user-centered interface for a scheduling system. The purpose of this interface is to provide graphical and interactive ways of defining a scheduling problem. To create such user interface an evaluation-centered user interaction development method was adopted: the star life cycle. The created prototype comprises the Task Module and the Scheduling Problem Module. The first one allows users to define a sequence of operations, i.e., a task. The second one enables a scheduling problem definition, which consists in a set of tasks. Both modules are equipped with a set of real time validations to assure the correct definition of the necessary data input for the scheduling module of the system. The usability evaluation allowed us to measure the ease of interaction and observe the different forms of interaction provided by each participant, namely the reactions to the real time validation mechanism.