选址问题报告

徐州工程学院 管理学院实验报告管理学院实验报告 实验课程名称实验课程名称 选址问题选址问题 实验地点 实验地点 南主楼七楼机房经济管理实验中心南主楼七楼机房经济管理实验中心 20152015 年年 5 5 月至月至 20152015 年年 6 6 月月 1 实验报告实验报告 实验项目 实验项目 B15201303 实验学时 实验学时 4 个学时个学时 实验日期 实验日期 2015 5 2015 6 实验要求 通过物流选址方法的梳理选其中一种方法解决一个实际问题实验要求 通过物流选址方法的梳理选其中一种方法解决一个实际问题 实验内容 案例分析物流选址实验内容 案例分析物流选址 问题背景问题背景 物流中心的选址问题是一个十分重要的决策问题 被称为是最重要的物流战略规 划问题 它决定了整个物流系统的模式 结构和形状 选址问题通常十分复杂 因此 建立合理的模型并设计有效的求解方法 以此来辅助决策者进行选址决策是非常必要 的 物流中心的选址问题研究通过求解不同类型的选址一分配问题 确定了物流系统 中所使用设施的数量 位置和规模 这些设施包括了系统中的各种节点 例如 工厂 仓库 配送中心和分销点等等 货物通过物流网络运往最终顾客过程中 都必须临时 经停的这些节点 其中 物流中心是连接供应与需求的一个承前启后的一个关键 因 此 通过优化物流中心的选址从而对优化整个物流系统具有极大的意义 物流中心的选址问题是一个十分重要的决策问题 被称为是最重要的物流战略规 划问题 它决定了整个物流系统的模式 结构和形状 选址问题通常十分复杂 因此 建立合理的模型并设计有效的求解方法 以此来辅助决策者进行选址决策是非常必要 的 物流中心的选址问题研究通过求解不同类型的选址 分配问题 确定了物流系统 中所使用设施的数量 位置和规模 这些设施包括了系统中的各种节点 例如 工厂 仓库 配送中心和分销点等等 货物通过物流网络运往最终顾客过程中 都必须临时 经停的这些节点 其中 物流中心是连接供应与需求的一个承前启后的一个关键 因 此 通过优化物流中心的选址从而对优化整个物流系统具有极大的意义 在物流系统中 物流中心居于重要的枢纽地位 其上游是供应地 工厂 码头等 下游是用户 物流中心的合理选址非常重要 随着市场竞争的日益激烈 物流管理已 经成为企业 地区乃至国家的重要任务 物流中心选址研究已形成了多种方法 1 1 下面是几种选址方法的比较下面是几种选址方法的比较 1 11 1 非线性非线性规划规划0 1 配送中心选址问题属于最小成本问题 即求解使运输成本 配送中心的可变成本和 固定成本之和最小的最优解 在本文研究里采用的数学模型接近于实际配送中心的选 址问题 属于非线性混合规划 0 1 基本假设 l 由供货点到配送中心 由配送中心到用户的运费均为线性函数 2 配送中心的可变成本为流量的凹函数 即 0 1 i W 3 配送中心的容量及个数受限制 目标函 1 数 111111 min x z mnnlnn kikiijijiiiii kiijii fc xh xzVWz F 2 约束条件 1 1 11 1 1 1 2 1 2 1 2 1 2 0 0 1 2 1 2 1 2 n kik i n ijj i ml kjij kj m kiii k n i i kiij xA km xDjl xx in st xz M in zP xx km jl in 式中 为供货点的个数 为第个供货点到配送中心的总供应量 为配送中心m k Akn 备选地址点的个数 为配送中心备选地址点的最大容量 为配送中心允许选定 i MP 个数的上限 为用户个数 为用户需求量 为由第个供货点到第 个配送中心l i D ki cki 的单位运输成本 为由第个供货点到第 个配送中心的运输量 为由第 个配 ki xki ij hi 送中心到第个用户的单位运输成本 为由第 个配送中心到第个用户的运输量 j ij xij 为第 个配送中心的可变成本系数 为第 个配送中心的固定费 为第 个配 i Vi i Fi i Wi 送中心的流量 为整数变量 当时 第 个配送中心被选中 当之时 未 i z1 i z i0 i z 被选中 1 21 2 重心法重心法 重心法是一种模拟方法 这种方法将物流系统中的需求点和资源点看成是分布 在某一平面范围内的物流系统 各点的需求量和资源量分别看成是物体的重量 物 体系统的重心作为物流网点的最佳设置点 利用求物体系统重心的方法来确定物流 网点的位置 重心法一般应用于一元网点布局 一元网点布局 是指在计划区域内设置网点 数目唯一的物流网点布局问题 在流通领域中 一元网点布局问题实际并不多 较 多的是多元网点布局问题 不过 对于多元网点布局 为了使模型简单化 计算工 作量减少 有时将它变换成一元网点布局问题来处理 现仅讨论用重心法在计划区域内设置一个网点的简单情况 在某计划区内 有个资源点和需求点 各点的资源量或需求量为 n 它们各自的坐标是 需设置一个网点 设网1 2 j Wjn 1 2 jj xyjn 点的坐标为 网点至资源点或需求点的运费率为 根据求平面中物体系统 x y j c 中心的方法有 jjjjj xC WC W X y jjjjj C WC W Y 3 整理后得 jjjjj yC W YC W 代入数字 实际求得 的值即为所求物流中心网点位置的坐标 记为 x y xy 重心法的最大特点是计算方法较简单 但该方法并不能求出精确的最佳网点位置 因为这一方法将纵向和横向的距离视为互相独立的量 与实际是不相符的 往往其 结果在现实环境中不能实现 因此只能作为一种参考结果 而利用微分法可以得出 精确解 微分法是为了克服重心法的上述缺点而提出来的 但它要利用重心法的结 果作为初始解 并通过迭代获得精确解 仍以重心法讨论的系统为例 设总运输费 用为 则 F 1 2 22 jjjj FC Wxxyy 使总运输费用 最小的网点位置 其坐标必须满足 F x y 1 2 2 20 jjjjj F xC Wxxxxyy 1 2 2 20 jjjjj F yC Wyyxxyy 由上式可解的 1 21 2 22 2 2 jjjjjjjjj XC W xxxyyC Wxxyy 1 21 2 22 2 2 jjjjjjjjj YC W yxxyyC Wxxyy 上面两式右边仍含有未知数 此时最佳网点位置坐标 还不能解出 如xy x y 果要将中右边的 完全消除 计算起来是相当复杂的 为此 下面采用一种xy 简便的迭代方式求解 迭代法求解必须事先给出一个初始解 通常的方法是由重心 法求得系统的重心坐标 以重心坐标作为初始解 用手工方法求解的过程是异常艰 辛的工作 但是不难发现 这里的计算量虽然非常大 但却不复杂 为此 可以开 发计算机仿真软件来仿真迭代过程 微分法由于利用重心法求得结果作为初值 所 以有时也称作精确重心法 用精确重心法得到的最优解只有一个点 而不会是一条 线段或者一个区域 1 31 3 层次分析法层次分析法 人们在进行社会的 经济的以及科学管理领域问题的系统分析中 面临的常常 是一个由相互关联 相互制约的众多因素构成的复杂而往往缺少定量数据的系统 层次分析法为这类问题的决策和排序提供了一种新的 简洁而实用的建模方法 运 用层次分析法建模 大体上可按下面四个步骤进行 1 建立递阶层次结构模型 2 构造出各层次中的所有判断矩阵 3 层次单排序及一致性检验 4 层次总排序及一致性检验 应用分析决策问题时 首先要把问题条理化 层次化 构造出一个有层AHP 次的结构模型 在这个模型下 复杂问题被分解为元素的组成部分 这些元素又按 其属性及关系形成若干层次 上一层次的元素作为准则对下一层次有关元素起支配 作用 4 这些层次可以分为三类 1 最高层 这一层次中只有一个元素 一般它是分析问题的预定目标或理想结 果 因此也称为目标层 2 中间层 这一层次中包含了为实现目标所涉及的中间环节 它可以由若干个 层次组成 包括所需考虑的准则 子准则 因此也称为准则层 3 最底层 这一层次包括了为实现目标可供选择的各种措施 决策方案等 因 此也称为措施层或方案层 递阶层次结构中的层次数与问题的复杂程度及需要分析的详尽程度有关 一般 地层次数不受限制 每一层次中各元素所支配的元素一般不要超过 9 个 这是因 为支配的元素过多会给两两比较判断带来困难 1 41 4 遗传算法遗传算法 遗传算法抽象于生物体的进化过程 是一种通过全面模拟自然选择和遗传机制 形成具有 生成 检验 特征的搜索算法 遗传算法以编码空间代替问题的参数空间 以适应度函数为评价依据 以编码群体为进化基础 以对群体中个体位串的遗传操作 实现选择和遗传机制 建立起一个迭代过程 在这一过程中 通过随机重组编码位串 中重要的基因 使新一代的位串集合优于老一代的位串集合 群体的个体不断进化 逐渐接近最优解 最终达到求解问题的目的 遗传算法的运行过程为一个典型的迭 代过程 其必须完成的工作内容和基本步骤如下 1 选择编码策略 把参数集合和域转换为位串结构空间 xS 2 定义适应值函数 f x 3 确定遗传策略 包括选择群体大小 选择 交叉 变异方法 以及确定交叉概n 率 变异概率 等遗传参数 c P m P 4 随机初始化生成群体 P 5 计算群体中个体位串解码后的适应值 f x 6 按照遗传策略 运用选择 交叉和变异算子作用于群体 形成下一代群体 7 判断群体性能是否满足某一指标 或者已完成预定迭代次数 不满足则返回步 骤 6 或者修改遗传策略再返回步骤 6 通过比较遗传算法属于智能算法能切合实际的解决选址问题 因此下面对遗传 算法进行详细说明 应用 2 2 遗传算法在配送中心选址问题中的应用遗传算法在配送中心选址问题中的应用 2 12 1 选择编码策略选择编码策略 用连续的整数为每一个备选配送中心赋一个号 例如 有 6 个备选配送中心 ID 那么号 1 到 6 分别表示一个物流中心 采用二进制编码方法 编码位串的长度为ID 配送中心备选个数 则编码位串 1 l 1 l l l 表示号为 l 2 4 5 6 的配送中nID 心被选中 2 22 2 适应函数适应函数 由于适应值是群体中个体生存机会选择的唯一确定性指标 所以适应函数的形 式直接决定着群体的进化行为 为了直接将适应函数与群体中的个体优劣度量相联 5 系 在遗传算法中适应值规定为非负 并且在任何情况下总是越大越好 配送中心选 址问题所建立的目标函数 本文中针对该式建立如下适应函 2 数 maxmax 0 Cf x zf x zC g x z 若 否则 式中 是到当前所有代 的最大值 此时 随着代数会有变化 max C f x z max C 例如 设初始群体规模为 10 则随机产生 10 个编码位串即染色体 假设编码位串 1 1 1 0 1 1 1 为其中之一 1 编码位串表示 代入上式中 则上式 1 1 0 1 1 1 124563 1 0zzzzzz 变为一个典型的运输问题 再次采用经典遗传算法求解出该运输问题的最优解或近 似最优解 可见配送中心选址问题反复使用了二次遗传算法 2 同理求出所有 10 个初始染色体的值 并将其中最大值赋给值 f x z max C 3 求出所有 10 个初始染色体的适应值 zg x 2 32 3 遗传算子遗传算子 标准遗传算法的操作算子一般都包括选择 交叉和变异三种基本形式 它们构 成了遗传算法具备强大搜索能力的核心 1 选择 本文中采用最优方式实现选择操作 即首先保证父代种群中适应值最大 的染色体在子代中至少出现一次 然后按照标准的轮盘赌方式进行选择操作 这样可 以保证最优秀的染色体被保留到下一代 2 交叉 遗传算法的交叉算子是模仿自然界有性繁殖的基因重组过程 其作用在 于将原有的优良基因遗传给下一代个体 并生成包含更复杂基因结构的新个体 本文 中采用两点交叉法进行交叉操作 因为一点交叉操作的信息量较小 而且位串末尾的 重要基因总是被交换 本文中采用线性递减函数产生交叉率 在第一代 选为 c P c P 75 线性递减至最后一代为 25 这样做的目的是使得运算初期包含更多的信息量 而到了后期有利于算法的收敛 3 变异 本文中采用一个线性函数来产生变异概率 其方程为 m P 0 001 0 200 001 m P 当前代数 总代数 式中 是随着代数的增加而增大的 这样做的目的是到了运算后期可以加速收敛 m P 2 42 4 对约束的处理对约束的处理 由于配送中心选址问题所对应的数学模型约束条件较多 所采用的编码方式中 不可行解在群体中的比例很大 所以考虑使用惩罚策略 惩罚策略本质上是通过惩罚 不可行解将约束问题转化为无约束问题 本文中采用和方法来构造MihcalewcizAtati 带有惩罚项的评估函数 即适应值函数 2 52 5 应用实例应用实例 某物流公司有 3 个供货点 和可供资源分别为 1 Q 2 Q 3 Q 123 40 60 50AAA 有 10 个用户 需求量见表 1 费率表见表 2 一 4 配送 1210 H HH 1 2 10 j Dj 中心备选地共 6 个 分别为 其固定成本及容量限制见表 5 由表 6 可知 126 w ww 配送中心个数上限 利用编程遗传算法 代码见下文 同得到配送中5P Matlab 心个数上限 5P 6 表 1 用户需求量 用户 i H 1 H 2 H 3 H 4 H 5 H 6 H 7 H 8 H 9 H 10 H 需求量 j D20151020101015201020 表 2 由第 k 个供货点到第 i 个配送中心的单位运输成本 i k 123456 187111276 29108788 312610899 表 3 由第 个配送中心到第个用户的单位运输成本ij j i 12345678910 175581032443 26773889345 310779678897 48899665544 566579104336 66886448655 表 4 中心 的可变成本系数i 1 V 2 V 3 V 4 V 5 V 6 V 758080757080 表 5 配送中心备选地址 备先地 1 W 2 W 3 W 4 W 5 W 6 W 固定费 80601206090130 容量限 302040203550 表 6 最优解 备先地 1 W 2 W 3 W 4 W 5 W 6 W 容量限 302040203550 通过遗传算法得出以上问题的最优解 求得使总成本最小的配送中心的地址及 相应的容量限 从而有效地解决物流系统分析与设计里关于配送中心的选址问题 优化物流系统 使物流系统能有效运作 给企业带来经济效益 真正成为企业 第 三利润源泉 7 遗传算法代码 遗传算法代码 Matlab citynum size d 2 n nargin if n 2 disp 缺少变量 end if n 2 termops 500 num 50 pc 0 25 cxops 3 pm 0 30 alpha 0 10 end if n 3 num 50 pc 0 25 cxops 3 pm 0 30 alpha 0 10 end if n 4 pc 0 25 cxops 3 pm 0 30 alpha 0 10 end if n 5 cxops 3 pm 0 30 alpha 0 10 end if n 6 pm 0 30 alpha 0 10 end if n 7 alpha 0 10 end if isempty cxops cxops 3 end 8 t initializega num citynum for i 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 End function t initializega num citynum for i 1 num t i randperm citynum end function l f d t m n size t for k 1 m for i 1 n 1 l k i d t k i t k i 1 end l k n d t k n t k 1 l k sum l k end function g grefenstette t m n size t for k 1 m t0 1 n for i 1 n for j 1 length t0 if t k i t0 j g k i j t0 j break end end end end 9 function t select t l alpha m n size l t1 t beforesort aftersort1 sort l 2 fsort from l to u for i 1 n aftersort i aftersort1 n 1 i change end for k 1 n t k t1 aftersort k l1 k l aftersort k end t1 t l l1 for i 1 size aftersort 2 evalv i alpha 1 alpha i 1 end m size t 1 q cumsum evalv qmax max q for k 1 m r qmax rand 1 for j 1 m if j 1 end end end 10 function g mutation g pm 均匀变异 m n size g ran rand 1 m r rand 1 3 dai gai jin rr floor n rand 1 3 1 x mu find ran pm for k 1 length mu for i 1 le