This work studies a combinatorial optimization problem encountered in industrial production planning: the single-item multi-resource lot-sizing problem with inventory bounds and lost sales. The demand to be satisfied by the production plan is subject to uncertainty and only probabilistically known. We consider a multi-stage decision process with a Decision–Hazard–Decision information structure in which decisions are made at each stage both before and after the uncertainty is revealed. Such a setting has not yet been studied for stochastic lot-sizing problems, and the resulting problem is modeled as a multi-stage stochastic integer program. We propose a solution approach based on an approximate stochastic dynamic programming algorithm. It relies on a decomposition of the problem into single-stage sub-problems and on the estimation at each stage of the expected future costs. Due to the Decision–Hazard–Decision information structure, each nested single-stage sub-problem is itself a two-stage stochastic integer program. We therefore introduce a Benders decomposition scheme to reduce the computational effort required to solve each nested sub-problem, and present a special-purpose polynomial-time algorithm to efficiently solve the single-scenario second-stage sub-problems involved in the Benders decomposition. The results of extensive simulation experiments carried out on large-size randomly generated instances are reported. They demonstrate the practical benefit, in terms of the actual production cost, of using the proposed approach as compared to a naive deterministic optimization approach based on the expected demand.

Electric vehicle sharing systems deployed in large cities provide alternative means of transportation for non-vehicle owners and visitors. This work considers the optimal design of a one-way station-based electric vehicle sharing system. Location of charging stations is assumed to be known so that the main strategic decisions regard the installation of charging ports at stations and the acquisition of electric vehicles. To assess the future system profitability, the strategic problem modeling should integrate tactical and operational decisions representing how the system will operate on a daily basis. This work investigates whether modeling an operational feature, vehicle relocation by employees, has a strong impact on the quality of the design decisions recommended by the optimization model.

International audience

International audience

We study the uncapacitated lot-sizing problem with uncertain demand and costs. The problem is modeled as a multistage stochastic mixed-integer linear program in which the evolution of the uncertain parameters is represented by a scenario tree. To solve this problem, we propose a new extension of the stochastic dual dynamic integer programming algorithm (SDDiP). This extension aims at being more computationally efficient in the management of the expected cost-to-go functions involved in the model, in particular by reducing their number and by exploiting the current knowledge on the polyhedral structure of the stochastic uncapacitated lot-sizing problem. The algorithm is based on a partial decomposition of the problem into a set of stochastic subproblems, each one involving a subset of nodes forming a subtree of the initial scenario tree. We then introduce a cutting plane–generation procedure that iteratively strengthens the linear relaxation of these subproblems and enables the generation of an additional strengthened Benders’ cut, which improves the convergence of the method. We carry out extensive computational experiments on randomly generated large-size instances. Our numerical results show that the proposed algorithm significantly outperforms the SDDiP algorithm at providing good-quality solutions within the computation time limit. Summary of Contribution: This paper investigates a combinatorial optimization problem called the uncapacitated lot-sizing problem. This problem has been widely studied in the operations research literature as it appears as a core subproblem in many industrial production planning problems. We consider a stochastic extension in which the input parameters are subject to uncertainty and model the resulting stochastic optimization problem as a multistage stochastic integer program. To solve this stochastic problem, we propose a novel extension of the recently published stochastic dual dynamic integer programming (SDDiP) algorithm. The proposed extension relies on two main ideas: the use of a partial decomposition of the scenario tree and the exploitation of existing knowledge on the polyhedral structure of the stochastic uncapacitated lot-sizing problem. We provide the results of extensive computational experiments carried out on large-size randomly generated instances. These results show that the proposed extended algorithm significantly outperforms the SDDiP at providing good-quality solutions for the stochastic uncapacitated lot-sizing problem. Although the paper focuses on a basic lot-sizing problem, the proposed algorithmic framework may be useful to solve more complex practical production planning problems.

International audience

We consider the design of a charging infrastructure based on fast-charging capacitated stations to enable electric vehicles to carry out long-distance trips. We focus on taking into account the impact of the non-system-optimal drivers' behavior on the station capacity consumption in the modeling of the facility location problem. This leads to the formulation of a bi-level optimization model. In this bi-level program, the upper level represents the station location problem faced by the charging infrastructure provider and the lower level represents the selfish behavior of EV drivers who will seek to use the charging stations opened by the infrastructure provider to carry out their trips with a minimum number of stops. We propose a solution approach based on the reformulation of the bi-level program into a mixed-integer linear program thanks to the use of the primal-dual optimality conditions of linear programming. Our preliminary computational experiments carried out on small instances show the impact on the global system performance of ignoring the selfish drivers' behavior and the potential benefit from using a bi-level programming model.

We consider an uncapacitated 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 assume a stochastic environment, in which the input data of the optimization problem are subject to uncertainty. We consider a multi-stage stochastic integer programming approach relying on scenario trees to represent the uncertain information structure and propose a solution method based on an extension of the stochastic dual dynamic programming algorithm. Our results show that this approach can provide good quality solutions for large-size instances in a reasonable time and significantly outperforms the use of a stand-alone mathematical solver.

International audience

We consider a workforce management problem arising in call centers, namely a staffing and shift-scheduling problem. It consists in determining the minimum-cost number of agents to be assigned to each shift of the scheduling horizon so as to reach the required customer quality of service. We assume that the mean call arrival rate in each period of the horizon is a random variable following a continuous distribution. We model the resulting optimization problem as a stochastic program involving joint probabilistic constraints. This allows to manage the risk of not reaching the required quality of service at the horizon level rather than on a period by period basis. We propose a solution approach based on linear approximations to provide heuristic solutions of the problem. We finally give numerical results carried out on a real-life instance. These results show that the proposed approach compares well with previously published approaches both in terms of risk management and cost minimization.

Best application paper award