校车安排问题

探讨如何安排校车运行使得教师和工作人员尽量满意的问题.首先建立动态规划模型和选址规划模型,求出合理站点位置及其总距离.然后用归一法定义满意度与距离的函数关系,考虑各区域人数,建立选址规划模型.得到合理站点位置和总满意度.之后建立双目标非线性规划模型,利用量纲分析法给出权重,以此求出合理乘车位置和满意度.最后对问题进行推...     

Sequential competitive location on networks

We present a survey of recent developments in the field of sequential competitive location problems, including the closely related class of voting location problems, i.e. problems of locating resources as the result of a collective election. Our focus is on models where possible locations are not a priori restricted to a finite set of points. Furthermore, we restrict our attention to problems defined on networks. Since a line, i.e. an interval of one-dimensional real space, may be interpreted as a special type of network and because models defined on lines might contain ideas worth adopting in more general network models, we include these models as well, yet without describing them in detail for the sake of brevity.     

On solving the discrete location problems when the facilities are prone to failure

The classical discrete location problem is extended here, where the candidate facilities are subject to failure. The unreliable location problem is defined by introducing the probability that a facility may become inactive. The formulation and the solution procedure have been motivated by an application to model and solve a large size problem for locating base stations in a cellular communication network. We formulate the unreliable discrete location problems as 0–1 integer programming models, and implement an enhanced dual-based solution method to determine locations of these facilities to minimize the sum of fixed cost and expected operating (transportation) cost. Computational tests of some well-known problems have shown that the heuristic is efficient and effective for solving these unreliable location problems.     

Edge-minimization of non-deterministic finite automata

In this paper we consider non-deterministic finite Rabin-Scott’s automata. We use a special structure to describe all the possible edges of non-deterministic finite automaton defining the given regular language. Such structure can be used for solving various problems of finite automata theory. One of these problems is edge-minimization of non-deterministic automata. As we have not touched this problem before, we obtain here two versions of the algorithm for solving this problem to continue previous series of articles.     

Deterministic flow-demand location problems

In flow-covering (interception) models the focus is on the demand for service that originates from customers travelling in the network (not for the purpose of obtaining the service). In contrast, in traditional location models a central assumption is that the demand for service comes from customers residing at nodes of the network. In this paper we combine these two types of models. The paper presents four new problems. Two of the four deal with the problem of locating m facilities so as to maximize the total number of potential customers covered by the facilities (where coverage does not necessarily imply the actual consumption of service). In the two other problems the attention is directed to the consumption of service and thus the criteria is to maximize (minimize) the number of actual users (distance travelled). It is shown in the paper that all four problems have similar structure to other known location problems.     

A computational evaluation of a general branch-and-price framework for capacitated network location problems

The purpose of this paper is to illustrate a general framework for network location problems, based on column generation and branch-and-price. In particular we consider capacitated network location problems with single-source constraints. We consider several different network location models, by combining cardinality constraints, fixed costs, concentrator restrictions and regional constraints. Our general branch-and-price-based approach can be seen as a natural counterpart of the branch-and-cut-based commercial ILP solvers, with the advantage of exploiting the tightness of the lower bound provided by the set partitioning reformulation of network location problems. Branch-and-price and branch-and-cut are compared through an extensive set of experimental tests.     

Possible edges of a finite automaton defining a given regular language

In this paper we consider non-deterministic finite Rabin-Scott’s automata. We define special abstract objects, being pairs of values of states-marking functions. On the basis of these objects as the states of automaton, we define its edges; the obtained structure is considered also as a non-deterministic automaton. We prove, that any edge of any non-deterministic automaton defining the given regular language can be obtained by such techniques. Such structure can be used for solving various problems in the frames of finite automata theory.     

Outbound supply chain network design with mode selection,lead times and capacitated vehicle distribution centers

Most distribution network design models considered to date have focused on minimizing fixed costs of facility location and transportation costs. Measures of customer satisfaction driven by the operational dynamics such as lead times have seldom been considered. We consider the design of an outbound supply chain network considering lead times, location of distribution facilities and choice of transportation mode. We present a Lagrangian heuristic that gives excellent solution quality in reasonable computational time. Scenario analyses are conducted on industrial data using this algorithm to observe how the supply chain behaves under different parameter values.     

The minmax regret gradual covering location problem on a network with incomplete information of demand weights

The gradual covering location problem seeks to establish facilities on a network so as to maximize the total demand covered, allowing partial coverage. We focus on the gradual covering location problem when the demand weights associated with nodes of the network are random variables whose probability distributions are unknown. Using only information on the range of these random variables, this study is aimed at finding the “minmax regret” location that minimizes the worst-case coverage loss. We show that under some conditions, the problem is equivalent to known location problems (e.g. the minmax regret median problem). Polynomial time algorithms are developed for the problem on a general network with linear coverage decay functions.     

Filtering Policies in Loss Queuing Network Location Problems

In this paper we deal with two stationary loss queuing network location models. We analyze the influence of filtering policies on the locational aspect of the problems. We assume that requests for service are placed at nodes of a transportation network and they arrive in time as independent homogeneous Poisson processes with different input rates. The considered policies only cover a given proportion of requests even if there are idle service units. This proportion is stationary and fixed in advance and only depends on the node where the request is originated. The objective is to find the location of the facilities together with the filtering policy to be applied that minimize the expected total cost per unit time with respect to a given cost structure. Properties and computational results are presented enabling the resolution of these problems efficiently and showing the good performance of filtering policies in terms of both the overall operating costs, and the demand that is served.     

A specialized branch & bound & cut for Single-Allocation Ordered Median Hub Location problems

The Single-Allocation Ordered Median Hub Location problem is a recent hub model introduced by Puerto et al. (2011) [32] that provides a unifying analysis of the class of hub location models. Indeed, considering ordered objective functions in hub location models is a powerful tool in modeling classic and alternative location paradigms, that can be applied with success to a large variety of problems providing new distribution patterns induced by the different users’ roles within the supply chain network. In this paper, we present a new formulation for the Single-Allocation Ordered Median Hub Location problem and a branch-and-bound-and-cut (B&B&Cut) based algorithm to solve optimally this model. A simple illustrative example is discussed to demonstrate the technique, and then a battery of test problems with data taken from the AP library are solved. The paper concludes that the proposed B&B&Cut approach performs well for small to medium sized problems.     

The Ordered Gradual Covering Location Problem on a Network

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. The Ordered Median Location problem is a generalization of most of the classical locations problems like p-median or p-center problems. The OGCLP model provides a unifying structure for the standard location models and allows us to develop objectives sensitive to both relative and absolute customer-to-facility distances. 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 is 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.     

Fuzzy facility location problem with preference of candidate sites

Models so far considered as facility location problems treat either min–max or max–min criterion, that is, the facility is either desirable or undesirable. We propose the following model considering the satisfaction degree with respect to the distance from the facility for each customer (residents) and preference of the site in an urban area. The objective is to find the site of the facility which maximizes the minimal satisfaction degree among all demand points and maximizes the preference of the site. Since generally speaking, there exists no site that maximizes both criteria, we seek non-dominated sites after defining non-domination.     

General network design: A unified view of combined location and network design problems

This paper presents a unified framework for the general network design problem which encompasses several classical problems involving combined location and network design decisions. In some of these problems the service demand relates users and facilities, whereas in other cases the service demand relates pairs of users between them, and facilities are used to consolidate and re-route flows between users. Problems of this type arise in the design of transportation and telecommunication systems and include well-known problems such as location-network design problems, hub location problems, extensive facility location problems, tree-star location problems and cycle-star location problems, among others. Relevant modeling aspects, alternative formulations and possible algorithmic strategies are presented and analyzed.     

Facility location models for planning a transatlantic communications network

This paper presents two facility location models for the problem of determining how to optimally serve the requirements for communication circuits between the United States and various European and Middle Eastern countries. Given a projection of future requirements, the problem is to plan for the economic growth of a communications network to satisfy these requirements. Both satellite and submarine cable facilities may be used. The objective is to find an optimal placement of cables (type, location, and timing) and the routing of individual circuits between demand points (over both satellites and cables) such that the total discounted cost over a T-period horizon is minimized. This problem is cast as a multiperiod, capacitated facility location problem. Two mathematical models differing in their provisions for network reliability are presented. Solution approaches are outlined and compared by means of computational experience. Use of the models both in planning the growth of the network and in the economic evaluation of different cable technologies is also discussed.     

Improving solution of discrete competitive facility location problems

We consider discrete competitive facility location problems in this paper. Such problems could be viewed as a search of nodes in a network, composed of candidate and customer demand nodes, which connections correspond to attractiveness between customers and facilities located at the candidate nodes. The number of customers is usually very large. For some models of customer behavior exact solution approaches could be used. However, for other models and/or when the size of problem is too high to solve exactly, heuristic algorithms may be used. The solution of discrete competitive facility location problems using genetic algorithms is considered in this paper. The new strategies for dynamic adjustment of some parameters of genetic algorithm, such as probabilities for the crossover and mutation operations are proposed and applied to improve the canonical genetic algorithm. The algorithm is also specially adopted to solve discrete competitive facility location problems by proposing a strategy for selection of the most promising values of the variables in the mutation procedure. The developed genetic algorithm is demonstrated by solving instances of competitive facility location problems for an entering firm.     

On solving complex multi-period location models using simulated annealing

This paper describes a study aimed at evaluating the capabilities of simulated annealing in dealing with complex, real-world multi-period location problems raised by school network planning in Portugal. The problems were formulated as mixed-integer linear optimization models. The models allow for facility closure or size reduction besides facility opening and size expansion, with sizes possibly limited to a set of pre-defined standards. They assume facility costs to be divided into a fix component and two variable components, respectively dependent on facility size and facility attendance. Results obtained through the study indicate that simulated annealing can be a useful tool for solving these kinds of models.     

Continuous covering and cooperative covering problems with a general decay function on networks

A cooperative covering location problem anywhere on the networks is analysed. Each facility emits a signal that decays by the distance along the arcs of the network and each node observes the total signal emitted by all facilities. A node is covered if its cumulative signal exceeds a given threshold. The cooperative approach differs from traditional covering models where the signal from the closest facility determines whether or not a point is covered. The objective is to maximize coverage by the best location of facilities anywhere on the network. The problems are formulated and analysed. Optimal algorithms for one or two facilities are proposed. Heuristic algorithms are proposed for location of more than two facilities. Extensive computational experiments are reported.     

A continuous covering location model with risk consideration

This paper proposes a continuous covering location model with risk consideration. The investigated model is an extension of the discrete covering location models in continuous space. The objective function consists of installation and risk costs. Because of uncertain covering radius, customer satisfaction degree of covering radius is introduced by fuzzy concept. Since, the uncertainty may cause risk of uncovering customers; the risk cost is added to the objective function. The installation cost is assigned to a zone with a predetermined radius from its center. The model is solved by a fuzzy method named α$\alpha$-cut. After solving the model based on different α$\alpha$-values, the zones with the largest possibilities are determined for locating new facilities and the best locations are calculated based on the obtained possibilities. Then, the model is solved to determine the best covering values. This paper, also introduces a risk analysis method based on Response Surface Methodology (RSM) to consider risk management in the location models. Finally, a numerical example is expressed to illustrate the proposed model.     

<Emphasis Type="Italic">k</Emphasis>-Phase Oscillator Synchronization for Graph Coloring

This paper investigates ways of applying oscillator synchronization to graph coloring. A previous method based on the generalization of the Aihara model is sensitive to the varying degree of the vertices in the graph and there is a strong tendency for the network to form suboptimal limit cycles on regular graphs. Other models such as those by Wu and Nakaguchi, Jin’no and Tanaka do not generalize well into greater than 2-coloring. In this paper, we present ways to overcome these problems and describe the results of our experiments on graphs requiring more than two colors. Our k-phase model enhances the coloring performance over the previous similar models. We further attempt to formalize and analyze the categorical behavior of these systems and discuss connections to other optimization methods.