Search

The logistics sector has undergone profound changes over the past decade, mainly due to growing demand and shipping time requirements. For example, the global volume of parcel shipment has doubled in the last five years and is expected to double again in the next five [1], even without considering the boost of e-commerce due to Covid-19. This pushes logistics companies to operate more efficiently in order to handle and ship large volumes of goods faster. Furthermore, growing environmental concerns put increasing pressure on logistics and freight operators to integrate sustainability goals into their strategy and reduce their typically high carbon footprint.

Planning a railway system is done in multiple stages that are typically intractable to optimize in an integrated manner. This work develops a novel iterative approach to tackle two of these stages jointly: line planning and timetabling. Compared to existing approaches that iteratively ban a whole conflicting line plan when the timetable is found infeasible, our method can accurately identify the smallest set of incompatible services. Besides, by efficiently exploiting the available railway infrastructure, our method accounts for all the possible routing options of trains, a feature commonly neglected to reduce complexity but that helps gaining timetable feasibility. Using real data from a railway company in Switzerland, we find that our approach is (i) practical for solving real-life instances, (ii) an order of magnitude faster than existing benchmarks, and (iii) able to solve more instances. Our insights shed light on the necessity of considering infrastructure and banning conflicts rather than line plans in the joint line planning and timetabling problem.

The multi-drop container loading problem (MDCLP) requires loading a truck so that boxes can be unloaded at each drop-off point without rearranging other boxes to deliver later. However, modeling such unloading constraints as hard constraints, as done in the literature, considerably limits the flexibility to optimize the packing and utilize the vehicle capacity. We thus propose a more general approach that considers soft unloading constraints. Specifically, we penalize unnecessary relocations of boxes using penalty functions that depend on the volume and weight of the boxes to move as well as the type of move. Our goal is to maximize the total value of the loaded cargo including penalty functions due to violations of the unloading constraints. We provide a mixed-integer linear programming formulation for the MDCLP with soft unloading constraints, which can solve to optimality small scale instances but is intractable for larger ones. We thus propose a heuristic framework to solve large instances, which is based on a randomized extreme-point constructive phase and a subsequent improvement phase. The latter phase iteratively destroys regions in the packing space where high penalties originate, and reconstructs them. Extensive numerical experiments involving different penalties show that our approach significantly outperforms: (i) the hard unloading constraints approach, and (ii) a sequential heuristic that neglects unloading constraints first and evaluates the penalties afterwards. Our findings underscore the relevance of accounting for soft unloading constraints in the MDCLP.

Planning railway and metro systems includes the critical step of finding a schedule for the trains. Although buffer times and running supplements are added to the schedule to make operations re- silient to minor disturbances, they do not protect against all possible events that may lead to con- flicts during everyday operations. Thus, real-time train rescheduling models are needed to restore fea- sibility using actions such as retiming, reordering, rerouting, overtaking or cancelling of trains. Un- fortunately, despite many rescheduling models that have been developed in the literature, only a few can learn actions from past, simulated, or ongoing events and cope with disturbances and disruptions’ stochastic nature. However, the last decade’s ex- pansion of learning algorithms is gaining momen- tum in the train rescheduling literature by bring- ing novel and promising ideas. This paper aims to review the state-of-the-art learning algorithms ap- plied to the real-time railway and metro reschedul- ing, identifying challenges and opportunities while making a parallel with other areas where learning algorithms led to breakthroughs.

Predicting the delays of trains in real-time is an active area of research with a considerable amount of literature published in recent years. Moreover, increasing availability of historic and live train movement data creates new opportunities and challenges for future research. This paper examines and classifies approaches on train delay prediction in terms of prediction input, type of output, prediction horizon and dynamics of application. This should clear the jungle of the incredible diversity of approaches in this lively area of research and will be the initial point of a discussion of certain advantages and disadvantages of applied methods. Finally we discuss two research gaps and possible enrichments for future analysis and research.

The train trajectory optimization problem consists in determining the speed profile of a train between two stations that minimizes energy consumption while respecting the scheduled arrival time and operational constraints such as speed limits. The problem is well-known in the literature but has so far been studied without accounting for external factors as weather conditions or train load that in reality vary in each journey. These factors have an impact on the train resistance, which in turn can affect energy consumption. In this paper, we focus on wind uncertainty and propose a novel train resistance equation that accounts for the impact of wind intensity and direction. For different wind conditions, we determine optimal trajectories as dynamic programs defined on a space-speed network that embeds the physical train motion relations updated with the actual wind information. Numerical experiments show that our “wind-aware” train trajectories are more energy-efficient than traditional solutions computed independent of wind information.

Public transport networks such as bus and railway networks are highly complex systems. In fact, multiple sources of uncertainty including fluctuating passenger demand, variable road and traffic conditions, weather, and technical failures affect the network performance and reliability. These uncontrollable, stochastic factors follow intricate dynamics in space and time that makes it difficult to incorporate them into important decision-making processes of traffic management. For example, understanding how delays evolve (fade out absorbed by available buffer times,remain the same, or propagate through the network) is critical to undertake correct rescheduling actions for vehicles in the presence of delays or disruptions. Moreover, the number of stochastic factors is usually very large due to the many moving units or network links, which poses further modeling challenges. Goal of this paper is twofold. First, we review the existing stochastic models of the uncertainty employed in the public transport optimization literature, underlying their merits and shortcomings. Second, we define a roadmap for modeling high-dimensional uncertainties in public transport networks in a sound manner, with the goal of incorporating this uncertainty into stochastic optimization approaches.

Energisektoren er under hastig forandring, hvilket skaber behov for at løse en lang række nye optimeringsproblemer. Form˚alet med denne afhandling er at udvikle avancerede analytiske løsninger til bæredygtig energiforsyning og investeringsproblemer underlagt usikkerhed. Vi betragter case studier relateret til både industrielle anvendelser og husholdninger, og studerer problemer relateret til energieffektivitet, vedvarende energi og virksomhedernes sociale og miljømæssige ansvar. Problemer studeret i denne afhandling omfatter: (i) opbygning af en energikontrakt portefølje for virksomheder, der forpligter sig til at n˚a et m˚al for vedvarende energi, hvilket betyder at de skal have en bestemt procentdel af elforbruget dækket af vedvarende energikilder inden for en fremtidig horisont; (ii) optimering af nedluknings-beslutning i råvare og energiproduktionsaktiver med focus p˚a et socialt perspektiv, det vil sige under hensyntagentil de indirekte konsekvenser som en nedlukning af anlægget har for samfundet; (iii) modellering af optimale markedsbud-strategier for virtuelle kraftgeneratorer under en ny foresl˚aet elektricitetsmarkedsstruktur, der ville fremme integrering af vedvarende produktionsenheder; og (iv) undersøge faktorerne bag forbrugerinvesteringer i energieffektive husholdningsapparater, og finde de optimale energibesparende investeringer ud fra et forbruger- og energisystemperspektiv.For at løse disse problemer anvender vi værktøjer fra operationsanalyse til at designe ny metodik og udfører energianalyser. Flere problemer i denne afhandling kan formuleres som uh˚andterlige Markov-beslutningsprocesser (MDP’er) med multidimensional eksogene og/eller endogene komponenter i tilstanden. For at overvinde denne uhåndterbarhed udvikler vi approximerede dynamisk programmeringsmetoder (ADP) til beregning af næroptimale drifts- og investeringsbeslutninger, samt nedre og øvre grænser på den optimale MDP-værdi. I særdeleshed omfatter ADP-metoderne som vi udvikler: (i) en udvidelse af regress-senere mindste kvadrater Monte Carlo (LSML) metoden til at tilnærme risikoavers MDP’er, (ii) en kombination af LSML og klassifikation for at lære beslutningsregler (iii) en kortest-vej reformulering af reoptimiserings heuristikken, og (iv) en ny anvendelse af informationsrelaxeringerne og dualitetsrammen til at udtrække beslutningsregler uafhængigt på fremtiden fra testfordelinger. Vi anvender også mere klassisk scenarie-baseret stokastisk programmering. Bidragene fra denne afhandling omfatter modellering, metodologi og applikationer. Vibidrager til definitionen, forst˚aelsen og løsningen af nye optimeringsproblemer inden for bæredygtig energi og investering, og rapporterer resultater og indsigt som kan være nyttige for virksomheder og beslutningstagere. Vi bidrager til udviklingen af nye operationsanalyse, algoritmer og teori til løsning af stor-skala stokastiske optimeringsproblemer med særlig fokus p˚a ADP teknikker. Nogle af de metoder, der er udviklet i denne afhandling, har potentiel bredere relevans i andre anvendelses sammenhæng, såsom lagerstyring og finansiel porteføljeoptimering. The energy sector is undergoing a rapid transformation that gives rise to a variety of new optimization problems to solve. The goal of this thesis is to develop advanced analytical solutions for sustainable energy operations and investment problems that are subject to uncertainty. We consider case studies related to both industrial applications and consumer models, and cover problems related to energy efficiency, renewable energy, and corporate social and environmental responsibility. The problems that we consider in this thesis are the following: (i) constructing a power contract portfolio for companies that commit to reach a renewable energy target, which means, to procure a specific percentage of electricity demand from renewable energy sources by a future date; (ii) managing shutdown decisions in commodity and energy production assets from a social commerce perspective, that is, taking into account the indirect consequences that a plant shutdown has on the society; (iii) modeling the optimal market bidding strategies of virtual power generators under a novel proposed electricity market structure that would favor the integration of renewable production units; and (iv)investigating the factors behind the consumer investments in energy efficient household appliances, and the optimal energy saving investments from a consumer and energy system perspectives.To tackle these problems, we leverage tools from operations research to design novel methodology and perform energy analysis. Several problems encountered in this thesis can be formulated as intractable Markov decision processes (MDPs) with high-dimensional exogenous and/or endogenous component of the state. To overcome this intractability, we develop approximate dynamic programming (ADP) methods to compute near optimal operating and investment policies, and lower and upper bounds on the optimal MDP value. In particular, the ADP methods that we develop include: (i) an extension of the regress-later least squares Monte Carlo (LSML) to approximate risk-averse MDPs, (ii) a combination of LSML and classification to learn decision rules, (iii) a shortest path reformulation of the reoptimization heuristic, and (iv) a novel use of the information relaxations and duality framework to extract non-anticipative decision rules from sampleaction distributions. We also use more classical scenario-based stochastic programming. The contributions of this thesis cover modeling, methodology, and applications. We contribute to the definition, understanding, and resolution of emerging optimization problems in sustainable energy operations and investments, and provide results and insights that can be useful for companies and policy makers. We contribute to the development of new operations research models, algorithms, and theory for solving large-scale stochastic optimization problems, with particular focus on ADP techniques. Some of the methodology developed in this thesis has potential broader relevance in other application contexts,such as inventory control and financial portfolio optimization.