Decision, Operations & Information Technologies Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2761
Browse
15 results
Search Results
Item DATA-DRIVEN OPTIMIZATION AND STATISTICAL MODELING TO IMPROVE DECISION MAKING IN LOGISTICS(2019) Sinha Roy, Debdatta; Golden, Bruce; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this dissertation, we develop data-driven optimization and statistical modeling techniques to produce practically applicable and implementable solutions to real-world logistics problems. First, we address a significant and practical problem encountered by utility companies. These companies collect usage data from meters on a regular basis. Each meter has a signal transmitter that is automatically read by a receiver within a specified distance using radio-frequency identification (RFID) technology. The RFID signals are discontinuous, and each meter differs with respect to the specified distance. These factors could lead to missed reads. We use data analytics, optimization, and Bayesian statistics to address the uncertainty. Second, we focus on an important problem experienced by delivery and service companies. These companies send out vehicles to deliver customer products and provide services. For the capacitated vehicle routing problem, we show that reducing route-length variability while generating the routes is an important consideration to minimize the total operating and delivery costs for a company when met with random traffic. Third, we address a real-time decision-making problem experienced in practice. In one application, routing companies participating in competitive bidding might need to respond to a large number of requests regarding route costs in a very short amount of time. In another application, during post-disaster aerial surveillance planning or using drones to deliver emergency medical supplies, route-length estimation would quickly need to assess whether the duration to cover a region of interest would exceed the drone battery life. For the close enough traveling salesman problem, we estimate the route length using information about the instances. Fourth, we address a practical problem encountered by local governments. These organizations carry out road inspections to decide which street segments to repair by recording videos using a camera mounted on a vehicle. The vehicle taking the videos needs to proceed straight or take a left turn to cover an intersection fully. Right turns and U-turns do not capture an intersection fully. We introduce the intersection inspection rural postman problem, a new variant of the rural postman problem involving turns. We develop two integer programming formulations and three heuristics to generate least-cost vehicle routes.Item Algorithms for Online Advertising Portfolio Optimization and Capacitated Mobile Facility Location(2017) Sahin, Mustafa; Raghavan, Subramanian; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this dissertation, we apply large-scale optimization techniques including column generation and heuristic approaches to problems in the domains of online advertising and mobile facility location. First, we study the online advertising portfolio optimization problem (OAPOP) of an advertiser. In the OAPOP, the advertiser has a set of targeting items of interest (in the order of tens of millions for large enterprises) and a daily budget. The objective is to determine how much to bid on each targeting item to maximize the return on investment. We show the OAPOP can be represented by the Multiple Choice Knapsack Problem (MCKP). We propose an efficient column generation (CG) algorithm for the linear programming relaxation of the problem. The computations demonstrate that our CG algorithm significantly outperforms the state-of-the-art linear time algorithm used to solve the MCKP relaxation for the OAPOP. Second, we study the problem faced by the advertiser in online advertising in the presence of bid adjustments. In addition to bids, the advertisers are able to submit bid adjustments for ad query features such as geographical location, time of day, device, and audience. We introduce the Bid Adjustments Problem in Online Advertising (BAPOA) where an advertiser determines base bids and bid adjustments to maximize the return on investment. We develop an efficient algorithm to solve the BAPOA. We perform computational experiments and demonstrate, in the presence of high revenue-per-click variation across features, the revenue benefit of using bid adjustments can exceed 20%. Third, we study the capacitated mobile facility location problem (CMFLP), which is a generalization of the well-known capacitated facility location problem that has applications in supply chain and humanitarian logistics. We provide two integer programming formulations for the CMFLP. The first is on a layered graph, while the second is a set partitioning formulation. We develop a branch-and-price algorithm on the set partitioning formulation. We find that the branch-and-price procedure is particularly effective, when the ratio of the number of clients to the number of facilities is small and the facility capacities are tight. We also develop a local search heuristic and a rounding heuristic for the CMFLP.Item Mathematical Programming Models for Influence Maximization on Social Networks(2016) Zhang, Rui; Raghavan, Subramanian; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.Item Essays on Supply Chain Finance(2016) Zhu, Weiming; Tunca, Tunay; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)I study how a larger party within a supply chain could use its superior knowledge about its partner, who is considered to be financially constrained, to help its partner gain access to cheap finance. In particular, I consider two scenarios: (i) Retailer intermediation in supplier finance and (ii) The Effectiveness of Supplier Buy Back Finance. In the fist chapter, I study how a large buyer could help small suppliers obtain financing for their operations. Especially in developing economies, traditional financing methods can be very costly or unavailable to such suppliers. In order to reduce channel costs, in recent years large buyers started to implement their own financing methods that intermediate between suppliers and financing institutions. In this paper, I analyze the role and efficiency of buyer intermediation in supplier financing. Building a game-theoretical model, I show that buyer intermediated financing can significantly improve supply chain performance. Using data from a large Chinese online retailer and through structural regression estimation based on the theoretical analysis, I demonstrate that buyer intermediation induces lower interest rates and wholesale prices, increases order quantities, and boosts supplier borrowing. The analysis also shows that the retailer systematically overestimates the consumer demand. Based on counterfactual analysis, I predict that the implementation of buyer intermediated financing for the online retailer in 2013 improved channel profits by 18.3%, yielding more than $68M projected savings. In the second chapter, I study a novel buy-back financing scheme employed by large manufacturers in some emerging markets. A large manufacturer can secure financing for its budget-constrained downstream partners by assuming a part of the risk for their inventory by committing to buy back some unsold units. Buy back commitment could help a small downstream party secure a bank loan and further induce a higher order quantity through better allocation of risk in the supply chain. However, such a commitment may undermine the supply chain performance as it imposes extra costs on the supplier incurred by the return of large or costly-to-handle items. I first theoretically analyze the buy-back financing contract employed by a leading Chinese automative manufacturer and some variants of this contracting scheme. In order to measure the effectiveness of buy-back financing contracts, I utilize contract and sales data from the company and structurally estimate the theoretical model. Through counterfactual analysis, I study the efficiency of various buy-back financing schemes and compare them to traditional financing methods. I find that buy-back contract agreements can improve channel efficiency significantly compared to simple contracts with no buy-back, whether the downstream retailer can secure financing on its own or not.Item APPLYING OPERATIONS RESEARCH MODELS TO PROBLEMS IN HEALTH CARE(2015) Price, Stuart Patrick; Golden, Bruce; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Intensity- modulated radiation therapy is a form of cancer treatment that directs high energy x-rays to irradiate a tumor volume. In order to minimize the damage to surround-ing tissue the radiation is delivered from multiple angles. The selection of angles is an NP-hard problem and is currently done manually in most hospitals. We use previously evaluated treatment plans to train a machine learning model to sort potential treatment plans. By sorting potential treatment plans we can find better solutions while only evalu-ating a fifth as many plans. We then construct a genetic algorithm and use our machine learning models to search the space of all potential treatment plans to suggest a potential best plan. Using the genetic algorithm we are able to find plans 2% better on average than the previously best known plans. Proton therapy is a new form of radiation therapy. We simulated a proton therapy treatment center in order to optimize patient throughput and minimize patient wait time. We are able to schedule patients reducing wait times between 20% and 35% depending on patient tardiness and absenteeism. Finally, we analyzed the impact of operations research on the treatment of pros-tate cancer. We reviewed the work that has been published in both operations research and medical journals, seeing how it has impacted policy and doctor recommendations.Item MANAGING INNOVATIONS: INFORMATION AND CONTRACTS(2014) Chen, He; Xu, Yi; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Innovation has been acknowledged by both researchers and practitioners as a vital tool to yield growth and maintain competitive advantages. However, firms face stiff challenges in managing innovations. Developing new product generally requires substantial resource input, but the success rate is usually low due to internal technical difficulties and external market uncertainties. Even with successful innovative products, it is not guaranteed that the innovators will be rewarded for their efforts and investments, as the return from innovations may be siphoned off by suppliers, customers, and competitors. To profit from innovations, firms need to first create value with the right R&D strategies, and further capture value in the execution of innovations when dealing with the relevant partners. This dissertation studies the management of innovations and addresses these two important issues respectively. In the first essay, we investigate how strategically managing information can improve the new product performances in competitive R&D markets. The new product development process is essentially a series of inter-linked information processing activities: firms generate ideas, gather information from external environment to evaluate the feasibility and potential of the ideas, conduct research to create new knowledge and intellectual property, and finally commercialize the new knowledge into the market to generate value. We focus on how firms should acquire and manage external market information in competitive R&D markets, and how the information acquisition and management strategies impact their R&D investment decisions. The second essay studies how firms should manage the relationship with the relevant parties in the execution of innovations. The intrinsic uncertainty in the materialization of innovations, the intangibility of technical knowledge assets, and the difficulty of specifying and monitoring the performance of the other party, are the primary clauses that give rise to the hold-up problem in innovation partnerships -- that is, the R&D investment by a firm leaves it vulnerable to ex post opportunistic behaviors by its contracting partner (whether its supplier, customer, or joint venture partner). We study how the operational aspect of an evolving relationship may influence a firm's innate incentives to take advantage and `hold-up' the partner and mitigate the hold-up problem in innovation partnerships. The third essay extends the discussion of hold-up problem to general incomplete contracts and moral Darwinism. In conventional economic models, rational players are usually assumed to be self-interested and can take opportunistic actions to maximize their own payoffs, while socially desirable traits such as honesty and trust are often characterized as irrational and studied as deviations from tenets of rationality. However, these irrational traits are commonly observed in practice despite the widespread nature of incomplete contracts which have plenty of room for opportunism. This essay asks why traits such as honesty have not been weeded out by economic Darwinism, and offers a justification that the choice of honesty emerges both as desirable and rational under very reasonable conditions.Item The Effect of Behavioral Biases on Supply Chain Decisions(2014) Devlin, Anna; Elmaghraby, Wedad; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Traditional work in operations management has focused on topics such as supply chain contracts and pricing, studying design of efficient contracts and optimal pricing policies. After these optimal solutions and recommendations are derived, they must be implemented properly by managers in practice. Because this process is subject to behavioral decision biases, work in behavioral operations management has begun to connect theories of decision biases to behavior in classical operations management. My dissertation focuses in this area by studying how decisions are made by suppliers and retailers in B2B settings. In essay one, I investigate the effect of effort-dependent demand on supply chain contracts. It is found that the actual cost of effort affects the retailer's optimal level of effort and subsequently determines when a supplier should prefer a wholesale price contract to a buyback contract. As the retailer's cost of effort increases, the retailer's optimal level of effort decreases, leading the supplier to prefer the wholesale price contract. It is verified experimentally that retailer and supplier decisions are driven by cost of retailer effort. Furthermore, I demonstrate that suppliers' contract preferences are influenced by effort cost, not expected profit. In essay two, I look at the link between two supply chain decisions that have previously not been connected before. In this this essay, I study how the contract type (wholesale price or buyback) offered to the retailer affects his decision about which product to stock, particularly when one product is obviously riskier than another. I find, experimentally, that while contract type should make no difference in preferences between a safe and risky product, the retailer displays markedly different preferences arcoss contract type. I propose that this difference in preference structure can be explained by a model that incorporates a Prospect Theory weighting function. Finally, I demonstrate experimentally that this behavioral model of choice explains retailer product choice both when making the isolated product choice decision and the joint product/quantity decision.Item Problems and Models in Strategic Air Traffic Flow Management(2013) Swaroop, Prem; Ball, Michael O; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The thesis comprises of three essays. The first essay is titled "Do more US airports need slot controls? A welfare based approach to determine slot levels." It analyzes the welfare effects of slot controls on major US airports. We consider the fundamental trade-off between benefits from queuing delay reduction and costs due to simultaneous schedule delay increase to passengers while imposing slot limits at airports. A set of quantitative models and simulation procedures are developed to explore the possible airline scheduling responses through reallocating and trimming flights. We find that, of the 35 major US airports, a more widespread use of slot controls would improve travelers' welfare. The results from our analyses suggest that slot caps at the four airports that currently have slot controls (Washington Reagan, Newark, New York LaGuardia, New York John F. Kennedy) are set too high. Further slot reduction by removing some of the flights at these airports could generate additional benefits to passengers. Slot controls can potentially reduce two thirds of the total system delays caused by congestion. A number of implementation and design issues related to the use of slot controls are also discussed in the paper. The second essay is titled "Designing the Noah's Ark: A Multi-objective Multi-stakeholder Consensus Building Method." A significant challenge of effective air traffic flow management (ATFM) is to allow for various competing airlines to collaborate with an air navigation service provider (ANSP) in determining flow management initiatives. This challenge has led over the past 15 years to the development of a broad approach to ATFM known as collaborative decision making (CDM). A set of CDM principles has evolved to guide the development of specific tools that support ATFM resource allocation. However, these principles have not been extended to cover the problem of providing strategic advice to an ANSP in the initial planning stages of traffic management initiatives. In the second essay, we describe a mechanism whereby competing airlines provide ``consensus'' advice to an ANSP using a voting mechanism. It is based on the recently developed Majority Judgment voting procedure. The result of the procedure is a consensus real-valued vector that must satisfy a set of constraints imposed by the weather and traffic conditions of the day in question. While we developed and modeled this problem based on specific ATFM features, it appears to be highly generic and amenable to a much broader set of applications. Our analysis of this problem involves several interesting sub-problems, including a type of column generation process that creates candidate vectors for input to the voting process. The third essay is titled "Strategic Opportunity Analysis in COuNSEL -- A Consensus-Building Mechanism for Setting Service Level Expectations." The consensus-building mechanism described in the second essay has been accepted as a technically viable solution for the stated problem -- although many practical challenges still remain before it may be deployed in operations. A key issue worthy of further investigation is its strong strategy-resistance -- as claimed by the authors of Majority Judgment, the voting procedure embedded in COuNSEL. Using the broad ideas of Nash Equilibria, we characterize the necessary and sufficient conditions for an airline to benefit from unilaterally deviating from truthfully grading one or more candidates. The framework provides the airline with all the other airlines' grades on a set of candidates, and allows it an opportunity to present new grades. The analysis is repeated over multiple instances, and likelihood of beneficial strategic opportunity is presented.Item THE IMPACT OF RESOURCE MANAGEMENT ON HOSPITAL EFFICIENCY AND QUALITY OF CARE(2013) Anderson, David Ryberg; Golden, Bruce L; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Managing scarce resources plays a significant role in hospital operations. Effective use of resources (e.g., operating rooms, specialized doctors, etc.) allows hospitals to efficiently provide high-quality care to patients. In this dissertation, we study how hospitals manage scarce resources to identify systematic ways in which quality of care and efficiency might be improved. We study four different types of hospital resources: post-operative beds, specialist surgeons, resident physicians, and patient information. For each resource type, we show how better utilization could increase the quality of care delivered by the hospital or increase the efficiency of the system. We show that as post-operative bed utilization increases the discharge rate increases as well, meaning that bed shortages impact physician decision making. Further, we show that patients discharged on days with high bed utilization are significantly more likely to be readmitted to the hospital within 72 hours, which implies that poor bed management can lead to worse health outcomes for surgical patients. We also study how quality of care differs between night and day arrival in trauma centers. Based on a large national dataset, we conclude that a lack of specialized resources at hospitals during the off hours leads to significantly worse patient outcomes, including higher mortality and longer lengths of stay. Further, we exploit a natural experiment to determine the impact that residents have on efficiency in an academic emergency department. Using regression analysis, queueing models, and simulation, we find that when residents are present in the emergency department, treatment times are lowered significantly, especially among high severity patients. Finally, we show two novel uses of medical data to predict patient outcomes. We develop models to predict which patients will require an ICU bed after being transferred from outside hospitals to an internal medicine unit, using only five commonly measured medical characteristics of the patient. We also develop a model using MRI data to classify whether or not prostate cancer is present in an image.Item Integrating Social Network Effects in Product Design and Diffusion(2012) Gunnec, Dilek; Raghavan, Subramanian; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Connectivities among people are amplified with recent advancements in internet technology increasing the number of communication channels. Information spread over these networks strengthen the social influence among individuals and affect their purchasing decisions. In this thesis, we study three problems in the product design and diffusion context by integrating such social network effects where influence takes place over neighborhood relationship ties among the users of the product. We consider the setting where peer influence plays a significant role in a consumer's product choice or there is a tangible benefit from using the same product as the rest of one's social network. Building upon the well-known Share-of-Choice problem, we model an influence structure and define the Share-of-Choice problem with Network Effects. It is an NP-Hard combinatorial optimization problem which we solve using a Genetic Algorithm. Using simulated data we show that ignoring social network effects in the design phase of a product results in a significantly lower market share for a product. Our genetic algorithm obtains near-optimal solutions and is very robust in terms of its running time, scalability, and ability to adapt to additional constraints/variations of the model. In this setting, we introduce a product diffusion problem, the Least Cost Influence Problem, which increases the market share of a product by intervening the natural diffusion of it over the social network. This intervention is in the form of incentive supply to a group of people in a least costly way while maximizing the spread of the product. We generalize the Least Cost Influence Problem by moving away from the marketing setting and by treating the previous product as any piece of "information" that can spread over a social network by adoption. We show that this problem is polynomially solvable over tree networks under some conditions. We provide a Dynamic Programming algorithm to solve this problem and show that it can be interpreted as a greedy algorithm that gives incentives starting with the people that are least influenced by their neighbors, albeit the definition of susceptibility to influence from neighbors is updated throughout the algorithm. We introduce a two dimensional influence model and extend our modeling and solution methods for the product line design problem which involves designing multiple products within the same product line with the objective of appealing to the heterogeneous structure of the market. The first dimension of influence is the affection of individuals from using the same product, and the second dimension is the influence of using a similar product from the same product line which has a lower intensity of influence. We reexamine the Least Cost Influence Problem in the product line setting.