Integrated use of fuzzy c-means and convex programming for capacitated multi-facility location problem

In this study a fuzzy c-means clustering algorithm based method is proposed for solving a capacitated multi-facility location problem of known demand points which are served from capacitated supply centres. It involves the integrated use of fuzzy c-means and convex programming. In fuzzy c-means, data points are allowed to belong to several clusters with different degrees of membership. This feature is used here to split demands between supply centers. The cluster number is determined by an incremental method that starts with two and designated when capacity of each cluster is sufficient for its demand. Finally, each group of cluster and each model are solved as a single facility location problem. Then each single facility location problem given by fuzzy c-means is solved by convex programming which optimizes transportation cost is used to fine-tune the facility location. Proposed method is applied to several facility location problems from OR library (Osman & Christofides, 1994) and compared with centre of gravity and particle swarm optimization based algorithms. Numerical results of an asphalt producer’s real-world data in Turkey are reported. Numerical results show that the proposed approach performs better than using original fuzzy c-means, integrated use of fuzzy c-means and center of gravity methods in terms of transportation costs.     

Heuristics for a continuous multi-facility location problem with demand regions

We consider a continuous multi-facility location allocation problem where the demanding entities are regions in the plane instead of points. The problem can be stated as follows: given m (closed, convex) polygonal demand regions in the plane, find the locations of q facilities and allocate each region to exactly one facility so as to minimize a weighted sum of squares of the maximum Euclidean distances between the demand regions and the facilities they are assigned to.We propose mathematical programming formulations of the single and multiple facility versions of the problem considered. The single facility location problem is formulated as a second order cone programming (SOCP) problem, and hence is solvable in polynomial time. The multiple facility location problem is NP-hard in general and can be formulated as a mixed integer SOCP problem. This formulation is weak and does not even solve medium-size instances. To solve larger instances of the problem we propose three heuristics. When all the demand regions are rectangular regions with their sides parallel to the standard coordinate axes, a faster special heuristic is developed. We compare our heuristics in terms of both solution quality and computational time.     

A hierarchical algorithm for the planar single-facility location routing problem

Location routing problem (LRP) is an important logistical problem that comprises two of the main logistical drivers namely facility location and vehicle routing. In this paper, we focus on the planar single-facility LRP with Euclidean distance where the location of the facility can be anywhere in the space and not restricted to a given set of potential sites only as in the discrete case. A hierarchical heuristic-based method is put forward which continuously takes into account the information from the routing results while systematically improving the location using the end-points of the obtained routes. In addition, some enhancement schemes that include a set of local searches as well as diversification and intensification mechanisms are also incorporated into the search. The proposed method outperformed the existing approaches when tested on the data sets taken from the literature. Our approach produced nine new best results out of the fifteen in the literature besides being relatively robust when compared to the existing methods.     

A credibility-based fuzzy location model with Hurwicz criteria for the design of distribution systems in B2C e-commerce

Facility location problem is one of the most critical elements in the design of distribution systems, and numerous studies have focused on this issue. However, facility location theory and guidelines for B2C firms are sparse. In this paper, with regard to the customer characteristics peculiar to B2C e-commerce and the turbulence of the competitive market, a new fuzzy location model is proposed to optimize the distribution system design in B2C e-commerce. The model adopts a hierarchical agglomerative clustering method to classify customers and estimate the fuzzy delivery cost. At the same time, due to the turbulence of competitive market, both market supply and customer demand are treated as fuzzy variables in the model. Afterward, the credibility measure and Hurwicz criterion are introduced to convert the model into a crisp one which has NP-hard complexity. In order to solve the crisp model, an improved genetic algorithm with particle swarm optimization is developed. Finally, the computational results of some numerical examples are used to illustrate the application and performance of the proposed model and algorithm.     

Solving fuzzy capacitated location routing problem using hybrid variable neighborhood search and evolutionary local search

A fuzzy capacitated location routing problem (FCLRP) is solved by using a heuristic method that combines variable neighborhood search (VNS) and evolutionary local search (ELS). Demands of the customer and travel times between customers and depots are considered as fuzzy and deterministic variables, respectively in FCLRP. Heterogeneous and homogeneous fleet sizes are performed together to reach the least multi-objective cost in a case study. The multi-objective cost consists of transportation cost, additional cost, vehicle waiting cost and delay cost. A fuzzy chance constrained programming model is added by using credibility theory. The proposed method reaches the solution by performing four stages. In the first stage, initial solutions are obtained by using a greedy heuristic method, and then VNS heuristic, which consists of seven different neighborhood structures, is performed to improve the solution quality in the second stage. In the third stage, a perturbation procedure is applied to the improved solution using ELS algorithm, and then VNS heuristic is applied again in the last stage. The combination of VNS and ELS is called VNSxELS algorithm and applied to a case study, which has fifty-seven customers and five distributing points, effectively in a reasonable time.     

A fuzzy approach for the reviewer assignment problem

Assignment of experts to project proposals is a significant task for funding agencies which have to assess the potential value of the research and development (R&D) projects through peer review. The problem is known as reviewer assignment problem and has real-world applications in funding agencies, conferences and research journals. Given a set of experts and a set of proposals; the problem can be defined as assigning the most suitable experts to the proposals under some constraints, which are generally encountered by funding agencies. In this study, a fuzzy model is offered to solve the reviewer assignment problem. The objective of the model is to maximize the total matching degree of assigned experts under some constraints such as cost of forming a panel and the size of a panel. The matching degrees are defined using linguistic variables to denote the expertise of each expert with respect to each proposal. The fuzzy mathematical model, which also takes into account different constraints related to the problem, is solved via the selected fuzzy ranking methods namely; the signed distance method and the method of ranking fuzzy numbers with integral value. The solution of an example problem – inspired from a real-life situation – with both of the mentioned methods revealed the effectiveness of the solution approach. It is believed that the use of the offered fuzzy approach could improve the accuracy of the decisions made by funding agencies.     

A tabu search-based algorithm for the fuzzy clustering problem

The Fuzzy Clustering Problem (FCP) is a mathematical program which is difficult to solve since it is nonconvex, which implies possession of many local minima. The fuzzy C-means heuristic is the widely known approach to this problem, but it is guaranteed only to yield local minima. In this paper, we propose a new approach to this problem which is based on tabu search technique, and aims at finding a global solution of FCP. We compare the performance of the algorithm with the fuzzy C-means algorithm.     

A fuzzy clustering method for generating fuzzy models

A systematic fuzzy approach considering both accuracy and interpretability is developed in the paper. First, a fuzzy modeling method based on a new objective function is proposed. The proposed method can deal with the problem where the input variables have an affect on the input space of the fuzzy system while the output variables do not exert any influence on input space of fuzzy system. Then rule reduction is performed to obtain the model structure of the fuzzy system by QR decomposition of the fuzzy reference matrix. According to analysis of the rank loss of the matrix, the important rules and unimportant rules can be confirmed in this paper. Simulation results demonstrate that the proposed approach can be used to build fuzzy models of nonlinear systems. Copyright © 2008 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

模糊需求下物流系统CLRIP 问题研究

从物流系统集成的角度出发．考虑到客户需求的模糊性，建立了多仓库单级物流配送系统中的设施选址、车辆运输路线安排、库存控制的集成优化模型．用来解决在给定的多个潜在设施点中选出一系列设施的位置．并确定巡回运输路线．同时基于客户所采用的单时期模糊需求存贮策略确定其最佳订货量，并给出了求解该模型的启发式算法．最后通过实例计算证明了上述模型和算法的有效性．     

A fuzzy multi-objective covering-based vehicle location model for emergency services

Timeliness is one of the most important objectives that reflect the quality of emergency services such as ambulance and firefighting systems. To provide timeliness, system administrators may increase the number of service vehicles available. Unfortunately, increasing the number of vehicles is generally impossible due to capital constraints. In such a case, the efficient deployment of emergency service vehicles becomes a crucial issue. In this paper, a multi-objective covering-based emergency vehicle location model is proposed. The objectives considered in the model are maximization of the population covered by one vehicle, maximization of the population with backup coverage and increasing the service level by minimizing the total travel distance from locations at a distance bigger than a prespecified distance standard for all zones. Model applications with different solution approaches such as lexicographic linear programming and fuzzy goal programming (FGP) are provided through numerical illustrations to demonstrate the applicability of the model. Numerical results indicate that the model generates satisfactory solutions at an acceptable achievement level of desired goals.     

A heuristic method for large-scale multi-facility location problems

A heuristic method for solving large-scale multi-facility location problems is presented. The method is analogous to Cooper's method (SIAM Rev. 6 (1964) 37), using the authors’ single facility location method (Comput. Optim. Appl. 21 (2002) 213) as a parallel subroutine, and reassigning customers to facilities using the heuristic of nearest center reclassification. Numerical results are reported. Scope and purpose We study the multiple facility location problem (MFLP). The objective in MFLP is to locate facilities to serve optimally a given set of customers. MFLPs have many applications in Operations Research, and a rich literature, see Drezner (Location Sci. 3(4) (1995) 275) for a recent survey.MFLPs involve, in addition to the location decision, also the assignment of customers to facilities. The MFLP is therefore a special clustering problem, the clusters here are the sets of customers assigned to the same facility.We propose a parallel heuristic method for solving MFLPs, using ideas from cluster analysis (nearest mean reclassification (Cluster Analysis, 3rd Edition, Edward Arnold, London, 1993)), and the authors’ Newton bracketing method for convex minimization (Comput. Optim. Appl. 21 (2002) 213) as a subroutine. The method is suitable for large-scale problems, as illustrated by numerical examples.     

基于仿射传播聚类的大规模选址布局问题求解*

选址布局问题是一个广泛研究的运筹学问题。通过将选址布局问题看做聚类问题,结合仿射传播聚类算法并且将候选地址的信息映射为特征向量,提出了两种求解选址布局问题的方法：基于块划分的选址布局方法和基于道路网络的选址布局方法。使用模拟数据集和真实数据集来评估两种方法,实验结果表明两种方法都能够求解设施资源受限和不受限情况下的选址布局问题,而且可以很好地解决大规模的选址布局问题。     

An interactive possibilistic programming approach for a multi-objective hub location problem: Economic and environmental design

This paper presents a new multi-objective mathematical model for a multi-modal hub location problem under a possibilistic-stochastic uncertainty. The presented model aims to minimize the total transportation and traffic noise pollution costs. Furthermore, it aims to minimize the maximum transportation time between origin-destination nodes to ensure a high probability of meeting the service guarantee. In order to cope with the uncertainties and the multi-objective model, we propose a two-phase approach, including fuzzy interactive multi-objective programming approach and an efficient method based on the Me measure. Due to the NP-hardness of the presented model, two meta-heuristic algorithms, namely hybrid differential evolution and hybrid imperialist competitive algorithm, are developed. Furthermore, a number of sensitivity analyses are provided to demonstrate the effectiveness of the presented model. Finally, the foregoing meta-heuristics are compared together through different comparison metrics.     

A hybrid solution method for fuzzy train formation planning

The train formation plan (TFP) determines the routing and frequency of trains, and assigns the demands to trains. In this paper, in order to consider the real-life condition of railways, a mathematical model with fuzzy costs is proposed for train formation planning in Iranian railway. In this fuzzy model, the costs are considered in three scenarios, namely optimistic, normal and pessimistic. The model is formulated based on the fixed-charge capacitated multicommodity network design problem. Since the TFP problem is NP-hard, an efficient hybrid algorithm combining local branching and relaxation induced neighborhood search methods is presented. A three-step method is applied for parameter tuning using design of experiments approach. To evaluate the efficiency and effectiveness of the proposed algorithm, the results are compared with those of the state-of-the-art optimization software.     

A novel nondominated sorting simplified swarm optimization for multi-stage capacitated facility location problems with multiple quantitative and qualitative objectives

Capacitated facility location problems (CFLPs) arise in the practical application of many supply chain networks that select a set of suppliers, plants, distribution centers, and customers. In general, the goal of CFLPs is to consider multiple critical performances that involve quantitative and qualitative factors, such as cost, transportation time, inventory, profit, and customer satisfaction, to obtain various perspectives from decision makers in most real-world applications. CFLP becomes increasingly complex and challenging when decision makers simultaneously consider both factors; however, offering comprehensive decisions is important. In this study, a novel solution based on simplified swarm optimization (SSO) and a nondominated sorting technique is proposed to provide Pareto-optimal solutions for enhancing search efficiency and solution quality. To yield feasible solutions, three repairer mechanisms, namely, random repair, cost-based, and utility-based mechanisms, are proposed to enhance the search efficiency and diversity of each population. A fuzzy analytic hierarchy process is used to calculate the weight of qualitative objectives. To evaluate the efficiency and effectiveness of the proposed algorithm, extensive experiments are conducted on benchmark and newly generated instances of the four stages of CFLPs. Then, results are compared with those of the nondominated sorting genetic algorithm-II, multi-objective SSO, and multi-objective particle swarm optimization reported from the literature. The computational results demonstrate that the proposed algorithm is highly competitive and performs well in terms of solution quality and computational time. The Pareto set in the investigated type of facility location problems leads to solutions that may better support decision-making.     

平面选址问题的引力搜索算法求解

为求解平面选址问题,给出了一种基于引力搜索算法的求解方法。算法利用万有引力定律进行全局搜索,采用一种邻域搜索方法进行局部搜索,实现算法全局优化和局部优化的平衡。通过大量实验和与现有求解方法的比较,结果验证了算法的可行性和有效性。     

A new stochastic approach for a reliable p-hub covering location problem

A hub location problem (HLP) is a fertile research field, in the aspect of interdisciplinary studies, such as transportation, operation research, network design, telecommunication and economics. The location of hub facilities and allocation of non-hub nodes to hubs configure the backbone of HLPs. This study presents a new mathematical model for a reliable HLP by a new stochastic approach to minimize the total transportation cost and obtain maximum flows that the network can carry, when its link capacities are subject to stochastic degradations, as in a form of daily traffic, earthquake, flood, etc. We consider the road capacity reliability as a probability that ensures the maximum network capacity is greater than or equal to the total incoming flow to the network by considering the road capacity as random variable. As a result, this paper assumes that link capacities satisfy in a Truncated Erlang $(\mathit{TErl})$ distribution function. Due to complexity of the HLP, a meta-heuristic algorithm, namely differential evolution (DE) algorithm, is applied on the problem in order to achieve near-optimal solutions. Furthermore, the performance of the proposed algorithm (i.e., DE) is evaluated by the performance of the genetic algorithm (GA) applied on the given problem. Some computational experiments are presented to illustrate the effectiveness of the presented model and proposed algorithm. Finally the conclusion is provided.     

一种基于改进客观聚类分析的模糊辨识方法

针对模糊辨识中采用迭代和人为决策法确定模糊规则数时易受噪声和人为因素的影响,而导致算法鲁棒性较差和计算量较高的问题,提出一种基于改进客观聚类分析的模糊辨识方法.首先引入并改进了客观聚类分析法,克服了迭代导致的规则数冗余,降低了人为因素对聚类结果的影响,从而减小了计算量并提高了鲁棒性;然后结合模糊聚类和稳态卡尔曼滤波法,分别辨识了前提和结论参数;最后通过Box-Jenkins仿真实例验证了所提方法的有效性.     

Numerical solution of fuzzy differential equations by predictor-corrector method

In this paper three numerical methods to solve “The fuzzy ordinary differential equations” are discussed. These methods are Adams-Bashforth, Adams-Moulton and predictor-corrector. Predictor-corrector is obtained by combining Adams-Bashforth and Adams-Moulton methods. Convergence and stability of the proposed methods are also proved in detail. In addition, these methods are illustrated by solving two fuzzy Cauchy problems.