TIMES modelling

Canada is aiming for zero net greenhouse gas (GHG) emissions by 2050. But how can we achieve this ambitious carbon neutrality objective? Mainly be taking action on energy production and consumption, both of which can be assessed using so-called “techno-economic” energy models. These models detail the entire energy sector with its various forms of energy (oil, bioenergy, electricity, eat.) and associated technologies, in order to identify strategies that would avoid or sequester GHG emissions.

Over time, GERAD members have developed several versions of such models, following particularly the TIMES approach as developed by the International Energy Agency. TIMES is a large mathematical program – consisting of millions of variables and equations – which can be used to create a model which can then be used to identify the most economically efficient GHG reduction scenarios and the optimal timeframe for implementing them.

TIMES is a mathematical program that identifies the most efficient GHG reduction scenarios.

GERAD designed an initial TIMES model adapted to the Canadian context (TIMES Canada). ESMIA Consultants – a firm founded by Kathleen Vaillancourt, an entrepreneur trained at GERAD – then transformed TIMES Canada into a North American version called NATEM. ESMIA uses this model to advise companies and government; for example, in collaboration with the Trottier Energy Institute and Olivier Bahn, professor in the Department of Decision Science at HEC Montréal and Director of GERAD, it is using the model to develop a Canadian energy outlook. In this regard, the latest report, published in 2018, highlights the importance of electrification and bioenergy deployment in achieving Canada’s ambitious GHG reduction targets.

ESMIA and Olivier Bahn also use NATEM in the university setting, for example to assess the economic and ecological relevance of a new construction material developed at McGill University with a view to replacing cement.

Planning Operations in Public Transport

All large cities have a public transport network that comprises, among others, a bus service. This infrastructure offers to the population the possibility to travel between the various neighbourhoods of the city in an economical and environmentally friendly fashion. Public transport companies are to a large extent subsidized by governments and must therefore offer good-quality service while avoiding excessive operating costs. Consequently, they rely on decision-making software to optimize operational planning.

Given that task complexity (for example, the Société de transport de Montréal offers more than 17,000 bus trips per day, distributed among 225 bus routes), planning for a bus network is typically done by steps. Network planning includes development of: i) bus routes; ii) trip schedules for each route; iii) bus schedules indicating the sequence of trips to perform for each bus; iv) daily work schedules specifying the sequences of trips an anonymous driver must cover; and v) drivers' schedules assigning work duties and days off to each driver for the next month. The problems in steps i) and ii) are at the strategic/tactical level and relate to maximizing the quality of service while respecting some global constraints on resource availability. On the other hand, the problems in steps iii) to v) are operational ones that relate to offering at least cost the service established in the previous steps while taking into account numerous practical constraints such as those stemming from the drivers' collective agreement.

For several decades now, GERAD's researchers have realized research projects on the operational problems of steps iii) to v). Most of these works have been conducted in collaboration with GIRO company, which is the world leader in the commercialization of optimization software for public transport. To solve the driver duty scheduling problem, François Soumis and Jacques Desrosiers have developed at the end of the 1980s, a column generation algorithm, called Gencol, that allows to select the best set of work duties to perform among a huge number of possible duties without having to enumerate them all. This algorithm, which is still in use at GIRO, has been enhanced over the years with new advancements made at the GERAD, namely, the dynamic constraint aggregation technique designed by Issmail El Hallaoui, François Soumis and Guy Desaulniers. More recently, GIRO has decided to also apply column generation for solving the bus scheduling problem in order to handle the recharging constraints of the electric buses. In this regard, a new collaboration with Guy Desaulniers has permitted to study different variants of this problem, including that considering the possibility to slighlty shift the trip start times. Finally, Guy Desaulniers, Andrea Lodi and François Soumis are teaming up to integrate statistical and machine learning methods in the optimization algorithms for public transit.

Integrated Production and Transportation Planning

In a supply chain, different activities are done in sequence, starting from the initial suppliers to the final customers. Some of the most important activities include production, inventory management and transportation. In many cases, these different activities are managed in isolation. However, important gains can be achieved by explicitly considering the interaction between the various activities and hence optimizing them simultaneously.

In the context of a Vendor Managed Inventory (VMI) system, the supplier makes replenishment decisions for their customers. This leads to complex trade-offs. For example, when deciding when to produce and deliver two different customer orders, the supplier must consider several elements. If the two customers are located close to each other, some economies in transportation cost might be achieved by delivering the orders in the same route. However, this might also induce additional holding costs if these orders have different due dates. Furthermore, if the supplier is also producing the goods, then production decisions need to be incorporated: are there any possible economies of scale in production and is there enough capacity available?

Clearly, the consideration of multiple stages in the supply chain makes the planning process much more complex, and this therefore requires more sophisticated tools. Since the different activities impact each other, planning requires an integrated approach. Several members of GERAD have studied integrated supply chain planning problems, such as the Inventory Routing Problem and the Production Routing Problem.

There are many real-life applications in which these problems appear. Guy Desaulniers studied an application for a catering service company delivering meals to various clients. In this case, an employee shift schedule needed to be established in addition to the production and distribution plan. Jean-François Cordeau and Raf Jans studied another real-life application of integrated production and routing planning for a meat producer who needs to deliver a whole range of products to close to 200 retailers having different time windows. In both cases, the problem is made more difficult because of the short life span of the products. Jean-François Cordeau and Raf Jans considered another application of the Production Routing Problem in the furniture industry. Guy Desaulniers, Jacques Desrosiers considered the Inventory Routing Problem in a maritime setting for liquefied natural gas. Leandro Coelho and Gilbert Laporte solved variants of the Inventory Routing Problem in various real-life applications: one for a bottled water manufacturer and another one for the replenishment of automated teller machines.

Together with the aforementioned researchers, other GERAD members such as Yossiri Adulyasak have also focused on developing efficient optimization algorithms for various integrated production, inventory and transportation planning problems, including efficient algorithms for the Inventory-Routing problem, the Production-Routing problem and the integrated Vessel Service Planning problem.

Other GERAD members have also considered different types of integrated logistics planning problems, such as the integration of vehicle routing and load planning by Marilène Cherkesly.

References:

• Adulyasak, Y., Cordeau, J.F., Jans, R., Optimization-based adaptive large neighborhood search for the production routing problem. Transportation Science, 48(1), 20-45, 2014.

• Adulyasak, Y., Cordeau, J.F., Jans, R., Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems. INFORMS Journal on Computing, 26(1), 103-120, 2014.

• Bertazzi, L., Coelho, L.C., De Maio, A., Laganà, D., A matheuristic algorithm for the multi-depot inventory routing problem. Transportation Research Part E: Logistics and Transportation Review, 122, 524-544, 2019.

• Cherkesly, M., Desaulniers, G., Laporte, G., Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and last-in-first-out loading. Transportation Science, 49(4), 752-766, 2015.

• Chitsaz, M., Cordeau, J.F., Jans, R., A unified decomposition matheuristic for assembly, production, and inventory routing. INFORMS Journal on Computing, 31(1), 134-152, 2019.

• Dayarian, I., Desaulniers, G., A branch-price-and-cut algorithm for a production-routing problem with short-life-span products. Transportation Science, 53(3), 829-849, 2019.

• Desaulniers, G., Rakke, J.G., Coelho, L.C., A branch-price-and-cut algorithm for the inventory-routing problem. Transportation Science, 50(3), 1060-1076, 2016.

• Grønhaug, R., Christiansen, M., Desaulniers, G., Desrosiers, J., A branch-and-price method for a liquefied natural gas inventory routing problem. Transportation Science, 44(3), 400-415, 2010.

• Guimarães, T. A., Coelho, L.C., Schenekemberg, C.M., Scarpin, C.T., The two-echelon multi-depot inventory-routing problem. Computers & Operations Research, 101, 220-233, 2019.

• Li, Y., Chu, F., Côté, J.F., Coelho, L.C., Chu, C., The multi-plant perishable food production routing with packaging consideration. International Journal of Production Economics, 221, 107472, 2020.

• Lmariouh, J., Coelho, L.C., Elhachemi, N., Laporte, G., Jamali, A., Bouami, D., Solving a vendor-managed inventory routing problem arising in the distribution of bottled water in Morocco. European Journal of Industrial Engineering, 11(2), 168-184, 2017.

• Neves-Moreira, F., Almada-Lobo, B., Cordeau, J.F., Guimarães, L., Jans, R., Solving a large multi-product production-routing problem with delivery time windows. Omega, 86, 154-172, 2019.

• Van Anholt, R.G., Coelho, L.C., Laporte, G., Vis, I.F., An inventory-routing problem with pickups and deliveries arising in the replenishment of automated teller machines. Transportation Science, 50(3), 1077-1091, 2016.

• Wu, L., Adulyasak, Y., Cordeau, J.-F., Wang, S., Vessel Service Planning in Seaports. Operations Research (Forthcoming), 2021.