规划和Dijktra算法在物流上的应用
0-10-1 规划和规划和 Dijkstra 算法在物流上的应用算法在物流上的应用1.前言物流是物品从供应地到接收地的实体流动过程,根据实际需要将运输储存,装卸搬运包装流通加工配送信息处理,等基本功能实施有机结合.有物流成本的降低是第三利润源之说,这个理论来自于日本学者西泽修的著作.西泽修教授在他的著作物流-降6低成本的关键. 企业的利润源泉随着时代的发展,和企业经营重点的转移而变化.日本 1950 年正处于工业化大生产时期,企业的经营重点放在了降低制造成本上,这便是日本在第二次世界大战后,企业经营的第一利润源.然而靠自动化生产手段制造出来的,大量产品引起了市场泛滥,产生了对大量销售的需要.1955 年日本迎来的市场营销的时代.这边是日本在第二次世界大战后,企业经营的第二利润源.所以 1970 年开始,这一时期,降低制造成本的潜力有限,增加销售额也已经走到了尽头.迫切需要寻求新的利润源,物流成本的降低,是第三利润源的提法恰恰符合当时企业经营的需要.时代 经营重点 利润源图 1.1 西泽修教授的“第三利润源”说物流组织的好坏直接影响着生产过程的顺利进行,决定着物品的价值和使用价值能否实现.而且物流成本已经成为生产成本和流通成本的重要组成部分.通过采用合理建设物流中心,合理组织运输减少装卸次数,提高装卸,效率改进,商品包装和装卸工具,合工业时代 制造成本的降低 第一利润源市场营销时代 销售额的增加 第二利润源物流时代 物流费的降低 第三利润源理规划,运输路线,合理规划派送路线等措施,降低物流费用将成为企业第三利润的源泉.在我国,节约物资消耗和提高劳动生产率的潜力固然很大,但节约流通费用的潜力更大.开发物流改进促使提高物流管理水平,无论是对于企业经济效益还是对社会宏观经济效益来说都是具有十分重要的意义.运筹学是多种学科的综合性学科,是最早形成的一门软科学.它把科学的方法、1技术和工具应用到包括一个系统管理在内的各种问题上,以便那些掌握系统的人们提供最佳的解决问题的办法.它用科学的方法研究与某一系统最优管理有关的问题.它能帮助决策人解决那些可以用定量方法和有关理论来处理的问题.通过构造模型和进行模拟了解有关因素之间的关系预测各种供选择的方案和可以产生的后果,从而选择达到既定目标的最优途径.在满足既定的要求下,按照某一衡量指标来寻找最优方案,即求解约束条件下目标函数的极值,极大值和极小值的问题.如果目标函数和约束条件的数学表达式都是线性的,则称为线性规划否则就称为非线性规划.如果说考虑的规划问题,可按时间分为几个阶段求解,则称为动态规划.线性规划可解决物质调运,配送和人员分配的问题；整数规划,可以求解完成工作所需要的人数,机器设备台数和仓库选址的问题；动态规划,可以用来解决,诸如最优途径、资源分配、生产调度、库存控制、设备更新的问题.本文将会用到运筹学中的整数规划里的 0-1 规划算法和 Dijkstra 算法来研究23配送中心选址问题,配送路线问题.2.0-1 规划在物流配送中心选址的应用2.1 配送中心配送中心是货物进入与配送集散地,接入点与配送中心及配送中心与配送点的之间都有线路相连,接入点货物必须通过配送中心,再分送到配送点.以某城市物流配送中心选址为例,在考虑多个城市的接入点、多个的配送中心、多个的配送点情况下,建立数学模型,并通过实例求解.城市接入点一般在城市的郊区而且大多紧挨着铁路货场、高速公路、港口及机场等.一般来说选择不同中心的单位运输成本,费用不同.过路费用,房子租用等产生固定成本,可以统计当地实际情况然后来分析问题,建立模型来解决问题.物流配送中心,是为了在供应到消费过程中实现调节跟踪服务的主体结构,是满4足订货、储存、包装、加工、配送、运输、结算和信息处理等需要手段和设施.而配送中心布局和选址,对其功能发挥和综合效益影响极大,所以应该根据不同因素展开不同的综合分析.最终使得总成本最小.本节内容主要应用 0-1 规划的解法来解决实际问题.2.2 建立模型设某物流公司在 A 地有 m 个接入点,有 a 个配送点,现在准备建立配送中心,经过实地考察后选取 n 个地方为备选配送中心.配送中心每天存储量最大是配送中心货物抵达的时候,这时的最大存储量为接入点抵达配送中心的货物量与配送中心到配送点的发货量之和.每个备选配送中心的建设费、设备费、保养费与人工费设备费用都包含在固定费用里.具体情况如下所示：图 2.2.1 给定参数：第 个接入点.ii：第个备选配送中心.jj：第个配送点.kk：接入点个数.m：备选派送中心个数.n：派送点个数.a：为可建配送中心的最大数.L：从接入点到的单位变动成本.ijCj：从到的单位变动成本.' jkCjk：的日平均固定成本.jQj：备选配送中心的最大容量.jPj：每日 送到的货物量.ijXij：每日送到的货物量.' jkXjk变量参数：选中为 1,否则为 0.iD这类问题属于 0-1 型整数规划,建立模型如下：jnjjnjakjjkjkjijminjijDQDXCDXCMinZ 111''11s.t jnjjnjakjkjijminjjPDXDXD 111'11LDnjj11或0jD1其中：,都是常数；, ,.,；, ,.,ijCijX' jkC' jkXjQjPL1i23m1j23；, ,.,.n1k23a上面的模型,目标函数求费用最小.约束条件,当天进入货物量加上当天配送量应该小于配送中心的最大容积；配送中心建造个数应该大于一小于可建配送中心的最大数；以及的变量要求.jD2.3 整数规划 0-1 规划算法0-1 规划模型必须是下述标准型： njjjXCZ1min满足 , ,.,.injijba 11i23m或 ,对一切.0=jX1j其中,可以是正数、负数或 0,所有约束条件方程必须是“”型式.0jCib如果不是标准型,使其化成标准型在计算.这里介绍两种算法：1第一种,全枚举发.全枚举发就是检查每个变量等于 1 或 0 的所有组合,满足所以约束条件,并且使目标函数最优的组合就是 0-1 规划的最优解.如 0-1 变量有个,需要检n查个变量组合.当时,这几乎是不可能的.n216n第二种,隐枚举法.隐枚举法只要检查全部变量组合中的一部分组合就可以求出最优解.下面介绍一种隐枚举法.利用变量只能取 0 或 1 两个值的特性,进行分枝.首先令全部变量取 0 值,检验解是否可行.如果可行,已得最优解；如果不可行.则令一个变量取值 0 或 1,称此变0Z量为固定变量,这时就将问题分成了两个子域,其余未被指定取值的变量称为自由变量.由于这些自由变量在目标函数中的系数都是正数,因此令自由变量为 0 与固定变量组成的子域的解使得目标函数值最小.经过几次检验,或者停止分枝,或者将第二个自由变量转化为固定变量,令其值为 0 或 1,将此子域再分成两个子域.如此继续进行,直到没有自由变量或全部子域停止分枝为止,就求出最优解.2.4 实例求解例 2.4 某一物流公司在一地区有两个城市接入点,三个配送点.现在要建立配送中心点,经过详细调查,有三个备选的配送中心满足配送中心的场地要求.物流公司要求实际建立配送中心点必须多于一个而不得超过两个,第一个备选配送中心的最大容积为10,第二个备选配送中心的最大容积为 11,第三个备选配送中心的最大容积为 8,怎么建造配送中心才能使总成本费用最少.已知调查数据如下：图 2.4.1 从接入点 到备选配送中心的货物量ij图 2.4.2 从接入点 到备选配送中心的单位成本ij图 2.4.3 从备选配送中心送到配送点的货物量jk图 2.4.4 从备选配送中心到配送点的单位变动费jk图 2.4.5 第备选配送中心的最大容量j图 2.4.6 第个备选配送中心的日固定成本j解 由表格中可以知道每日送到备选配送中心 1 的货物花费成本为：.7312221211111XCXC每日送到备选配送中心 2 的货物花费成本为：.14324222221212XCXC每日送到备选配送中心 3 的货物花费成本为：.9233123231313XCXC每日从备选配送中心 1 送到配送点的货物花费成本为：.12232212' 13' 13' 12' 12' 11' 11XCXCXC每日从备选配送中心 2 送到配送点的货物花费成本为：i123jP10118j123jQ403050.8021223' 23' 23' 22' 22' 21' 21XCXCXC每日从备选配送中心 3 送到配送点的货物花费成本为：.8311213' 33' 33' 32' 32' 31' 31XCXCXC第 1 个备选配送中心当天货物库存量与当天货物配送量之和是：.1132132' 13' 12' 112111XXXXX第 2 个备选配送中心当天货物库存量与当天货物配送量之和是：.1001243' 23' 22' 212212XXXXX第 3 个备选配送中心当天货物库存量与当天货物配送量之和是：.1031123' 33' 32' 312313XXXXX根据上面计算,此问题接下来可以写成如下所示：321675259DDDMinZs.t 32132181110101011DDDDDD211njjD或 (选中为 ,否则为）,.0=iD1103 , 2 , 1i上述问题属于 0-1 整数规划,但不符合标准型,化成标准型为：321675259DDDMinZs.t 02321DDD211njjD或 （选中为 ,否则为）,.0=iD1103 , 2 , 1i用全枚举发计算如下：列出全部的变量组合为：,.0 , 0 , 00 , 0 , 10 , 1 , 01 , 0 , 00 , 1 , 11 , 0 , 11 , 1 , 01 , 1 , 1因为,所以排除组合和.211njjD0 , 0 , 01 , 1 , 1代入不满足约束条件,不可行.0 , 0 , 1代入满足约束条件,是可行解.0 , 1 , 052Z代入不满足约束条件,不可行.1 , 0 , 0代入满足约束条件,是可行解.0 , 1 , 1111Z代入不满足约束条件,不可行.1 , 0 , 1代入不满足约束条件,不可行.1 , 1 , 0因为本题是求最小,所以最优解是.52Z即只选中第二个备选配送中心.用隐枚举法计算如下：图 2.4.7 隐枚举法分枝图令全部变量取 0 值,检验结果,不满足约束条件,不可行.进行下一步.将转为固定变量,令其取值为 1 或 0,使问题分成两个子域 1 和 2.1D子域 1 中的固定变量取值为 1,令自由变量都取 0 值,检验不可行,此子域的解1D不可行.对子域 1,将取值为 1 或 0,使子域 1 分成 3 和 4.591Z2D子域 2 中的固定变量取值为 0,令自由变量都取 0 值,检验不可行,此子域的解1D不可行.对子域 2,将取值为 1 或 0,使子域 2 分成 5 和 6.02Z2D子域 3 中的固定变量取值为 1,令自由变量都取 0 值,检验可行,此时可2D1113Z行.停止分枝.子域 4 中的固定变量取值为 0,将,带入第一个约束条件2D11D02D,左边的最小值为 1 大于右端值 0 所以子域 4 是不可行子域,不再分枝.02321DDD子域 5 中的固定变量取值为 1,令
