In this thesis, we consider problems connected to navigation and tracking for autonomousrobots under the assumption of constraints on sensors and kinematics. We study formation controlas well as techniques for filtering and smoothing of noise contaminated input. The scientific contributions of the thesis comprise five papers.In Paper A, we propose three cascaded, stabilizing formation controls for multi-agent systems.We consider platforms with non-holonomic kinematic constraints and directional rangesensors. The resulting formation is a leader-follower system, where each follower agent tracksits leader agent at a specified angle and distance. No inter-agent communication is required toexecute the controls. A switching Kalman filter is introduced for active sensing, and robustnessis demonstrated in experiments and simulations with Khepera II robots.In Paper B, an optimization-based adaptive Kalman filteringmethod is proposed. The methodproduces an estimate of the process noise covariance matrix Q by solving an optimization problemover a short window of data. The algorithm recovers the observations h(x) from a system˙ x = f (x), y = h(x)+v without a priori knowledge of system dynamics. The algorithm is evaluatedin simulations and a tracking example is included, for a target with coupled and nonlinearkinematics. In Paper C, we consider the problem of estimating a closed curve in R2 based on noisecontaminated samples. A recursive control theoretic smoothing spline approach is proposed, thatyields an initial estimate of the curve and subsequently computes refinements of the estimateiteratively. Periodic splines are generated by minimizing a cost function subject to constraintsimposed by a linear control system. The optimal control problem is shown to be proper, andsufficient optimality conditions are derived for a special case of the problem using Hamilton-Jacobi-Bellman theory.Paper D continues the study of recursive control theoretic smoothing splines. A discretizationof the problem is derived, yielding an unconstrained quadratic programming problem. Aproof of convexity for the discretized problem is provided, and the recursive algorithm is evaluatedin simulations and experiments using a SICK laser scanner mounted on a PowerBot from ActivMedia Robotics. Finally, in Paper E we explore the issue of optimal smoothing for control theoretic smoothingsplines. The output of the control theoretic smoothing spline problem is essentially a tradeoff between faithfulness to measurement data and smoothness. This tradeoff is regulated by the socalled smoothing parameter. In Paper E, a method is developed for estimating the optimal valueof this smoothing parameter. The procedure is based on general cross validation and requires noa priori information about the underlying curve or level of noise in the measurements. / QC 20100722

Crew costs are one of the largest expenses for airlines and effective manpower planning is therefore important to maximize profit. The focus of research in the field of manpower planning for airlines has mainly been on the scheduling of crew, while other areas, surprisingly, have received very little attention. This thesis provides an overview of some of the other problems facing manpower planners, such as designing a career ladder, planning transitions and making course schedules. Mathematical models are presented for some of theses problems, and for the problem of allocating training and vacation in time the mathematical model has been tested on data from SAS Scandinavian Airlines. When allocating training and vacation there are many aspects to consider, such as avoiding crew shortage, access to resources needed for training, and vacation laws. Comparisons between solutions obtained with the model and SAS Scandinavian Airlines manual plan show encouraging results with savings around 10%.

The BMW Group uses load units for the transportation of assembly parts from the suppliers to the plants and for the internal material flow. This thesis analyses the advantageousness of introducing a load unit with a new size. There are three reasons why the current choice of containers is not sufficient. Firstly, there is a certain range of assembly parts that does not fit very well into the existing standard load units. Secondly, the average measurements of the parts have grown in the last years and thirdly, several of the existing containers leave unused space in the transportation vehicles. For this the relevant costs and other, more qualitative aspects like the placing at the assembly line are considered. A container size is identified that offers a significant savings potential. For this potential the handling and transportation costs are identified as the relevant leverages. These costs are found to depend mainly on the utilisation degree of the load units. To calculate the different utilisation degrees, a packing-algorithm in form of a four-block heuristic is applied and its results are extrapolated on the basis of existing BMW packing information. Thus, several assembly parts are identified that fit better into the suggested load unit than in the existing ones. These results are assessed using BMW’s expense ratios for handling and transportation. 80 parts are determined for which the migration to the new size would result in savings of more than 5,000 EUR for each per year in Dingolfing. Together, these parts offer a savings potential of about 0.9 million Euro.

I avhandlingen studeras hur kostnadseffektiva underhålls- (uh-)planer för belagd väg kan genereras, på basis av information om aktuellt vägytetillstånd och funktionella modeller för kostnads- och tillståndsförändringar, delvis utvecklade i samarbete med svenska Vägverket (VV). Tilltänkt användning är på strategisk och programnivå, innan mer detaljerad objektinformation finns att tillgå. Till skillnad från hittills använda modeller, så genereras individuella uh-planer för varje vägsegment (en homogen vägsträcka vad gäller aktuellt beläggningstillstånd och beläggningshistorik), i kontinuerliga tillstånds- och åtgärdsrum. Genom användning av Lagrangerelaxerande optimeringsteknik, så kan de speciella nytto/kostnads-kvot-villkor som VV ålägger varje uh-objekt naturligen hanteras med dualpriser för budgetvillkoren. Antalet vägsegment som konkurrerar om budgetmedlen är vanligtvis stort. Data från VV:s Vägdatabank för Värmland har använts, omfattande ca 9000 vägsegment. Genom den stora datamängden har datorprogrammen implementerats för parallellbearbetning. Under avhandlingsarbetet har projektet beviljats tillgång till Monolith PCklustret vid NSC. För att kunna reducera optimeringskörtiderna har modell- och metodutveckling varit nödvändig. Genom att aggregera vägsegmenten till vägklasser har goda startvärden på dualpriserna erhållits. Genom utvecklingen av en speciell restvärdesrutin har den explicit behandlade tidsperioden kunnat reduceras. Vid lösandet av det duala subproblemet har speciell uppmärksamhet ägnats åt de diskretiseringseffekter som uppstår i metoden dynamisk programmering. En typ av tillämpning avser ett delvägnät, exempelvis en väg. Valideringsstudier har genomförts på väg 63 i Värmland – med lovande men inte tillfredsställande resultat (se nedan). En speciell modell för samordnat uh beaktar stordriftsfördelarna vid samtidig åtgärd på en hel vägsträcka. Den andra huvudtypen av studier gäller ett helt nätverk. Flera metodtyper har tillämpats, både för att lösa de relaxerade optimeringsproblemen och för att generera uhplaner som uppfyller budgetvillkoren. För en anständig diskretisering är körtiderna för hela Värmland mindre än 80 CPU-timmar. Genom en a posteriori primal heuristik reduceras kraven på parallellbearbetning till ett litet PC-kluster. Avhandlingen studerar vidare effekterna av omfördelade budgetmedel samt en övergång till en transparent, stokastisk modell – vilka båda visar små avvikelser från basmodellen. Optimeringsresultaten för Värmland indikerar att budgetnivåer på ca 40% av Värmlands verkliga uh-budget är tillräckliga. Dock saknas viktiga kostnadsdrivande faktorer i denna första modellomgång, exempelvis vissa funktionella prestanda (säkerhet), all miljöpåverkande prestanda (buller etc.) och strukturell prestanda (ex.vis bärighet, som enbart modelleras via ett åldersmått). För ökad tilltro till PMS i allmänhet och optimering i synnerhet, bör avvikelserna analyseras ytterligare och leda till förbättringar vad gäller tillståndsmätning, tillståndseffekt- & kostnadsmodellering samt matematisk modellering & implementering. / The thesis deals with the generation of cost efficient maintenance plans for paved roads, based on database information about the current surface conditions and functional models for costs and state changes, partly developed in cooperation with Vägverket (VV, Swedish Road Administration). The intended use is in a stage of budgeting and planning, before concrete project information is available. Unlike the up to now used models, individual maintenance plans can be formulated for each segment (a homogeneous road section as to the current pavement state and paving history), in continuous state and works spaces. By using Lagrangean relaxation optimisation techniques, the special benefit/cost-ratio constraints that VV puts on each maintenance project can be naturally mastered by dual prices for the budget constraints. The number of segments competing for budget resources is usually large. Data from VV Vägdatabank (SRA Road Database) in county Värmland were used, comprising around 9000 road segments. Due to the large data amount the implemented programs rely on parallel computation. During the thesis work, access to the PC-cluster Monolith at NSC was granted. In order to reduce optimisation run times, model & method development was needed. By aggregating the road segments into road classes, good initial values of the dual prices were achieved. By adding new state dimensions, the use of the Markov property could be motivated. By developing a special residual value routine, the explicitly considered time period could be reduced. At solving the dual subproblem special attention was paid to the discretization effects in the dynamic programming approach. One type of study is on a sub-network, e.g. a road. Validation studies were performed on road 63 in Värmland – with promising but not satisfactory results (see below). A special model for co-ordinated maintenance considers the fine-tuned cost effects of simultaneous maintenance of contiguous road segments. The other main type of study is for a whole network. Several method types have been applied, both for solving the relaxed optimisation problems and for generating maintenance plans that fit to the budgets. For a decent discretization, the run time for the whole Värmland network is less than 80 CPU-hrs.A posterior primal heuristics reduces the demands for parallel processing to a small PC-cluster.The thesis further studies the effects of redistributing budget means, as well as turning to a transparent stochastic model – both showing modest deviations from the basic model. Optimisation results for Värmland indicate budget levels around 40% of the actual Värmland budget as sufficient. However, important cost triggers are missing in this first model round, e.g., certain functional performance (safety), all environmental performance (noise etc.) and structural performance (e.g. bearing capacity, only modelled by an age measure). For increased credibility of PMS in general and optimisation in particular, the discrepancies should be further analysed and lead to improvements as to condition monitoring, state effect & cost modelling and mathematical modelling & implementation.

<p>This thesis studies the allocation of stock in a two-level inventory system with stochastic demand. The system consists of one central warehouse which supplies N non-identical retailers with one single product. Customer demand occurs solely at the retailers and follows independent Poisson processes. The purpose is to investigate the value of using a more advanced allocation policy than First Come-First Serve at the central warehouse. The focus is on evaluating how well the simple First Come-First Serve assumption works in a system where the warehouse has access to real-time point-of-sale data, and where shipments are time based and consolidated for all retailers. The considered allocation policy is a myopic policy where the solution to a minimization problem, formulated as a constrained newsvendor problem, determines how the warehouse allocates its stock to the retailers. The minimization problem is solved using (a heuristic method based on) Lagrangian relaxation, and simulation is used to evaluate the average inventory holding costs and backorder costs per time unit when using the considered policy. The simulation study shows that cost savings around 1-4 percent can be expected for most system configurations. However, there were cases where savings were as high as 5 percent, as well as cases where the policy performed worse than First Come-First Serve. The study also shows that the highest cost savings are found in systems with relatively low demand, few retailers, short transportation times and a short time interval between shipments.</p>

<p>Using mathematical models with the purpose to understand and store knowlegde about a system is not a new field in science with early contributions dated back to, e.g., Kepler’s laws of planetary motion.</p><p>The aim is to obtain such a comprehensive predictive and quantitative knowledge about a phenomenon so that mathematical expressions or models can be used to forecast every relevant detail about that phenomenon. Such models can be used for reducing pollutions from car engines; prevent aviation incidents; or developing new therapeutic drugs. Models used to forecast, or predict, the behavior of a system are refered to predictive models. For such, the estimation problem aims to find one model and is well known and can be handeled by using standard methods for global nonlinear optimization.</p><p>Descriptive models are used to obtain and store quantitative knowledge of system. Estimation of descriptive models has not been much described by the literature so far; instead the methods used for predictive models have beed applied. Rather than finding one particular model, the parameter estimation for descriptive models aims to find every model that contains descriptive information about the system. Thus, the parameter estimation problem for descriptive models can not be stated as a standard optimization problem.</p><p>The main objective for this thesis is to propose methods for estimation of descriptive models. This is made by using methods for nonlinear optimization including both new and existing theory.</p>

<p> </p><p>Crew costs are one of the largest expenses for airlines and effective manpower planning is therefore important to maximize profit. The focus of research in the field of manpower planning for airlines has mainly been on the scheduling of crew, while other areas, surprisingly, have received very little attention. This thesis provides an overview of some of the other problems facing manpower planners, such as designing a career ladder, planning transitions and making course schedules.</p><p>Mathematical models are presented for some of theses problems, and for the problem of allocating training and vacation in time the mathematical model has been tested on data from SAS Scandinavian Airlines. When allocating training and vacation there are many aspects to consider, such as avoiding crew shortage, access to resources needed for training, and vacation laws. Comparisons between solutions obtained with the model and SAS Scandinavian Airlines manual plan show encouraging results with savings around 10%.</p><p> </p>

<p>Integer programming can be used to provide solutionsto complex decision and planning problems occurring in a wide varietyof situations. Applying integer programming to a real life problembasically involves a first phase where a mathematical model isconstructed, and a second phase where the problem described by themodel is solved. While the nature of the challenges involved in therespective two phases differ, the strong relationship between theproperties of models, and which methods that are appropriate for theirsolution, links the two phases. This thesis constitutes of threepapers, of which the third one considers the modeling phase, while thefirst and second one consider the solution phase.</p><p> </p><p>Many applications of column generation yield master problems of setpartitioning type, and the first and second papers presentmethodologies for solving such problems. The characteristics of themethodologies presented are that all successively found solutions arefeasible and integral, where the retention of integrality is a majordistinction from other column generation methods presented in theliterature.</p><p> </p><p>The third paper concerns nurse scheduling and describes the results ofa pilot implementation of a scheduling tool at a Swedish nursing ward.This paper focuses on the practical aspects of modeling and thechallenges of providing a solution to a complex real life problem.</p>

Titel: Initiativ för en hållbar operativ produktionsplanering inom träindustrin - En fallstudie vid ESS-ENN  Kurs: 4FE19E Examensarbete i Supply Chain Management för Civilekonomprogrammet, 30 HP. Författare: Ali Yousefi &amp; Martin Samuelsson Examinator: Helena Forslund Handledare: Peter Berling Syfte: Studien har ett primärt syfte. Presentera en lämplig planeringsmetod för den operativa produktionsplaneringen inom tillverkningsföretag i träindustrin med aspiration att stärka Ess-Enn.   Metod: Uppsatsen är en fallstudien grundad på en kvalitativ forskningsmetod som brukar sig av ett deduktivt angreppssätt. Semistrukturerade intervjuer i kombination av en litteraturöversikt för datainsamling. Analysmetoden under fallstudien använder sig av logiska modeller som analysverktyg. Slutsats:  Studien har besvarat tre frågeställningar där syftet har varit att identifiera en optimal planeringsmetod för fallföretagets nuvarande operativa planeringsmiljö. Med hjälp av kartläggningen av fallföretagets operativa planeringsmiljö från den första frågeställningen så kunde det konstateras att det inte identifierades någon lämplig planeringsmetod utifrån den tillgängliga teorin vid den andra frågeställningen. Detta ledde till den tredje frågeställningen som resulterade till studiens uppbyggda modell. Slutsatsen blev att fallföretaget bör implementera en anpassad planeringsmetod genom en kombination av MRP och den uppbyggda modellen för att uppnå en hållbar operativ produktionsplanering.

The European Union’s ambitious climate targets necessitate substantial reductions in greenhouse gas emissions, particularly within the heating and cooling sector, which accounts for a significant portion of energy consumption. District Heating and Cooling (DHC) systems emerge as a key solution for decarbonizing this sector by enabling high efficiency heat production and the integration of renewable and carbon-neutral energy sources. Despite the potential inherent in DHC systems, their utilization is limited, partly due to challenges associated with network topology selection. This master’s thesis addresses the optimization of District Heating Network layout expansion while tackling these challenges. Situated within the framework of an European funded project coordinated by EIFER, the research aims to develop an algorithm for modeling and planning the expansion of DHN networks, considering geographical location of pipes and heat production and consumption nodes. Building upon the Automatic Network Drawing Algorithm (ANDA) tool provided by EIFER, the project seeks to enhance it to generate expansion scenarios incorporating loops, a feature critical for network robustness absent in the current output. The tool pandapipes is used for fluid system modeling, effectively modelinghydraulics and heat through network elements such as heat producer, substationsand pipes. The algorithm’s core feature is to strategically determine optimallocations along initial tree-like network expansions to incorporate loops. Variousheuristic approaches are tested to identify the most efficient expansion strategies,subsequently adding new lines to minimize total costs, encompassing both capitaland operational expenses. Real-world data from a District Heating Network inMilan validate the algorithm’s capabilities. / Europeiska unionens ambitiösa klimatmål kräver avsevärda minskningar av utsläppen av växthusgaser, särskilt inom värme- och kylsektorn, som står för en betydande del av energiförbrukningen. Fjärrvärme- och fjärrkylasystem (DHC) framstår som en nyckellösning för att minska koldioxidutsläppen i denna sektor genom att möjliggöra högeffektiv värmeproduktion och integrering av förnybara och koldioxidneutrala energikällor. Trots potentialen som finns i DHC-system är deras användning begränsad, delvis på grund av utmaningar i samband med val av nätverkstopologi. Denna masteruppsats behandlar optimering av utbyggnaden av fjärrvärmenätets layout samtidigt som man tacklar dessa utmaningar. Beläget inom ramen för ett europeiskt finansierat projekt koordinerat av EIFER, syftar forskningen till att utveckla en algoritm för modellering och planering av utbyggnaden av DHN-nät, med hänsyn till den geografiska placeringen av rör och värmeproduktions- och förbrukningsnoder. Med utgångspunkt i verktyget Automatic Network Drawing Algorithm (ANDA) från EIFER, försöker projektet förbättra det för att generera expansionsscenarier med slingor, en funktion som är avgörande för nätverkets robusthet som saknas i den aktuella utgången. Verktyget pandapipes används för modellering av vätskesystem, effektiv modellering av hydraulik och värme genom nätverkselement som värmeproducent, transformatorstationer och rör. Algoritmens kärnfunktion är att strategiskt bestämma optimala platser längs initiala trädliknande nätverksutbyggnader för att införliva slingor. Olika heuristiska tillvägagångssätt testas för att identifiera de mest effektiva expansionsstrategierna, och sedan läggas till nya linjer för att minimera de totala kostnaderna, som omfattar både kapital- och driftskostnader. Verkliga data från ett fjärrvärmenätverk i Milano validerar algoritmens kapacitet.