Modeling system dynamics of interacting cruising trains to reduce
the impact of power peaks (with F. Corman).
Expert Systems with Applications, 230, 120650, 2023.
[ |
|
|
]
Rail operators around the globe are striving to improve the efficiency, automation, safety, and sustainability
of railway systems. Despite significant advances in technologies such as artificial intelligence and automated train
operations (ATO), achieving these goals is challenging for complex rail networks when accounting for unpredictable factors
that alter real-time operations. In this paper, we model railway traffic in a corridor as a string of interacting cruising
trains, each subject to random speed variations that are described by a stochastic process. We simulate this dynamic system
under assumptions that model human drivers and ATO systems, and compute performance measures focusing on energy consumption
and the power peaks arising when multiple trains accelerate simultaneously. We then investigate strategies to smooth these
peaks including the use of regenerative braking energy, potentially coupled with an electric energy storage, and a rule that
uses fixed waiting times before re-acceleration. Our findings shed light on when and why these strategies can be effective
at reducing energy consumption and/or shaving the peaks. We also show that employing a well-calibrated ATO controller in
which vehicles exchange information about their location improves energy performance compared to a model of a human driven.
We finally expose a trade-off between energy performance and traffic regularity, i.e., strategies to reduce power peaks may
slow rail traffic down, reducing capacity utilization.
Meeting corporate renewable power targets
(with D. Mohseni-Taheri and S. Nadarajah).
Management Science, 69(1), p.491–512, 2023.
Received the 2020 INFORMS ENRE Early Career Best Paper Award and the 2021 Best Paper Award by CEMA (Commodity and Energy Markets Association).
[ |
|
|
]
Several corporations have committed to procuring a percentage of their electricity demand from renewable sources by a future
date. Long-term financial contracts with renewable generators based on a fixed strike price, known as virtual power purchase
agreements (VPPAs), are popular to meet such a target. We formulate rolling power purchases using a portfolio of VPPAs as a
Markov decision process, accounting for uncertainty in generator availability and in the prices of electricity, renewable
energy certificates, and VPPAs. Obtaining an optimal procurement policy is intractable. We consider forecast-based reoptimization
heuristics consistent with practice that limit the sourcing of different VPPA types and the timing of new agreements. We extend
these heuristics and introduce an information-relaxation based reoptimization heuristic, both of which allow for full sourcing
and timing flexibilities. The latter heuristic also accounts for future uncertainties when making a decision. We assess the value
of decision flexibility in rolling power purchases to meet a renewable target by numerically comparing the aforementioned policies
and variants thereof on realistic instances involving a novel strike price stochastic process calibrated to data. Policies with
full timing flexibility and no sourcing flexibility reduce procurement costs significantly compared to one with neither type of
flexibility. Introducing sourcing flexibility in the former policies results in further significant cost reduction, thus providing
support for using VPPA portfolios that are both dynamic and heterogeneous. Computing near-optimal portfolios of this nature
entails using our information-relaxation based reoptimization heuristic because portfolios constructed via forecast-based
reoptimization exhibit higher suboptimality.
Modeling soft unloading constraints in the multi-drop container loading problem
(with G. Bonet Filella and F. Corman). .
European Journal of Operational Research, 308(1), p.336–352, 2023.
[ |
|
]
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, limits the flexibility to optimize the packing and utilize the vehicle capacity.
We instead 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 value of the loaded cargo including penalties 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 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 instances and penalties highlight the advantages of our method
compared to a commercial optimization solver and a heuristic from the literature developed for a related problem. They
also 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.
Enhancing the interaction of railway timetabling and line planning with infrastructure awareness
(with F. Fuchs and F. Corman).
Transportation Research Part C: Emerging Technologies, 142, 103805, 2022.
[ |
|
]
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.
Multi-scale design optimization of modern offshore wind farms
(with D. Cazzaro, F. Corman and D. Pisinger).
Applied Energy, 314, 118830, 2022.
[ |
]
The traditional optimization of the layout of a wind farm consisted in arranging the wind turbines inside a designated area.
In contrast, the 2021 tender from the UK government, Offshore Wind Leasing Round 4 ("UK Round-4") and upcoming bids only specify
large regions where the wind farm can be built. This leads to the new challenge to select the shape and area of the wind farm,
out of a larger region, to maximize its profitability. We introduce this problem as the "wind farm area selection problem" and
present a novel optimization framework to efficiently solve it. Specifically, our framework combines three scales of design:
(i) on a macro-scale, choosing the approximate location of the wind farm out of larger regions, (ii) on a meso-scale, generating
the optimal shape of the wind farm, and (iii) on a micro-scale, choosing the exact position of the turbines within the shape.
In particular, we propose a new constructive heuristic to choose the best shape of a wind farm at the meso-scale, which is scarcely
studied in literature. Moreover, while macro and micro-scales have already been investigated, our framework is the first to integrate
them. We perform a detailed computational analysis using real-life data and constraints from the recent UK Round-4 tender. Compared
to the best rectangular-shaped wind farm at the same location, our results show that optimizing the shape increases profitability
by 1.2% on average and up to 2.9%, corresponding to 50 and 112 million Euro respectively.
A review of train delay prediction approaches
(with T. Spanninger, B. Buchel and F. Corman).
Journal of Rail Transport Planning & Management,, 22, 100312, 2022.
[ |
|
]
Railway operations are vulnerable to delays. Accurate predictions of train arrival and departure delays improve the
passenger service quality and are essential for real-time railway traffic management to minimise their further spreading.
This review provides a synoptic overview and discussion covering the breadth of diverse approaches to predict train delays.
We first categorise research contributions based on their underlying modelling paradigm (data-driven and event-driven) and
their mathematical model. We then distinguish between very short to long-term predictions and classify different input data
sources that have been considered in the literature. We further discuss advantages and disadvantages of producing deterministic
versus stochastic predictions, the applicability of different approaches during disruptions and their interpretability.
By comparing the results of the included contributions, we can indicate that the prediction error generally increases when
broadening the prediction horizon. We find that data-driven approaches might have the edge on event-driven approaches in
terms of prediction accuracy, whereas event-driven approaches that explicitly model the dynamics and dependencies of railway
traffic have their strength in providing interpretable predictions, and are more robust concerning disruption scenarios.
The growing availability of railway operations data is expected to increase the appeal of big-data and machine learning methods.
An optimization approach for a complex real-life container loading problem
(with M. Gajda, R. Mansini and D. Pisinger).
Omega, 107, 102559, 2022.
Selected as one of the six finalist of the EURO Excellence in Practice Award (EEPA) in 2021.
[ |
|
|
]
We consider a real-world packing problem faced by a logistics company that loads and ships hundreds of trucks every day.
For each shipment, the cargo has to be selected from a set of heterogeneous boxes. The goal of the resulting container loading
problem (CLP) is to maximize the value of the cargo while satisfying a number of practical constraints to ensure safety and
facilitate cargo handling, including customer priorities, load balancing, cargo stability, stacking constraints, positioning
constraints, and limiting the number of unnecessary cargo move operations during multi-shipment deliveries. Although some of
these constraints have been considered in the literature, this is the first time a problem tackles all of them jointly on real
instances. Moreover, differently from the literature, we treat the unnecessary move operations as soft constraints and analyze
their trade-off with the value maximization. As a result, the problem is inherently multi-objective and extremely challenging.
We tackle it by proposing a randomized constructive heuristic that iteratively combines items in a preprocessing procedure, sorts
them based on multiple criteria, uses randomization to partially perturb the sorting, and finally constructs the packing while
complying with all the side constraints. We also propose dual bounds based on CLP relaxations. On large-scale industry instances,
our algorithm runs in a few seconds and outperforms (in terms of value and constraints handling) both the solutions constructed
manually by the company and those provided by a commercial software. The algorithm is currently used by the company generating
significant economic and CO2 savings.
Socially responsible merchant operations: Comparison of shutdown-averse CVaR
and anticipated regret policies (with S.Nadarajah).
Operations Research Letters, 49(4), p.553-558, 2021.
[ |
]
Commodity and energy production assets are managed as real options on market uncertainties. Social impacts of plant
shutdowns incentivize balancing asset value with shutdown probability. We propose new shutdown-averse policies based on
the popular dynamic conditional value-at-risk (CVaR). We analytically and numerically compare these policies to known
shutdown-averse policies based on anticipated regret (AR). Our findings support the use of AR over CVaR to embed
shutdown-aversion and the consideration of hybrid policies that are asymptotically time-consistent but easily interpretable.
The multi-commodity network flow problem with soft transit time constraints:
Application to liner shipping (with F. Corman, D.F. Koza and D. Pisinger).
Transportation Research Part E: Logistics and Transportation Review, 150, 102342, 2021.
[ |
|
]
The multi-commodity network flow problem (MCNF) consists in routing a set of commodities through a capacitated network
at minimum cost and is relevant for routing containers in liner shipping networks. As commodity transit times are often a critical
factor, the literature has introduced hard limits on commodity transit times. In practical contexts, however, these hard limits
may fail to provide sufficient flexibility since routes with even tiny delays would be discarded. Motivated by a major liner
shipping operator, we study an MCNF generalization where transit time restrictions are modeled as soft constraints, in which
delays are discouraged using penalty functions of transit time. Similarly, early commodity arrivals can receive a discount in
cost. We derive properties that distinguish this model from other MCNF variants and adapt a column generation procedure to
efficiently solve it. Extensive numerical experiments conducted on realistic liner shipping instances reveal that the explicit
consideration of penalty functions can lead to significant cost reductions compared to hard transit time deadlines. Moreover,
the penalties can be used to steer the flow towards slower or faster configurations, resulting in a potential increase in
operational costs, which generates a trade-off that we quantify under varying penalty functions.
Stochastic process models of railway traffic flow: Models, methods, and implications
(with F. Corman and M.Keyvan-Ekbatani).
Transportation Research Part C: Emerging Technologies, 128, 103167, 2021. Published as part of the ISTTT24 Conference.
[ |
|
]
We model railway traffic dynamics based on microscopic behavior of vehicles, i.e. speed and distance between vehicles.
We consider domain dynamics (e.g. signalling system, kinematic equations) and additional components which are modelled as
stochastic factors, affecting speed. Those latter model well the trajectories of railway vehicles observed in real life, representing
the combined effect of human actions, track variations, resistances, control systems and actions. We propose multiple stochastic
process models (i.e. Brownian motion, Ornstein-Uhlenbeck, doublybounded Cox-Ingersoll-Ross, and doubly mean-reverting Langevin equation)
which extend the existing traffic flow theory models for cars towards railway traffic and its specific requirements and constraints.
To the best of authors' knowledge, this paper is the first work which considers stochastic components in order to model mathematically
realistic railway traffic dynamics in line with the findings in roadway microscopic traffic behaviour modelling. Closed expressions
of relevant characteristics for some stochastic process models have been derived. The behavior of the system has been simulated to
derive macroscopic performance indicators and later compared with a deterministic model performance as a benchmark. The models can
be useful to estimate the benefits introduced by automation in railways, including Automated Train Operation (ATO).
Managing shutdown decisions in merchant commodity and energy production: A social commerce perspective
(with S. Nadarajah, S.E. Fleten, D. Maziers and D. Pisinger).
Manufacturing & Service Operations Management, 23(2), p.311-330, 2021.
[ |
|
]
Problem definition: Merchant commodity and energy production assets operate in markets with volatile prices and exchange rates.
Plant closures adversely affect societal entities beyond the specific plant being shut down, such as the parent company and the
local community. Motivated by an aluminum producer, we study if mitigating these hard-to-assess broader impacts of a shutdown is
financially viable using the plant's operating flexibility. Academic/practical relevance: Our social commerce perspective toward
managing shutdown decisions deviates from the commonly used asset value maximization objective in merchant operations.
Identifying operating policies that delay or decrease the likelihood of a shutdown without incurring a significant asset value
loss supports socially responsible plant shutdown decisions. Methodology: We formulate a constrained Markov decision process to
manage shutdown decisions and limit the probability of future plant closures. We provide theoretical support for approximating this
intractable model using unconstrained stochastic dynamic programs with modified shutdown costs and explore two classes of operating
policies. Our first policy leverages anticipated regret theory, and the second policy generalizes, using machine learning,
production-margin heuristics used in practice. We compute the former and latter policies using a least squares Monte Carlo method
and combining this method with binary classification, respectively. Results: Anticipated-regret policies possess desirable asymptotic
properties absent in classification-based policies. On instances created using real data, anticipated-regret and classification-based
policies outperform practice-based production-margin strategies. Significant reductions in shutdown probability and delays in plant
closures are possible while incurring small asset value losses. Managerial implications: A plant's operating flexibility provides
an effective lever to balance the social objective to reduce closures and the financial goal to maximize asset value. Adhering to
both objectives requires combining short-term commitments with external stakeholders to avoid shutdown with longer-term internal
efforts to reduce the probability of plant closures.
The impact of wind on energy-efficient train control
(with P. Wang and F. Corman).
EURO Journal on Transportation and Logistics, 10, 100013, 2021.
[ |
]
An energy-efficient train trajectory corresponds to 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. Determining
this trajectory is a well-known problem in the operations research and transport literature, but has so far been studied
without accounting for stochastic variables like weather conditions or train load that in reality vary in each journey.
These variables have an impact on the train resistance, which in turn affects the energy consumption. In this paper, we
focus on wind variability and propose a train resistance equation that accounts for the impact of wind speed and direction
explicitly on the train motion. Based on this equation, we compute the energy-efficient speed profile that exploits the
knowledge of wind available before train departure, i.e., wind measurements and forecasts. Specifically, we: (i) construct
a distance-speed network that relies on a new non-linear discretization of speed values and embeds the physical train motion
relations updated with the wind data, and (ii) compute the energy-efficient trajectory by combining a line-search framework
with a dynamic programming shortest path algorithm. Extensive numerical experiments reveal that our "wind-aware" train
trajectories present different shape and reduce energy consumption compared to traditional speed profiles computed regardless
of any wind information.
A stochastic programming approach for scheduling extra metro trains to serve passengers from uncertain delayed
high-speed railway trains (with S. Long, L. Meng, X. Luan, J. Miao, and F. Corman).
Journal of Advanced Transportation, 8894174, 2020.
[ |
]
The metro system is an important component of the urban transportation system due to the large volume of
transported passengers. Hub stations connecting metro and high-speed railway (HSR) networks are particularly
critical in this system. When HSR trains are delayed due to a disruption on the HSR network, passengers of these
trains arriving at the hub station at night may fail to get their last metro connection. The metro operator can thus
decide to schedule extra metro trains at night to serve passengers from delayed HSR trains. In this paper, we consider
the extra metro train scheduling problem in which the metro operator decides how many extra metro trains to dispatch and
their schedules. The problem is complex because (i) the arrival of delayed HSR trains is usually uncertain, and (ii) the
operator has to minimize operating costs (i.e., number of additional trains and operation-ending time) but maximize the
number of served passengers, which are two conflicting objectives. In other words, the problem we consider is stochastic
and biobjective. We formulate this problem as a two-stage stochastic program with recourse and use an epsilon-constrained
method to find a set of nondominated solutions. We perform extensive numerical experiments using realistic instances based
on the Beijing metro network and two HSR lines connected to this network. We find that our stochastic model outperforms
out-of-sample a deterministic model that relies on forecasts of the delay by a range of 3-5%. Moreover, we show that our
solutions are nearly optimal by computing a perfect information dual bound and obtaining average optimality gaps below 1%.
Train trajectory optimization for improved on-time arrival under parametric uncertainty
(with P. Wang, R. Goverde and F. Corman).
Transportation Research Part C: Emerging Technologies, 119(1), 102680, 2020.
[ |
]
In this paper we study the problem of computing train trajectories in an uncertain environment in which the values of some
system parameters are difficult to determine. Specifically, we consider uncertainty in traction force and train resistance, and
their impact on travel time and energy consumption. Our ultimate goal is to be able to control trains such that they will arrive
on-time, i.e. within the planned running time, regardless of uncertain factors affecting their dynamic or kinematic performance.
We formulate the problem as a Markov decision process and solve it using a novel numerical approach which combines: (i) an off-line
approximate dynamic programming (ADP) method to learn the energy and time costs over iterations, and (ii) an on-line search process
to determine energy-efficient driving strategies that respect the real-time time windows, more in general expressed as train path
envelope constraints. To evaluate the performance of our approach, we conducted a numerical study using real-life railway
infrastructure and train data. Compared to a set of benchmark driving strategies, the trajectories from our ADP-based method
reduce the probability of delayed arrival, and at the same time are able to better use the available running time for energy saving.
Our results show that accounting for uncertainty is relevant when computing train trajectories and that our ADP-based method can handle
this uncertainty effectively.
Enabling active/passive electricity trading in dual-price balancing markets
(with N. Mazzi and J.M. Morales).
IEEE Transactions on Power Systems, 34(3), p.1980-1990, 2019.
[ |
]
]
In electricity markets with a dual-pricing scheme for balancing energy, controllable production units typically participate
in the balancing market as "active" actors by offering regulating energy to the system, while renewable stochastic units
are treated as "passive" participants that create imbalances and are subject to less competitive prices. Against this
background, we propose an innovative market framework whereby the participant in the balancing market is allowed to act as an
active agent (i.e., a provider of regulating energy) in some trading intervals and as a passive agent (i.e., a user of regulating
energy) in some others. To illustrate and evaluate the proposed market framework, we consider the case of a virtual power plant
(VPP) that trades in a two-settlement electricity market composed of a day-ahead and a dual-price balancing market. We formulate
the optimal market offering problem of the VPP as a three-stage stochastic program, where uncertainty is in the day-ahead
electricity prices, balancing prices and the power output from the renewable units. Computational experiments show that the VPP
expected revenues can increase substantially compared to an active-only or passive-only participation, and we discuss how the
variability of the stochastic sources affects the balancing market participation choice.
Modeling of electricity savings in the Danish households sector:
from the energy system to the end-user (with M. Baldini). Energy Efficiency, 11(7), p.1563-1581, 2018.
[ |
]
In this paper we examine the value of investing in energy-efficient household appliances from both an energy system
and end-user perspective. We consider a set of appliance categories constituting the majority of the electricity consumption
in the private household sector, and focus on the stock of products which need to be replaced. First, we look at the
energy system and investigate whether investing in improved energy efficiency can compete with the cost of
electricity supply from existing or new power plants. To assess the analysis, Balmorel, a linear optimization model
for the heat and power sectors, has been extended in order to endogenously determine the best possible investments
in more efficient household appliances. Second, we propose a method to relate the optimal energy system solution to the
end-user choices by incorporating consumer behavior and electricity price addition due to taxes. The model is non-exclusively
tested on the Danish energy system under different scenarios. Computational experiments show that several energy efficiency
measures in the household sector should be regarded as valuable investments (e.g. an efficient lighting system) while
others would require some form of support to become profitable. The analysis quantifies energy and economic savings
from the consumer side and reveals the impacts on the Danish power system and surrounding countries. Compared to a
business-as-usual energy scenario, the end-user attains net economic savings in the range of 30-40 EUR per year,
and the system can benefit of an annual electricity demand reduction of 140-150 GWh. The paper enriches the existing
literature about EE modeling in households, contributing with novel models, methods, and findings related to the Danish case.
The impact of socioeconomic and behavioural factors for purchasing
energy efficient household appliances: A case study for Denmark (with M. Baldini and J.W. Wente).
Energy Policy, 120(1), p.503-513, 2018.
[ |
]
Increasing the share of evermore energy efficient household electric appliances is one strategy to address environmental
impacts arising from residential electricity demand. Hence, governments and energy actors are interested in the determining
factors behind the consumer choice of conventional versus high efficiency labelled appliances. This study employs empirical
survey data from the Danish Energy Agency to model influential factors behind Danish consumer choice of energy efficient
appliances. To estimate consumer propensities, we use a logistic regression model over a set of socioeconomic, demographic,
and behavioural variables. The study regresses over this unique combination of end-use behavioural variables by creating
an energy efficiency index. Statistical results show that housing type, quantity of inhabitants, age, and end-use behaviour
are strong predictors for choosing energy efficient appliances. Interestingly, income is a weaker predictor. Despite a
relatively wealthy national income and well-educated population, information campaigns have been largely ineffective in
driving high efficiency investments. In light of this study's results and exogenous factors such as urbanising demographics
and shifting Danish housing stock towards apartments, the study suggests improved information campaigns by targeting key
demographics.
The load-balanced multi-dimensional bin-packing problem (with D. Pisinger).
Computers & Operations Research, 74(1), p.152-164, 2016.
[ |
]
The bin-packing problem is one of the most investigated and applicable combinatorial optimization problems.
In this paper we consider its multi-dimensional version with the practical extension of load balancing, i.e.
to find the packing requiring the minimum number of bins while ensuring that the average center of mass of the
loaded bins falls as close as possible to an ideal point, for instance, the center of the bin. We formally describe
the problem using mixed-integer linear programming models, from the simple case where we want to optimally balance
a set of items already assigned to a single bin, to the general balanced bin-packing problem. Given the difficulty
for standard solvers to deal even with small size instances, a multi-level local search heuristic is presented.
The algorithm takes advantage of the Fekete-Schepers representation of feasible packings in terms of particular
classes of interval graphs, and iteratively improves the load balancing of a bin-packing solution using different
search levels. The first level explores the space of transitive orientations of the complement graphs associated
with the packing, the second modifies the structure itself of the interval graphs, the third exchanges items between
bins repacking proper n-tuples of weakly balanced bins. Computational experiments show very promising results on a set of
3D bin-packing instances from the literature.
|
