1、Facility location models for Facility location models for distribution system designdistribution system design物流系统设计的选址模型IntroductionIntroductionTypes of modelsTypes of modelsGeneral methodsGeneral methodsThe design of the distribution system is a strategic issue for almost every company.The problem
2、 of locating facilities and allocating customers covers the core topics of distribution system design.IntroductionIndustrial firms must locate fabrication(制造厂)and assembly plants(组装厂)as well as warehouses(仓库).Stores have to be located by retail outlets(零售网点).The ability to manufacture and market its
3、 products is dependent in part on the location of the facilities.Similarly,government agencies have to decide about the location of offices,schools,hospitals,fire stations,etc.In every case,the quality of the services depends on the location of the facilities in relation to other facilities.Types of
4、 modelsTypes of modelsFacility location models can be broadly classified as follows:The shape or topography of the set of potential plants yields models in the plane,network location models(网络选址模型),and discrete location(离散选址)or mixed-integer programming models(混合正数规划模型),respectively.Objectives(目标函数)
5、may be either of the minsum or the minmax type.Minsum models are designed to minimize average distances while minmax models have to minimize maximum distances.Predominantly(此外),minsum models embrace location problems of private companies while minmax models focus on location problems arising in the
6、public sector.Models without capacity constraints do not restrict(限制)demand allocation.If capacity constraints for the potential sites have to be obeyed demand has to be allocated carefully.In the latter case we have to examine whether single-sourcing(单来源)or multiple-sourcing(多来源)is essential.Single
7、-stage models(单阶段模型)focus on distribution systems covering only one stage explicitly.In multi-stage models(多阶段模型)the flow of goods comprising several hierarchical(层次)stages has to be examined.Single-product models(单产品模型)are characterized by the fact that demand,cost and capacity for several products
8、 can be aggregated to a single homogeneous product.If products are inhomogeneous their effect on the design of the distribution system has to be analyzed,viz.multi-product models(多产品模型)have to be studied.Location models base on the assumption that demand is inelastic(无弹性的),that is,demand is independ
9、ent of spatial decisions.If demand is elastic(弹性的)the relationship between,e.g.,distance and demand has to be taken into account explicitly.In the latter case cost minimization(成本最小)has to be replaced through,for example,revenue maximization(收益最大).Static models(静态模型)try to optimize system performanc
10、e(性能)for one representative(代表)period.By contrast dynamic models(动态模型)r e f l e c t d a t a (c o s t,d e m a n d,capacities,etc.)varying over time within a given planning horizon.In practice model(实践模型)input is usually not known with certainty.Data are based on forecasts and,hence,are likely to be u
11、ncertain.As a consequence,we have either deterministic models(确定模型)if input is(assumed to be)known with certainty or probabilistic models(概率模型)if input is subject to uncertainty.In classical models the quality of demand allocation is measured on isolation for each pair of supply and demand points.Un
12、fortunately,if demand is satisfied through delivery tours(运输,投递)then,for instance,delivery cost cannot be calculated for each pair of supply and demand points separately.Combined location/routing models(选址/路线模型)elaborate on this interrelationship.General methodsGeneral methodsAHP(Analytic Hierarchy
13、Process)层次分析法Fuzzy Clustering 模糊聚类法Cross-median method交叉中值法gravity method重心法P-median method P-中值法Systemic arithmetic 系统模拟法Genetic algorithm(GA)遗传算法The shortest path method最短路径法Simulated Annealing(SA)模拟退火算法The Analytic Hierarchy Process(AHP)is a structured technique for dealing with complex deciision
14、.Rather than prescribing a correct decision,the AHP helps the decision makers find one that best suits their goal and their understanding of the problem.Based on mathematics and psychology,the AHP was developed by Thomas L.Saaty in the 1970s and has been extensively studied and refined since then.It
15、 provides a comprehensive(全面)and rational framework（合理的框架）for structuring a decision problem（结构化决策问题）,for representing and quantifying its elements,for relating those elements to overall goals,and for evaluating alternative solutions.It is used around the world in a wide variety of decision situatio
16、ns,in fields such as government,business,industry,healthcare,and education.AHPFuzzy ClusteringFuzzy clustering is a class of algorithms for cluster analysis in which the allocation of data points to clusters is not hard(all-or-nothing)but fuzzy in the same sense as fuzzy logic.In hard clustering,dat
17、a is divided into distinct clusters,where each data element belongs to exactly one cluster.In fuzzy clustering(also referred to as soft clustering),data elements can belong to more than one cluster,and associated with each element is a set of membership levels(隶属关系).These indicate the strength of th
18、e association between that data element and a particular cluster.Fuzzy clustering is a process of assigning these membership levels,and then using them to assign data elements to one or more clusters.gravity method总运费=设施与客户之间的直线距离(欧几里德距离)需求量 对上式分别对x，y求偏微分，可以求出下面的一对隐含有最优解的等式，应用这两个等式通过迭代的方法分别对x，y进行求解，
19、即可得最优解。Cross-median method总费用=设施到需求点的折线距离(城市距离)需求量上述目标函数可以用两个互不相干的部分来表述：其中:最优位置是由如下坐标组成的点:xs是在x方向的所有的权重wi的中值点,ys是在y方向的所有的权重wi的中值点。The genetic algorithm(GA)is a search heuristic(启发式)that mimics(模仿)the process of natural evolution.This heuristic is routinely used to generate useful solutions to optimi
20、zation and search problems.Genetic algorithms belong to the larger class of evolutionary algorithms(EA)(进化算法),which generate solutions(生成解决方案)to optimization problems using techniques inspired by natural evolution,such as inheritance(继承),mutation(突变),selection(选择),and crossover(杂交).Genetic algorithm
21、Simulated Annealing Simulated annealing(SA)is a generic probabilistic metaheuristic(启发式)for the global optimization problem of applied mathematics(应用数学),namely locating a good approximation(逼近)to the global optimum of a given function in a large search space.It is often used when the search space is
22、 discrete(e.g.,all tours that visit a given set of cities).For certain problems,simulated annealing may be more effective than exhaustive enumeration(穷举法)provided that the goal is merely to find an acceptably good solution in a fixed amount of time,rather than the best possible solution.Minisum Mini
23、max Maximin Minisum被称为网络上的中值问题。Minimax被称为网络上的中心问题。Maximin被称为反中心问题(Anti-Center)。假设在一条直线上，在位置0,5,6和7上有4个点。为每个点服务的成本与这些点和新设施间的距离成正比。对于Minisum目标来说，新设施的最优位置是这些点的中值5.5，即在选址的左边和右边有相同多的点。对于Minimax目标来说，最优位置就是这些点的中心3.5，即选址位置到最左边点和最右边点的距离是相等的。对于Maximin目标来说最优位置是反中心点2.5。Maximin目标由已存在设施中成本最小的个体组成，目标是使最坏的情况最优化。mul
24、ti-source Weber problem(MWP)多来源韦伯问题 This problem is NP-hard,It can be modelled as the non-linear mixed-integer program(非线性混合整数规划).P-median problem 中值问题(PMP)P-center problem 中值问题(PCP)其中：Uncapacitated,single-stage models(无容量限制单阶段模型)Capacitated,single-stage models(有容量限制单阶段模型)Two-stage capacitated facility location problem(带容量限制的两阶段设施选址问题)multi-product models(多产品模型多产品模型)dynamic models(动态模型动态模型)probabilistic models(概率模型概率模型)Thank you!
