Refine
Year of publication
Document Type
- Report (26) (remove)
Language
- English (26)
Has Fulltext
- yes (26)
Keywords
- Integer programming (4)
- hub location (3)
- Heuristics (2)
- Logistics (2)
- Supply Chain Management (2)
- facility location (2)
- software development (2)
- supply chain management (2)
- : multiple objective programming (1)
- Assigment (1)
- Capacitated Hub Location (1)
- Capacity decisions (1)
- Complexity theory (1)
- Constraint Programming (1)
- Decision support systems (1)
- Facility location (1)
- Geographical Information Systems (1)
- Geometric (1)
- Gradual Covering (1)
- Heuristic (1)
- Home Health Care (1)
- Hub Location (1)
- Linear Programming (1)
- MILP formulations (1)
- MIP formulations (1)
- Metaheuristics (1)
- Network Location (1)
- Network design (1)
- Optimization (1)
- Ordered Median Function (1)
- Recycling (1)
- Rounding (1)
- Route Planning (1)
- Supply Chain Design (1)
- batch presorting problem (1)
- big triangle small triangle method (1)
- bounds (1)
- branch and cut (1)
- competetive analysis (1)
- decomposition (1)
- dial-a-ride (1)
- discrete facility location (1)
- discrete location (1)
- dynamic mode (1)
- efficient set (1)
- evolutionary algorithms (1)
- facets (1)
- financial decisions (1)
- genetic algorithms (1)
- geographical information systems (1)
- global optimization (1)
- heuristic (1)
- heuristics (1)
- in-house hospital transportation (1)
- integer programming (1)
- logistics (1)
- multi-period planning (1)
- multi-stage stochastic programming (1)
- online optimization (1)
- optimization algorithms (1)
- ordered median (1)
- planar location (1)
- political districting (1)
- polynomial algorithms (1)
- project management and scheduling (1)
- public transport (1)
- risk (1)
- sales territory alignment (1)
- strategic (1)
- tabu search (1)
- territory desgin (1)
- transportation (1)
- valid inequalities (1)
- variable neighborhood search (1)
Faculty / Organisational entity
Territory design may be viewed as the problem of grouping small geographic areas into larger geographic clusters called territories in such a way that the latter are acceptable according to relevant planning criteria. In this paper we review the existing literature for applications of territory design problems and solution approaches for solving these types of problems. After identifying features common to all applications we introduce a basic territory design model and present in detail two approaches for solving this model: a classical location–allocation approach combined with optimal split resolution techniques and a newly developed computational geometry based method. We present computational results indicating the efficiency and suitability of the latter method for solving large–scale practical problems in an interactive environment. Furthermore, we discuss extensions to the basic model and its integration into Geographic Information Systems.
In this paper we develop a network location model that combines the characteristics of ordered median and gradual cover models resulting in the Ordered Gradual Covering Location Problem (OGCLP). The Gradual Cover Location Problem (GCLP) was specifically designed to extend the basic cover objective to capture sensitivity with respect to absolute travel distance. Ordered Median Location problems are a generalization of most of the classical locations problems like p-median or p-center problems. They can be modeled by using so-called ordered median functions. These functions multiply a weight to the cost of fulfilling the demand of a customer which depends on the position of that cost relative to the costs of fulfilling the demand of the other customers. We derive Finite Dominating Sets (FDS) for the one facility case of the OGCLP. Moreover, we present efficient algorithms for determining the FDS and also discuss the conditional case where a certain number of facilities are already assumed to exist and one new facility is to be added. For the multi-facility case we are able to identify a finite set of potential facility locations a priori, which essentially converts the network location model into its discrete counterpart. For the multi-facility discrete OGCLP we discuss several Integer Programming formulations and give computational results.
The capacitated single-allocation hub location problem revisited: A note on a classical formulation
(2009)
Denote by G = (N;A) a complete graph where N is the set of nodes and A is the set of edges. Assume that a °ow wij should be sent from each node i to each node j (i; j 2 N). One possibility is to send these °ows directly between the corresponding pairs of nodes. However, in practice this is often neither e±cient nor costly attractive because it would imply that a link was built between each pair of nodes. An alternative is to select some nodes to become hubs and use them as consolidation and redistribution points that altogether process more e±ciently the flow in the network. Accordingly, hubs are nodes in the graph that receive tra±c (mail, phone calls, passengers, etc) from di®erent origins (nodes) and redirect this tra±c directly to the destination nodes (when a link exists) or else to other hubs. The concentration of tra±c in the hubs and its shipment to other hubs lead to a natural decrease in the overall cost due to economies of scale.
In this paper, a multi-period supply chain network design problem is addressed. Several aspects of practical relevance are considered such as those related with the financial decisions that must be accounted for by a company managing a supply chain. The decisions to be made comprise the location of the facilities, the flow of commodities and the investments to make in alternative activities to those directly related with the supply chain design. Uncertainty is assumed for demand and interest rates, which is described by a set of scenarios. Therefore, for the entire planning horizon, a tree of scenarios is built. A target is set for the return on investment and the risk of falling below it is measured and accounted for. The service level is also measured and included in the objective function. The problem is formulated as a multi-stage stochastic mixed-integer linear programming problem. The goal is to maximize the total financial benefit. An alternative formulation which is based upon the paths in the scenario tree is also proposed. A methodology for measuring the value of the stochastic solution in this problem is discussed. Computational tests using randomly generated data are presented showing that the stochastic approach is worth considering in these type of problems.
In this paper we propose a general approach solution method for the single facility ordered median problem in the plane. All types of weights (non-negative, non-positive, and mixed) are considered. The big triangle small triangle approach is used for the solution. Rigorous and heuristic algorithms are proposed and extensively tested on eight different problems with excellent results.
In this paper, an extension to the classical capacitated single-allocation hub location problem is studied in which the size of the hubs is part of the decision making process. For each potential hub a set of capacities is assumed to be available among which one can be chosen. Several formulations are proposed for the problem, which are compared in terms of the bound provided by the linear programming relaxation. Di®erent sets of inequalities are proposed to enhance the models. Several preprocessing tests are also presented with the goal of reducing the size of the models for each particular instance. The results of the computational experiments performed using the proposed models are reported.
Facility location problems in the plane are among the most widely used tools of Mathematical Programming in modeling real-world problems. In many of these problems restrictions have to be considered which correspond to regions in which a placement of new locations is forbidden. We consider center and median problems where the forbidden set is
a union of pairwise disjoint convex sets. As applications we discuss the assembly of printed circuit boards, obnoxious facility location and the location of emergency facilities.
We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets of this polyhedron. We develop some general rules about lifting facets from the uncapacitated facility location (UFL) for UHL and projecting facets from UHL to UFL. By applying these rules we get a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we get a new formulation of UHL whose constraints are all facet–defining. We show its superior computational performance by benchmarking it on a well known data set.
Home Health Care (HHC) services are becoming increasingly important in Europe’s aging societies. Elderly people have varying degrees of need for assistance and medical treatment. It is advantageous to allow them to live in their own homes as long as possible, since a long-term stay in a nursing home can be much more costly for the social insurance system than a treatment at home providing assistance to the required level. Therefore, HHC services are a cost-effective and flexible instrument in the social system. In Germany, organizations providing HHC services are generally either larger charities with countrywide operations or small private companies offering services only in a city or a rural area. While the former have a hierarchical organizational structure and a large number of employees, the latter typically only have some ten to twenty nurses under contract. The relationship to the patients (“customers”) is often long-term and can last for several years. Therefore acquiring and keeping satisfied customers is crucial for HHC service providers and intensive competition among them is observed.
In this paper, a new mixed integer mathematical programme is proposed for the application of Hub Location Problems (HLP) in public transport planning. This model is among the few existing ones for this application. Some classes of valid inequalities are proposed yielding a very tight model. To solve instances of this problem where existing standard solvers fail, two approaches are proposed. The first one is an exact accelerated Benders decomposition algorithm and the latter a greedy neighborhood search. The computational results substantiate the superiority of our solution approaches to existing standard MIP solvers like CPLEX, both in terms of computational time and problem instance size that can be solved. The greedy neighborhood search heuristic is shown to be extremely efficient.
Structuring global supply chain networks is a complex decision-making process. The typical inputs to such a process consist of a set of customer zones to serve, a set of products to be manufactured and distributed, demand projections for the different customer zones, and information about future conditions, costs (e.g. for production and transportation) and resources (e.g. capacities, available raw materials). Given the above inputs, companies have to decide where to locate new service facilities (e.g. plants, warehouses), how to allocate procurement and production activities to the variousmanufacturing facilities, and how to manage the transportation of products through the supply chain network in order to satisfy customer demands. We propose a mathematical modelling framework capturing many practical aspects of network design problems simultaneously. For problems of reasonable size we report on computational experience with standard mathematical programming software. The discussion is extended with other decisions required by many real-life applications in strategic supply chain planning. In particular, the multi-period nature of some decisions is addressed by a more comprehensivemodel, which is solved by a specially tailored heuristic approach. The numerical results suggest that the solution procedure can identify high quality solutions within reasonable computational time.
Given Q different objective functions, three types of single-facility problems
are considered: Lexicographic, pareto and max ordering problems. After discussing the interrelation between the problem types, a complete characterization of lexicographic locations and some instances of pareto and max ordering locations is given. The characterizations result in efficient solution algorithms for finding these locations. The paper relies heavily on the theory of restricted locations developed by the same authors, and can be further extended, for instance, to multifacility problems with several objectives. The proposed approach is more general than previously published results on multicriteria planar location problems and is particulary suited for modelling real-world problems.
In this paper, we are going to propose the first mathematical model for Multi- Period Hub Location Problems (MPHLP). We apply this mixed integer program- ming model on public transport planning and call it Multi-Period Hub Location Problem for Public Transport (MPHLPPT). In fact, HLPPT model proposed earlier by the authors is extended to include more facts and features of the real-life application. In order to solve instances of this problem where existing standard solvers fail, a solution approach based on a greedy neighborhood search is developed. The computational results substantiate the efficiency of our solution approach to solve instances of MPHLPPT.
The objective of this paper is to bridge the gap between location theory and practice. To meet this objective focus is given to the development of software capable of addressing the different needs of a wide group of users. There is a very active community on location theory encompassing many research fields such as operations research, computer science, mathematics, engineering, geography, economics and marketing. As a result, people working on facility location problems have a very diverse background and also different needs regarding the software to solve these problems. For those interested in non-commercial applications (e. g. students and researchers), the library of location algorithms (LoLA can be of considerable assistance. LoLA contains a collection of efficient algorithms for solving planar, network and discrete facility location problems. In this paper, a detailed description of the functionality of LoLA is presented. In the fields of geography and marketing, for instance, solving facility location problems requires using large amounts of demographic data. Hence, members of these groups (e. g. urban planners and sales managers) often work with geographical information too s. To address the specific needs of these users, LoLA was inked to a geographical information system (GIS) and the details of the combined functionality are described in the paper. Finally, there is a wide group of practitioners who need to solve large problems and require special purpose software with a good data interface. Many of such users can be found, for example, in the area of supply chain management (SCM). Logistics activities involved in strategic SCM include, among others, facility location planning. In this paper, the development of a commercial location software tool is also described. The too is embedded in the Advanced Planner and Optimizer SCM software developed by SAP AG, Walldorf, Germany. The paper ends with some conclusions and an outlook to future activities.
In this paper we focus on the strategic design of supply chain networks. We propose a mathematical modeling framework that captures many practical aspects of network design problems simultaneously but which have not received adequate attention in the literature. The aspects considered include: dynamic planning horizon, generic supply chain network structure, external supply of materials, inventory opportunities for goods, distribution of commodities, facility configuration, availability of capital for investments, and storage limitations. Moreover, network configuration decisions concerning the gradual relocation of facilities over the planning horizon are considered. To cope with fluctuating demands, capacity expansion and reduction scenarios are also analyzed as well as modular capacity shifts. The relation of the proposed modeling framework with existing models is discussed. For problems of reasonable size we report on our computational experience with standard mathematical programming software. In particular, useful insights on the impact of various factors on network design decisions are provided.
We present two heuristic methods for solving the Discrete Ordered Median Problem (DOMP), for which no such approaches have been developed so far. The DOMP generalizes classical discrete facility location problems, such as the p-median, p-center and Uncapacitated Facility Location problems. The first procedure proposed in this paper is based on a genetic algorithm developed by Moreno Vega [MV96] for p-median and p-center problems. Additionally, a second heuristic approach based on the Variable Neighborhood Search metaheuristic (VNS) proposed by Hansen & Mladenovic [HM97] for the p-median problem is described. An extensive numerical study is presented to show the efficiency of both heuristics and compare them.
Facility location decisions play a critical role in the strategic design of supply chain networks. In this paper, an extensive literature review of facility location models in the context of supply chain management is given. Following a brief review of core models in facility location, we identify basic features that such models must capture to support decision-making involved in strategic supply chain planning. In particular, the integration of location decisions with other decisions relevant to the design of a supply chain network is discussed. Furthermore, aspects related to the structure of the supply chain network, including those specific to reverse logistics, are also addressed. Significant contributions to the current state-of-the-art are surveyed taking into account numerous factors. Supply chain performance measures and optimization techniques are also reviewed. Applications of facility location models to supply chain network design ranging across various industries are discussed. Finally, a list of issues requiring further research are highlighted.
The Discrete Ordered Median Problem (DOMP) generalizes classical discrete location problems, such as the N-median, N-center and Uncapacitated Facility Location problems. It was introduced by Nickel [16], who formulated it as both a nonlinear and a linear integer program. We propose an alternative integer linear programming formulation for the DOMP, discuss relationships between both integer linear programming formulations, and show how properties of optimal solutions can be used to strengthen these formulations. Moreover, we present a specific branch and bound procedure to solve the DOMP more efficiently. We test the integer linear programming formulations and this branch and bound method computationally on randomly generated test problems.
This paper analyzes and solves a patient transportation problem arising in several large hospitals. The aim is to provide an efficient and timely transport service to patients between several locations on a hospital campus. Transportation requests arrive in a dynamic fashion and the solution methodology must therefore be capable of quickly inserting new requests in the current vehicle routes. Contrary to standard dial-a-ride problems, the problem under study contains several complicating constraints which are specific to a hospital context. The paper provides a detailed description of the problem and proposes a two-phase heuristic procedure capable of handling its many features. In the first phase a simple insertion scheme is used to generate a feasible solution, which is improved in the second phase with a tabu search algorithm. The heuristic procedure was extensively tested on real data provided by a German hospital. Results show that the algorithm is capable of handling the dynamic aspect of the problem and of providing high quality solutions. In particular, it succeeded in reducing waiting times for patients while using fewer vehicles.
Bringing robustness to patient flow management through optimized patient transports in hospitals
(2007)
Intra-hospital transports are often required for diagnostic or therapeutic reasons. Depending on the hospital layout, transportation between nursing wards and service units is either provided by ambulances or by trained personnel who accompany patients on foot. In many large German hospitals, the patient transport service is poorly managed and lacks workflow coordination. This contributes to higher hospital costs (e.g. when a patient is not delivered to the operating room on time) and to patient inconvenience due to longer waiting times. We have designed a computer-based planning system - Opti-TRANS c - that supports all phases of the transportation flow, ranging from travel booking, dispatching transport requests to monitoring and reporting trips in real-time. The methodology developed to solve the underlying optimization problem - a dynamic dial-a-ride problem with hospital-specific constraints - draws on fast heuristic methods to ensure the efficient and timely provision of transports. We illustrate the strong impact of Opti-TRANS c on the daily performance of the patient transportation service of a large German hospital. The major benefits obtained with the new tool include streamlined transportation processes and workflow, significant savings and improved patient satisfaction. Moreover, the new planning system has contributed to increase awareness among hospital staff about the importance of implementing efficient logistics practices.
In this paper we consider short term storage systems. We analyze presorting strategies to improve the effiency of these storage systems. The presorting task is called Batch PreSorting Problem (BPSP). The BPSP is a variation of an assigment problem, i.e., it has an assigment problem kernel and some additional constraints. We present different types of these presorting problems, introduce mathematical programming formulations and prove the NP-completeness for one type of the BPSP. Experiments are carried out in order to compare the different model formulations and to investigate the behavior of these models.
A general multi-period network redesign problem arising in the context of strategic supply chain planning (SCP) is studied. Several aspects of practical relevance in SCP are captured namely, multiple facility layers with different types of facilities, flows between facilities in the same layer, direct shipments to customers, and facility relocation. An efficient two-phase heuristic approach is proposed for obtaining feasible solutions to the problem, which is initially modeled as a large-scale mixed-integer linear program. In the first stage of the heuristic, a linear programming rounding strategy is applied to second initial values for the binary location variables in the model. The second phase of the heuristic uses local search to correct the initial solution when feasibility is not reached or to improve the solution when its quality does not meet given criteria. The results of an extensive computational study performed on randomly generated instances are reported.
The problem discussed in this paper is motivated by the new recycling directiveWEEE of the EC. The core of this law is, that each company which sells electrical or electronic equipment in a European country has the obligation to recollect and recycle an amount of returned items which is proportional to its market share. To assign collection stations to companies, in Germany for one product type a territory design approach is planned. However, in contrast to classical territory design, the territories should be geographically as dispersed as possible to avoid that a company, resp. its logistics provider responsible for the recollection, gains a monopoly in some region. First, we identify an appropriate measure for the dispersion of a territory. Afterwards, we present a first mathematical programming model for this new problem as well as a solution method based on the GRASP methodology. Extensive computational results illustrate the suitability of the model and assess the effectiveness of the heuristic.
In this article, we consider the problem of planning inspections and other tasks within a software development (SD) project with respect to the objectives quality (no. of defects), project duration, and costs. Based on a discrete-event simulation model of SD processes comprising the phases coding, inspection, test, and rework, we present a simplified formulation of the problem as a multiobjective optimization problem. For solving the problem (i.e. finding an approximation of the efficient set) we develop a multiobjective evolutionary algorithm. Details of the algorithm are discussed as well as results of its application to sample problems.
Territory design and districting may be viewed as the problem of grouping small geographic areas into larger geographic clusters called territories in such a way that the latter are acceptable according to relevant planning criteria. The availability of GIS on computers and the growing interest in Geo-Marketing leads to an increasing importance of this area. Despite the wide range of applications for territory design problems, when taking a closer look at the models proposed in the literature, a lot of similarities can be noticed. Indeed, the models are many times very similar and can often be, more or less directly, carried over to other applications. Therefore, our aim is to provide a generic application-independent model and present efficient solution techniques. We introduce a basic model that covers aspects common to most applications. Moreover, we present a method for solving the general model which is based on ideas from the field of computational geometry. Theoretical as well as computational results underlining the efficiency of the new approach will be given. Finally, we show how to extend the model and solution algorithm to make it applicable for a broader range of applications and how to integrate the presented techniques into a GIS.