Combinatorial Optimization and Supply-Chain

Friday, December 13th, 2024

At the CNAM, Paris
192 rue Saint Martin, Amphitheater Jean-Baptiste Say (access 1, floor -1)

The registration is free, but please register!

See the list of the participants here

9h30 - 10h00  Welcome

10h00 - 10h45  Diego Delle Donne (ESSEC Business School of Paris)

Integrating Public Transport in Sustainable Last-Mile Delivery: Column Generation Approaches

We tackle the problem of coordinating a three-echelon last-mile delivery system. In the first echelon, trucks transport parcels from distribution centres outside the city to public transport stops. In the second echelon, the parcels move on public transport and reach the city centre. In the third echelon, zero-emission vehicles pick up the parcels at public transport stops and deliver them to customers. We introduce two extended formulations for this problem. The first has two exponential sets of variables, while the second has one. We propose column generation algorithms and compare several methods to solve the pricing problems on specially constructed graphs. We also devise dual bounds, which we can compute even when the graphs are so large that not a single pricing round completes within the time limit. Compared to previous formulations, our models find 16 new best known solutions out of an existing dataset of 24 instances from the literature.

Joint work with Claudia Archetti and Alberto Santini.

10h45 - 11h15  Coffee break

11h15 - 12h00  Onur Ozturk (Faculty of Telfer School of Management, University of Ottawa)

Exact and heuristic solution methods in the context of parallel batch scheduling

Parallel batching (p-batch) operations consist of processing multiple jobs at the same time using the same resource. p-batch can be encountered in diverse industries and contexts such as semi-conductor manufacturing, steel production, truck loading with heterogenous items, etc. Multiple objective functions can be considered such as the minimization of the total flow time to decrease work-in-progress levels, or weighted earliness/tardiness in accordance with a just-in-time production philosophy. It is possible to present p-batch problems as (mixed) integer linear programming models. Yet, the inefficiency of these models for large size instances requires other solution approaches such as column generation, branch and bound or heuristics. Thus, we will present how a time indexed set-partitioning formulation of the problem can be efficiently solved by column generation. Given the final solution is not always integer, we will also present how exact and heuristic solutions can be obtained through semi-binary branching in a tree search.
About the speaker: 
Onur Ozturk is an associate professor in the field of business analytics/operations management at the Telfer School of Management of the University of Ottawa. He has received his PhD from Grenoble Institute of Technology. Dr. Ozturk’s particular areas of research interest includes large scale optimization applied to production management, transportation and staff/patient scheduling in healthcare settings. He has published in international journals such as POM, EJOR, OMEGA, IJPR, ANOR, etc.

12h00 - 14h00 Lunch

14h00 - 14h45 Franco Quezada (Faculty of Engineering, Industrial Engineering Department, University of Santiago of Chile)

Multi-stage stochastic programming approach for a lot-sizing problem with remanufacturing

We consider an uncapacitated multi-item multi-echelon lot-sizing problem within a remanufacturing system involving three production echelons: disassembly, refurbishing and reassembly. We seek to plan the production activities on this system over a multi-period horizon. We consider a stochastic environment, in which the input data of the optimization problem are subject to uncertainty. We propose a multi-stage stochastic integer programming approach relying on scenario trees to represent the uncertain information structure and develop a branch-and-cut algorithm in order to solve the resulting mixed-integer linear program to optimality. This algorithm relies on a new set of tree inequalities obtained by combining valid inequalities previously known for each individual scenario of the scenario tree. These inequalities are used within a cutting-plane generation procedure based on a heuristic resolution of the corresponding separation problem. Computational experiments carried out on randomly generated instances show that the proposed branch-and-cut algorithm performs well as compared to the use of a stand-alone mathematical solver for medium-size instances. We then introduce a new dynamic programming formulation that relies on a partial nested decomposition of the scenario tree and propose a new approximate stochastic dual dynamic integer programming algorithm based on this partial decomposition. Our numerical results show that the proposed solution approach is able to provide near-optimal solutions for large-size instances with a reasonable computational effort.

Joint work with Céline Gicquel and Safia Kedad-Sidhoum.

14h45 - 15h30  Frédéric Semet (Centrale Lille, CRIStAL UMR CNRS)

15h30 - 16h00 Coffee break

16h00 - 16h45 Laurent Alfandari (ESSEC Business School)

Designing a robust supply chain of relief material for disaster preparedness with aftershocks: a branch-and-cut approach

Earthquakes are one of the deadliest natural disasters that can cause catastrophic damages,
leading to loss of life and property and displacing thousands of people. Often, most earthquakes
are followed by major and minor aftershocks. The aftershocks could also lead to other secondary
disasters like tsunamis, floods, avalanches, building collapses, etc. Thus, it is crucial to take
into account the damages caused by aftershocks in the preparation process. In this paper, we
study an uncapacitated facility location problem for storing relief materials in warehouses in the event of
such a disaster, minimizing the average time to supply material to disaster areas. We adopt a two-stage budgeted-robustness approach. We consider a major earthquake in the first stage, followed by aftershocks in the second stage. We propose several 
Mixed-Integer Linear Programming formulations for our problem and employ Branch-and-Cut
methods to separate uncertainty scenarios . We analyze the performance of our models on synthetically
generated instances and provide a case study on Turkey, which is highly prone to earthquakes.
The relevance of modeling the second-stage aftershocks and its impact on optimal locations of the warehouses are also assessed, comparing with solutions obtained when modelling only the main earthquake without aftershocks.

Joint work with Minkashi Punam-Mandal, Ivana Ljubic (ESSEC Business School)

Organizer: Zacharie Ales