A Lagrangian heuristic algorithm for a public healthcare facility location problem

We consider a healthcare facility location problem in which there are two types of patients, low-income patients and middle- and high-income patients. The former can use only public facilities, while the latter can use both public facilities and private facilities. We focus on the problem of determining locations of public healthcare facilities to be established within a given budget and allocating the patients to the facilities for the objective of maximizing the number of served patients while considering preference of the patients for the public and private facilities. We present an integer programming formulation for the problem and develop a heuristic algorithm based on Lagrangian relaxation and subgradient optimization methods. Results of computational experiments on a number of problem instances show that the algorithm gives good solutions in a reasonable computation time and may be effectively used by the healthcare authorities of the government.     

Allocation of Doctors to Health Centres in Haryana State of India — A Case Study

Medical Administrators are usually confronted with the problem of determining the number of doctors to be posted at different health centres within their jurisdiction. In India the number of doctors allocated to a health centre is normally decided without any proper study of the health needs of the area served by the centre. In certain areas the number of doctors posted is considerably different from the requirement of the area. Also, in certain health centres situated in villages lacking in modern amenities, absenteeism among doctors poses a very serious problem in day to day running of the health centres. The problem of allocation is formulated and a heuristic method is suggested for determining the optimum number of doctors to be posted at each health centre in order to maximise the number of patients seen by the doctor per day. The heuristic method is applied to nine health centres of Haryana state of India in order to demonstrate the potential benefits.     

A heuristic algorithm for the truckload and less-than-truckload problem

The delivery of goods from a warehouse to local customers is an important and practical problem of a logistics manager. In reality, we are facing the fluctuation of demand. When the total demand is greater than the whole capacity of owned trucks, the logistics managers may consider using an outsider carrier.Logistics managers can make a selection between a truckload (a private truck) and a less-than-truckload carrier (an outsider carrier). Selecting the right mode to transport a shipment may bring significant cost savings to the company.In this paper, we address the problem of routing a fixed number of trucks with limited capacity from a central warehouse to customers with known demand. The objective of this paper is developing a heuristic algorithm to route the private trucks and to make a selection of less-than-truckload carriers by minimizing a total cost function. Both the mathematical model and the heuristic algorithm are developed. Finally, some computational results and suggestions for future research are presented.     

A discrete competitive facility location model with variable attractiveness

We consider the discrete version of the competitive facility location problem in which new facilities have to be located by a new market entrant firm to compete against already existing facilities that may belong to one or more competitors. The demand is assumed to be aggregated at certain points in the plane and the new facilities can be located at predetermined candidate sites. We employ Huff's gravity-based rule in modelling the behaviour of the customers where the probability that customers at a demand point patronize a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. The objective of the firm is to determine the locations of the new facilities and their attractiveness levels so as to maximize the profit, which is calculated as the revenue from the customers less the fixed cost of opening the facilities and variable cost of setting their attractiveness levels. We formulate a mixed-integer nonlinear programming model for this problem and propose three methods for its solution: a Lagrangean heuristic, a branch-and-bound method with Lagrangean relaxation, and another branch-and-bound method with nonlinear programming relaxation. Computational results obtained on a set of randomly generated instances show that the last method outperforms the others in terms of accuracy and efficiency and can provide an optimal solution in a reasonable amount of time.     

Scheduling multi-stage parallel-processor services to minimize average response time

The problem of scheduling on a multi-stage parallel-processor architecture in computer centres is addressed with the objective of minimizing average completion time of a set of requests. The problem is modelled as a flexible flowshop problem for which few heuristics exist in the flowshop scheduling literature. A new three-phase heuristic is proposed in this paper. An extensive computational experiment has been conducted to compare the performance of the existing heuristics and the proposed heuristic. The results indicate that the proposed heuristic significantly outperforms the existing ones. More specifically, the overall average error of the best existing heuristic is about five times that of the proposed heuristic while the overall average CPU time of the proposed heuristic is about half of the best existing one. More importantly, as the number of requests increases, the CPU time of the proposed heuristic decreases considerably (compared to the best existing heuristic) while the ratio of the error (of the best existing to the proposed heuristic) of about five times remains almost the same.     

A model and solution method for multi-period sales promotion design

This research addresses the optimal design of a series of promotions (which might offer free gifts, discounts, or special services) periodically mailed to potential customers. A model and methodology are presented which maximize the multiple purchases of these customers over time using opinions from both promotion designers and customers. A Genetic Algorithm-based heuristic is developed to efficiently arrive at good promotion designs, and the methodology is applied to a problem using real data.     

Heuristic Methods for Large Centroid Clustering Problems

This article presents new heuristic methods for solving a class of hard centroid clustering problems including the p-median, the sum-of-squares clustering and the multi-source Weber problems. Centroid clustering is to partition a set of entities into a given number of subsets and to find the location of a centre for each subset in such a way that a dissimilarity measure between the entities and the centres is minimized. The first method proposed is a candidate list search that produces good solutions in a short amount of time if the number of centres in the problem is not too large. The second method is a general local optimization approach that finds very good solutions. The third method is designed for problems with a large number of centres; it decomposes the problem into subproblems that are solved independently. Numerical results show that these methods are efficient—dozens of best solutions known to problem instances of the literature have been improved—and fast, handling problem instances with more than 85,000 entities and 15,000 centres—much larger than those solved in the literature. The expected complexity of these new procedures is discussed and shown to be comparable to that of an existing method which is known to be very fast.     

Fuzzy chance-constrained programming model for a multi-echelon reverse logistics network for household appliances

Efficient planning and design of an appropriate reverse logistics network is crucial to the economical collection and disposal of scrapped household appliances and electrical products. Such systems are commonly modelled as mixed-integer programs, whose solutions will determine the location of individual facilities that optimize material flow. One of the major drawbacks of current models is that they do not adequately address the important issue of uncertainty in demand and supply. Another deficiency in current models is that they are restricted to a two-echelon system. This study addresses these deficiencies by embodying such uncertainties in the model using the technique of fuzzy-chance constrained programming, and by extending the model to a three-echelon system. A heuristic in the form of a hybrid genetic algorithm is then employed to generate low-cost solutions. The overall objective is to find economical solutions to the general problem of determining the volume of appliances to be moved between the three echelons of customer base to collection sites, collection sites to disposal centres and disposal centre to landfill centre/remanufacturing centre; and to the problems of positioning the disposal centres and the landfill centre/remanufacturing centres within the problem domain. A case example in China is presented and the quality and robustness of the solutions are explored through sensitivity analysis.     

An Optimization Model to Determine Master Designs and Runs for Advertisement Printing

In this paper we consider a common optimization problem faced by a printing company while designing masters for advertisement material. A printing company may receive from various customers, advertisements for their products and services and their demand is for a specified number of copies to be printed. In a particular case, the printer receives these orders to be delivered next week from the customers, until the Thursday of a week. By Monday the printed copies have to be delivered to the customers. These advertisement items of the various customers are to be printed on large sheets of papers of specified standard sizes. The size is called a k-up if k items can be printed on one sheet. It is a given constraint that only items of the same size can be loaded on a master. This constraint results in a decomposition of the original problem of designing masters into many sub-problems, one for each size. The objective is to minimize the number of masters required while meeting the requirements of the customers. We formulate this optimization problem mathematically, discuss the computational issues and present some heuristic approaches for solving the problem.     

An iterated local search heuristic for the capacitated prize-collecting travelling salesman problem

This paper considers a variant of the travelling salesman problem named the capacitated prize-collecting travelling salesman problem (CPCTSP), which is derived from the colour-coating production scheduling in a cold rolling mill. The objective of the CPCTSP is to minimize the travel cost and the penalties paid for unvisited customers in such a way that a sufficiently large prize is collected and the demand of the visited customers does not exceed the salesman's capacity. For this problem, we propose an iterated local search (ILS) heuristic adopting guided kick and enhanced dynasearch. The experimental results on randomly generated instances show that the proposed heuristic outperforms the improved tabu search algorithm using frequency-based memory, and the further experimental results on instances collected from real colour-coating production also show that the proposed ILS algorithm is more effective and efficient than the currently adopted manual scheduling method.     

A tabu search heuristic for the split delivery vehicle routing problem with production and demand calendars

The purpose of this article is to propose a tabu search heuristic for the split delivery Vehicle Routing Problem with Production and Demand Calendars (VRPPDC). This new problem consists of determining which customers will be served by a common carrier, as well as the delivery routes for those served by the private fleet, in order to minimize the overall transportation and inventory costs. We first model this problem and then propose a simple decomposition procedure that can be used to provide a starting solution. Next, we introduce a new tabu search heuristic and we describe two new neighbor reduction strategies. Finally, we present the results of our extensive computational tests. According to these tests, our reduction strategies are efficient not only at reducing computing time but also at improving the overall solution quality.     

A Lagrangean Heuristic for a Modular Capacitated Location Problem

This paper considers the Modular Capacitated Location Problem (MCLP) which consists of finding the location and capacity of the facilities, to serve a set of customers at a minimum total cost. Each customer has an associated demand and the capacity of each potential location must be chosen from a finite and discrete set of available capacities. Practical applications of this problem can be found in the location of warehouses, schools, health care services or other types of public services. For the MCLP different mixed integer linear programming models are proposed. The authors develop upper and lower bounds on the problem's optimal value and present computational results with randomly generated tests problems.     

Simple dynamic location problem with uncertainty: a primal-dual heuristic approach

Abstract

In this paper, the simple dynamic facility location problem is extended to uncertain realizations of the potential locations for facilities and the existence of customers as well as fixed and variable costs. With limited knowledge about the future, a finite and discrete set of scenarios is considered. The decisions to be made are where and when to locate the facilities, and how to assign the existing customers over the whole planning horizon and under each scenario, in order to minimize the expected total costs. Whilst assignment decisions can be scenario dependent, location decisions have to take into account all possible scenarios and cannot be changed according to each scenario in particular. We first propose a mixed linear programming formulation for this problem and then we present a primal-dual heuristic approach to solve it. The heuristic was tested over a set of randomly generated test problems. The computational results are provided.     

Asymptotique d'un problème de positionnement optimalAsymptotic of an optimal location problem

We consider the problem of optimal location of production centres to serve a non-uniform distribution of customers. The location is required to be optimal with respect to the cost of transportation which is modeled by a weighted average of the distance function to the nearest production centre. In this Note we study the asymptotic behaviour of the problem as the number of production centres increases. This is done in connection with the theory of Monge–Kantorovich for mass transportation. To cite this article: G. Bouchitté et al., C. R. Acad. Sci. Paris, Ser. I 335 (2002) 853–858.     

An exact algorithm for a cross-docking supply chain network design problem

This paper proposes a branch-and-price algorithm as an exact algorithm for the cross-docking supply chain network design problem introduced by one of the authors of this paper. The objective is to optimally locate cross-docking (CD) centres and allocate vehicles for direct transportation services from the associated origin node to the associated CD centre or from the associated CD centre to the associated destination node so as to satisfy a given set of freight demands at minimum cost subject to the associated service (delivery) time restriction. A set-partitioning-based formulation is derived for the problem for which some solution properties are characterized. Based on the properties, a branch-and-price algorithm is derived. The properties can also be used in deriving any efficient local search heuristics with the move operation (neighbourhood search operation) of modifying assignment of some freight demands from current CD centres to other CD centres. Computational experiments show that the branch-and-price algorithm is effective and efficient and also that the solution properties contribute to improve the efficiency of the local search heuristics.     

The maximin HAZMAT routing problem

The hazardous material routing problem from an origin to a destination in an urban area is addressed. We maximise the distance between the route and its closest vulnerable centre, weighted by the centre’s population. A vulnerable centre is a school, hospital, senior citizens’ residence or the like, concentrating a high population or one that is particularly vulnerable or difficult to evacuate in a short time. The potential consequences on the most exposed centre are thus minimized. Though previously studied in a continuous space, the problem is formulated here over a transport (road) network. We present an exact model for the problem, in which we manage to significantly reduce the required variables, as well as an optimal polynomial time heuristic. The integer programming formulation and the heuristic are tested in a real-world case study set in the transport network in the city of Santiago, Chile.     

Health visitors revisited

Cambridgeshire Area Health Authority commissioned a team from the University of Aston Management Centre to carry out an operational research project in order to assist in planning the provision of health visitor services in Peterborough health District. Since Peterborough is a Development Area there has been a rapid increase in population which it is planned will continue for some years. This change in size and age-distribution of the population poses considerable problems for planning the provision of health visitor services.Health visitors are trained nurses who have highly independent roles in the National Health Service. They are largely concerned with preventive work, traditionally with children and increasingly with the elderly, in which it is difficult to set quantitative objectives and measure outputs.This paper will describe the research plan and the models developed. Considerable attention will be paid to the relationship of the research team to the client system, consisting of the Area and District managers and the individual health visitors. The implications of this type of study in extending the practice of O.R. will be considered.     

城市配送车辆路径优化集束式算法的客户点归并策略

VRP问题的研究起步较早,求解方法也非常丰富,然而,面对客户规模庞大,交通网络复杂的多约束车辆优化调度问题,现有算法显得无能为力.为有效解决需求点规模庞大的城市配送车辆优化调度问题,提出一种新的两阶段启发式算法——集束式算法,采用"集中后分派,分派后扩展"的思想,对末梢客户和同路段客户进行客户点合并,从全局上降低搜索范围,并提出相关客户点归并算法.     

The uncapacitated facility location problem with demand-dependent setup and service costs and customer-choice allocation

We consider a generalization of the uncapacitated facility location problem, where the setup cost for a facility and the price charged for service may depend on the number of customers patronizing the facility. Customers are represented by the nodes of the transportation network, and facilities can be located only at nodes; a customer selects a facility to patronize so as to minimize his (her) expenses (price for service + the part of transportation costs paid by the customer). We assume that transportation costs are paid partially by the service company and partially by customers. The objective is to choose locations for facilities and balanced prices so as to either minimize the expenses of the service company (the sum of the total setup cost and the total part of transportation costs paid by the company), or to maximize the total profit. A polynomial-time dynamic programming algorithm for the problem on a tree network is developed.     

Implementation of Health Facilities in a New City

A new city is under construction in a developing country. The town will be organized in modules, and the population projection is established till the 90s. The ratio of medical personnel to inhabitants is fixed according to health policy criteria. The primary care system should be composed of a set of health centres which are identical with regard to equipment and personnel. The problem is to determine the number--and thus the size--of the health centres, and their location. The solution depends on two opposing factors: the total construction cost, which is increasing with the number of centres, and the walking distance for the patient, which is decreasing with the number of centres. For a given critical distance, we find--using techniques of location theory in network--the smallest number of centres that will ensure that all inhabitants are located within the critical distance. A Fortran program in which the sensitivity of the solution is studied as a function of the given critical distance is developed.