物流网点选址课件.ppt

第四章 物流网点选址模型,总体框架,论述选址问题的分类与选址的方法,利用模型进行实际问题的求解,选址模型及其算法的详细介绍,1.选址问题分类,连续选址,离散选址,在一个连续空间内所有点都是可选方案，需从数量无限的点中选择其中一个最优点。,目标选址区域是一个离散的候选位置的集合，候选位置的数量是有限的。,2.选址的方法,3.网点间距离的计算,直线距离与折线距离比较,计算公式,直线距离,折线距离,当选址区域范围较大时，网点间的距离常可用直线距离金丝代替，或用直线距离乘以一个适当的系数。区域内两点（xi，yi）和（xj，yj）间的直线距离dij计算公式为：,当选址范围较小而且区域内道路较规则时，可用折线距离代替两点间的距离。计算公式为：,直线距离,j点,折线距离,i点,xj,xi,x,yj,yi,选址问题模型中，最基本的一个参数是各点之间的距离，一般采用直线距离和折线距离两种方法来计算。,P-中值模型,1.问题,P-中值模型是指在确定区域内应建设的物流设施数之后，需进一步从若干个候选点中选取P个位置作为设施的地址，并确定各设施的服务对象，使得总运输成本最少。图4-8能够直观的表达P-中值模型：,2.建立模型,约束条件：,模型参数：设：N-系统中的n个需求点（客户）M-m个可建设的候选地点-第i个需求点的需求量-从i到j的单位运输费用 p-将建设的设施总数 1，在j点建立设施 jM=0，否则,模型求解-贪婪取走算法,第一步：令当前选中的设施点数k=m，即将将所有的候选位置选中。第二步：将每个用户指派给k个设施中离其最近的一个设施点。求出总运输费用z第三步：若k=p，输出k个设施的指派结果，停止，否则转入第四步。第四步：从k个设施候选点中确定个取走点，满足假如将其取走并将它的客户指派给其他最近设施点后，总费用增加量最小。第五步：从候选点集合中删去取去点，令k=k-1，转第二步。,例：仓库选址问题,某个公司在某地有8个超市客户，拟在该地区新建2个仓库，现在有4个候选地点，从候选地到各个超市的运输成本 和各个超市的需求量 都已经确定，试选其中两个候选地点作为仓库地址，使总运输成本最小。,4 12 20 62 10 25 103 4 16 146 5 9 218 12 7 32 4 930 2 1124 12 6 22,10050120802007060100,候选地 1 2 3 4,第一步：解：令k=4，令第i个超市指派给 中最小的候选点。第一次指派的结果是A=（a1,a2，a8)=（1，1，1，4，4，2，3，3）运输总费用 Z=2480,4 12 20 62 10 25 103 4 16 146 5 9 218 12 7 32 4 930 2 1124 12 6 22,=,候选地 1 2 3 4,第二步：分别删除候选点1，2，3，4进行分析若删除候选点1，则A=（a1,a2，a8)=（4，2，2，4，4，2，3，3）,候选地 2 3 4,12 20 6 10 25 10 4 16 14 5 9 2 12 7 3 2 4 9 30 2 11 12 6 22,=,运输总费用 z=3200，增量z=3200-2480=720,同理，若删除候选点2，则A=（a1,a2，a8)=（1，1，1，4，4，3，3，3），z=2620，增量z=140若删除候选点3，则增量z=1140若删除候选点4，则增量z=1040由此可知，移走候选点2时，运费增加最少，因此移走候选点2。此时k=3，A=（a1,a2，a8)=（1，1，1，4，4，3，3，3），分别删除1，3，4候选点进行分析,第三步：若删除候选点1，z=4540，z=4540-2620=1920 若删除候选点3，z=2490若删除候选点4，z=1120因此移走第4个候选点此时k=2=p，计算结束，结果为在候选位置的1，3两个候选点处投建新仓库，总运输成本最低。,