Stop location design in public transportation networks: covering and accessibility objectives

We consider the location of new stops along the edges of an existing public transportation network. Examples of StopLoc include the location of bus stops along some given bus routes or of railway stations along the tracks in a railway system. In order to evaluate the decision assume that potential customers in given demand facilities are known. Two objectives are proposed. In the first one, we minimize the number of stations such that any of the demand facilities can reach a closest station within a given distance of r. In the second objective, we fix the number of new stations and minimize the sum of the distances between demand facilities and stations. The resulting two problems CovStopLoc and AccessStopLoc are solved by a reduction to a classical set covering and a restricted location problem, respectively. We implement the general ideas in two different environments, the plane, where demand facilities are represented by coordinates, and in networks, where they are nodes of a graph.     

随机容错设施选址问题的原始-对偶近似算法

研究两阶段随机容错设施选址问题,其中需要服务的顾客在第二阶段出现（在第一阶段不知道）．两个阶段中每个设施的开设费用可以不同,设施的开设依赖于阶段和需要服务的顾客集合（称为场景）．并且在出现的场景里的每个顾客都有相同的连接需求,即每个顾客需要由r个不同的设施服务．给定所有可能的场景及相应的概率,目标是在两个阶段分别选取开设的设施集合,将出现场景的顾客连接到r个不同的开设设施上,使得包括设施费用和连接费用的总平均费用最小．根据问题的特定结构,给出了原始。对偶（组合）3-近似算法．     

Sequencing and scheduling in flowshops with task redistribution

In some manufacturing situations, station tasks or operations can be shifted or redistributed to adjacent stations. This can be done when these stations have the appropriate equipment, and the workers on that station can perform the shifted work to a reasonable level of competency. This paper addresses such an environment and provides a general framework for applying the shifting or redistribution of tasks methodology to the intermediate storage, no-intermediate storage and no-wait flowshop problems. The outcome of this research is a way in which to utilise more efficiently the general-purpose facilities of this type of production environment. It includes mathematical models, recurrence equations and solution techniques for sequencing and scheduling. From an extensive numerical investigation, the benefits achieved by the application of this methodology are detailed.     

Competitive facility location problem with attractiveness adjustment of the follower: A bilevel programming model and its solution

We are concerned with a problem in which a firm or franchise enters a market by locating new facilities where there are existing facilities belonging to a competitor. The firm aims at finding the location and attractiveness of each facility to be opened so as to maximize its profit. The competitor, on the other hand, can react by adjusting the attractiveness of its existing facilities with the objective of maximizing its own profit. The demand is assumed to be aggregated at certain points in the plane and the facilities of the firm can be located at predetermined candidate sites. We employ Huff’s gravity-based rule in modeling the behavior of the customers where the fraction of customers at a demand point that visit a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. We formulate a bilevel mixed-integer nonlinear programming model where the firm entering the market is the leader and the competitor is the follower. In order to find the optimal solution of this model, we convert it into an equivalent one-level mixed-integer nonlinear program so that it can be solved by global optimization methods. Apart from reporting computational results obtained on a set of randomly generated instances, we also compute the benefit the leader firm derives from anticipating the competitor’s reaction of adjusting the attractiveness levels of its facilities. The results on the test instances indicate that the benefit is 58.33% on the average.     

A Strategy for Solving the Plant Layout Problem

We consider the problem of laying out the facilities of which a plant is composed, in terms of specifying which facilities are to be adjacent. For each pair of facilities a benefit from siting them adjacent to each other is known. We seek to maximise the sum of benefits over all pairs of adjacent facilities.The problem is stated in terms of graph theory, and provision is made for some edges to be considered necessary and others forbidden, where each edge represents an adjacency. We describe a branch and bound algorithm for finding an optimal layout and a sequence of tests for determining whether or not the graphs constructed in the course of the algorithm are planar.     

A multi-objective genetic algorithm for a bi-objective facility location problem with partial coverage

In this study, we present a bi-objective facility location model that considers both partial coverage and service to uncovered demands. Due to limited number of facilities to be opened, some of the demand nodes may not be within full or partial coverage distance of a facility. However, a demand node that is not within the coverage distance of a facility should get service from the nearest facility within the shortest possible time. In this model, it is assumed that demand nodes within the predefined distance of opened facilities are fully covered, and after that distance the coverage level decreases linearly. The objectives are defined as the maximization of full and partial coverage, and the minimization of the maximum distance between uncovered demand nodes and their nearest facilities. We develop a new multi-objective genetic algorithm (MOGA) called modified SPEA-II (mSPEA-II). In this method, the fitness function of SPEA-II is modified and the crowding distance of NSGA-II is used. The performance of mSPEA-II is tested on randomly generated problems of different sizes. The results are compared with the solutions of the most well-known MOGAs, NSGA-II and SPEA-II. Computational experiments show that mSPEA-II outperforms both NSGA-II and SPEA-II.     

Generalized Weber Problem with Rectangular Regions

The problem of locating one or more new facilities relative to a number of existing rectangular regions is treated for the case where the rectilinear norm is used. The new facilities are to be located such that the total weighted distance is minimized. If there is interfacility interaction among the new facilities, a gradient-free nonlinear search algorithm is utilized. Computational experience suggests that this algorithm is expedient even in the solution of large problems.     

Developments in network location with mobile and congested facilities

We review four facility location problems which are motivated by urban service applications and which can be thought of as extensions of the classic Q-median problem on networks. In problems P1 and P2 it is assumed that travel times on network links change over time in a probabilistic way. In P2 it is further assumed that the facilities (servers) are movable so that they can be relocated in response to new network travel times. Problems P3 and P4 examine the Q-median problem for the case when the service capacity of the facilities is finite and, consequently, some or all of the facilities can be unavailable part of the time. In P3 the facilities have stationary home locations but in P4 they have movable locations and thus can be relocated to compensate for the unavailability of the busy facilities. We summarize our main results to date on these problems.     

Online facility location with facility movements

In the online facility location problem demand points arrive one at a time and the goal is to decide where and when to open a facility. In this paper we consider a new version of the online facility location problem, where the algorithm is allowed to move the opened facilities in the metric space. We consider the uniform case where each facility has the same constant cost. We present an algorithm which is 2-competitive for the general case and we prove that it is 3/2-competitive if the metric space is the line. We also prove that no algorithm with smaller competitive ratio than \({(\sqrt{13}+1)/4\approx 1.1514}\) exists. We also present an empirical analysis which shows that the algorithm gives very good results in the average case.     

An arc cover–path-cover formulation and strategic analysis of alternative-fuel station locations

In this study, we present a new formulation of the generalized flow-refueling location model that takes vehicle range and trips between origin–destination pairs into account. The new formulation, based on covering the arcs that comprise each path, is more computationally efficient than previous formulations or heuristics. Next, we use the new formulation to provide managerial insights for some key concerns of the industry, such as: whether infrastructure deployment should focus on locating clusters of facilities serving independent regions or connecting these regions by network of facilities; what is the impact of uncertainty in the origin–destination demand forecast; whether station locations will remain optimal as higher-range vehicles are introduced; and whether infrastructure developers should be willing to pay more for stations at higher-cost intersections. Experiments with real and random data sets are encouraging for the industry, as optimal locations tend to be robust under various conditions.     

An algorithm portfolio for the dynamic maximal covering location problem

The location of facilities (antennas, ambulances, police patrols, etc) has been widely studied in the literature. The maximal covering location problem aims at locating the facilities in such positions that maximizes certain notion of coverage. In the dynamic or multi-period version of the problem, it is assumed that the nodes’ demand changes with the time and as a consequence, facilities can be opened or closed among the periods. In this contribution we propose to solve dynamic maximal covering location problem using an algorithm portfolio that includes adaptation, cooperation and learning. The portfolio is composed of an evolutionary strategy and three different simulated annealing methods (that were recently used to solve the problem). Experiments were conducted on 45 test instances (considering up to 2500 nodes and 200 potential facility locations). The results clearly show that the performance of the portfolio is significantly better than its constituent algorithms.     

Scalable methodology for supply chain inventory coordination with private information

This paper considers the problems of coordinating serial and assembly inventory systems with private information where end-item demands are known over a finite horizon. In a private information environment, the objective function and cost parameters of each facility are regarded as private information that no other facilities in the system have access to. The solution approach decomposes the problem into separable subproblems such that the private information is partitioned as required. Global optimality is sought with an iterative procedure in which the subproblems negotiate the level of material flows between facilities. At the core of the solution procedure is a supplier–buyer link model that can be used as a building block to form other supply chain configurations. Experimental results show that the proposed methodology provides promising results when compared to competing methodologies that disregard information privacy.     

Locating an obnoxious facility within a polygonal region

The purpose of this paper is to review some of the many instances in which a location analyst must make a decision as to where an obnoxious facility should be placed. An obnoxious facility is one that can be defined as a facility which has undesirable interactions with existing facilities. Examples include equipment which emit pollutants such as particulates, noise and radiation or warehouses that contain flammable materials. Other obnoxious facilities include machines that are potential sources of hazards to nearby machines and workers. The interaction between the obnoxious facility and each existing facility is reflected through a weighting factor. The feasible region is considered to be continuous in the form of a convex or nonconvex simple polygon. Since the new facility is to be located away from the existing facilities, an appropriate criterion for optimization is the MAXIMIN or the MAXISUM criterion. Algorithms are reviewed for two common metrics under both criteria, i.e. Euclidean and rectilinear.     

Solving a Huff-like competitive location and design model for profit maximization in the plane

A chain wants to set up a single new facility in a planar market where similar facilities of competitors, and possibly of its own chain, are already present. Fixed demand points split their demand probabilistically over all facilities in the market proportionally with their attraction to each facility, determined by the different perceived qualities of the facilities and the distances to them, through a gravitational or logit type model. Both the location and the quality (design) of the new facility are to be found so as to maximise the profit obtained for the chain. Several types of constraints and costs are considered.     

Facility location for market capture when users rank facilities by shorter travel and waiting times

A firm wants to locate several multi-server facilities in a region where there is already a competitor operating. We propose a model for locating these facilities in such a way as to maximize market capture by the entering firm, when customers choose the facilities they patronize, by the travel time to the facility and the waiting time at the facility. Each customer can obtain the service or goods from several (rather than only one) facilities, according to a probabilistic distribution. We show that in these conditions, there is demand equilibrium, and we design an ad hoc heuristic to solve the problem, since finding the solution to the model involves finding the demand equilibrium given by a nonlinear equation. We show that by using our heuristic, the locations are better than those obtained by utilizing several other methods, including MAXCAP, p-median and location on the nodes with the largest demand.     

Incorporating the threat of terrorist attacks in the design of public service facility networks

In this paper, we consider the design problem of a public service facility network with existing facilities when there is a threat of possible terrorist attacks. The aim of the system planner, who is responsible for the operation of the network, is to open new facilities, relocate existing ones if necessary, and protect some of the facilities to ensure a maximum coverage of the demand that is assumed to be aggregated at customer zones. By doing so, the system planner anticipates that a number of unprotected facilities will be rendered out-of-service by terrorist attacks. It is assumed that the sum of the fixed cost of opening new facilities, the relocation costs, and the protection costs cannot exceed a predetermined budget level. Adopting the approach of gradual (or partial) coverage, we formulate a bilevel programming model where the system planner is the leader and the attacker is the follower. The objective of the former is the maximization of the total service coverage, whereas the latter wants to minimize it. We propose a heuristic solution procedure based on tabu search where the search space consists of the decisions of the system planner, and the corresponding objective value is computed by optimally solving the attacker??s problem using CPLEX. To assess the quality of the solutions produced by the tabu search (TS) heuristic, we also develop an exhaustive enumeration method, which explores all the possible combinations of opening new facilities, relocating existing ones, and protecting them. Since its time complexity is exponential, it can only be used for relatively small instances. Therefore, to be used as a benchmark method, we also implement a hill climbing procedure employed with the same type of moves as the TS heuristic. Besides, we carry out a sensitivity analysis on some of the problem parameters to investigate their effect on the solution characteristics.     

Optimal assignment of servers to tasks when collaboration is inefficient

Consider a Markovian system of two stations in tandem with finite intermediate buffer and two servers. The servers are heterogeneous, flexible, and more efficient when they work on their own than when they collaborate. We determine how the servers should be assigned dynamically to the stations with the goal of maximizing the system throughput. We show that the optimal policy depends on whether or not one server is dominant (i.e., faster at both stations) and on the magnitude of the efficiency loss of collaborating servers. In particular, if one server is dominant then he must divide his time between the two stations, and we identify the threshold policy the dominant server should use; otherwise each server should focus on the station where he is the faster server. In all cases, servers only collaborate to avoid idleness when the first station is blocked or the second station is starved, and we determine when collaboration is preferable to idleness as a function of the efficiency loss of collaborating servers.     

Cooperative facility location games

The location of facilities in order to provide service for customers is a well-studied problem in the operations research literature. In the basic model, there is a predefined cost for opening a facility and also for connecting a customer to a facility, the goal being to minimize the total cost. Often, both in the case of public facilities (such as libraries, municipal swimming pools, fire stations, … ) and private facilities (such as distribution centers, switching stations, … ), we may want to find a ‘fair’ allocation of the total cost to the customers—this is known as the cost allocation problem. A central question in cooperative game theory is whether the total cost can be allocated to the customers such that no coalition of customers has any incentive to build their own facility or to ask a competitor to service them. We establish strong connections between fair cost allocations and linear programming relaxations for several variants of the facility location problem. In particular, we show that a fair cost allocation exists if and only if there is no integrality gap for a corresponding linear programming relaxation; this was only known for the simplest unconstrained variant of the facility location problem. Moreover, we introduce a subtle variant of randomized rounding and derive new proofs for the existence of fair cost allocations for several classes of instances. We also show that it is in general NP-complete to decide whether a fair cost allocation exists and whether a given allocation is fair.     

两阶段选址优化问题研究

本文主要考虑如下实际问题:假设选址决策者需要建设p个设施,但是由于资金等等的影响,实际建设时会被要求先建设q个设施,其次再建设p-q个设施(设p>q),同时要求,在建设p-q个设施的时候,已经建设好的q个设施不被删除。本文建立了一个两阶段优化问题,问题的输出是两个待修建的设施的集合Fq,Fp,|Fp|=p,|Fq|=q,且Fq是Fp的子集,问题的目标是最小化这两个设施集合的费用同对应的最优费用的比值的最大值。本文给出一个近似比为9的近似算法,并对一些特殊的情况进行了讨论。所得结论对实际的选址决策具有理论意义,同时也完善已有相关研究结果。     

Balancing U-lines in a multiple U-line facility

U-shaped production lines and facilities consisting of many such lines are important parts of modem manufacturing systems. The problem of balancing and rebalancing U-line facilities is studied in this paper. Like the traditional line balancing problem this problem is NP-hard. The objective is to assign tasks to a minimum number of regular, crossover, and multiline stations while satisfying cycle time, precedence, location, and station-type constraints. A secondary objective is to concentrate the idle time in one station so that improvement efforts can be focused there in accordance with modern just-in-time principles. A reaching dynamic programming algorithm is presented for determining optimal balances. It is effective for balancing and rebalancing facilities with any number of U-lines, provided that individual U-lines do not have more than 22 tasks and do not have wide, sparse precedence graphs.