共查询到20条相似文献,搜索用时 0 毫秒
1.
Mark-Christoph Körner Juan A. Mesa Federico Perea Anita Schöbel Daniel Scholz 《TOP》2014,22(1):227-253
In this paper the following facility location problem in a mixed planar-network space is considered: We assume that traveling along a given network is faster than traveling within the plane according to the Euclidean distance. A pair of points (A i ,A j ) is called covered if the time to access the network from A i plus the time for traveling along the network plus the time for reaching A j is lower than, or equal to, a given acceptance level related to the travel time without using the network. The objective is to find facilities (i.e. entry and exit points) on the network that maximize the number of covered pairs. We present a reformulation of the problem using convex covering sets and use this formulation to derive a finite dominating set and an algorithm for locating two facilities on a tree network. Moreover, we adapt a geometric branch and bound approach to the discrete nature of the problem and suggest a procedure for locating more than two facilities on a single line, which is evaluated numerically. 相似文献
2.
Christoph E. Mandl 《European Journal of Operational Research》1980,5(6):396-404
So far, not much attention has been given to the problem of improving public transportation networks. In many cities these networks have been built sequentially and do not fit to the needs of the users any more. The results are long travel times and an unnecessarily high number of people who have to transfer. Compared to other investments for improving the service level of public transportation systems, the costs of rerouting the public vehicles are low and can, yet, highly improve the performance of the system.To evaluate a public transportation network, the shortest distance and the shortest route from node x to node y, taking the waiting times for a vehicle into account, must be known.It is shown in this paper, how to compute distances and routes efficiently for large networks. Using this algorithm it is described how to evaluate the average transportation cost of the passengers in a public transportation network.In the second part of the paper a heuristic algorithm is stated that improves a public transportation network using the average transportation cost as the objective.Finally, some experiences with real world problems are reported. 相似文献
3.
The problem of fair zone design for local public transportation networks is considered. A network model which was introduced by Hamacher and Schöbel in [2] is investigated. We present theoretical results for special transportation networks and heuristic algorithms for the general problem. 相似文献
4.
In this paper, we present the first model of co-opetition for a Hub Location Problem between two logistics service provider (LSPs) companies where the mother company is the owner of infrastructure. The LSPs would like to cooperate with each other by establishing joint edges with limited capacities connecting their service networks. Such services are in form of pendulum services (a direct service between two points) between nodes of different networks. Additional market can be generated as a result of joining the two networks. At the same time, a competition is taking place between the two operators to increase their share from the additional market generated. In order to solve this problem, we propose a matheuristic approach combining a local search algorithm and a Lagrangian relaxation-based approach. In our matheuristic algorithm, the neighbourhood solutions are evaluated using a Lagrangian relaxation-based approach. Numerical results of applying the proposed algorithm on a real case study of the problem are presented. 相似文献
5.
A supply chain design problem based on a two-echelon single-product system is addressed. The product is distributed from plants to distribution centers and then to customers. There are several transportation channels available for each pair of facilities between echelons. These transportation channels introduce a cost?Ctime tradeoff in the problem that allows us to formulate it as a bi-objective mixed-integer program. The decisions to be taken are the location of the distribution centers, the selection of the transportation channels, and the flow between facilities. Three variations of the classic ??-constraint method for generating optimal Pareto fronts are studied in this paper. The procedures are tested over six different classes of instance sets. The three sets of smallest size were solved completely obtaining their efficient solution set. It was observed that one of the three proposed algorithms consistently outperformed the other two in terms of their execution time. Additionally, four schemes for obtaining lower bound sets are studied. These schemes are based on linear programming relaxations of the model. The contribution of this work is the introduction of a new bi-objective optimization problem, and a computational study of the ??-constraint methods for obtaining optimal efficient fronts and the lower bounding schemes. 相似文献
6.
Pieter Vansteenwegen 《4OR: A Quarterly Journal of Operations Research》2009,7(3):293-296
This is a summary of the author’s Ph.D. thesis supervised by Dirk Van Oudheusden and Willy Herroelen and defended in May 2008 at the Katholieke Universiteit Leuven. The thesis is written in English and is available from the author upon request. In this work different operations research techniques are applied to solve several scheduling problems in two different domains. The first domain deals with improved passenger service in railway systems. The second domain deals with the automated selection of the most interesting tourist attractions by means of a hand-held personalised electronic tourist guide. 相似文献
7.
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. 相似文献
8.
In this paper, the optimal design and analysis of evacuation routes in transportation networks is examined. An methodology for optimal egress route assignment is suggested. An integer programming (IP) formulation for optimal route assignment is presented, which utilizes M/G/c/c state dependent queueing models to cope with congestion and time delays on road links. M/G/c/c simulation software is used to evaluate performance measures of the evacuation plan: clearance time, total travelled distance and blocking probabilities. Extensive experimental results are included. 相似文献
9.
We study the transit frequency optimization problem, which aims to determine the time interval between subsequent buses for a set of public transportation lines given by their itineraries, i.e., sequences of stops and street sections. The solution should satisfy a given origin–destination demand and a constraint on the available fleet of buses. We propose a new mixed integer linear programming (MILP) formulation for an already existing model, originally formulated as a nonlinear bilevel one. The proposed formulation is able to solve to optimality real small-sized instances of the problem using MILP techniques. For solving larger instances we propose a metaheuristic which accuracy is estimated by comparing against exact results (when possible). Both exact and approximated approaches are tested by using existing cases, including a real one related to a small-city which public transportation system comprises 13 lines. The magnitude of the improvement of that system obtained by applying the proposed methodologies, is comparable with the improvements reported in the literature, related to other real systems. Also, we investigate the applicability of the metaheuristic to a larger-sized real case, comprising more than 130 lines. 相似文献
10.
In the last several years, the modeling of emergency vehicle location has focussed on the temporal availability of the vehicles. Vehicles are not available for service when they are engaged in earlier calls. To incorporate this dynamic aspect into facility location decisions, models have been developed which provide additional levels of coverage. In this paper, two new models are derived from the probabilistic location set covering problem. These models allow the examination of the relationships between the number of facilities being located, the reliability that a vehicle will be available, and a coverage standard. In addition, these models incorporate sectoral specific estimates of the availability of the vehicles. Solution of these models reveals that the use of sectoral estimates leads to facility locations which are distributed to a greater spatial extent over the region to be serviced. 相似文献
11.
Olav Holst 《European Journal of Operational Research》1979,3(4):267-282
The subject of this paper is planning of public transportation in sparsely populated areas.The paper consists of four main parts. In part I an analysis of the system to be planned is carried out. A comparison with a survey on the traffic and transportation models available in the literature, though very voluminous, reveals a lack of a general model-framework for planning public transportation in sparsely populated areas. It is the aim of the present paper to fill this gap.Part II discusses how to evaluate optional plans for the physical and socio-economic structure of a region and concludes that this must be done by means of accessibility. Acessibility is defined in this paragraph.In part III a model is presented which describes the interdependance between on one hand the demand of accessibility of the population and on the other hand the transportation system, both public and private, and the location of facilities and residential areas. The applicability of some standard transportation and traffic models is discussed briefly in this section.Finally part IV describes a case study, in which the models set out in part III are applied. Some results are presented with conclusions. 相似文献
12.
13.
Polynomial-time algorithms are presented for solving combinatorial packing and covering problems defined from the integral feasible flows in an integral supply-demand network. These algorithms are also shown to apply to packing and covering problems defined by the minimal integral solutions to general totally unimodular systems. Analogous problems arising from matroid bases are also discussed and it is demonstrated that a means for solving such problems is provided by recent work of Cunningham. 相似文献
14.
Alfredo Marín Stefan Nickel Sebastian Velten 《Mathematical Methods of Operations Research》2010,71(1):125-163
To model flexible objectives for discrete location problems, ordered median functions can be applied. 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. In this paper a reformulated and more compact version of a covering model
for the discrete ordered median problem (DOMP) is considered. It is shown that by using this reformulation better solution
times can be obtained. This is especially true for some objectives that are often employed in location theory. In addition,
the covering model is extended so that ordered median functions with negative weights are feasible as well. This type of modeling
weights has not been treated in the literature on the DOMP before. We show that several discrete location problems with equity
objectives are particular cases of this model. As a result, a mixed-integer linear model for this type of problems is obtained
for the first time. 相似文献
15.
Antoon Kolen 《European Journal of Operational Research》1983,12(3):266-278
Given a tree network on n vertices, a neighborhood subtree is defined as the set of all points on the tree within a certain radius of a given point, called the center. It is shown that for any two neighborhood subtrees containing the same endpoint of a longest path in the tree one is contained in the other. This result is then used to obtain O(n2) algorithms for the minimum cost covering problem and the minimum cost operating problem as well as an O(n3) algorithm for the uncapacitated plant location problem on the tree. 相似文献
16.
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. 相似文献
17.
Ranko Bon 《European Journal of Operational Research》1977,1(2):85-89
Existing accessibility measures imply either a perfectly legible structure of the communication network, or a perfectly informed “visitor”. In the study of transportation networks (as well as in the study of large architectural complexes, for example) this implied assumption is extremely unrealistic. Markov chain is interpreted as a model of communication process, and an information-theoretic measure is derived for the measurement of accesibility in conditions of uncertainty of the visitor about the structure of the communication network. A number of elementary network patterns are compared using deterministic and probabilistic measures of accessibility. It is claimed that different patterns differ in the degree of susceptibility to uncertainty in the communication process. 相似文献
18.
Dariusz R. Kowalski Eyal Nussbaum Michael Segal Vitaly Milyeykovsky 《Optimization Letters》2014,8(2):777-799
In this paper we consider online scheduling problems for linear topology under various objective functions: minimizing the maximum completion time, minimizing the largest delay, and minimizing the sum of completion times. We give optimal solutions for uni-directional version of the problem for each of the objectives and show that for the two-directional versions of each problem, no online algorithm can deterministically achieve the optimal solution for any of the considered objective functions. We also propose 2-approximation on-line algorithms for the MinMakespan and the MinSum minimization objectives. We also prove that no online algorithm can deterministically achieve the optimal solution for any of the considered objective functions for the weighted case of uni-directional scenarios. 相似文献
19.
Hisaaki Nagase 《Applied Mathematical Modelling》1980,4(2):101-108
This paper treats an optimal control problem of automobile traffic flows in an oversaturated transportation network with a rectangular grid of intersections. All O-D (origin-destination) traffic flows are divided into portions at each origin and one route for travelling to the destination is assigned to the each portion. The traffic flows are controlled by the traffic signals placed at each intersection. Examples of numerical solutions, which are obtained by applying the linear-programming technique, are presented. The effect of route assignment for decreasing the traffic congestion is shown by the examples. 相似文献
20.
Previous covering models for emergency service consider all the calls to be of the same importance and impose the same waiting time constraints independently of the service's priority. This type of constraint is clearly inappropriate in many contexts. For example, in urban medical emergency services, calls that involve danger to human life deserve higher priority over calls for more routine incidents. A realistic model in such a context should allow prioritizing the calls for service. In this paper, a covering model which considers different priority levels is formulated and solved. The model heritages its formulation from previous research on Maximum Coverage Models and incorporates results from Queuing Theory, in particular Priority Queuing. The additional complexity incorporated in the model justifies the use of a heuristic procedure. 相似文献