A multiobjective model for locating undesirable facilities

In this paper, we develop a multiobjective model to depict the tradeoffs involved when locating one or more undesirable facilities to service a region. We assume that the region requires a certain capacity of service, and that this capacity can be met by building a combination of different-sized facilities. Examples could include sanitary landfills, incinerators, and power-generating stations. Our objectives are to minimize the total cost of the facilities located, the total opposition to the facilities, and the maximum disutility imposed on any individual. Opposition and disutility are assumed to be nonlinearly decreasing functions of distance, and increasing functions of facility size. We formulate our model as a multiobjective mixed-integer program, and generate the set of efficient solutions using an enumeration algorithm. Our code can solve realistically sized problems on a microcomputer. We give an example to illustrate the tradeoffs between the three objectives, which are inevitable in such a location problem.This research was supported by the Natural Sciences and Engineering Research Council (NSERC) of Canada (OGP 25481), and by the Nova Fellowship of the Faculty of Business, University of Alberta.     

Optimizing pricing and location decisions for competitive service facilities charging uniform price

In this paper, we present the problem of optimizing the location and pricing for a set of new service facilities entering a competitive marketplace. We assume that the new facilities must charge the same (uniform) price and the objective is to optimize the overall profit for the new facilities. Demand for service is assumed to be concentrated at discrete demand points (customer markets); customers in each market patronize the facility providing the highest utility. Customer demand function is assumed to be elastic; the demand is affected by the price, facility attractiveness, and the travel cost for the highest-utility facility. We provide both structural and algorithmic results, as well as some managerial insights for this problem. We show that the optimal price can be selected from a certain finite set of values that can be computed in advance; this fact is used to develop an efficient mathematical programming formulation for our model.     

Branch and price for the vehicle routing problem with discrete split deliveries and time windows

The Discrete Split Delivery Vehicle Routing Problem with Time Windows (DSDVRPTW) consists of designing the optimal set of routes to serve, at least cost, a given set of customers while respecting constraints on vehicles’ capacity and customer time windows. Each customer can be visited by more than one vehicle since each customer’s demand, discretized in items, can be split in orders, i.e., feasible combinations of items. In this work, we model the DSDVRPTW assuming that all feasible orders are known in advance. Remarkably, service time at customer’s location depends on the delivered combination of items, which is a modeling feature rarely found in literature. We present a flow-based mixed integer program for the DSDVRPTW, we reformulate it via Dantzig-Wolfe and we apply column generation. The proposed branch-and-price algorithm largely outperforms a commercial solver, as shown by computational experiments on Solomon-based instances. A comparison in terms of complexity between constant service time vs delivery-dependent service time is presented and potential savings are discussed.     

Option contracts: a solution for overloading problems in the delivery service supply chain

Owing to the limited service capacity of express delivery providers, most online retailers have to reject many orders during hot selling seasons. In this paper, we consider an express delivery service supply chain consisting of an express delivery provider and an online retailer whereby the selling season includes both regular periods and online sales periods. Utilizing a modified newsvendor model, we derive the express delivery provider’s optimal capacity decision and find that the overloading problem cannot be avoided because delivery service cannot be inventoried. To solve such a problem, we introduce an option contract to coordinate the supply chain. By allowing the online retailer to book the capacity, the express delivery provider can rent capacity from a third party in advance. Results show this approach can mitigate the problem significantly. We also extend our model to a supply chain consisting of a delivery provider and two retailers.     

基于选址效益的联合覆盖模型研究

传统的覆盖模型含有“全有全无”和“单一覆盖”两个假设,即假设需求点在设施的服务半径内才被覆盖,否则不被覆盖;需求点只能被最近的设施覆盖。这两条假设在实际应用中均存在不合理之处。松弛了这两条假设,研究逐渐覆盖和联合覆盖。在保证每个需求点都享受到最低服务水平的情况下,提出了选址效益最大化的联合覆盖模型。由于目标函数中含有分式,通过引入辅助变量的方法,将含有分式目标函数的非线性规划转化成等价的线性规划。最后,通过数值算例分析了最低服务水平限制对最佳选址方案的影响,并得到选址成本、总服务水平和单位成本服务水平随最低服务水平限制的变化,同时对影响模型的重要参数做了敏感性分析。     

全渠道服务商在线上自助服务技术背景下的定价策略研究

在线上自助服务技术兴起的背景下,研究餐饮业服务商整合全渠道的定价策略。分析归纳了三种提供服务的渠道(线下取号排队、线上取号排队、线上预定);利用排队论以及依据消费者效用对服务系统进行理论建模,并结合数值分析,为服务商如何应对不同的消费者与市场环境指明了方向。研究发现:(1)给出了三种服务渠道的最优定价模型表示,并结合市场情况分析不同的定价策略,如在服务高峰期可以采取歧视定价策略;(2)指明了线上取号与线上预定两种渠道不宜同时提供,并给出了最优的线上预定的预留容量比例,对商家设计渠道具有指导意义;(3)发现了不管线下消费者比例如何,服务商营收曲线必定经过同一点,对服务商采取措施引流具有启发意义。本文对服务商全渠道理论建模具有启发意义。     

An optimization based approach for deployment of roadway incident response vehicles with reliability constraints

In recent years transportation agencies have introduced patrol based response programs to remove roadway incidents rapidly. With the evolution of technology incident detection and notification from remote traffic operation centers is possible and patrols to detect incidents are not necessary. Instead, the response units can be placed at various depots in urban areas and dispatched to incident sites upon notification. In this paper, we propose a reliability based mixed integer programming model to find best locations of incidence response depots and assign response vehicles to these depots so that incidents can be cleared efficiently at a minimum cost. The approach is unique as it considers fixed and variable costs of vehicles and depots, occurrences of major and minor incidents, and reliability of response service in the same model. Numerical results are generated for an example problem and sensitivity analysis is conducted to explore the relationships between parameters of the problem.     

Methods for solving nonlinear equations used in evaluating emergency vehicle busy probabilities

In this paper we present two iterative methods for solving a model to evaluate busy probabilities for Emergency Medical Service (EMS) vehicles. The model considers location dependent service times and is an alternative to the mean service calibration method; a procedure, used with the Hypercube Model, to accommodate travel times and location-dependent service times. We use monotonicity arguments to prove that one iterative method always converges to a solution. A large computational experiment suggests that both methods work satisfactorily in EMS systems with low ambulance busy probabilities and the method that always converges to a solution performs significantly better in EMS systems with high busy probabilities.     

Inventory control for point-of-use locations in hospitals

Most inventory management systems at hospital departments are characterised by lost sales, periodic reviews with short lead times, and limited storage capacity. We develop two types of exact models that deal with all these characteristics. In a capacity model, the service level is maximised subject to a capacity restriction, and in a service model the required capacity is minimised subject to a service level restriction. We also formulate approximation models applicable for any lost-sales inventory system (cost objective, no lead time restrictions etc). For the capacity model, we develop a simple inventory rule to set the reorder levels and order quantities. Numerical results for this inventory rule show an average deviation of 1% from the optimal service levels. We also embed the single-item models in a multi-item system. Furthermore, we compare the performance of fixed order size replenishment policies and (R,?s,?S) policies.     

Incorporating congestion in preventive healthcare facility network design

Preventive healthcare aims at reducing the likelihood and severity of potentially life-threatening illnesses by protection and early detection. The level of participation to preventive healthcare programs is a crucial factor in terms of their effectiveness and efficiency. This paper provides a methodology for designing a network of preventive healthcare facilities so as to maximize participation. The number of facilities to be established and the location of each facility are the main determinants of the configuration of a healthcare facility network. We use the total (travel, waiting and service) time required for receiving the preventive service as a proxy for accessibility of a healthcare facility, and assume that each client would seek the services of the facility with minimum expected total time. At each facility, which we model as an M/M/1 queue so as to capture the level of congestion, the expected number of participants from each population zone decreases with the expected total time. In order to ensure service quality, the facilities cannot be operated unless their level of activity exceeds a minimum workload requirement. The arising mathematical formulation is highly nonlinear, and hence we provide a heuristic solution framework for this problem. Four heuristics are compared in terms of accuracy and computational requirements. The most efficient heuristic is utilized in solving a real life problem that involves the breast cancer screening center network in Montreal. In the context of this case, we found out that centralizing the total system capacity at the locations preferred by clients is a more effective strategy than decentralization by the use of a larger number of smaller facilities. We also show that the proposed methodology can be used in making the investment trade-off between expanding the total system capacity and changing the behavior of potential clients toward preventive healthcare programs by advertisement and education.     

Capacity planning in networks of queues with manufacturing applications

This paper addresses capacity planning in systems that can be modeled as a network of queues. More specifically, we present an optimization model and solution methods for the minimum cost selection of capacity at each node in the network such that a set of system performance constraints is satisfied. Capacity is controlled through the mean service rate at each node. To illustrate the approach and how queueing theory can be used to measure system performance, we discuss a manufacturing model that includes upper limits on product throughput times and work-in-process in the system. Methods for solving capacity planning problems with continuous and discrete capacity options are discussed. We focus primarily on the discrete case with a concave cost function, allowing fixed charges and costs exhibiting economies of scale with respect to capacity to be handled.     

Capacity allocation for demand of different customer-product-combinations with cancellations, no-shows, and overbooking when there is a sequential delivery of service

We consider a problem where different classes of customers can book different types of services in advance and the service company has to respond immediately to the booking request confirming or rejecting it. Due to the possibility of cancellations before the day of service, or no-shows at the day of service, overbooking the given capacity is a viable decision. The objective of the service company is to maximize profit made of class-type specific revenues, refunds for cancellations or no-shows as well as the cost of overtime. For the calculation of the latter, information of the underlying appointment schedule is required. Throughout the paper we will relate the problem to capacity allocation in radiology services. Drawing upon ideas from revenue management, overbooking, and appointment scheduling we model the problem as a Markov decision process in discrete time which due to proper aggregation can be optimally solved with an iterative stochastic dynamic programming approach. In an experimental study we successfully apply the approach to a real world problem with data from the radiology department of a hospital. Furthermore, we compare the optimal policy to four heuristic policies, of whom one is currently in use. We can show that the optimal policy significantly improves the currently used policy and that a nested booking limit type policy closely approximates the optimal policy and is thus recommended for use in practice.     

A stochastic service network model with application to hospital facilities

This paper presents a methodology for estimating expected utilization and service level for a class of capacity constrained service network facilities operating in a stochastic environment. A semi-Markov process describes the flows of customers (patients) through a network of service units. We model the case where one of the units has finite capacity and no queues are allowed to form. We show that the expected level of utilization and service can be computed from a simple linear relationship based on (a) the equilibrium arrival rates at each unit which are associated with the case of infinite capacity, (b) mean holding times for each unit, and (c) the probability that the finite capacity unit is at full capacity. We use Erlang's loss formula to calculate the probability of full capacity, show this calculation to be exact for two cases, and recommend its use as an approximation in the general case. We test the accuracy of the approximation on a set of published data. In the discussion, we present a technique for analyzing collected patient flow data using the results of this methodology.     

应急物资预置问题的可信性优化模型

基于可信性理论,研究了多受灾点、多出救点、多物资的应急设备选址和物资预置问题.考虑到运输费用、出救点的供应量、受灾点的需求量和道路容量的不确定性,用模糊变量来刻画,建立了模糊环境下应急物资预置的可信性优化模型以最小化期望总费用.当模型中的模糊变量相互独立且服从三角分布时,推导了总费用目标及服务质量和弧容量约束的解析表达式,从而将原模型转化为等价的确定模型.鉴于等价模型是一个混合整数规划,可采用Lingo软件编程求解.最后,数值算例演示所提建模思想.实验结果说明了所建模型的有效性.     

An analysis of p-median location problem: Effects of backup service level and demand assignment policy

Any solution to facility location problems will consider determining the best suitable locations with respect to certain criteria. Among different types of location problems, involving emergency service system (ESSs) are one of the most widely studied in the literature, and solutions to these problems will mostly aim to minimize the mean response time to demands. In practice, however, a demand may not be served from its nearest facility if that facility is engaged in serving other demands. This makes it a requirement to assign backup services so as to improve response time and service quality. The level of backup service is a key, strategic-level planning factor, and must be taken into consideration carefully. Moreover, in emergency service operations conducted in congested demand regions, demand assignment policy is another important factor that affects the system performance. Models failing to adopt sufficient levels of backup service and realistic demand assignment policies may significantly deteriorate the system performance.Considering the classic p-median problem (pMP) location model, this paper investigates the effects of backup service level, demand assignment policy, demand density, and number of facilities and their locations on the solution performance in terms of multiple metrics. For this purpose, we adopt a combined optimization and simulation approach. We will first modify the classic pMP to account for distances to backup services. Next, we employ a discrete event simulation to evaluate the performance of location schemes obtained from the deterministic mathematical model. Our results provide insights for decision-makers while planning ESS operations.     

Telecommunication Network Capacity Design for Uncertain Demand

The expansion of telecommunication services has increased the number of users sharing network resources. When a given service is highly demanded, some demands may be unmet due to the limited capacity of the network links. Moreover, for such demands, telecommunication operators should pay penalty costs. To avoid rejecting demands, we can install more capacities in the existing network. In this paper we report experiments on the network capacity design for uncertain demand in telecommunication networks with integer link capacities. We use Poisson demands with bandwidths given by normal or log-normal distribution functions. The expectation function is evaluated using a predetermined set of realizations of the random parameter. We model this problem as a two-stage mixed integer program, which is solved using a stochastic subgradient procedure, the Barahona's volume approach and the Benders decomposition.     

Prepositioning supplies in preparation for disasters

In this paper, we examine the decision of where to preposition supplies in preparation for a disaster, such as a hurricane or terrorist attack, and how much to preposition at a location. If supplies are located closer to the disaster, it can allow for faster delivery of supplies after the disaster. As a result of being closer, though, the supplies may be in a risky location if the disaster occurs. Considering these risks, we derive equations for determining the optimal stocking quantity and the total expected costs associated with delivering to a demand point from a supply point. We provide a sensitivity analysis to show how different parameters impact stocking levels and costs. We show how our cost model can be used to select the single best supply point location from a discrete set of choices and how it can be embedded within existing location algorithms to choose multiple supply points. Our computational experiments involve a variety of relationships between distance and risk and show how these can impact location decisions and stocking levels.     

需求导向的容量设施竞争选址问题研究

客户意愿与容量限制是竞争设施选址问题中两个重要的影响因素,在考虑客户意愿与设施容量共同作用条件下,建立了最小化企业总成本以及每个客户费用为目标的竞争设施选址问题优化模型,通过设计需求导向服务分配机制解决设施与客户之间服务关系分配问题,结合模拟退火思想提出了求解模型的算法。最后利用数值例子分析了需求导向服务分配机制以及目标权重、预算限额等参数对于选址决策的影响,其中考虑需求导向因素会适当增加企业的总成本,但可以减少客户所付出的费用从而增强对客户的吸引力;另外企业的预算限额对于企业的设施选址决策有着重要的影响,企业所能获取的市场份额与其选址预算限额呈正相关的关系;而客户所需付出的总费用与企业提供服务的总成本两者之间则呈负相关的关系,因此需要通过服务质量与成本之间的权衡实现最理想的选址决策。     

Tool capacity planning for semiconductor fabrication facilities under demand uncertainty

This research is motivated by issues faced by a large manufacturer of semiconductor devices. Semiconductor manufacturing companies allocate millions of dollars every year for new types of machine tools for their facilities. Typically these are special purpose machine tools which are made to order. The rate of change in products and technology makes it difficult for manufacturers to have a good estimate of future tool requirements. Further, manufacturers experience a long lead time while procuring these tools. In this paper, we model the tool capacity planning problem under uncertainty in demand. The number of tools required in a facility is sufficiently large (nearly hundred or more tools) to make it nearly impossible to obtain efficient exact algorithms. We provide heuristics to find efficient tool procurement plans and test their quality using lower bounds on the formulation.     

Service differentiation in spare parts inventory management

The contemporary after-sales market is of increasing importance. One of the features required by the market is to provide differentiated service levels to different groups of customers. We use critical levels as a means to offer differentiation. Critical level policies aim to exploit the differences in target service levels by inventory rationing. In our multi-item single-location spare parts inventory model, we aim to minimize the spare parts provisioning cost, that is inventory holding and transportation cost, under the condition that aggregate mean waiting time constraints for all customer groups are met. In a computational experiment and a case study with data from a company in the semiconductor supplier industry, we show that significant cost reductions can be obtained when critical level policies are used instead of base stock policies (ie policies without critical levels).