共查询到20条相似文献,搜索用时 15 毫秒
1.
Natashia Boland Patricia Domínguez-Marín Stefan Nickel Justo Puerto 《Computers & Operations Research》2006
The discrete ordered median problem (DOMP) integrates classical discrete location problems, such as the N-median, N-center and Uncapacitated Facility Location problems. It was introduced by Nickel (In: Fleischmann B, Lasch R, Derigs U, Domschke W, Rieder U, editors. Operations Research Proceedings 2000, Berlin: Springer, 2001. p. 71–76), 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. 相似文献
2.
Andreas T. Ernst Horst Hamacher Houyuan Jiang Mohan Krishnamoorthy Gerhard Woeginger 《Computers & Operations Research》2009
The hub median problem is to locate hub facilities in a network and to allocate non-hub nodes to hub nodes such that the total transportation cost is minimized. In the hub center problem, the main objective is one of minimizing the maximum distance/cost between origin destination pairs. In this paper, we study uncapacitated hub center problems with either single or multiple allocation. Both problems are proved to be NP-hard. We even show that the problem of finding an optimal single allocation with respect to a given set of hubs is already NP-hard. We present integer programming formulations for both problems and propose a branch-and-bound approach for solving the multiple allocation case. Numerical results are reported which show that the new formulations are superior to previous ones. 相似文献
3.
Location of hub facilities and the allocation decisions in transport networks endogenously affect both the flow intensities and the transportation costs. Since the introduction of the hub location problem to the operations research literature in mid-1980s, many researchers investigated different ways of modelling the effects of hub facilities on the transportation costs. On the other hand, there has been very limited research on their effect on the flow intensities. This study proposes a new approach, inspired by the Bass diffusion model, to forecast the change in the demand patterns generated at different locations as a result of the placement of new hubs. This new model is used in the context of the uncapacitated single allocation p-hub median problem to investigate the effects of endogenous attraction, caused by the spatial interaction of present hubs, on future hub location decisions. Computational results indicate that the location and allocation decisions may be greatly affected when these forecasts are taken into account in the selection of future hub locations. 相似文献
4.
Meltem Peker Bahar Y. Kara James F. Campbell Sibel A. Alumur 《Networks and Spatial Economics》2016,16(4):1075-1101
Hubs are special facilities that serve as switching, transshipment and sorting nodes in many-to-many distribution systems. Flow is consolidated at hubs to exploit economies of scale and to reduce transportation costs between hubs. In this article, we first identify general features of optimal hub locations for single allocation hub location problems based on only the fundamental problem data (demand for travel and spatial locations). We then exploit this knowledge to develop a straightforward heuristic methodology based on spatial proximity of nodes, dispersion and measures of node importance to delineate subsets of nodes likely to contain optimal hubs. We then develop constraints for these subsets for use in mathematical programming formulations to solve hub location problems. Our methodology can also help narrow an organization’s focus to concentrate on more detailed and qualitative analyses of promising potential hub locations. Results document the value of including both demand magnitude and centrality in measuring node importance and the relevant tradeoffs in solution quality and time. 相似文献
5.
Hub location problems deal with finding the location of hub facilities and with the allocation of demand nodes to these located hub facilities. In this paper, we study the single allocation hub covering problem over incomplete hub networks and propose an integer programming formulation to this end. The aim of our model is to find the location of hubs, the hub links to be established between the located hubs, and the allocation of non-hub nodes to the located hub nodes such that the travel time between any origin–destination pair is within a given time bound. We present an efficient heuristic based on tabu search and test the performance of our heuristic on the CAB data set and on the Turkish network. 相似文献
6.
Inmaculada Espejo Alfredo Marín Justo Puerto Antonio M. Rodríguez-Chía 《Computers & Operations Research》2009
We consider a discrete facility location problem with a new form of equity criterion. The model discussed in the paper analyzes the case where demand points only have strict preference order on the sites where the plants can be located. The goal is to find the location of the facilities minimizing the total envy felt by the entire set of demand points. We define this new total envy criterion and provide several integer linear programming formulations that reflect and model this approach. The formulations are illustrated by examples. Extensive computational tests are reported, showing the potentials and limits of each formulation on several types of instances. Finally, some improvements for all the formulations previously presented are developed, obtaining in some cases much better resolution times. 相似文献
7.
A different approach to the capacitated single allocation hub location problem is presented. Instead of using capacity constraints to limit the amount of flow that can be received by the hubs, we introduce a second objective function to the model (besides the traditional cost minimizing function), that tries to minimize the time to process the flow entering the hubs. Two bi-criteria single allocation hub location problems are presented: in a first model, total time is considered as the second criteria and, in a second model, the maximum service time for the hubs is minimized. To generate non-dominated solutions an interactive decision-aid approach developed for bi-criteria integer linear programming problems is used. Both bi-criteria models are tested on a set of instances, analyzing the corresponding non-dominated solutions set and studying the reasonableness of the hubs flow charge for these non-dominated solutions. The increased information provided by the non-dominated solutions of the bi-criteria model when compared to the unique solution given by the capacitated hub location model is highlighted. 相似文献
8.
Reza Zanjirani Farahani Masoud Hekmatfar Alireza Boloori Arabani Ehsan Nikbakhsh 《Computers & Industrial Engineering》2013,64(4):1096-1109
Hub location problem (HLP) is a relatively new extension of classical facility location problems. Hubs are facilities that work as consolidation, connecting, and switching points for flows between stipulated origins and destinations. While there are few review papers on hub location problems, the most recent one (Alumur and Kara, 2008. Network hub location problems: The state of the art. European Journal of Operational Research, 190, 1–21) considers solely studies on network-type hub location models prior to early 2007. Therefore, this paper focuses on reviewing the most recent advances in HLP from 2007 up to now. In this paper, a review of all variants of HLPs (i.e., network, continuous, and discrete HLPs) is provided. In particular, mathematical models, solution methods, main specifications, and applications of HLPs are discussed. Furthermore, some case studies illustrating real-world applications of HLPs are briefly introduced. At the end, future research directions and trends will be presented. 相似文献
9.
Víctor G. Alfaro‐García José M. Merigó Anna M. Gil‐Lafuente Janusz Kacprzyk 《国际智能系统杂志》2018,33(7):1488-1506
The Hamming distance is a well‐known measure that is designed to provide insights into the similarity between two strings of information. In this study, we use the Hamming distance, the optimal deviation model, and the generalized ordered weighted logarithmic averaging (GOWLA) operator to develop the ordered weighted logarithmic averaging distance (OWLAD) operator and the generalized ordered weighted logarithmic averaging distance (GOWLAD) operator. The main advantage of these operators is the possibility of modeling a wider range of complex representations of problems under the assumption of an ideal possibility. We study the main properties, alternative formulations, and families of the proposed operators. We analyze multiple classical measures to characterize the weighting vector and propose alternatives to deal with the logarithmic properties of the operators. Furthermore, we present generalizations of the operators, which are obtained by studying their weighting vectors and the lambda parameter. Finally, an illustrative example regarding innovation project management measurement is proposed, in which a multi‐expert analysis and several of the newly introduced operators are utilized. 相似文献
10.
With the development and widespread use of large-scale nonlinear programming (NLP) tools for process optimization, there has been an associated application of NLP formulations with complementarity constraints in order to represent discrete decisions. In particular, these constraints arise frequently in equation-based formulations for real-time optimization. Also known as mathematical programs with equilibrium constraints (MPECs), these formulations can be used to model certain classes of discrete events and can be more efficient than a mixed integer formulation, particularly for large systems with many discrete decisions, such as dynamic systems with switches at any point in time. In this study, we consider and extend MPEC formulations for the optimization of a class of hybrid dynamic models, where the differential states remain continuous over time. These include differential inclusions of the Filippov type. Here, particular care is required in the formulation in order to preserve smoothness properties of the dynamic system. Results on three case studies, including process control examples, illustrate the effectiveness and accuracy of the proposed MPEC optimization methodology for a class of hybrid dynamic systems. 相似文献
11.
The geometric segmentation of a discrete geometric model obtained by the scanning of real objects is affected by various problems that make the segmentation difficult to perform without uncertainties. Certain factors, such as point location noise (coming from the acquisition process) and the coarse representation of continuous surfaces due to triangular approximations, introduce ambiguity into the recognition process of the geometric shape. To overcome these problems, a new method for geometric point identification and surface segmentation is proposed.The point classification is based on a fuzzy parameterization using three shape indexes: the smoothness indicator, shape index and flatness index. A total of 11 fuzzy domain intervals have been identified and comprise sharp edges, defective zones and 10 different types of regular points. For each point of the discrete surface, the related membership functions are dynamically evaluated to be adapted to consider, point by point, those properties of the geometric model that affects uncertainty in point type attribution.The methodology has been verified in many test cases designed to represent critical conditions for any method in geometric recognition and has been compared with one of the most robust methods described in the related literature. 相似文献
12.
Online Clustering with Variable Sized Clusters 总被引:1,自引:0,他引:1
Online clustering problems are problems where the classification of points into sets (called clusters) is performed in an online fashion. Points arrive at arbitrary locations, one by one, to be assigned to clusters at the time of arrival. A point can be either assigned to an existing cluster or a new cluster can be opened for it. Here, we study a one-dimensional variant on a line. Each cluster is a closed interval, and there is no restriction on the length of a cluster. The cost of a cluster is the sum of a fixed set-up cost and its diameter (or length). The goal is to minimize the sum of costs of the clusters used by the algorithm. We study several variants, each having the two essential properties that a point which has been assigned to a given cluster must remain assigned to that cluster and no pair of clusters can be merged. In the strict variant, the diameter and the exact location of the cluster must be fixed when it is initialized. In the flexible variant, the algorithm can shift the cluster or expand it, as long as it contains all points assigned to it. In an intermediate model, the diameter is fixed in advance but the exact location can be modified. Here we give tight bounds on the competitive ratio of any online algorithm in each of these variants. In addition, for each model we also consider the semi-online case where points are presented ordered by their location. 相似文献
13.
14.
15.
This paper deals with a two-level facility location–allocation problem on tree topology arising from the design of access networks. The access network design problem seeks to find an optimal location of switch and allocation of demands such that the total cost of switch and fiber cable is minimized, while satisfying switch port constraint, switch capacity constraint, and no-split routing constraint. The problem is formulated as a mixed-integer programming model and alternative formulations are developed by the reformulation-linearization technique (RLT) for improving computational effectiveness. By exploiting the tree structure of the problem, we develop some valid inequalities that have complementary strength and devise separation problems for finding effective valid inequalities that cut off fractional LP solutions. Also, we develop an effective MIP-based tree partitioning heuristic for finding good quality solutions for large size problems. Computational results demonstrate the efficacy of the valid inequalities and the proposed heuristic. 相似文献
16.
《Computers & Operations Research》2002,29(6):715-739
HubLocator is a new branch-and-bound procedure for the uncapacitated multiple allocation hub location problem. An existing optimal method developed by Klincewicz (Location Sci. 4 (1996) 173) is based on dual ascent and dual adjustment techniques applied to a disaggregated model formulation. These techniques have already successfully been used to solve the closely related simple plant location problem. However, due to the specific structure of the problem at hand, the success of these techniques in reducing the computational effort is rather restricted. Therefore, HubLocator additionally considers an aggregated model formulation enabling us to significantly tighten the lower bounds. Upper bounds which satisfy complementary slackness conditions for some constraints are constructed and improved by means of a simple heuristic procedure. Computational experiments demonstrate that optimal solutions for problems with up to 40 nodes can be found in a reasonable amount of time.Scope and purposeGround and air transportation networks, postal delivery networks, and computer networks are often configured as hub-and-spoke systems. Traffic between two locations is not transported directly between these locations, but routed via particular switching or consolidation points called hubs. Due to increased traffic on linkages between hubs, larger vehicles can be used or the capacity of existing vehicles can be utilized more efficiently, resulting in smaller per unit transportation costs. The exploitation of scale economies as a result of the reduced number of linkages, which have to be operated in a hub-and-spoke system, compared to a fully interconnected network is an important advantage of this type of system.Designing hub-and-spoke networks deals with the selection of hubs from a given set of potential locations and the routing of traffic. We consider a special type of such a hub location problem and adapt a successful technique developed to find an optimal solution for the well-known simple plant location problem. 相似文献
17.
A new trapezoidal Pythagorean fuzzy linguistic entropic combined ordered weighted averaging operator and its application for enterprise location
下载免费PDF全文
![点击此处可从《国际智能系统杂志》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Recently some new models based on Pythagorean fuzzy sets (PFSs) have been proposed to deal with the uncertainty in multiple attribute group decision making (MAGDM) problems. In this paper, considering linguistic variables and entropic, we propose a new trapezoidal Pythagorean fuzzy linguistic entropic combined ordered weighted averaging operator to solve MAGDM problems. Next, we study some main properties by utilizing some operational laws of the trapezoidal Pythagorean fuzzy linguistic variables. Finally, a numerical example concerning the enterprise location is given to illustrate the practicality and effectiveness of the proposed operator. 相似文献
18.
Fire and rescue services are among the most critical public services provided by governments to protect people, property and the environment from fires and other emergencies. Efficient deployment of fire stations is essential to ensure timely response to calls for service. Given the geographic nature of such problems, spatial optimization approaches have long been employed in public facility location modeling along these lines. In particular, median and coverage approaches have been widely adopted to help achieve travel-cost and service-coverage goals, respectively. This paper proposes a bi-objective spatial optimization model that integrates coverage and median goals in the service of demand areas. Based on the properties of derived objective functions, we presented a constraint-based solution procedure to generate the Pareto frontier, enabling the identification of alternative fire station siting scenarios. The developed model is applied to an empirical study that seeks to identify the best fire station locations in Nanjing, China. The results demonstrate the value of spatial optimization in assisting fire station planning and rescue resource deployment, highlighting important policy implications. 相似文献
19.
《Computers & Operations Research》2005,32(4):967-984
Hub location problems are widely studied in the area of location theory, where they involve locating the hub facilities and designing the hub networks. In this paper, we present a new and robust solution based on a genetic search framework for the uncapacitated single allocation hub location problem (USAHLP). To present its effectiveness, we compare the solutions of our GA-based method with the best solutions presented in the literature by considering various problem sizes of the CAB data set and the AP data set. The experimental work demonstrates that even for larger problems the results of our method significantly surpass those of the related work with respect to both solution quality and the CPU time to obtain a solution. Specifically, the results from our method match the optimal solutions found in the literature for all test cases generated from the CAB data set with significantly less running time than the related work. For the AP data set, our solutions match the best solutions of the reference study with an average of 8 times less running time than the reference study. Its performance, robustness and substantially low computational effort justify the potential of our method for solving larger problem sizes. 相似文献
20.
Some methods for strategic decision‐making problems with immediate probabilities in Pythagorean fuzzy environment
下载免费PDF全文
![点击此处可从《国际智能系统杂志》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Harish Garg 《国际智能系统杂志》2018,33(4):687-712
In this article, a new decision‐making model with probabilistic information and using the concept of immediate probabilities has been developed to aggregate the information under the Pythagorean fuzzy set environment. In it, the existing probabilities have been modified by introducing the attitudinal character of the decision maker by using an ordered weighted average operator. Based on it, we have developed some new probabilistic aggregation operator with Pythagorean fuzzy information, namely probabilistic Pythagorean fuzzy weighted average operator, immediate probability Pythagorean fuzzy ordered weighted average operator, probabilistic Pythagorean fuzzy ordered weighted average, probabilistic Pythagorean fuzzy weighted geometric operator, immediate probability Pythagorean fuzzy ordered weighted geometric operator, probabilistic Pythagorean fuzzy ordered weighted geometric, etc. Furthermore, we extended these operators by taking interval‐valued Pythagorean fuzzy information and developed their corresponding aggregation operators. Few properties of these operators have also been investigated. Finally, an illustrative example about the selection of the optimal production strategy has been given to show the utility of the developed method. 相似文献