As the transport industry shifts towards Battery Electric Vehicles (BEVs) the need for accurate route planning rises. BEVs have reduced range compared to traditional fuel based vehicles, and the range can vary greatly depending on ambient conditions and vehicle load. Existing research focuses more on the theoretical algorithms, and often have none or very simple vehicle models, leaning towards consumer cars instead of heavy duty trucks. Vehicle Route Planning (VRP) is a wide research area, and this thesis focuses on the Shortest Path subproblem. Contraction Hierarchies (CHs) is a commonly used family of algorithms for finding shortest paths in road networks, and is prevalent in the research frontier. CHs however comes with certain drawbacks, such as having to perform a costly preprocessing phase whenever metrics change, and not being able to share map data between multiple vehicles in a fleet. This thesis extends CHs to support a mixed fleet, with fast metric updates and support for more detailed cost optimization goals. This is done by implementing Customizable Contraction Hierarchies (CCHs), but with custom data structures and customization phase. This implementation allows map data to be shared between vehicles in a fleet, and keeps each vehicle's edge weights separate. The edge weights can be updated quickly, as the customization phase scales linearly with the size of the map. The implementation also supports edge weights that do not adhere to triangle inequality, which the previous research did not. Experiments are executed on a map of Stockholm and a synthetic map, to test the algorithm's performance, verify correctness, and stress the importance of accurate metrics for optimization goals. The CCH performed as expected, if not better, and its correctness is upheld. The implementation is fit to be integrated into a route planner, but further research should be conducted to see how it meshes with other parts of VRP, such as time windows, turn costs, and charging stations. / När transportindustrin övergår till batterielektriska fordon ökar behovet av rigorös ruttplanering. Batterielektriska fordon har minskad räckvidd jämfört med traditionella bränslebaserade fordon, och räckvidden kan variera stort beroende på omgivningsförhållanden och fordonets belastning. Existerande forskning fokuserar mer på de teoretiska algoritmerna och har ofta inga eller mycket enkla fordonsmodeller, som liknar mer konsumentbilar istället för tunga lastbilar. Ruttplanering är ett brett forskningsområde, och denna avhandling fokuserar på underproblemet att hitta kortaste vägen. Kontraktionshierarkier är en välanvänd familj av algoritmer för att hitta kortaste vägen i ett vägnät, och är prevalent i forskningsfronten. Kontraktionshierarkier har dock vissa nackdelar, som att de behöver utföra en kostsam förbehandlingsfas när parametrar ändras, och att kartdatan inte kan delas mellan flera fordon i en flotta. Den här avhandlingen utökar Kontraktionshierarkier för att stödja en blandad fordonsflotta, med snabba uppdateringar av parametrar och stöd för mer detaljerade optimeringsmål. Detta görs genom att implementera Anpassningsbara Kontraktionsierarkier, men med anpassade datastrukturer och anpassningsfas. Denna implementering tillåter att kartdata delas mellan fordonen i en flotta, och håller varje fordons kantvikter separat. Kantvikterna kan uppdateras snabbt, eftersom anpassningsfasen skalas linjärt med storleken på kartan. Implementationen stöder också kantvikter som inte följer triangelojämlikheten, vilket den tidigare forskningen inte gjorde. Experiment utförs på en karta över Stockholm och en syntetisk karta, för att testa algoritmens prestanda, verifiera korrekthet, och betona vikten av detaljerade parametrar i optimeringsmål. Anpassningsbara Kontraktionshierarkier presterade som förväntat, om inte bättre, och dess korrekthet uppehölls. Implementeringen är lämplig för att integreras i en ruttplanerare, men ytterligare forskning bör genomföras för att se hur den passar ihop med andra delar av ruttplaneringsproblemet, så som tidsfönster, svängkostnader och laddstationer.

Introduction: The case study was conducted at the transport company Akka Frakt which faces the challenge of electrifying its vehicle fleet. The purpose of the study is to investigate how Akka Frakt can implement the conversion with as little impact as possible on the environment and operational activities. Problem description: Akka Frakt has recently invested in many new fossil-fueled trucks that have a long lifetime left. In addition to that, electric trucks are a new industry, which means that the technology has not been developed to adapt to all types of special constructions for trucks. Theory: The study's theoretical starting point is sustainable development where all three dimensions have been important to review. Method: The empirics was collected through qualitative methods in the form of a literature search, interviews, and the provision of internal documents. When analyzing the data, the tools Ishikawa diagram, breakdown, and risk analysis have been used. Results: The results show that the optimal changeover for Akka Frakt is ongoing over a ten-year period and electrifying all trucks where possible with today's technology. The existing trucks that have not yet been replaced are refueled with HVO100 and where electrification is not possible, the trucks are converted to biogas. Conclusions: There are problems with electrifying Akka Frakt's vehicle fleet. A major problem is the current lack of technology that does not make it possible to electrify the entire vehicle fleet. With the electrification, there are also problems that affect the operational activities, for example a running-in period. / Inledning: Fallstudien har genomförts på transportföretaget Akka Frakt som står inför utmaningen att elektrifiera sin fordonsflotta. Syftet med studien är att undersöka hur Akka Frakt kan genomföra omställningen med en så liten påverkan som möjligt på miljön och den operativa verksamheten. Problembeskrivning: Akka Frakt har nyligen investerat i många nya fossildrivna lastbilar som har lång livstid kvar. Utöver det är ellastbilar en ny bransch, vilket gör att tekniken inte utvecklats för att anpassas till alla typer av specialbyggnationer till lastbilar. Teori: Studiens teoretiska utgångspunkt är hållbar utveckling där alla tre dimensioner varit viktiga att granska. Metod: Empirin samlades in genom kvalitativa metoder i form av litteratursökning, intervjuer samt tillhandahållandet av interna dokument. Vid analysering av data har verktygen Ishikawa- diagram, uppdelning och riskanalys använts. Resultat: Resultatet visar att den optimala omställningen för Akka Frakt pågår under en tioårsperiod och elektrifierar alla lastbilar där det är möjligt med dagens teknik. De befintliga lastbilar som ej blivit utbytta ännu tankas med HVO100 och där det ej är möjligt att elektrifiera ställs lastbilarna om till biogas. Slutsatser: Det finns problem med att elektrifiera Akka Frakts fordonsflotta. Ett stort problem är den bristande tekniken som finns i nuläget som inte gör det möjligt att elektrifiera hela fordonsflottan. Vid elektrifieringen tillkommer även problem som påverkar den operativa verksamheten, exempelvis en inkörningsperiod.

[pt] A matriz brasileira de transporte retrata a dominância rodoviária sobre os demais modais, na movimentação de cargas no país. O aumento da eficiência operacional e redução de custos é fator que pode elevar a participação e competitividade dos trens nesse contexto. A aplicação de técnicas de otimização no processo de dimensionamento e planejamento operacional da frota de locomotivas possui grande potencial de economia de recursos, principalmente devido aos seus elevados custos de aquisição e manutenção. O presente trabalho apresenta uma metodologia para obtenção de uma solução exata para um horizonte mensal de planejamento, aproveitando se do caráter cíclico da grade de formação dos trens de carga geral, para definir o tamanho ótimo da frota necessário ao seu adequado funcionamento. A metodologia, implementada em linguagem Python e aplicada em um cenário de uma grade conhecida, teve sua frota resultante comparada com o dimensionamento manual realizado em uma concessionária brasileira e foi capaz de indicar a redução de 2 locomotivas no planejamento de frota. Associada a esta redução, a economia de capital estimada seria entre 400 mil reais e 20 milhões de reais, para o cenário conservador de economia dos gastos de manutenção e para o cenário mais otimista evitando a aquisição de novas locomotivas. Além da redução de frota e aumento na competitividade tarifária dos trens de carga geral, a metodologia cria, por meio de critérios científicos, diretrizes objetivas para o processo de dimensionamento e planejamento da frota de locomotivas, em substituição ao processo empírico atualmente aplicado na referida concessionária. / [en] The Brazilian transport matrix presents the road dominance over other modes in the movement of cargo in the country. The increase in operational efficiency and cost reduction is a factor that can increase the participation and competitiveness of trains in this context. The application of optimi zation techniques in the process of dimensioning and operational planning of the locomotive fleet has great potential for saving resources, mainly due to its high acquisition and maintenance costs. This work presents a methodology to obtain an exact soluti on for a monthly planning horizon, taking advantage of the cyclical character of the general freight trains timetables and defining the optimum fleet size necessary for its proper functioning. The methodology, implemented in Python language and applied in a scenario of a defined timetable had its resulting fleet compared with the manual sizing process carried out in a Brazilian dealership and was able to indicate the reduction of 2 locomotives in the fleet planning. Associated with this reduction, the est imated capital savings would be between 400 thousand reais and 20 million reais, for the conservative scenario of savings in maintenance costs and for the more optimistic scenario avoiding the acquisition of new locomotives. In addition to reducing the fleet and increasing the tariff competitiveness of general freight trains, the methodology creates, through scientific criteria, objective guidelines for the process of dimensioning and planning the locomotive fleet, replacing the empirical process currently applied in the aforementioned concessionaire.

There is an asymmetry in demand for transportation means of goods and commodities globally. One industry in which this trend is especially prominent is the pharmaceutical industry, where the European Union is by far the largest net exporter of pharmaceutical products globally, followed by Switzerland. The largest global net importer of pharmaceutical products is America, and given that many pharmaceutical products need to be transported in a cold chain, a niche within the transportation industry has grown – one that focuses primarily on transportation of high-value temperature-sensitive goods. Transportation companies working with circulating assets around the world need to determine how much capacity can be allocated to the sale of one-way trips (which may displace assets within the fleet to places in which they cannot be sold again due to the lack of business) whilst still allowing the sale of round-trip leases to continue. We conducted a case study within Company A that is a cold chain provider for air freight to provide context on how a heuristic model for capacity control should be developed, and incorporated this with learnings from theory within the fields of revenue management and fleet management together with literature in similar business settings. This resulted in a four-step model with unique planning horizons for each level, ranging from strategic perspectives for fleet balancing down to operational aspects of daily allocation and release of containers. We conclude which factors are essential for the context of the case study and showcase how a model can be constructed taking these findings into account. The thesis deals with the issue of capacity control for one-way leases. Other models have used pricing strategies to accomplish similar tasks and this is not included in the proposed model which is a limitation of this study, this is discussed and elaborated on. Furthermore, possible implications for the customer behaviour with the suggested model is discussed. / Det finns en global asymmetri i efterfrågan för transport av gods och råvaror. En industri där detta är speciellt framstående är läkemedelsindustrin – där Europa är den största exportören globalt följt av Schweiz. Den största importören av dessa produkter är Nordamerika, och givet att många läkemedelsprodukter behöver transporteras i en kylkedja har en nisch inom transportsektorn vuxit fram – en som fokuserar primärt på transport av temperaturkänsligt gods av högt värde. Transportbolag som jobbar med cirkulerande tillgångar världen över behöver bestämma hur mycket kapacitet som kan allokeras till envägsuthyrningar (vilket kan fördela flottan så att ingen efterfrågan finns för att sälja dessa igen) medan den fortsatta försäljningen av tur-och-retur-uthyrningar fortfarande tillåts. Vi utför en fallstudie inom Företag A, som tillhandahåller tjänster för kylkedjor gjorda för flygfrakt, detta för att skapa förståelse för hur en heuristisk modell för kapacitetskontroll kan utvecklas. Detta vävs samman med lärdomar från teori inom fälten intäktsoptimering och förvaltning och styrning av utrustningsflottor tillsammans med litteratur inom liknande affärskontexter. Detta resulterade i en fyrstegsmodell med unika planeringshorisonter för varje nivå. Modellen sträcker sig från strategiska beslut för balansering av flottan ner till operationella aspekter för daglig allokering och överlåtande av containrar. Vi sammanfattar vilka faktorer som är relevanta inom ramarna för fallstudien och visar hur en modell kan vara uppbyggd där dessa faktorer tas i beaktning. Avhandlingen hanterar problemet kapacitetskontroll för envägsuthyrningar. Andra modeller har använt prissättningsstrategier för att åstadkomma liknande mål och detta har inte inkluderats i den föreslagna modellen vilket är en begränsning i avhandlingen, detta diskuteras och vidareutvecklas. Möjliga implikationer på kundbeteende med den föreslagna modellen diskuteras också.

Целью исследования является совершенствование инструментария повышения эффективности деятельности авиакомпаний в сфере региональных воздушных перевозок. Предложен методический подход к повышению эффективности региональных воздушных перевозок, элементами которого являются выработка стратегических решений по совершенствованию структуры парка воздушных судов, тактических решений по их распределению по маршрутам региональных перевозок, обоснование направлений совершенствования системы полетного сервиса и методическое обеспечение этих элементов. Предложенные автором рекомендации позволяют повысить эффективность деятельности авиакомпаний в сфере региональных воздушных перевозок. / The aim of the work is to improve the instruments of operational efficiency in the regional airlines. Methods to improving operational efficiency in the regional airlines consist of the development of strategic solutions to improve air fleet efficiency, tactical decisions of aircraft routing on regional air traffic, the rationale for the flight services improvement and methodological support of these elements. The author’s methods make it possible to improving operational efficiency in the regional airlines.

No description available.

No description available.

This dissertation addresses five fundamental resource allocation problems on networks, all of which have applications to support Homeland Security or industry challenges. In the first application, we model and solve the strategic problem of minimizing the expected loss inflicted by a hostile terrorist organization. An appropriate allocation of certain capability-related, intent-related, vulnerability-related, and consequence-related resources is used to reduce the probabilities of success in the respective attack-related actions, and to ameliorate losses in case of a successful attack. Given the disparate nature of prioritizing capital and material investments by federal, state, local, and private agencies to combat terrorism, our model and accompanying solution procedure represent an innovative, comprehensive, and quantitative approach to coordinate resource allocations from various agencies across the breadth of domains that deal with preventing attacks and mitigating their consequences. Adopting a nested event tree optimization framework, we present a novel formulation for the problem as a specially structured nonconvex factorable program, and develop two branch-and-bound schemes based respectively on utilizing a convex nonlinear relaxation and a linear outer-approximation, both of which are proven to converge to a global optimal solution. We also investigate a fundamental special-case variant for each of these schemes, and design an alternative direct mixed-integer programming model representation for this scenario. Several range reduction, partitioning, and branching strategies are proposed, and extensive computational results are presented to study the efficacy of different compositions of these algorithmic ingredients, including comparisons with the commercial software BARON. The developed set of algorithmic implementation strategies and enhancements are shown to outperform BARON over a set of simulated test instances, where the best proposed methodology produces an average optimality gap of 0.35% (compared to 4.29% for BARON) and reduces the required computational effort by a factor of 33. A sensitivity analysis is also conducted to explore the effect of certain key model parameters, whereupon we demonstrate that the prescribed algorithm can attain significantly tighter optimality gaps with only a near-linear corresponding increase in computational effort. In addition to enabling effective comprehensive resource allocations, this research permits coordinating agencies to conduct quantitative what-if studies on the impact of alternative resourcing priorities. The second application is motivated by the author's experience with the U.S. Army during a tour in Iraq, during which combined operations involving U.S. Army, Iraqi Army, and Iraqi Police forces sought to interdict the transport of selected materials used for the manufacture of specialized types of Improvised Explosive Devices, as well as to interdict the distribution of assembled devices to operatives in the field. In this application, we model and solve the problem of minimizing the maximum flow through a network from a given source node to a terminus node, integrating different forms of superadditive synergy with respect to the effect of resources applied to the arcs in the network. Herein, the superadditive synergy reflects the additional effectiveness of forces conducting combined operations, vis-à-vis unilateral efforts. We examine linear, concave, and general nonconcave superadditive synergistic relationships between resources, and accordingly develop and test effective solution procedures for the underlying nonlinear programs. For the linear case, we formulate an alternative model representation via Fourier-Motzkin elimination that reduces average computational effort by over 40% on a set of randomly generated test instances. This test is followed by extensive analyses of instance parameters to determine their effect on the levels of synergy attained using different specified metrics. For the case of concave synergy relationships, which yields a convex program, we design an inner-linearization procedure that attains solutions on average within 3% of optimality with a reduction in computational effort by a factor of 18 in comparison with the commercial codes SBB and BARON for small- and medium-sized problems; and outperforms these softwares on large-sized problems, where both solvers failed to attain an optimal solution (and often failed to detect a feasible solution) within 1800 CPU seconds. Examining a general nonlinear synergy relationship, we develop solution methods based on outer-linearizations, inner-linearizations, and mixed-integer approximations, and compare these against the commercial software BARON. Considering increased granularities for the outer-linearization and mixed-integer approximations, as well as different implementation variants for both these approaches, we conduct extensive computational experiments to reveal that, whereas both these techniques perform comparably with respect to BARON on small-sized problems, they significantly improve upon the performance for medium- and large-sized problems. Our superlative procedure reduces the computational effort by a factor of 461 for the subset of test problems for which the commercial global optimization software BARON could identify a feasible solution, while also achieving solutions of objective value 0.20% better than BARON. The third application is likewise motivated by the author's military experience in Iraq, both from several instances involving coalition forces attempting to interdict the transport of a kidnapping victim by a sectarian militia as well as, from the opposite perspective, instances involving coalition forces transporting detainees between interment facilities. For this application, we examine the network interdiction problem of minimizing the maximum probability of evasion by an entity traversing a network from a given source to a designated terminus, while incorporating novel forms of superadditive synergy between resources applied to arcs in the network. Our formulations examine either linear or concave (nonlinear) synergy relationships. Conformant with military strategies that frequently involve a combination of overt and covert operations to achieve an operational objective, we also propose an alternative model for sequential overt and covert deployment of subsets of interdiction resources, and conduct theoretical as well as empirical comparative analyses between models for purely overt (with or without synergy) and composite overt-covert strategies to provide insights into absolute and relative threshold criteria for recommended resource utilization. In contrast to existing static models, in a fourth application, we present a novel dynamic network interdiction model that improves realism by accounting for interactions between an interdictor deploying resources on arcs in a digraph and an evader traversing the network from a designated source to a known terminus, wherein the agents may modify strategies in selected subsequent periods according to respective decision and implementation cycles. We further enhance the realism of our model by considering a multi-component objective function, wherein the interdictor seeks to minimize the maximum value of a regret function that consists of the evader's net flow from the source to the terminus; the interdictor's procurement, deployment, and redeployment costs; and penalties incurred by the evader for misperceptions as to the interdicted state of the network. For the resulting minimax model, we use duality to develop a reformulation that facilitates a direct solution procedure using the commercial software BARON, and examine certain related stability and convergence issues. We demonstrate cases for convergence to a stable equilibrium of strategies for problem structures having a unique solution to minimize the maximum evader flow, as well as convergence to a region of bounded oscillation for structures yielding alternative interdictor strategies that minimize the maximum evader flow. We also provide insights into the computational performance of BARON for these two problem structures, yielding useful guidelines for other research involving similar non-convex optimization problems. For the fifth application, we examine the problem of apportioning railcars to car manufacturers and railroads participating in a pooling agreement for shipping automobiles, given a dynamically determined total fleet size. This study is motivated by the existence of such a consortium of automobile manufacturers and railroads, for which the collaborative fleet sizing and efforts to equitably allocate railcars amongst the participants are currently orchestrated by the \textit{TTX Company} in Chicago, Illinois. In our study, we first demonstrate potential inequities in the industry standard resulting either from failing to address disconnected transportation network components separately, or from utilizing the current manufacturer allocation technique that is based on average nodal empty transit time estimates. We next propose and illustrate four alternative schemes to apportion railcars to manufacturers, respectively based on total transit time that accounts for queuing; two marginal cost-induced methods; and a Shapley value approach. We also provide a game-theoretic insight into the existing procedure for apportioning railcars to railroads, and develop an alternative railroad allocation scheme based on capital plus operating costs. Extensive computational results are presented for the ten combinations of current and proposed allocation techniques for automobile manufacturers and railroads, using realistic instances derived from representative data of the current business environment. We conclude with recommendations for adopting an appropriate apportionment methodology for implementation by the industry. / Ph. D.

The air transportation market has been growing steadily for the past three decades since the airline deregulation in 1978. With competition also becoming more intense, airline companies have been trying to enhance their market shares and profit margins by composing favorable flight schedules and by efficiently allocating their resources of aircraft and crews so as to reduce operational costs. In practice, this is achieved based on demand forecasts and resource availabilities through a structured airline scheduling process that is comprised of four decision stages: schedule planning, fleet assignment, aircraft routing, and crew scheduling. The outputs of this process are flight schedules along with associated assignments of aircraft and crews that maximize the total expected profit. Traditionally, airlines deal with these four operational scheduling stages in a sequential manner. However, there exist obvious interdependencies among these stages so that restrictive solutions from preceding stages are likely to limit the scope of decisions for succeeding stages, thus leading to suboptimal results and even infeasibilities. To overcome this drawback, we first study the aircraft routing problem, and develop some novel modeling foundations based on which we construct and analyze an integrated model that incorporates fleet assignment, aircraft routing, and crew pairing within a single framework. Given a set of flights to be covered by a specific fleet type, the aircraft routing problem (ARP) determines a flight sequence for each individual aircraft in this fleet, while incorporating specific considerations of minimum turn-time and maintenance checks, as well as restrictions on the total accumulated flying time, the total number of takeoffs, and the total number of days between two consecutive maintenance operations. This stage is significant to airline companies as it directly assigns routes and maintenance breaks for each aircraft in service. Most approaches for solving this problem adopt set partitioning formulations that include exponentially many variables, thus requiring the design of specialized column generation or branch-and-price algorithms. In this dissertation, however, we present a novel compact polynomially sized representation for the ARP, which is then linearized and lifted using the Reformulation-Linearization Technique (RLT). The resulting formulation remains polynomial in size, and we show that it can be solved very efficiently by commercial software without complicated algorithmic implementations. Our numerical experiments using real data obtained from United Airlines demonstrate significant savings in computational effort; for example, for a daily network involving 344 flights, our approach required only about 10 CPU seconds for deriving an optimal solution. We next extend Model ARP to incorporate its preceding and succeeding decision stages, i.e., fleet assignment and crew pairing, within an integrated framework. We formulate a suitable representation for the integrated fleeting, routing, and crew pairing problem (FRC), which accommodates a set of fleet types in a compact manner similar to that used for constructing the aforementioned aircraft routing model, and we generate eligible crew pairings on-the-fly within a set partitioning framework. Furthermore, to better represent industrial practice, we incorporate itinerary-based passenger demands for different fare-classes. The large size of the resulting model obviates a direct solution using off-the-shelf software; hence, we design a solution approach based on Benders decomposition and column generation using several acceleration techniques along with a branch-and-price heuristic for effectively deriving a solution to this model. In order to demonstrate the efficacy of the proposed model and solution approach and to provide insights for the airline industry, we generated several test instances using historical data obtained from United Airlines. Computational results reveal that the massively-sized integrated model can be effectively solved in reasonable times ranging from several minutes to about ten hours, depending on the size and structure of the instance. Moreover, our benchmark results demonstrate an average of 2.73% improvement in total profit (which translates to about 43 million dollars per year) over a partially integrated approach that combines the fleeting and routing decisions, but solves the crew pairing problem sequentially. This improvement is observed to accrue due to the fact that the fully integrated model effectively explores alternative fleet assignment decisions that better utilize available resources and yield significantly lower crew costs. / Ph. D.

The purpose of this thesis is to illustrate the importance of the military principle of unity of command by examining the military history of a Union army unit during the Civil War. The Mississippi Marine Brigade and its predecessor, the Ellet Ram Fleet, being a creation of the War Department, and yet conducting tactical operations within the scope of the Navy Department, vividly illustrates the problems inherent in joint army-navy operations. The brigade's primary mission was to counter guerrilla warfare in the Mississippi River valley. The text describes the organization, administration, and major operations of the brigade as a mobile, independent, private military force.