Optimizing Hydroelectric Production and Maintenance

Hydroelectricity is a clean and renewable energy source that uses the power of water to produce energy. In Canada, more than 60% of electricity is generated by hydroelectricity, while in Quebec this figure rises to 97%. A hydroelectric system comprises power plants and reservoirs. Optimization models are used to efficiently manage these complex systems due to the spatiotemporal dependencies between facilities and uncertain water supplies at the planning stage. Indeed, these systems are subject to the vagaries of weather and hydrological forecasting: they also rely on turbines with different efficiencies.

The field of hydroelectric optimization is interested in development of mathematical models to solve these systems. Sara Séguin, professor in the Department of Computer Science and Mathematics at the Université du Québec à Chicoutimi and a GERAD member, works particularly on short-term models which aim to make decisions on short-term horizons (in hours or days) over periods of one to a few weeks. Sara Séguin has been working with Rio Tinto since 2013 to refine and develop new models. Projects are also underway with Dominique Orban and Miguel F. Anjos, respectively professors at Polytechnique Montréal and the University of Edinburgh. The research aims at refining models in order to produce more energy using the same facilities. Innovative modelling of production functions has made it possible to model and solve the problem over a very short computation time. It is particularly important to model production functions, considering they are essentially non-linear and non-convex. Solving these models makes it possible to avoid floods by keeping the reservoir levels at safe values, and allows for boating on lakes over the summer months by keeping the level high enough. In addition, producing more energy with the same amount of water ends up reducing costs for consumers.

Scaling Up Battery Swapping Services in Cities

Electrification of urban transportation is at the heart of burgeoning smart-city transformations. Electric vehicles run on batteries and electric motors, and therefore offer the prospect of benefits such as reducing carbon emissions. These anticipated benefits have pushed governments around the world to aggressively incentivize the adoption of electric vehicles. For example, the UK and France plan to ban the sale of new internal-combustion vehicles by 2035 and 2040, respectively. Chinese megacities ration more electric vehicle sales than fossil-fuel car sales by capping the numbers of issued licence plates. Given these trends, over 500 million passenger vehicles on the road, or 30% of the entire fleet, are expected to be electric by 2040.

As electric vehicles thrive, battery swapping is reviving. Battery swapping is an alternative to plugging in cars for battery charging: it refers to refuelling an electric vehicle by replacing the depleted battery on board with a charged one. The revival of battery swapping is driven by its three advantages over plug-in charging: 1) Speed: The swap process takes only 3-5 minutes, whereas using even Telsa's supercharger takes more than 30 minutes to charge a battery to 80%. 2) Compactness: The short service time allows a swapping station to occupy much less space than a plug-in charging station in order to achieve the same service level. 3) Safety: Compared with vehicle owners, service providers can more efficiently charge and maintain batteries. Therefore, battery swapping is widely believed likely to prevail, especially in large cities.

Nevertheless, electric vehicle companies and municipalities are now facing major challenges when they try to scale up battery swapping services in cities:

• Demand Uncertainty and Service Proximity: The infrastructure deployment needs to be dense so that random swapping demands are able to access a swapping station without much detour. The resulting urban swapping station networks are highly decentralized and thus difficult to operate.
• Battery Availability: Swapping stations also need to ensure a high availability of charged batteries in stock to satisfy swapping demands and to avoid queueing. This operational challenge is exacerbated by the decentralized layout of swapping stations, since swapping demands are more variable when disaggregated than when pooled. Consequently, the service provider has to build up massive battery inventories, which are expensive and environmentally detrimental.
• Grid Accessibility: Finally, charging depleted batteries at swapping stations may overload or even destabilize local low-voltage power distribution grids. These "last-mile" grids were often built without allocating enough capacity for electric vehicle charging. Upgrading existing distribution grids would be prohibitive, if not infeasible.

For years, GERAD's researchers have been working on operations research problems concerning greening our urban transportation systems under uncertainty. In particular, Wei Qi and his collaborators within and outside of GERAD have been working on providing deeper understanding of how to scale up citywide battery swapping services in order to cope with the aforementioned challenges. For example, these researchers are examining a "swap locally, charge centrally" network setting where batteries are locally swapped at decentralized swapping stations, and transported to and charged at more centralized charging stations that are connected to grids of sufficient capacity (which are typically of higher-voltage levels or near a substation). They have built models that analytically characterize the intertwined and stochastic operations of stocking, swapping, charging, and circulating batteries between a centralized charging station and decentralized swapping stations. They have also developed a new algorithmic framework combining constraint-generation and parameter-search techniques to solve intricate joint infrastructure planning and operations problems.

Reference:

• Qi, W., Zhang, Y., Zhang, N., Scaling Up Battery Swapping Services in Cities (June 19, 2020).

Demand Uncertainty in Inventory, Routing, and Location Decisions

One of the main complexities in supply chain planning comes from the unavoidable uncertainties which must be dealt with. GERAD members have developed methods based on robust and stochastic optimization to make better decisions in the face of uncertainty in supply chain applications. These problems range from operational and tactical problems such as routing or production and inventory planning, to strategic problems such as facility location.

The main uncertainty which complicates supply chain planning at all levels is the uncertainty in demand. When making production and inventory decisions, safety stock is used to protect against this demand uncertainty. The planner must balance the cost of not having enough inventory versus the cost of having too much inventory. Determining the right amount of safety stock is hence difficult and requires sophisticated optimization approaches. Yossiri Adulyasak, Jean-François Cordeau, Erick Delage, Raf Jans and Gilbert Laporte have leveraged stochastic programming and robust approaches to solve such production and inventory problems. Other uncertainties come from the production process itself, e.g., stochastic setup time, and must be considered in order to make efficient plans.

GERAD has a long and rich tradition of research on vehicle routing problems. Many GERAD members, including Yossiri Adulyasak, Leandro Coelho, Jean-François Cordeau, Guy Desaulniers, Fausto Errico, Raf Jans, Gilbert Laporte, and Andrea Lodi have considered the incorporation of stochastic elements into various vehicle routing problems. This includes not only the consideration of stochastic demand, but also stochastic travel times or service times. Furthermore, integrated planning problems considering production, inventory and routing decisions have also been studied in a stochastic environment.

Uncertainty also needs to be considered for more tactical and strategic decisions. An extremely important supply chain decision relates to the location of new facilities. These are long-term investment decisions and hence they must be taken when there is a lot of uncertainty related to future demand. Since it is difficult to have good information about such long-term demand, robust approaches have been used by Erick Delage and Yossiri Adulyasak. Also, other types of uncertainty, such as the possibility of disruptions at a facility, have been incorporated in such models. At a tactical level, Errico Fausto considered the demand uncertainty in a two-tier city logistics planning problem.

References:
Stochastic VRP

• Adulyasak, Y., Jaillet, P., Models and algorithms for stochastic and robust vehicle routing with deadlines. Transportation Science, 50(2), 608-626, 2016.

• Errico, F., Desaulniers, G., Gendreau, M., Rei, W., Rousseau, L.M., The vehicle routing problem with hard time windows and stochastic service times. EURO Journal on Transportation and Logistics, 7(3), 223-251, 2018.

• Errico, F., Desaulniers, G., Gendreau, M., Rei, W., Rousseau, L.M., A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times. European Journal of Operational Research, 249(1), 55-66, 2016.

• Gauvin, C., Desaulniers, G., Gendreau, M., A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands. Computers & Operations Research, 50, 141-153, 2014.

• Hoogeboom, M., Adulyasak, Y., Dullaert, W., Jaillet, P., The robust vehicle routing problem with time window assignments. Transportation Science, 55(2). 275-552, 2021.

• Markov, I., Bierlaire, M., Cordeau, J. F., Maknoon, Y., Varone, S., A unified framework for rich routing problems with stochastic demands. Transportation Research Part B: Methodological, 114, 213-240, 2018.

• Rostami, B., Desaulniers, G., Errico, F., Lodi, A., Branch-price-and-cut algorithms for the vehicle routing problem with stochastic and correlated travel times. Operations Research, 69(2), 436-455, 2021.

Stochastic integrated vehicle routing and inventory problems

• Adulyasak, Y., Cordeau, J.F., Jans, R., Benders decomposition for production routing under demand uncertainty. Operations Research, 63(4), 851-867, 2015.

• Alvarez, A., Cordeau, J.F., Jans, R., Munari, P., Morabito, R., Inventory routing under stochastic supply and demand. Omega, 102, 102304, 2021.

• Coelho, L.C., Cordeau, J.F., Laporte, G., Heuristics for dynamic and stochastic inventory-routing. Computers & Operations Research, 52, 55-67, 2014.

• Markov, I., Bierlaire, M., Cordeau, J.F., Maknoon, Y., Varone, S., Waste collection inventory routing with non-stationary stochastic demands. Computers & Operations Research, 113, 104798, 2020.

• Roldán, R.F., Basagoiti, R., Coelho, L.C., Robustness of inventory replenishment and customer selection policies for the dynamic and stochastic inventory-routing problem. Computers & Operations Research, 74, 14-20, 2016.

• Solyalı, O., Cordeau, J.F., Laporte, G., Robust inventory routing under demand uncertainty. Transportation Science, 46(3), 327-340, 2012.

Stochastic production and inventory planning

• Ardestani-Jaafari, A., Delage, E., Robust optimization of sums of piecewise linear functions with application to inventory problems. Operations research, 64(2), 474-494, 2016.

• Rodrigues, F., Agra, A., Requejo, C., Delage, E., Lagrangian duality for robust problems with decomposable functions: the case of a robust inventory problem. INFORMS Journal on Computing, 33(2), 685-705, 2021.

• Sereshti, N., Adulyasak, Y., Jans, R., The value of aggregate service levels in stochastic lot sizing problems. Omega, 102, 10233, 2021.

• Solyalı, O., Cordeau, J.F., Laporte, G., The impact of modeling on robust inventory management under demand uncertainty. Management Science, 62(4), 1188-1201, 2016.

• Taş, D., Gendreau, M., Jabali, O., Jans, R., A capacitated lot sizing problem with stochastic setup times and overtime. European Journal of Operational Research, 273(1), 146-159, 2019.

• Thevenin, S., Adulyasak, Y., Cordeau, J.F., Material requirements planning under demand uncertainty using stochastic optimization. Production and Operations Management, 30(2), 475-493, 2021.

Tactical and strategic stochastic problems

• Ardestani-Jaafari, A., Delage, E., The value of flexibility in robust location–transportation problems. Transportation Science, 52(1), 189-209, 2018.

• Cheng, C., Adulyasak, Y., Rousseau, L.M., Robust facility location under disruptions. INFORMS Journal on Optimization, 2021.

• Cheng, C., Adulyasak, Y., Rousseau, L.M., Robust facility location under demand uncertainty and facility disruptions. Omega, 103, 102429, 2021.

• Crainic, T.G., Errico, F., Rei, W., Ricciardi, N., Modeling demand uncertainty in two-tier city logistics tactical planning. Transportation Science, 50(2), 559-578, 2016.

• Saif, A., Delage, E., Data-driven distributionally robust capacitated facility location problem. European Journal of Operational Research, 291(3), 995-1007, 2021.