选址问题报告

PAGEPAGE1徐州工程学院管理学院实验实验课程名称：选址问实验地点：南主楼七楼机房经济管理实验中心2015年5月至2015年6月实验报告实验项目：B15201303实验学时：4个学时实验日期：2015/5---2015/6实验要求：通过物流选址方法的梳理选其中一种方法解决一个实际问题实验内容：案例分析物流选址问题背景物流中心的选址问题是一个十分重要的决策问题，被称为是最重要的物流战略规划问题。它决定了整个物流系统的模式、结构和形状，选址问题通常十分复杂，因此，建立合理的模型并设计有效的求解方法，以此来辅助决策者进行选址决策是非常必要的。物流中心的选址问题研究通过求解不同类型的选址一分配问题，确定了物流系统中所使用设施的数量、位置和规模。这些设施包括了系统中的各种节点，例如，工厂、仓库、配送中心和分销点等等，货物通过物流网络运往最终顾客过程中，都必须临时经停的这些节点。其中，物流中心是连接供应与需求的一个承前启后的一个关键。因此，通过优化物流中心的选址从而对优化整个物流系统具有极大的意义。物流中心的选址问题是一个十分重要的决策问题，被称为是最重要的物流战略规划问题。它决定了整个物流系统的模式、结构和形状，选址问题通常十分复杂，因此，建立合理的模型并设计有效的求解方法，以此来辅助决策者进行选址决策是非常必要的。物流中心的选址问题研究通过求解不同类型的选址－分配问题，确定了物流系统中所使用设施的数量、位置和规模。这些设施包括了系统中的各种节点，例如，工厂、仓库、配送中心和分销点等等，货物通过物流网络运往最终顾客过程中，都必须临时经停的这些节点。其中，物流中心是连接供应与需求的一个承前启后的一个关键。因此，通过优化物流中心的选址从而对优化整个物流系统具有极大的意义。在物流系统中，物流中心居于重要的枢纽地位，其上游是供应地（工厂、码头等），下游是用户。物流中心的合理选址非常重要，随着市场竞争的日益激烈，物流管理已经成为企业、地区乃至国家的重要任务。物流中心选址研究已形成了多种方法。1.下面是几种选址方法的比较1.1非线性规划配送中心选址问题属于最小成本问题,即求解使运输成本、配送中心的可变成本和固定成本之和最小的最优解。在本文研究里采用的数学模型接近于实际配送中心的选址问题,属于非线性混合规划。基本假设：(l)由供货点到配送中心、由配送中心到用户的运费均为线性函数;(2)配送中心的可变成本为流量的凹函数,即：；(3)配送中心的容量及个数受限制。目标函：约束条件:式中,为供货点的个数;为第个供货点到配送中心的总供应量;为配送中心备选地址点的个数;为配送中心备选地址点的最大容量;为配送中心允许选定个数的上限;为用户个数;为用户需求量;为由第个供货点到第个配送中心的单位运输成本;为由第个供货点到第个配送中心的运输量;为由第个配送中心到第个用户的单位运输成本;为由第个配送中心到第个用户的运输量;为第个配送中心的可变成本系数;为第个配送中心的固定费;为第个配送中心的流量;为整数变量。当时,第个配送中心被选中;当之时,未被选中。1.2重心法重心法是一种模拟方法。这种方法将物流系统中的需求点和资源点看成是分布在某一平面范围内的物流系统，各点的需求量和资源量分别看成是物体的重量，物体系统的重心作为物流网点的最佳设置点，利用求物体系统重心的方法来确定物流网点的位置。重心法一般应用于一元网点布局。一元网点布局，是指在计划区域内设置网点数目唯一的物流网点布局问题。在流通领域中，一元网点布局问题实际并不多，较多的是多元网点布局问题。不过，对于多元网点布局，为了使模型简单化、计算工作量减少，有时将它变换成一元网点布局问题来处理。现仅讨论用重心法在计划区域内设置一个网点的简单情况。在某计划区内，有个资源点和需求点，各点的资源量或需求量为，它们各自的坐标是。需设置一个网点，设网点的坐标为，网点至资源点或需求点的运费率为。根据求平面中物体系统中心的方法有：整理后得:代入数字，实际求得的值即为所求物流中心网点位置的坐标，记为。重心法的最大特点是计算方法较简单，但该方法并不能求出精确的最佳网点位置，因为这一方法将纵向和横向的距离视为互相独立的量，与实际是不相符的，往往其结果在现实环境中不能实现，因此只能作为一种参考结果，而利用微分法可以得出精确解，微分法是为了克服重心法的上述缺点而提出来的，但它要利用重心法的结果作为初始解，并通过迭代获得精确解。仍以重心法讨论的系统为例，设总运输费用为，则：使总运输费用最小的网点位置，其坐标必须满足：由上式可解的：上面两式右边仍含有未知数，，此时最佳网点位置坐标,还不能解出。如果要将中右边的，完全消除，计算起来是相当复杂的。为此，下面采用一种简便的迭代方式求解。迭代法求解必须事先给出一个初始解，通常的方法是由重心法求得系统的重心坐标，以重心坐标作为初始解。用手工方法求解的过程是异常艰辛的工作，但是不难发现，这里的计算量虽然非常大，但却不复杂，为此，可以开发计算机仿真软件来仿真迭代过程。微分法由于利用重心法求得结果作为初值，所以有时也称作精确重心法。用精确重心法得到的最优解只有一个点，而不会是一条线段或者一个区域。1.3层次分析法人们在进行社会的、经济的以及科学管理领域问题的系统分析中，面临的常常是一个由相互关联、相互制约的众多因素构成的复杂而往往缺少定量数据的系统。层次分析法为这类问题的决策和排序提供了一种新的、简洁而实用的建模方法。运用层次分析法建模，大体上可按下面四个步骤进行：（1）建立递阶层次结构模型；（2）构造出各层次中的所有判断矩阵；（3）层次单排序及一致性检验；（4）层次总排序及一致性检验。应用分析决策问题时，首先要把问题条理化、层次化，构造出一个有层次的结构模型。在这个模型下，复杂问题被分解为元素的组成部分。这些元素又按其属性及关系形成若干层次。上一层次的元素作为准则对下一层次有关元素起支配作用。这些层次可以分为三类：（1）最高层：这一层次中只有一个元素，一般它是分析问题的预定目标或理想结果，因此也称为目标层；（2）中间层：这一层次中包含了为实现目标所涉及的中间环节，它可以由若干个层次组成，包括所需考虑的准则、子准则，因此也称为准则层；（3）最底层：这一层次包括了为实现目标可供选择的各种、决策等，因此也称为措施层或方案层。递阶层次结构中的层次数与问题的复杂程度及需要分析的详尽程度有关，一般地层次数不受限制。每一层次中各元素所支配的元素一般不要超过9个。这是因为支配的元素过多会给两两比较判断带来困难。1.4遗传算法遗传算法抽象于生物体的进化过程,是一种通过全面模拟自然选择和遗传机制,形成具有“生成+检验”特征的搜索算法.遗传算法以编码空间代替问题的参数空间,以适应度函数为评价依据,以编码群体为进化基础,以对群体中个体位串的遗传操作实现选择和遗传机制,建立起一个迭代过程。在这一过程中,通过随机重组编码位串中重要的基因,使新一代的位串集合优于老一代的位串集合,群体的个体不断进化,逐渐接近最优解,最终达到求解问题的目的。遗传算法的运行过程为一个典型的迭代过程,其必须完成的工作内容和基本步骤如下：（1）选择编码策略，把参数集合和域转换为位串结构空间；（2）定义适应值函数；（3）确定遗传策略,包括选择群体大小,选择、交叉、变异方法,以及确定交叉概率、变异概率等遗传参数；（4）随机初始化生成群体；（5）计算群体中个体位串解码后的适应值；（6）按照遗传策略,运用选择、交叉和变异算子作用于群体,形成下一代群体；（7）判断群体性能是否满足某一指标,或者已完成预定迭代次数,不满足则返回步骤6,或者修改遗传策略再返回步骤6。通过比较遗传算法属于智能算法能切合实际的解决选址问题。因此下面对遗传算法进行详细说明、应用。2遗传算法在配送中心选址问题中的应用2.1选择编码策略用连续的整数为每一个备选配送中心赋一个号.例如,有6个备选配送中心,那么号1到6分别表示一个物流中心.采用二进制编码方法,编码位串的长度为配送中心备选个数。则编码位串{1,l,1,l,l,l}表示号为l,2,4,5,6的配送中心被选中。2.2适应函数由于适应值是群体中个体生存机会选择的唯一确定性指标,所以适应函数的形式直接决定着群体的进化行为.为了直接将适应函数与群体中的个体优劣度量相联系,在遗传算法中适应值规定为非负,并且在任何情况下总是越大越好。配送中心选址问题所建立的目标函数,本文中针对该式建立如下适应函:式中;是到当前所有代的最大值,此时。随着代数会有变化。例如,设初始群体规模为10,则随机产生10个编码位串即染色体,假设编码位串{1，1,1,0,1,1,1}为其中之一。（1）编码位串表示，代入上式中,则上式变为一个典型的运输问题,再次采用经典遗传算法求解出该运输问题的最优解或近似最优解,可见配送中心选址问题反复使用了二次遗传算法；（2）同理求出所有10个初始染色体的值,并将其中最大值赋给值；（3）求出所有10个初始染色体的适应值。2.3遗传算子遗传算法的操作算子一般都包括选择、交叉和变异三种基本形式,它们构成了遗传算法具备强大搜索能力的核心。（1）选择:本文中采用最优方式实现选择操作,即首先保证父代种群中适应值最大的染色体在子代中至少出现一次,然后按照标准的轮盘赌方式进行选择操作.这样可以保证最优秀的染色体被保留到下一代。（2）交叉:遗传算法的交叉算子是模仿自然界有性繁殖的基因重组过程,其作用在于将原有的优良基因遗传给下一代个体,并生成包含更复杂基因结构的新个体.本文中采用两点交叉法进行交叉操作,因为一点交叉操作的信息量较小,而且位串末尾的重要基因总是被交换.本文中采用线性递减函数产生交叉率。,在第一代。选为75%,线性递减至最后一代为25%.这样做的目的是使得运算初期包含更多的信息量,而到了后期有利于算法的收敛。（3）变异;本文中采用一个线性函数来产生变异概率,其方程为：式中,是随着代数的增加而增大的.这样做的目的是到了运算后期可以加速收敛。2.4对约束的处理由于配送中心选址问题所对应的数学模型约束条件较多,所采用的编码方式中不可行解在群体中的比例很大,所以考虑使用惩罚策略.惩罚策略本质上是通过惩罚不可行解将约束问题转化为无约束问题.本文中采用和方法来构造带有惩罚项的评估函数,即适应值函数。2.5应用实例某物流公司有3个供货点,和可供资源分别为；有10个用户,需求量见表1;费率表见表2一4;配送中心备选地共6个,分别为,其固定成本及容量限制见表5；由表6可知配送中心个数上限。利用编程遗传算法（代码见下文）同得到配送中心个数上限。表1用户需求量用户需求量20151020101015201020表2由第k个供货点到第i个配送中心的单位运输成本12345618711127629108788312610899表3由第个配送中心到第个用户的单位运输成本12345678910175581032443267738893453107796788974889966554456657910433666886448655表4中心的可变成本系数758080757080表5配送中心备选地址备先地固定费80601206090130容量限302040203550表6最优解备先地容量限302040203550通过遗传算法得出以上问题的最优解，求得使总成本最小的配送中心的地址及相应的容量限，从而有效地解决物流系统分析与设计里关于配送中心的选址问题，优化物流系统，使物流系统能有效运作，给企业带来经济效益，真正成为企业“第三利润源泉”。遗传算法代码：citynum=size(d,2);n=nargin;ifn<2disp('缺少变量！！')endifn<2termops=500;num=50;pc=0.25;cxops=3;pm=0.30;alpha=0.10;endifn<3num=50;pc=0.25;cxops=3;pm=0.30;alpha=0.10;endifn<4pc=0.25;cxops=3;pm=0.30;alpha=0.10;endifn<5cxops=3;pm=0.30;alpha=0.10;endifn<6pm=0.30;alpha=0.10;endifn<7alpha=0.10;endifisempty(cxops)cxops=3;end[t]=initializega(num,citynum);fori=1:termops[l]=f(d,t);[x,y]=find(l==max(l));trace(i)=-l(y(1));bestpop=t(y(1),:);[t]=select(t,l,alpha);[g]=grefenstette(t);[g1]=crossover(g,pc,cxops);[g]=mutation(g1,pm);%均匀变异[t]=congrefenstette(g);Endfunction[t]=initializega(num,citynum)fori=1:numt(i,:)=randperm(citynum);endfunction[l]=f(d,t)[m,n]=size(t);fork=1:mfori=1:n-1l(k,i)=d(t(k,i),t(k,i+1));endl(k,n)=d(t(k,n),t(k,1));l(k)=-sum(l(k,:));endfunction[g]=grefenstette(t)[m,n]=size(t);fork=1:mt0=1:n;fori=1:nforj=1:length(t0)ift(k,i)==t0(j)g(k,i)=j;t0(j)=[];breakendendendendfunction[t]=select(t,l,alpha)[m,n]=size(l);t1=t;[beforesort,aftersort1]=sort(l,2);%fsortfromltoufori=1:naftersort(i)=aftersort1(n+1-i);%changeendfork=1:n;t(k,:)=t1(aftersort(k),:);l1(k)=l(aftersort(k));endt1=t;l=l1;fori=1:size(aftersort,2)evalv(i)=alpha*(1-alpha).^(i-1);endm=size(t,1);q=cumsum(evalv);qmax=max(q);fork=1:mr=qmax*rand(1);forj=1:mifj==1&r<=q(1)t(k,:)=t1(1,:);elseifj~=1&r>q(j-1)&r<=q(j)t(k,:)=t1(j,:);endendendfunction[g]=mutation(g,pm)%均匀变异[m,n]=size(g);ran=rand(1,m);r=rand(1,3);%daigaijinrr=floor(n*rand(1,3)+1);[x,mu]=find(ran