Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

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.

Méthode de génération de colonnes pour les problèmes de conception de réseaux avec coûts d’ajout de capacité

Les problèmes de conception de réseaux ont reçu un intérêt particulier et ont été largement étudiés de par leurs nombreuses applications dans différents domaines, tels que les transports et les télécommunications. Nous nous intéressons dans ce mémoire au problème de conception de réseaux avec coûts d’ajout de capacité. Il s’agit d’installer un ensemble d’équipements sur un réseau en vue de satisfaire la demande, tout en respectant les contraintes de capacité, chaque arc pouvant admettre plusieurs équipements. L’objectif est de minimiser les coûts variables de transport des produits et les coûts fixes d’installation ou d’augmentation de capacité des équipements. La méthode que nous envisageons pour résoudre ce problème est basée sur les techniques utilisées en programmation linéaire en nombres entiers, notamment celles de génération de colonnes et de coupes. Ces méthodes sont introduites dans un algorithme général de branch-and-bound basé sur la relaxation linéaire. Nous avons testé notre méthode sur quatre groupes d’instances de tailles différentes, et nous l’avons comparée à CPLEX, qui constitue un des meilleurs solveurs permettant de résoudre des problèmes d’optimisation, ainsi qu’à une méthode existante dans la littérature combinant des méthodes exactes et heuristiques. Notre méthode a été plus performante que ces deux méthodes, notamment pour les instances de très grandes tailles.

Spectral Analysis of Bounded Self-adjoint operators - A Linear Algebraic Approach

This thesis Entitled Spectral theory of bounded self-adjoint operators -A linear algebraic approach.The main results of the thesis can be classified as three different approaches to the spectral approximation problems. The truncation method and its perturbed versions are part of the classical linear algebraic approach to the subject. The usage of block Toeplitz-Laurent operators and the matrix valued symbols is considered as a particular example where the linear algebraic techniques are effective in simplifying problems in inverse spectral theory. The abstract approach to the spectral approximation problems via pre-conditioners and Korovkin-type theorems is an attempt to make the computations involved, well conditioned. However, in all these approaches, linear algebra comes as the central object. The objective of this study is to discuss the linear algebraic techniques in the spectral theory of bounded self-adjoint operators on a separable Hilbert space. The usage of truncation method in approximating the bounds of essential spectrum and the discrete spectral values outside these bounds is well known. The spectral gap prediction and related results was proved in the second chapter. The discrete versions of Borg-type theorems, proved in the third chapter, partly overlap with some known results in operator theory. The pure linear algebraic approach is the main novelty of the results proved here.

Stochastic processes and their applications semi-markov analysis of some inventory and queuing problems

This thesis analyses certain problems in Inventories and Queues. There are many situations in real-life where we encounter models as described in this thesis. It analyses in depth various models which can be applied to production, storag¢, telephone traffic, road traffic, economics, business administration, serving of customers, operations of particle counters and others. Certain models described here is not a complete representation of the true situation in all its complexity, but a simplified version amenable to analysis. While discussing the models, we show how a dependence structure can be suitably introduced in some problems of Inventories and Queues. Continuous review, single commodity inventory systems with Markov dependence structure introduced in the demand quantities, replenishment quantities and reordering levels are considered separately. Lead time is assumed to be zero in these models. An inventory model involving random lead time is also considered (Chapter-4). Further finite capacity single server queueing systems with single/bulk arrival, single/bulk services are also discussed. In some models the server is assumed to go on vacation (Chapters 7 and 8). In chapters 5 and 6 a sort of dependence is introduced in the service pattern in some queuing models.

Verfahren zur echtzeitfähigen Simulation dynamischer Emissionsverläufe ausgewählter Schadstoffe von Ottomotoren

Im Rahmen dieser Arbeit werden Modellbildungsverfahren zur echtzeitfähigen Simulation wichtiger Schadstoffkomponenten im Abgasstrom von Verbrennungsmotoren vorgestellt. Es wird ein ganzheitlicher Entwicklungsablauf dargestellt, dessen einzelne Schritte, beginnend bei der Ver-suchsplanung über die Erstellung einer geeigneten Modellstruktur bis hin zur Modellvalidierung, detailliert beschrieben werden. Diese Methoden werden zur Nachbildung der dynamischen Emissi-onsverläufe relevanter Schadstoffe des Ottomotors angewendet. Die abgeleiteten Emissionsmodelle dienen zusammen mit einer Gesamtmotorsimulation zur Optimierung von Betriebstrategien in Hybridfahrzeugen. Im ersten Abschnitt der Arbeit wird eine systematische Vorgehensweise zur Planung und Erstellung von komplexen, dynamischen und echtzeitfähigen Modellstrukturen aufgezeigt. Es beginnt mit einer physikalisch motivierten Strukturierung, die eine geeignete Unterteilung eines Prozessmodells in einzelne überschaubare Elemente vorsieht. Diese Teilmodelle werden dann, jeweils ausgehend von einem möglichst einfachen nominalen Modellkern, schrittweise erweitert und ermöglichen zum Abschluss eine robuste Nachbildung auch komplexen, dynamischen Verhaltens bei hinreichender Genauigkeit. Da einige Teilmodelle als neuronale Netze realisiert werden, wurde eigens ein Verfah-ren zur sogenannten diskreten evidenten Interpolation (DEI) entwickelt, das beim Training einge-setzt, und bei minimaler Messdatenanzahl ein plausibles, also evidentes Verhalten experimenteller Modelle sicherstellen kann. Zum Abgleich der einzelnen Teilmodelle wurden statistische Versuchs-pläne erstellt, die sowohl mit klassischen DoE-Methoden als auch mittels einer iterativen Versuchs-planung (iDoE ) generiert wurden. Im zweiten Teil der Arbeit werden, nach Ermittlung der wichtigsten Einflussparameter, die Model-strukturen zur Nachbildung dynamischer Emissionsverläufe ausgewählter Abgaskomponenten vor-gestellt, wie unverbrannte Kohlenwasserstoffe (HC), Stickstoffmonoxid (NO) sowie Kohlenmono-xid (CO). Die vorgestellten Simulationsmodelle bilden die Schadstoffkonzentrationen eines Ver-brennungsmotors im Kaltstart sowie in der anschließenden Warmlaufphase in Echtzeit nach. Im Vergleich zur obligatorischen Nachbildung des stationären Verhaltens wird hier auch das dynami-sche Verhalten des Verbrennungsmotors in transienten Betriebsphasen ausreichend korrekt darge-stellt. Eine konsequente Anwendung der im ersten Teil der Arbeit vorgestellten Methodik erlaubt, trotz einer Vielzahl von Prozesseinflussgrößen, auch hier eine hohe Simulationsqualität und Ro-bustheit. Die Modelle der Schadstoffemissionen, eingebettet in das dynamische Gesamtmodell eines Ver-brennungsmotors, werden zur Ableitung einer optimalen Betriebsstrategie im Hybridfahrzeug ein-gesetzt. Zur Lösung solcher Optimierungsaufgaben bieten sich modellbasierte Verfahren in beson-derer Weise an, wobei insbesondere unter Verwendung dynamischer als auch kaltstartfähiger Mo-delle und der damit verbundenen Realitätsnähe eine hohe Ausgabequalität erreicht werden kann.

Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We study the preconditioning of symmetric indefinite linear systems of equations that arise in interior point solution of linear optimization problems. The preconditioning method that we study exploits the block structure of the augmented matrix to design a similar block structure preconditioner to improve the spectral properties of the resulting preconditioned matrix so as to improve the convergence rate of the iterative solution of the system. We also propose a two-phase algorithm that takes advantage of the spectral properties of the transformed matrix to solve for the Newton directions in the interior-point method. Numerical experiments have been performed on some LP test problems in the NETLIB suite to demonstrate the potential of the preconditioning method discussed.

Integración de SEXTANTE en GearSCape

SEXTANTE es un marco para el desarrollo de algoritmos dedicados al procesamiento de información geográficamente referenciada, que actualmente cuenta con más de doscientos algoritmos que son capaces de operar sobre datos vectoriales, alfanuméricos y raster. Por otra parte, GearScape es un sistema de información geográfico orientado al geoprocesamiento, que dispone de un lenguaje declarativo que permite el desarrollo de geoprocesos sin necesidad de herramientas de desarrollo complejas. Dicho lenguaje está basado en el estándar SQL y extendido mediante la norma OGC para el acceso a fenómenos simples. Al ser un lenguaje mucho más simple que los lenguajes de programación imperativos (java, .net, python, etc.) la creación de geoprocesos es también más simple, más fácil de documentar, menos propensa a bugs y además la ejecución es optimizada de manera automática mediante el uso de índices y otras técnicas. La posibilidad de describir cadenas de operaciones complejas tiene también valor a modo de documentación: es posible escribir todos los pasos para la resolución de un determinado problema y poder recuperarlo tiempo después, reutilizarlo fácilmente, comunicárselo a otra persona, etc. En definitiva, el lenguaje de geoprocesamiento de GearScape permite "hablar" de geoprocesos. La integración de SEXTANTE en GearScape tiene un doble objetivo. Por una parte se pretende proporcionar la posibilidad de usar cualquiera de los algoritmos con la interfaz habitual de SEXTANTE. Por la otra, se pretende añadir al lenguaje de geoprocesamiento de GearScape la posibilidad de utilizar algoritmos de SEXTANTE. De esta manera, cualquier problema que se resuelva mediante la utilización de varios de estos algoritmes puede ser descrito con el lenguaje de geoprocesamiento de GearScape. A las ventajas del lenguaje de GearScape para la definición de geoprocesos, se añade el abanico de geoprocesos disponible en SEXTANTE, por lo que el lenguaje de geoprocesamiento de GearScape nos permite "hablar" utilizando vocabulario de SEXTANTE

Flux comparison of Eulerian and Lagrangian estimates of Agulhas leakage: A case study using a numerical model

Estimating the magnitude of Agulhas leakage, the volume flux of water from the Indian to the Atlantic Ocean, is difficult because of the presence of other circulation systems in the Agulhas region. Indian Ocean water in the Atlantic Ocean is vigorously mixed and diluted in the Cape Basin. Eulerian integration methods, where the velocity field perpendicular to a section is integrated to yield a flux, have to be calibrated so that only the flux by Agulhas leakage is sampled. Two Eulerian methods for estimating the magnitude of Agulhas leakage are tested within a high-resolution two-way nested model with the goal to devise a mooring-based measurement strategy. At the GoodHope line, a section halfway through the Cape Basin, the integrated velocity perpendicular to that line is compared to the magnitude of Agulhas leakage as determined from the transport carried by numerical Lagrangian floats. In the first method, integration is limited to the flux of water warmer and more saline than specific threshold values. These threshold values are determined by maximizing the correlation with the float-determined time series. By using the threshold values, approximately half of the leakage can directly be measured. The total amount of Agulhas leakage can be estimated using a linear regression, within a 90% confidence band of 12 Sv. In the second method, a subregion of the GoodHope line is sought so that integration over that subregion yields an Eulerian flux as close to the float-determined leakage as possible. It appears that when integration is limited within the model to the upper 300 m of the water column within 900 km of the African coast the time series have the smallest root-mean-square difference. This method yields a root-mean-square error of only 5.2 Sv but the 90% confidence band of the estimate is 20 Sv. It is concluded that the optimum thermohaline threshold method leads to more accurate estimates even though the directly measured transport is a factor of two lower than the actual magnitude of Agulhas leakage in this model.

Damage rate is a predictor of fatigue life and creep strain rate in fatigue of tensile human cortical bone samples

We present results on the growth of damage in 29 fatigue tests of human femoral cortical bone from four individuals, aged 53–79. In these tests we examine the interdependency of stress, cycles to failure, rate of creep strain, and rate of modulus loss. The behavior of creep rates has been reported recently for the same donors as an effect of stress and cycles (Cotton, J. R., Zioupos, P., Winwood, K., and Taylor, M., 2003, "Analysis of Creep Strain During Tensile Fatigue of Cortical Bone," J. Biomech. 36, pp. 943–949). In the present paper we first examine how the evolution of damage (drop in modulus per cycle) is associated with the stress level or the "normalized stress" level (stress divided by specimen modulus), and results show the rate of modulus loss fits better as a function of normalized stress. However, we find here that even better correlations can be established between either the cycles to failure or creep rates versus rates of damage than any of these three measures versus normalized stress. The data indicate that damage rates can be excellent predictors of fatigue life and creep strain rates in tensile fatigue of human cortical bone for use in practical problems and computer simulations.

Infant-mother attachment and the growth of externalizing problems across the primary-school years

Background:  Some contend that attachment insecurity increases risk for the development of externalizing behavior problems in children. Method:  Latent-growth curve analyses were applied to data on 1,364 children from the NICHD Study of Early Child Care to evaluate the association between early attachment and teacher-rated externalizing problems across the primary-school years. Results:  Findings indicate that (a) both avoidant and disorganized attachment predict higher levels of externalizing problems but (b) that effects of disorganized attachment are moderated by family cumulative contextual risk, child gender and child age, with disorganized boys from risky social contexts manifesting increases in behavior problems over time. Conclusions:  These findings highlight the potentially conditional role of early attachment in children’s externalizing behavior problems and the need for further research evaluating causation and mediating mechanisms.

Selection of funding schemes by a borrowing decision model: a Hong Kong case study

In financial decision-making, a number of mathematical models have been developed for financial management in construction. However, optimizing both qualitative and quantitative factors and the semi-structured nature of construction finance optimization problems are key challenges in solving construction finance decisions. The selection of funding schemes by a modified construction loan acquisition model is solved by an adaptive genetic algorithm (AGA) approach. The basic objectives of the model are to optimize the loan and to minimize the interest payments for all projects. Multiple projects being undertaken by a medium-size construction firm in Hong Kong were used as a real case study to demonstrate the application of the model to the borrowing decision problems. A compromise monthly borrowing schedule was finally achieved. The results indicate that Small and Medium Enterprise (SME) Loan Guarantee Scheme (SGS) was first identified as the source of external financing. Selection of sources of funding can then be made to avoid the possibility of financial problems in the firm by classifying qualitative factors into external, interactive and internal types and taking additional qualitative factors including sovereignty, credit ability and networking into consideration. Thus a more accurate, objective and reliable borrowing decision can be provided for the decision-maker to analyse the financial options.

Planetary-wave-induced transport in the stratosphere

In the stratosphere, chemical tracers are drawn systematically from the equator to the pole. This observed Brewer–Dobson circulation is driven by wave drag, which in the stratosphere arises mainly from the breaking and dissipation of planetary-scale Rossby waves. While the overall sense of the circulation follows from fundamental physical principles, a quantitative theoretical understanding of the connection between wave drag and Lagrangian transport is limited to linear, small-amplitude waves. However, planetary waves in the stratosphere generally grow to a large amplitude and break in a strongly nonlinear fashion. This paper addresses the connection between stratospheric wave drag and Lagrangian transport in the presence of strong nonlinearity, using a mechanistic three-dimensional primitive equations model together with offline particle advection. Attention is deliberately focused on a weak forcing regime, such that sudden warmings do not occur and a quasi-steady state is reached, in order to examine this question in the cleanest possible context. Wave drag is directly linked to the transformed Eulerian mean (TEM) circulation, which is often used as a surrogate for mean Lagrangian motion. The results show that the correspondence between the TEM and mean Lagrangian velocities is quantitatively excellent in regions of linear, nonbreaking waves (i.e., outside the surf zone), where streamlines are not closed. Within the surf zone, where streamlines are closed and meridional particle displacements are large, the agreement between the vertical components of the two velocity fields is still remarkably good, especially wherever particle paths are coherent so that diabatic dispersion is minimized. However, in this region the meridional mean Lagrangian velocity bears little relation to the meridional TEM velocity, and reflects more the kinematics of mixing within and across the edges of the surf zone. The results from the mechanistic model are compared with those from the Canadian Middle Atmosphere Model to test the robustness of the conclusions.

Continuity of the dynamics in a localized large diffusion problem with nonlinear boundary conditions

This paper is concerned with singular perturbations in parabolic problems subjected to nonlinear Neumann boundary conditions. We consider the case for which the diffusion coefficient blows up in a subregion Omega(0) which is interior to the physical domain Omega subset of R(n). We prove, under natural assumptions, that the associated attractors behave continuously as the diffusion coefficient blows up locally uniformly in Omega(0) and converges uniformly to a continuous and positive function in Omega(1) = (Omega) over bar\Omega(0). (C) 2009 Elsevier Inc. All rights reserved.