Applications of OR V

Contributed Session

Time Slot: Friday Morning

Room: 001

Chair: Roberto Roberti

Demand Forecasting Methods: A Case Study in the Italian Processed Meat Industry

Time: 9:00

Mirko Mucciarini (Marco Biagi Foundation, University of Modena and Reggio Emilia, Largo Marco Biagi 10, 41121 Modena, Italy), Caselli Giulia, Iori Manuel, Lippi Marco

Demand forecasting is acquiring more and more importance in the fast-changing business world, where market instability and economic shocks such as Covid-19 pandemic require firms to be both efficient and flexible. This work is based on a research project aiming at the development of a demand forecasting model for a company that operates in the Italian processed meat segment. The purpose is to obtain a forecast as accurate as possible and then use it at a later stage to carry out an optimal production scheduling (see, e.g., [1], [2]). Especially in the food sector, a proper integration of forecast and production management is essential, because the perishable nature of the items does not allow for over production. In this work, we compared different Machine Learning forecasting algorithms, including Linear Regressor, Random Forest Regressor, Support Vector Regressor and Multi- layer Perceptron Regressor. We compared these methods with the ones used in the literature to define a baseline, like random walk and seasonal mean. Extensive computational tests on a two-year real-world data series prove the effectiveness of the algorithms, especially the Support Vector Regressor, in providing an accurate forecast. The resulting model is now used by the company on a daily basis.Acknowledgements: We thank Inalca S.p.A. for financial support.

[1] W. Wong, Z. Guo, A hybrid intelligent model for medium-term sales forecasting in fashion retail supply chains using extreme learning machine and harmony search algorithm, International Journal of Production Economis 128(2) (2010) 614–624.
[2] G. Tsoumakas, A survey of machine learning techniques for food sales prediction, Artificial Intelligence Review, 52(1), (2019) 441-447.

A new efficient heuristic for the Automatic Scene Detection Problem

Time: 9:20

Roberto Ronco (Department of Informatics, Bioengineering, Robotics and System Engineering (DIBRIS), University of Genoa), Catanzaro Daniele,Pesenti Raffaele

Nowadays, the automatic extraction of semantic and metadata information from video content has become essential in tackling the huge amount of audio and visual data that are produced every day. The several applications of this task range from video management and advertising insertions to automatic audio description and fast video browsing. As a result, its automation constitutes a compelling matter for video industry and consumers as well. The Automatic Scene Detection Problem (ASDP), first introduced in the literature of video processing in [1], is a combinatorial optimization problem that consists in segmenting a set of shots, each constituted by a sequence of frames ideally taken from the same viewpoint, into semantically consistent scenes, by optimizing a measure of similarity between shots. We specifically consider the ASDP variant introduced in [2], that is nontrivial for a generic number of scenes, and deciding its complexity is still an open question. We present an approximate solution algorithm [3] able to outperform the previous state-of-the-art one [2] both in terms of speed and quality of the solution. We also provide a complete characterization of the computational complexity of the two algorithms, by laying out fundamental concepts on the combinatorics of the ASDP.

[1] Daniel Rotman, Dror Porat, and Gal Ashour. Robust and efficient video scene detection using optimal sequential grouping. In Proceedings of the 2016 IEEE International Symposium on Multimedia (ISM), pages 275–280, 2016.
[2] Daniel Rotman, Dror Porat, Gal Ashour, and Udi Barzelay. Optimally grouped deep features using normalized cost for video scene detection. In Proceedings of the 2018 ACM on International Conference on Multimedia Retrieval, pages 187–195, 2018.
[3] Daniele Catanzaro, Raffaele Pesenti, and Roberto Ronco. A new fast and accurate heuristic for the automatic scene detection problem. Computers and Operations Research, 136:105495, 2021.

A unified approach to data envelopment analysis models

Time: 9:40

Maria Trnovska (Faculty of Mathematics, Physics and Informatics, Comenius University in Bratislava), Halicka Margareta

Data envelopment analysis (DEA) defines a variety of models to assess the performance of decision-making units. The models take form of mathematical programming problemsthat link together an efficiency measure and a given technology set in the input-output space. DEA defines two basic classes of models. The models in the first classassume proportional change of inputs and outputs and search for the benchmark by following a parametric path. The models in the second class allow individual change of eachinput and output component and integrate the input excesses and output shortfalls into an overall efficiency measure. We analyze properties of models in each of the two classes by means of a unified framework and offer a generalized dual (multiplier) form of models in each class.

Capacitated Disassembly Lot-Sizing Problem with Disposal Decisions for Multiple Product Types with Parts Commonality

Time: 10:00

Lionel Amodeo (ICD-LOSI, University of Technology of Troyes (UTT)), Meisam Pour-Massahian-Tafti, Godichaud Matthieu

This paper addresses capacitated disassembly lot sizing problem for multiproduct structure with parts commonality. Disposal decisions are considered to manage the accumulation of unnecessary items obtained after disassembly operations during the planning horizon. A new mixed-integer programming (MIP) model is given to formulate the problem. Exact method by using CPLEX solver can be applied to obtain optimal solutions for the small-sized problem. A fix-and-optimize heuristic is proposed for larger sizes of the problem, it solves successively a series of subproblems. In each sub-problem, a subset of variables are fixed while the remaining are optimized using an exact method. Computational tests are performed on a number of randomly generated instances and the results demonstrate the performance of the proposed model and methods.

Anticipatory Time Window Assignment for Next-Day Service Routing

Time: 10:20

Roberto Roberti (Department of Information Engineering – University of Padova), Paradiso Rosario, Ulmer Marlin

In many home delivery services, customers must be present when the Logistics Service Provider (LSP) arrives and operates. This type of service is known as Attended Home Delivery (AHD) services. Examples of AHD are the delivery of large, valuable, or perishable items, technician services for installment, repair, maintenance, or meter reading, and several healthcare applications. In most AHD applications, customers are not entitled to select the time at which the service takes place, but a service time window is assigned to the customer by the LSP. From an operational viewpoint, whenever a new customer requests service, the LSP must decide whether the request should be accepted or rejected and, if accepted, on which day and within which time window to serve the customer. If a time window is offered, then all accepted requests must be served within the corresponding offered time windows. Yet, to guarantee efficient operations, the LSP should assign the time windows to the customers to serve as many customers as possible while maintaining flexibility for future unknown requests.The dynamic assignment of time windows to customers poses several optimization challenges, such as how many drivers sho
uld be scheduled per day? On which day (if any) should a new customer be served? Which time window should be offered to a customer on that day? In this talk, we address this last question. In particular, throughout a capture phase (“today”), customers request service within a fulfillment phase (“tomorrow”). Each customer is either assigned a time window from a predefined set (9-10 a.m., 10-11 a.m., 11-12 a.m., …) or the customer is postponed to another day (outside of the scope of this work). A time window can only be assigned if a vehicle routing plan that serves the new customer and the previous customers within their respective time windows can be found. The goal is to maximize the number of customers that can be served in the fulfillment phase.The problem we address can be formulated as a stochastic dynamic decision problem. However, finding an optimal policy is a challenging task for two main reasons. First, in every state, checking the feasibility of offering a time window to the new customer calls for solving a Vehicle Routing Problem with Time Windows (VRPTW), which is NP-hard. Second, evaluating the impact of offering a (feasible) time window at a given state requires the anticipation of future customers and future time-window decisions, on which only limited stochastic information is known. We propose a solution method that addresses these two issues by (a) checking the feasibility of a time window with an exact solution method and (b) assessing the quality of a decision (i.e., offering a given time window) at a given state through Bellman equations of immediate reward (1 or 0) and an approximation of the expected future reward (value). In particular, the future reward is approximated by generating a set of scenarios, each corresponding to a team-orienteering problem (TOP) with multiple time windows and mandatory customers. We approximate the reward of each TOP by deriving fast upper bounds provided by the linear relaxation of a set packing formulation solved via column generation.We test our algorithm on artificial data and real-life data from Iowa city. The results show that our method increases the number of customers served significantly compared to a rolling horizon approach without anticipation. Our algorithm can also provide solutions that, on average, serve 90% of the customers when compared to an ex-post upper on the static counterpart of the problem.