Tactical Vehicle Routing Planning with Application to Milk Collection and Distribution

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.

Laser Spectroscopy: TDLAS instrumentation and NIR analysis of some organic materials

Near-infrared spectroscopy can be a workhorse technique for materials analysis in industries such as agriculture, pharmaceuticals, chemicals and polymers. A near-infrared spectrum represents combination bands and overtone bands that are harmonics of absorption frequencies in the mid-infrared. Near-infrared absorption includes a combination-band region immediately adjacent to the mid-infrared and three overtone regions. All four near-infrared regions contain "echoes" of the fundamental mid-infrared absorptions. For example, vibrations in the mid-infrared due to the C-H stretches will produce four distinct bands in each of the overtone and combination regions. As the bands become more removed from the fundamental frequencies they become more widely separated from their neighbors, more broadened and are dramatically reduced in intensity. Because near-infrared bands are much less intense, more of the sample can be used to produce a spectra and with near-infrared, sample preparation activities are greatly reduced or eliminated so more of the sample can be utilized. In addition, long path lengths and the ability to sample through glass in the near-infrared allows samples to be measured in common media such as culture tubes, cuvettes and reaction bottles. This is unlike mid-infrared where very small amounts of a sample produce a strong spectrum; thus sample preparation techniques must be employed to limit the amount of the sample that interacts with the beam. In the present work we describe the successful the fabrication and calibration of a linear high resolution linear spectrometer using tunable diode laser and a 36 m path length cell and meuurement of a highly resolved structure of OH group in methanol in the transition region A v =3. We then analyse the NIR spectrum of certain aromatic molecules and study the substituent effects using local mode theory

Betweenness Centrality in Some Classes of Graphs

There are several centrality measures that have been introduced and studied for real world networks. They account for the different vertex characteristics that permit them to be ranked in order of importance in the network. Betweenness centrality is a measure of the influence of a vertex over the flow of information between every pair of vertices under the assumption that information primarily flows over the shortest path between them. In this paper we present betweenness centrality of some important classes of graphs.

Small World Folksonomies: Clustering in Tri-Partite Hypergraphs

Many recent Web 2.0 resource sharing applications can be subsumed under the "folksonomy" moniker. Regardless of the type of resource shared, all of these share a common structure describing the assignment of tags to resources by users. In this report, we generalize the notions of clustering and characteristic path length which play a major role in the current research on networks, where they are used to describe the small-world effects on many observable network datasets. To that end, we show that the notion of clustering has two facets which are not equivalent in the generalized setting. The new measures are evaluated on two large-scale folksonomy datasets from resource sharing systems on the web.

Network properties of folksonomies

Social resource sharing systems like YouTube and del.icio.us have acquired a large number of users within the last few years. They provide rich resources for data analysis, information retrieval, and knowledge discovery applications. A first step towards this end is to gain better insights into content and structure of these systems. In this paper, we will analyse the main network characteristics of two of the systems. We consider their underlying data structures – socalled folksonomies – as tri-partite hypergraphs, and adapt classical network measures like characteristic path length and clustering coefficient to them. Subsequently, we introduce a network of tag co-occurrence and investigate some of its statistical properties, focusing on correlations in node connectivity and pointing out features that reflect emergent semantics within the folksonomy. We show that simple statistical indicators unambiguously spot non-social behavior such as spam.

Network properties of folksonomies

Social resource sharing systems like YouTube and del.icio.us have acquired a large number of users within the last few years. They provide rich resources for data analysis, information retrieval, and knowledge discovery applications. A first step towards this end is to gain better insights into content and structure of these systems. In this paper, we will analyse the main network characteristics of two of these systems. We consider their underlying data structures – so-called folksonomies – as tri-partite hypergraphs, and adapt classical network measures like characteristic path length and clustering coefficient to them. Subsequently, we introduce a network of tag cooccurrence and investigate some of its statistical properties, focusing on correlations in node connectivity and pointing out features that reflect emergent semantics within the folksonomy. We show that simple statistical indicators unambiguously spot non-social behavior such as spam.

Interferometrische Sensoren mit Modulation der optischen Weglänge für die Fertigungsmesstechnik

Ziel dieser Dissertation ist es, eine Klasse interferometrischer Messgeräte zu charakterisieren und weiter zu entwickeln. Die Modulation der optischen Weglänge (OPLM) im Referenzarm eines interferometrischen Messsystems ist ein anpassungsfähiger Ansatz. Sie ist zur Messung von Oberflächenprofilen mit einer Auflösung bis in den sub-nm-Bereich bei einem Messbereich von bis zu 100 Mikrometer geeignet. Wird ein statisches Messobjekt gemessen, tritt durch die Modulation im Referenzarm am Detektor ein periodisches Interferenzmuster auf. Dies ist in der unten stehenden Abbildung schematisch dargestellt. Bei einer Veränderung des Abstandes zwischen Objekt und Messgerät kann aus der Phasen- und/oder Hüllkurvenverschiebung im Interferenzmuster die Abstandsänderung abgeleitet werden.Im Rahmen der Arbeit sind zwei funktionsfähige OPLM-Messsysteme entwickelt, aufgebaut und getestet worden. Diese demonstrieren, dass der OPLM-Ansatz ein breites Spektrum an Anwendungen durch eine optische Messung abdecken kann. Allerdings zeigen sich an den Messsystemen auch die Limitierungen des OPLM-Ansatzes. Die Systeme basieren auf einer Punktmessung mittels einer fasergekoppelten Sonde sowie auf einer linienförmigen Messung durch eine Zeilenkamera. Um eine hohe laterale Auflösung zu erzielen, wird die Zeilenkamera mit einem Mikroskop kombiniert. Damit flächenhaft gemessen werden kann, ist es notwendig, Messobjekt und Sensor zueinander zu verschieben. Daher wird eine Theorie entwickelt, unter welchen Randbedingungen bewegte Objekte von einem OPLM-Messsystem aufgelöst werden können. Die Theorie wird anschließend experimentell überprüft und bestätigt. Für die Auswertung der bei der Modulation der optischen Weglänge entstehenden Interferenzen existieren bereits einige erprobte Algorithmen, welche auf ihre Eignung hin untersucht und mit selbst entwickelten Algorithmen verglichen werden. Auch wird darauf eingegangen, welches die zentralen Herausforderungen bei der Planung von OPLM-Interferometern sind und wie sich insbesondere die Wahl des Aktors für die OPLM auf das gesamte Messsystem auswirkt. Bei den beiden Messsystemen werden jeweils wichtige Komponenten wie analoge Elektronik und Aktorik sowie ihre Funktionsweise erläutert. Es wird detailliert beschrieben, wie ein OPLM-Messsystem charakterisiert und kalibriert werden muss, um möglichst zuverlässige Messwerte zu liefern. Abschließend werden die Möglichkeiten der beiden entwickelten Systeme durch Beispielmessungen demonstriert, sowie ihre Messgenauigkeit charakterisiert.

Safe Distributed Coordination of Heterogeneous Robots through Dynamic Simple Temporal Networks

Research on autonomous intelligent systems has focused on how robots can robustly carry out missions in uncertain and harsh environments with very little or no human intervention. Robotic execution languages such as RAPs, ESL, and TDL improve robustness by managing functionally redundant procedures for achieving goals. The model-based programming approach extends this by guaranteeing correctness of execution through pre-planning of non-deterministic timed threads of activities. Executing model-based programs effectively on distributed autonomous platforms requires distributing this pre-planning process. This thesis presents a distributed planner for modelbased programs whose planning and execution is distributed among agents with widely varying levels of processor power and memory resources. We make two key contributions. First, we reformulate a model-based program, which describes cooperative activities, into a hierarchical dynamic simple temporal network. This enables efficient distributed coordination of robots and supports deployment on heterogeneous robots. Second, we introduce a distributed temporal planner, called DTP, which solves hierarchical dynamic simple temporal networks with the assistance of the distributed Bellman-Ford shortest path algorithm. The implementation of DTP has been demonstrated successfully on a wide range of randomly generated examples and on a pursuer-evader challenge problem in simulation.

On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs

A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan’s functional inverse of Ackermann’s function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T₁ time on a single processor can be checked on the fly for determinacy races in O(T₁) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks. By combining SP-order with Feng and Leiserson’s serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T₁ work, and a critical-path length of T[subscript ∞]. When executed on P processors, we prove that SP-hybrid runs in O((T₁/P + PT[subscript ∞]) lg n) expected time. To understand this bound, consider that the original program obtains linear speed-up over a 1-processor execution when P = O(T₁/T[subscript ∞]). In contrast, SP-hybrid obtains linear speed-up when P = O(√T₁/T[subscript ∞]), but the work is increased by a factor of O(lg n).

An improved method for discovering link criticality in transport networks

Quantitatively assessing the importance or criticality of each link in a network is of practical value to operators, as that can help them to increase the network's resilience, provide more efficient services, or improve some other aspect of the service. Betweenness is a graph-theoretical measure of centrality that can be applied to communication networks to evaluate link importance. However, as we illustrate in this paper, the basic definition of betweenness centrality produces inaccurate estimations as it does not take into account some aspects relevant to networking, such as the heterogeneity in link capacity or the difference between node-pairs in their contribution to the total traffic. A new algorithm for discovering link centrality in transport networks is proposed in this paper. It requires only static or semi-static network and topology attributes, and yet produces estimations of good accuracy, as verified through extensive simulations. Its potential value is demonstrated by an example application. In the example, the simple shortest-path routing algorithm is improved in such a way that it outperforms other more advanced algorithms in terms of blocking ratio

All-Optical Label Stacking: Easing the Trade-offs Between Routing and Architecture Cost in All-Optical Packet Switching

All-optical label swapping (AOLS) forms a key technology towards the implementation of all-optical packet switching nodes (AOPS) for the future optical Internet. The capital expenditures of the deployment of AOLS increases with the size of the label spaces (i.e. the number of used labels), since a special optical device is needed for each recognized label on every node. Label space sizes are affected by the way in which demands are routed. For instance, while shortest-path routing leads to the usage of fewer labels but high link utilization, minimum interference routing leads to the opposite. This paper studies all-optical label stacking (AOLStack), which is an extension of the AOLS architecture. AOLStack aims at reducing label spaces while easing the compromise with link utilization. In this paper, an integer lineal program is proposed with the objective of analyzing the softening of the aforementioned trade-off due to AOLStack. Furthermore, a heuristic aiming at finding good solutions in polynomial-time is proposed as well. Simulation results show that AOLStack either a) reduces the label spaces with a low increase in the link utilization or, similarly, b) uses better the residual bandwidth to decrease the number of labels even more

Inventory control exercises

Exercises and solutions in LaTex

MA230exam01pdf

Exam questions and solutions in PDF

MA230exam99pdf

Exam questions and solutions in PDF

MA230exam99

Exam questions and solutions in LaTex