OUUTA
Optimization under Uncertainty: Theory and Applications I

Invited Session

Time Slot: Tuesday Afternoon

Room: 001

Chair: Daniele Manerba

Optimal ordering under a low-quality substitute in case of shortage and stochastic lead time

Time: 14:10

Nema Abu Jomaa (Bar-Ilan University, Ramat-Gan 52900, Israel and The International Committee of the Red Cross (ICRC), Geneva, Switzerland ), Kogan Konstantin

Delivery lead time is becoming a key factor which uncertainty significantly affects supply chain performance. Empirical studies in different industries show that stock-out-based substitution is a common way to handle shortages. Notably, during the COVID-19 pandemic, the demand for medical supplies intensely increased, not only because of the fast spread of the infection but also because the related shortages of genuine products contributed to an increase in number of substandard medical products. In this work we consider a finite replenishment cycle in a humanitarian organization where (i) a high-quality material is characterized by a stochastic lead time, (ii) the demand during the replenishment cycle is known but it can be affected by last minute requests. Furthermore, in case of shortage, the high-quality material can be substituted with a low-quality material, but the substitute impacts the demand. Specifically, the demand increases due to the fact that the low-quality product wears out faster than the other product. The formulation involves continuous-time inventory depletion and associated purchase and inventory holding costs. The goal is to order the supplies so that to minimize the total cost of meeting the demand during the replenishment cycle. We formalize the analysis with the aid of a number of scenarios characterizing the cases when there is no need to substitute the high-quality products with the low-quality ones; when there exists a time point such that the high-quality products will be substituted with the low-quality products; and when the high-quality products will be substituted twice over the time horizon. All scenarios account for a last-minute demand. With the aid of these scenarios, we reduce the problem to minimizing a cost function consisting of two convex functions determined along two adjacent order quantity intervals thereby implying not-necessarily convex optimization.

Pickup and delivery requests through a multi-company e-commerce platform

Time: 14:30

Demetrio Laganà (Department of Mechanical, Energy and Management Engineering, University of Calabria), Stoia Sara, Ohlmann Jeffrey W.

Delivery services have been developed within the grocery and restaurant domain such as for non-food items with different platforms but the demand patterns and consumer behavior differ in the case of food and non-food products. A single e-platform serving a wide range of local businesses could provide the volume and smooth the non-stationary demand patterntypical of restaurant delivery.There is an opportunityfor local brick-and-mortar companies to utilize such an e-platform, particularly if pairedwith a high level of customer service (professional shopper consultation, favorable returnpolicy, etc.) to support “shop local” initiatives and stave off a “retail apocalypse.” A primary motivation for local businesses to join an e-platform is to compete with the distribution power of companies like Amazon [Mattioli, June 17 2021], even because theglobal COVID-19 pandemic has altered consumer behavior (perhaps permanently) and local brick-and-mortar stores may need to serve as showrooms (for in-person shopping)and/or dark stores (warehouses), with employees serving as salespeople and/or as order-pickers. Schrotenboeret al. [2021] examine a similar setting motivated by local delivery via bicycle. In our problem we assume that a third-party logistics (3PL) company receives the customer requests stochastically throughout the day and dispatches these requests to available vehicles, using a fleet of dedicatedvehicles and a fleet of crowdsourced vehicles that arrives stochastically during the day by offering a known limited time availability. The incorporation of crowdshippers has implications on sustainability of city logistics by reducing the number of vehicles dedicated to deliveries. In the treatment of our problem, we consider two aspects of the logistical design of a delivery system: cost and service. Our formulation focuses on workforce costs as these represent a major component of operating costs. Along the service dimension, we focus on on-time delivery with particular modeling of time-dependent travel times. To represent the stochastic nature of the arrival of customer requests and of the availability of crowdshippers, we model the problem as a Markov decision process (MDP) over finite, discrete-time horizon and the solution approach is based on an approximate dynamic programming method.

[1] D. Mattioli. Shops join forces against amazon. The Wall Street Journal, June 17 2021.
[2] A. H. Schrotenboer, M. A. Broek, P. Buijs, and M. W. Ulmer. Fighting the e-commercegiants: Efficient routing and effective consolidation for local delivery platforms. arXivpreprint arXiv:2108.12608, 2021.

Bounds for Multistage Mixed-Integer Distributionally Robust Optimization

Time: 14:50

Daniel Faccini (Department of Management, Information and Production Engineering
University of Bergamo), Guzin Bayraksan, Francesca Maggioni University of Bergamo, Ming Yang

Multistage mixed-integer distributionally robust optimization (DRO) forms a class of extremely challenging problems since their size grows exponentially with the number of stages. One way to model the uncertainty in multistage DRO is by creating sets of conditional distributions (the so-called conditional ambiguity sets) on a finite scenario tree and requiring that such distributionsremain close to nominal conditional distributions according to some measureof similarity/distance (e.g., phi-divergences or Wasserstein distance).In this talk, new bounding criteria for this class of difficult decision problems are provided through scenario grouping using the ambiguity sets associated with various commonly used phi-divergences and the Wasserstein distance. Our approach does not require any special problem structure such aslinearity, convexity, stagewise independence, and so forth. Therefore, whilewe focus on multistage mixed-integer DRO, our bounds can be applied to a wide range of DRO problems including two-stage and multistage, with or without integer variables, convex or nonconvex, and nested or non-nested formulations. Numerical results on a multistage mixed-integer production problem show the efficiency of the proposed approach through different choicesof partition strategies, ambiguity sets, and levels of robustness.

A Robust Optimization Approach for Designing Renewable Energy Charging Stations

Time: 15:10

Giovanna Miglionico (Università della Calabria), Beraldi Patrizia, Giallombardo Giovanni

We consider strategic and operational planning decisions arising in managing plug-in electric vehicle (PEV) charging stations. At a strategic level, we face the problems of both defining the optimal configuration of the energy system of a PEV charging station and of setting the optimal retail prices for PEV-charging energy. These decisions depend on the unknown values for the productivity of the renewable resources, for the number of PEV clients and for the wholesale prices. Based on the worst possible outcome for these random variables the PEV owner would like to make the best operational decisions regarding the quantity of supplementary energy to be produced. A similar problem has been considered in [1] where a bilevel robust optimization model is first formulated and then transformed into an equivalent single-level problem to be solved by a column-and-constraint-generation algorithm.We test the PEV charging station robust optimization formulation on a series of instances drawn from the literature.

[1] Bo Zeng, Houqi Dong, Ramteen Sioshansi, Fuquiamg Xu and Ming Zeng, Bilevel Robust Optimization of Electric Vehicle Charging Stations with Distributed Energy Resources. IEEE Transactions on Industry Applications, 56 (5), pp. 5836-5847
[2] Manlio Gaudioso, Giovanni Giallombardo and Giovanna Miglionico, Minimizing Piecewise-Concave Functions Over Polyhedra. MATHEMATICS OF OPERATIONS RESEARCH, 43 (2), pp. 580–597.

Stochastic Programs with extreme behaviors-focused second stages: a Deterministic Equivalent Formulation

Time: 15:30

Daniele Manerba (Università degli Studi di Brescia), Fotio Tiotsop Lohic, Fadda Edoardo, Bierlaire Michel

A closed deterministic form of a two-stage Stochastic Programming (SP) problem is obtainable when the expected optimum of the second-stage problem can be analytically calculated. However, in practice, this is almost always impossible given the complexity of the multidimensional integral of such an expected value. In this work, we consider and formally define a large class of two-stage Stochastic Programs whose second-stage expected optimum is Decomposable into a finite number of expectations of Extreme Values (tsSP-DEV). Typical applications of tsSP-DEVs can be found, e.g., in location-allocation problems under allocation costs uncertainty. In a sense, a tsSP-DEV involves characteristics both from the classical SP paradigm and from the Robust Optimization one. In fact, the tsSP-DEV optimization perspective is still focused in making here-and-now decisions by also evaluating the expected value of an uncertain problem over all the possible future situations, but assuming that such a value can be obtained as a function of extreme future behaviors.We show that a closed-form analytical expression of the expected second-stage optimum of any tsSP-DEV can be derived by exploiting some results coming from the Extreme Value Theory [1], and thus an equivalent deterministic version of the SP problem can be obtained. This can be done under the mild hypothesis that the involved uncertain data follow a Multivariate Extreme Value (MEV) distribution. The MEV family includes many common distributions, and some of them are of practical interest since they enable a modeling of the second-stage problem uncertainty structure through well-known and widely used Discrete Choice Models (e.g., Logit, Nested Logit, Cross-Nested Logit).Finally, a tsSP-DEV special case, named two-stage Stochastic Programs embedding Discrete Choice Problems (tsSP-DCP), is further defined. In a tsSP-DCP, the second stage consists of a sequence of independent Discrete Choice Problems (DCPs), each one triggered or weighted by the value of a specific first-stage variable. In this case, the deterministic equivalent problem results to be linear and thus further properties can be derived. This allows to well-approximate many realistic uncertain MILP problems by solving their deterministic versions [2]. We validate our approach through numerical experiments on common combinatorial optimization SP problems and compare its efficiency and effectiveness with respect to scenario-based paradigms.

[1] D. McFadden (1978). Modelling the choice of residential location. A Karlquist et al., ed., Spatial interaction theory and residential location, 75–96. North-Holland, Amsterdam.
[2] E. Fadda, L. Fotio Tiotsop, D. Manerba, R. Tadei (2020). The stochastic multi-path Traveling Salesman Problem with dependent random travel costs. Transportation Science 54 (5), 1372-1387.