Management Science and Engineering

Permanent URI for this collectionhttps://uwspace.uwaterloo.ca/handle/10012/9910

This is the collection for the University of Waterloo's Department of Management Science and Engineering.

Research outputs are organized by type (eg. Master Thesis, Article, Conference Paper).

Waterloo faculty, students, and staff can contact us or visit the UWSpace guide to learn more about depositing their research.

Browse

Now showing 1 - 12 of 12

Data Driven Efficiency for E-Warehousing: Descriptive and Prescriptive Analytics
(University of Waterloo, 2018-05-18) Ugur, Yildiz; Gzara, Fatma; Elhedhli, Samir
Based on data provided by a warehouse logistics management company, we analyze the warehousing operation and its major processes of order picking and order consolidation. Without access to the actual layouts and process flow diagrams, we analyze the data to describe the processes in detail, and prescribe changes to improve the operation. We investigate the characteristics of the order preparation process and the order consolidation operation. We find that products from different orders are mixed for effective picking. Similar products from different orders are picked together in containers called totes. Full totes are stored in a buffer area, and then routed to a conveyor system where products are sorted. The contents of the totes are then consolidated into orders. This order consolidation process depends on the sequence in which totes are processed and has a huge impact on the order completion time. OCP is a new problem for both the warehouse management system and the parallel machine scheduling literature. We provide mathematical formulations for the problem and devise two solution methods. The first is a simulated annealing metaheuristic, while the second is an exact branch-and-price method. We test the solutions on both random and industry data. Simulated Annealing is found to achieve near optimal solutions within 0.01 % of optimality. For the branch-and-price approach, we use a set partitioning formulation and a column generation method where the subproblems are single machine scheduling problems that are solved using dynamic programming. We also devise a new branching rule and new dynamic programming algorithm to solve the subproblem after branching. To assess the efficiency of the proposed branch-and-price methodology, we compare against the branch-and-price approach of Chen and Powell (1999) for the parallel machine scheduling problem. We take advantage of the fact that OCP is a generalization of the parallel machine scheduling problem. The proposed, more general, branch-and-price approach achieves the same solution quality, but takes more time.
A data-driven optimization approach for mixed-case palletization and three-dimensional bin packing
(University of Waterloo, 2018-01-18) de Carvalho, Paulo R. V.; Elhedhli, Samir
Palletization is the most standard method of packaging and transportation in the retail industry. Their building involves the solution of a three-dimensional packing problem with side practical constraints such as item support and pallet stability, leading to what is known as the mixed-case palletization problem. Motivated by the fact that solving industry-size instances is still very challenging for current methods, we propose a new solution methodology that combines data analysis at the instance level and optimization to build pallets. Item heights are first analyzed to identify possible layers and to derive relationships between item positions. Items are stacked in pairs and trios to create super items, which are then arranged to create layers of even height. The resulting layers are finally stacked to create pallets. The layers are constructed using a reduced-size mixed integer program as well as a two-dimension placement heuristic. Computational tests on industry data show that the solution approach is extremely efficient in producing high-quality solutions in fast computational times.
Data-driven Structure Detection in Optimization: Decomposition, Hub Location, and Brain Connectivity
(University of Waterloo, 2018-07-13) Khaniyev, Taghi; Elhedhli, Samir; Erenay, Fatih Safa
Employing data-driven methods to efficiently solve practical and large optimization problems is a recent trend that focuses on identifying patterns and structures in the problem data to help with its solution. In this thesis, we investigate this approach as an alternative to tackle real life large scale optimization problems which are hard to solve via traditional optimization techniques. We look into three different levels on which data-driven approaches can be used for optimization problems. The first level is the highest level, namely, model structure. Certain classes of mixed-integer programs are known to be efficiently solvable by exploiting special structures embedded in their constraint matrices. One such structure is the bordered block diagonal (BBD) structure that lends itself to Dantzig-Wolfe reformulation (DWR) and branch-and-price. Given a BBD structure for the constraint matrix of a general MIP, several platforms (such as COIN/DIP, SCIP/GCG and SAS/ DECOMP) exist that can perform automatic DWR of the problem and solve the MIP using branch-and-price. The challenge of using branch-and-price as a general-purpose solver, however, lies in the requirement of the knowledge of a structure a priori. We propose a new algorithm to automatically detect BBD structures inherent in a matrix. We start by introducing a new measure of goodness to capture desired features in BBD structures such as minimal border size, block cohesion and granularity of the structure. The main building block of the proposed approach is the modularity-based community detection in lieu of traditional graph/hypergraph partitioning methods to alleviate one major drawback of the existing approaches in the literature: predefining the number of blocks. When tested on MIPLIB instances using the SAS/DECOMP framework, the proposed algorithm was found to identify structures that, on average, lead to significant improvements both in computation time and optimality gap compared to those detected by the state-of-the-art BBD detection techniques in the literature. The second level is problem type where problem-specific patterns/characteristics are to be detected and exploited. We investigate hub location problem (HLP) as an example. HLP models the problem of selecting a subset of nodes within a given network as hubs, which enjoy economies of scale, and allocating the remaining nodes to the selected hubs. The main challenge of using HLP in certain promising domains is the inability of current solution approaches to handle large instances (e.g., networks with more than 1000 nodes). In this work, we explore an important pattern in the optimal hub networks: spatial separability. We show that at the optimal solutions, nodes are typically partitioned into allocation clusters in such a way that convex hulls of these clusters are disjoint. We exploit this pattern and propose a new data-driven approach that uses the insights generated from the solution of a smaller problem - low resolution representation - to find high quality solutions for the large HLPs. The third and the lowest level is the instance level where the instance-specific data is explored for patterns that would help solution of large problem instances. To this end, we open up a new application of HLPs originating from human brain connectivity networks (BCN) by introducing the largest (with 998 nodes) and the first three-dimensional dataset in the literature so far. Experiments reveal that the HLP models can successfully reproduce similar results to those in the medical literature related to hub organisation of the brain. We conclude that with certain customizations and methods that allow tackling very large instances, HLP models can potentially become an important tool to further investigate the intricate nature of hub organisations in human brain.
A Feasible Lagrangian Approach with Application to the Generalized Assignment Problem
(University of Waterloo, 2019-01-28) Punjwani, Shahroz; Gzara, Fatma; Elhedhli, Samir
Lagrangian relaxation is a widely used decomposition approach to solve difficult optimization problems that exhibit special structure. It provides a lower bound on the optimal objective of a minimization problem. On the other hand, an upper bound and quality feasible solutions may be obtained by perturbing solutions of the subproblem. In this thesis, we enhance the Lagrangian approach by using information at the subproblem to push for feasibility to the original problem. We exploit the idea that if the solution for the subproblem is pushed towards feasibility to the original problem, it may lead to improved lower bounds as well as good feasible solutions. Our proposed strategy is to solve the subproblem repeatedly at each iteration of the Lagrangian procedure and strengthen it with valid inequalities. As cuts are added to the subproblem, it inevitably becomes harder to solve. We propose to solve it under a time limit and adjust the Lagrangian bound accordingly. Two variants of the approach are explored that we call a Modified Lagrangian approach and a Feasible Lagrangian approach. We use the Generalized Assignment Problem for testing. We develop two methodologies based on minimal covering inequalities. The first solves the subproblem repeatedly for a given number of iterations and generates minimal cover inequalities that are either discarded or passed on to subsequent Lagrangian iterations. The second starts with initial multipliers and repeatedly solves the subproblem until a feasible solution is attained. At that point, the regular Lagrangian approach is used to find a lower bound. We test on GAP instances from the literature and compare the lower bound to the Lagrangian bound and the feasible solution to the best known solution in the literature. The results demonstrate that the proposed feasible Lagrangian approach leads to improved lower bounds and good quality feasible solutions.
Green Supply Chain Network Design with Emission Sensitive Demand
(University of Waterloo, 2019-04-30) Waltho, Cynthia; Elhedhli, Samir; Gzara, Fatma
Over the last few decades, the argument for a link between greenhouse gas emissions and global warming has become stronger. In response, there has been a global shift. Politicians are implementing carbon policies while consumers are becoming more aware of their own impact on the environment. This thesis explores how environmental policies and consumer awareness impact supply chain network design and provides a new modelling framework in which demand is dependent on carbon footprint. In the first part of the thesis, a comprehensive literature review on green supply chain network design between 2010 and mid 2017 is presented. The review focuses on models and methodologies that explicitly include carbon emissions and environmental policies. It is evident that incorporating carbon policy is popular, particularly carbon cap, carbon offset, cap-and-trade, and carbon tax. By reconfiguring the supply chain and investing in lower-emitting resources, each policy is able to achieve significant emission reduction with marginal increase in total cost. This is achieved by reconfiguring the supply chain and investing in lower-emitting resources. The review finds that there is a lack of models that consider the complex nature of emissions. Other complexities, such as multivariate emissions and uncertainty, are considered in only a few papers. Most importantly, however, it is clear that demand as a function of supply chain emissions is rarely accounted for in supply chain network design literature. In the second part, a two echelon supply chain with emission sensitive demand is considered. A new model is provided that determines at which points investments in lower emitting technologies at the warehouses is necessary. Being nonlinear due to the complex carbon footprint constraint, the resulting model is first reformulated as a second-order cone program, and is tested on a hypothetical e-commerce supply chain. The results illustrate that without proper response to consumer preferences, companies will lose out on revenue. It also illustrates investments are made at clear points as consumer sensitivity to emissions increases, rather than continuously. This work is important for e-commerce companies who wish to set themselves apart from competitors by catering to environmentally conscious consumers. The third part of the thesis presents a new model for green supply chain network design with emission sensitive demand. The supply chain is composed of one plant and multiple warehouses that serve multiple customer zones. Decisions pertaining to the technology type used at the plant, the location and technology of the warehouses, the assignment of customer zones to warehouses, and the flow between the different echelons are modelled. In addition, demand is modelled as a function of carbon footprint. The resulting model is nonlinear due to the carbon footprint constraint. To be able to solve it, we reformulate the problem as a second-order cone program. To test the model and draw insights from it, we build a hypothetical, but realistic potato chip supply chain located in the province of Ontario, Canada. The testing confirms the ability of the model to trade-off between demand and emissions for environmentally conscious customers and provides insight into to how companies could advertise carbon footprint information to capture demand, and their potential impact on the supply chain.
Hierarchical and Nesting Approaches for the Facility Layout Problem
(University of Waterloo, 2018-08-16) Ulch, Daniel; Elhedhli, Samir
The Facility Layout Problem (FLP) seeks to determine the dimensions, coordinates and arrangement of rectangular departments within a given facility. The goal is to minimize the cost of inter-department flow. It has several real-world applications, including the design of manufacturing and warehousing facilities and electronic chips. Despite being studied for several decades, the FLP is still very difficult to solve for facilities with thirty or more departments. Thus, many heuristic approaches have been developed to solve the problem in a reasonable time. One such approach tackles the problem in two stages. In the first, some decision, usually the relative positioning of the departments, is fixed. In the second, an easier restricted problem is solved. This thesis explores hierarchical and nesting approaches for the FLP in an attempt to leverage the fact that smaller instances of the FLP can be solved to optimality relatively quickly. The goal is to find ways in which the FLP can be decomposed into several smaller problems and recombined to form a high-quality solution to the original problem. Hierarchical approaches use clustering or related methods to generate a tree where the leaves are the original departments and the root is the facility. The intermediate nodes are super-departments within an overall layout. A new hierarchical approach for the FLP is presented which performs layouts down this tree in a manner that controls dead-space and generates high-quality solutions. The approach provides solutions competitive with the best-known solutions on benchmark instances from the literature, with up to 8% improvement. The success of the hierarchical approach provided the motivation for a new formulation that nests departments within super-departments. The resulting formulation is even more difficult to solve directly than the original FLP; however, it is suitable for a two-stage solution approach. The first stage determines the assignment of departments to super-departments and the relative positioning of the super-departments. In the second stage, the remainder of the formulation is solved. The approach is found to provide better solutions than the hierarchical approach. Solutions are found with up to 14% improvement over the best-known solutions from the literature.
A Lagrangian Approach for The Airfreight Consolidation Problem Under Pivot-weight
(University of Waterloo, 2018-05-23) Alzaeem, Mohammad Alqssem; Elhedhli, Samir
International airfreight forwarders are faced with the problem of consolidating ship- ments for efficient transportation by airline carriers. The use of standard unit loading devices (ULDs) is a solution adopted by the airfreight industry to speed up cargo loading, increase safety, and protect cargo. We study the airfreight consolidation problem from the forwarders perspective where a decision on the number of ULDs used and the assignment of shipments to ULDs is optimized. The cost of using a ULD consists of a fixed charge and depends on the weight of the cargo it contains. A ULD is charged at an under-pivot rate if the total weight is below a threshold limit, called the pivot-weight. Additional weight is charged at the over-pivot rate. We propose a solution methodology based on Lagrangian relaxation that is capable of providing high quality solutions in reasonable computational times. Besides, a high-quality lower bound, we propose three heuristics to generate feasible solutions, all based on the solution of the subproblems. The first, takes the solution of one of the subproblems and solves a restricted version of the original problem (LagHeur). The other two heuristics are a heuristic based on solving two knapsack problems (2knap) and a best-fit greedy heuristic (bestfit). Problems with up to 100 ULDs and 1000 shipments are solved to within an average of 1%, 2%, 2% of optimality in less than 51.05s, 50.57s and 589.16s by bestfit, 2knap and LagHeur, respectively.
Models and Solution Methods for the Pallet Loading Problem
(University of Waterloo, 2018-05-07) Yildiz, Burak Can; Elhedhli, Samir; Gzara, Fatma
The three-dimensional bin packing problem (3DBPP) seeks to find the minimum number of bins to pack a finite number of rectangular boxes. It has a wide array of applications, ranging from airline cargo transportation to warehousing. Its practical extension, the distributor's pallet loading problem (DPLP), requires the pallets to be stable, packable, and adhering to several industry requirements such as packing sequences and weight limits. Despite being studied extensively in the optimization literature, the 3DBPP is still one of the most difficult problems to solve. Currently, medium to large size instances are only solved heuristically and remain out of reach of exact methods. This also applies to the DPLP, as the addition of practical constraints further complicates the proposed models. A recent survey identified the scarcity of exact solution methods that are capable of handling practical versions of the problem and the lack of a realistic benchmark data set as major research gaps. In this thesis, firstly, we propose a novel formulation and an exact solution approach based on column generation for the 3DBPP, where the pricing subproblem is a two-dimensional layer generation problem. Layers are highly desirable in practical packings as they are easily packable and can accommodate important practical constraints such as item support, family groupings, isle friendliness, and load bearing. Being key to the success of the column generation approach, the pricing subproblem is solved optimally as well as heuristically, and is enhanced using item grouping, item replacement, layer reorganization, and layer spacing. We also embed the column generation approach within a branch-and-price framework. We conduct extensive computational experiments and compare against existing approaches. The proposed approach outperforms the best performing algorithm in the literature \boldred{in most instances} and succeeds to solve practical size instances in very reasonable computational times. Secondly, we extend the column generation scheme to incorporate practical constraints set by the warehousing industry. We introduce a nonlinear layer spacing model to improve the stability of the planned pallets, which we then reformulate as an SOCP. In order to calculate the weight distribution within pallets, we introduce a new graph representation for placed items. Finally, we propose construction and improvement heuristics to tackle each practical constraint, such as vertical support, different item shapes, planogram sequencing, load bearing, and weight limits. We conduct extensive computational experiments to demonstrate the good performance of the proposed methodology, and provide results for future benchmarking. To the best of our knowledge, this is the first approach to fully solve the DPLP. Computational experiments show that the proposed approach succeeds in solving industry size instances in record computational times and achieves high quality solutions that account for all practical constraints. Finally, we propose realistic benchmark instances by designing and training an instance generator using industry data. We apply clustering and curve fitting techniques to 342 industry instances with 166,406 items to obtain the distributions for item volumes, dimensions, and frequencies. We separate the instances into several classes and categories using $k$-clustering and generate multiple instances with different sizes. We, then, extend the generator to incorporate practical features such as weight, load capacity, shape, planogram sequencing, and reduced edge support.
Optimal Order Batching for Automated Warehouse Picking
(University of Waterloo, 2023-09-18) Kucuksari, Zeynep; Elhedhli, Samir
With the unexpected increase in demand and the need to minimize human interaction during the Covid-19 pandemic, companies have been forced to accelerate the transition from traditional to robotic mobile fulfillment systems. The key to a successful warehouse management system, whether traditional or automated, is an efficient order-picking process. In this study, we focus on the order batching problem, where items and orders are grouped into batches for simultaneous picking in automated warehouses that use autonomous picking carts. We propose five different mathematical models, including a generalized quadratic assignment model. We focus on the latter as it provides the best results and propose a Lagrangian relaxation to obtain lower bounds and an iterative Simulated Annealing (SA) algorithm that generates an initial solution using a K-means clustering algorithm. We carry out testing using an open-source dataset to assess the iterative SA algorithm in minimizing congestion and travel distance in an automated warehouse. We find that it finds solutions of good quality as measured by Lagrangian relaxation and is capable of solving large realistic instances. The solutions successfully minimize travel distance and reduce congestion by limiting path intersections.
PPE Distribution Planning and Capacity Acquisition During the COVID-19 Pandemic
(University of Waterloo, 2021-09-27) Kiss, Jordan; Elhedhli, Samir
The COVID-19 pandemic caused disruptions to global supply chains and the uncer- tainty surrounding its progression has created challenges in distributing critical supplies such as personal protective equipment (PPE). We consider the problem of distributing PPE during the COVID-19 pandemic by acquiring distribution and storage capacity from independent carriers for timely and efficiently delivery to health regions. First, a priority- based distribution model is presented that prioritizes health regions by pandemic sever- ity where priorities are based on COVID-19 case counts. Then, we propose a two-stage stochastic model with recourse to examine PPE distribution with uncertain demand. In the first stage, capacity acquisition decisions are made along with an initial distribution plan. Once the pandemic severity unveils, changes to the distribution plan are made in the second stage. The stochastic model is solved using Benders decomposition and approxi- mated using sample average approximation. Benders decomposition and sample average approximation produce similar results with an optimality gap of less than 1%. Benders decomposition requires about 20 minutes to solve, while sample average approximation requires almost an hour. We test on the Ontario health regions network and use the On- tario healthcare worker and COVID-19 data to predict future PPE demand using 1024 scenarios. Comparing the results with actual COVID-19 realizations, we found that the stochastic model provides sufficient PPE to satisfy demand at all regions. Furthermore, only minimum supply is rerouted in the second stage and existing inventory is used to satisfy demand increases where possible. When supply is more spread out amongst the regions, the proportion of demand received at high-priority regions is more balanced, and in the event of supply disturbances, distribution centres are used to stockpile PPE for time periods with low supply.
Strategic Blockchain Adoption in Supply Chain Operations
(University of Waterloo, 2021-12-17) de Carvalho, Paulo R. V.; Elhedhli, Samir; Naoum-Sawaya, Joe
Supply chains have often benefited from breakthroughs in information technology. Most recently, blockchain is promising to revolutionize the way supply chains are designed and operated. In this thesis, we explore blockchain adoptions in three supply chain settings. First, we optimize blockchain deployment at the supply chain network design stage and propose a mixed-integer quadratic programming model for it. Based on a case study from the fresh flowers supply chain, we find that significant cost savings could be achieved from the strategic deployment of blockchain throughout the supply chain as opposed to full blockchain adoption, which translates to lower market prices to consumers, increased demand, better product quality products, and higher profits. In the second, we investigate the potential of blockchain adoption to deter counterfeiters. We present a game-theoretic model that uses blockchain technology to increase the capability of detecting deceptive counterfeits. We find that blockchain is not always financially viable for manufacturers to discourage counterfeiting and it becomes less attractive for premium and luxury products. Our framework also demonstrates that manufacturers can strategically balance product quality and blockchain investment to combat counterfeiting. Last, we explore the potential of blockchain to accurately track carbon emissions. We study a competitive supplier selection problem with one manufacturer and two suppliers and investigate the use of financial incentives to encourage suppliers to adopt greener technologies. The game-theoretic framework is modelled as a bi-level optimization problem. We find that financial incentives are effective in fostering greener components from the suppliers and that blockchain offers suppliers the flexibility to explore emission reductions either by better reporting or technological upgrades.
Supply Chain Network Design with Concave Costs: Theory and Applications
(University of Waterloo, 2016-01-13) Saif, Ahmed; Elhedhli, Samir
Many practical decision models can be formulated as concave minimization problems. Supply chain network design problems (SCNDP) that explicitly account for economies-of-scale and/or risk pooling often lead to mathematical problems with a concave objective and linear constraints. In this thesis, we propose new solution approaches for this class of problems and use them to tackle new applications. In the first part of the thesis, we propose two new solution methods for an important class of mixed integer concave minimization problems over a polytope that appear frequently in SCNDP. The first is a Lagrangian decomposition approach that enables a tight bound and a high quality solution to be obtained in a single iteration by providing a closed-form expression for the best Lagrangian multipliers. The Lagrangian approach is then embedded within a branch-and-bound framework. Extensive numerical testing, including implementation on three SCNDP from the literature, demonstrates the validity and efficiency of the proposed approach. The second method is a Benders approach that is particularly effective when the number of concave terms is small. The concave terms are isolated in a low dimensional master problem that can be efficiently solved through enumeration. The subproblem is a linear program that is solved to provide a Benders cut. Branch-and-bound is then used to restore integrality if necessary. The Benders approach is tested and benchmarked against commercial solvers and is found to outperform them in many cases. In the second part, we formulate and solve the problem of designing a supply chain for chilled and frozen products. The cold supply chain design problem is formulated as a mixed-integer concave minimization problem with dual objectives of minimizing the total cost, including capacity, transportation, and inventory costs, and minimizing the global warming impact that includes, in addition to the carbon emissions from energy usage, the leakage of high global-warming-potential refrigerant gases. Demand is modeled as a general distribution, whereas inventory is assumed managed using a known policy but without explicit formulas for the inventory cost and maximum level functions. The Lagrangian approach proposed in the first part is combined with a simulation-optimization approach to tackle the problem. An important advantage of this approach is that it can be used with different demand distributions and inventory policies under mild conditions. The solution approach is verified through extensive numerical testing on two realistic case studies from different industries, and some managerial insights are drawn. In the third part, we propose a new mathematical model and a solution approach for the SCNDP faced by a medical sterilization service provider serving a network of hospitals. The sterilization network design problem is formulated as a mixed-integer concave minimization program that incorporates economies of scale and service level requirements under stochastic demand conditions, with the objective of minimizing long-run capacity, transportation, and inventory holding costs. To solve the problem, the resulting formulation is transformed into a mixed-integer second-order cone programming problem with a piecewise-linearized cost function. Based on a realistic case study, the proposed approach was found to reach high quality solutions efficiently. The results reveal that significant cost savings can be achieved by consolidating sterilization services as opposed to decentralization due to better utilization of resources, economies of scale, and risk pooling.

Browse

Browsing Management Science and Engineering by Author "Elhedhli, Samir"