0-1规划和Dijktra算法在物流上的应用(2)

0-1规划和Dijkstra算法在物流上的应用1.前言物流是物品从供应地到接收地的实体流动过程,根据实际需要将运输储存,装卸搬运包装流通加工配送信息处理,等基本功能实施有机结合.有物流成本的降低是第三利润源之说,这个理论来自于日本学者西泽修的著作.西泽修教授在他的著作物流-降低成本的关键. 企业的利润源泉随着时代的发展,和企业经营重点的转移而变化.日本1950年正处于工业化大生产时期,企业的经营重点放在了降低制造成本上,这便是日本在第二次世界大战后,企业经营的第一利润源.然而靠自动化生产手段制造出来的,大量产品引起了市场泛滥,产生了对大量销售的需要.1955年日本迎来的市场营销的时代.这边是日本在第二次世界大战后,企业经营的第二利润源.所以1970年开始,这一时期,降低制造成本的潜力有限,增加销售额也已经走到了尽头.迫切需要寻求新的利润源,物流成本的降低,是第三利润源的提法恰恰符合当时企业经营的需要. 时代 经营重点 利润源 工业时代 制造成本的降低 第一利润源 市场营销时代 销售额的增加 第二利润源 物流时代 物流费的降低 第三利润源图1.1 西泽修教授的“第三利润源”说物流组织的好坏直接影响着生产过程的顺利进行,决定着物品的价值和使用价值能否实现.而且物流成本已经成为生产成本和流通成本的重要组成部分.通过采用合理建设物流中心,合理组织运输减少装卸次数,提高装卸,效率改进,商品包装和装卸工具,合理规划,运输路线,合理规划派送路线等措施,降低物流费用将成为企业第三利润的源泉.在我国,节约物资消耗和提高劳动生产率的潜力固然很大,但节约流通费用的潜力更大.开发物流改进促使提高物流管理水平,无论是对于企业经济效益还是对社会宏观经济效益来说都是具有十分重要的意义.运筹学是多种学科的综合性学科,是最早形成的一门软科学.它把科学的方法、技术和工具应用到包括一个系统管理在内的各种问题上,以便那些掌握系统的人们提供最佳的解决问题的办法.它用科学的方法研究与某一系统最优管理有关的问题.它能帮助决策人解决那些可以用定量方法和有关理论来处理的问题.通过构造模型和进行模拟了解有关因素之间的关系预测各种供选择的方案和可以产生的后果,从而选择达到既定目标的最优途径.在满足既定的要求下,按照某一衡量指标来寻找最优方案,即求解约束条件下目标函数的极值,极大值和极小值的问题.如果目标函数和约束条件的数学表达式都是线性的,则称为线性规划否则就称为非线性规划.如果说考虑的规划问题,可按时间分为几个阶段求解,则称为动态规划.线性规划可解决物质调运,配送和人员分配的问题；整数规划,可以求解完成工作所需要的人数,机器设备台数和仓库选址的问题；动态规划,可以用来解决,诸如最优途径、资源分配、生产调度、库存控制、设备更新的问题.本文将会用到运筹学中的整数规划里的0-1规划算法和Dijkstra算法来研究配送中心选址问题,配送路线问题.2.0-1规划在物流配送中心选址的应用2.1配送中心配送中心是货物进入与配送集散地,接入点与配送中心及配送中心与配送点的之间都有线路相连,接入点货物必须通过配送中心,再分送到配送点.以某城市物流配送中心选址为例,在考虑多个城市的接入点、多个的配送中心、多个的配送点情况下,建立数学模型,并通过实例求解.城市接入点一般在城市的郊区而且大多紧挨着铁路货场、高速公路、港口及机场等.一般来说选择不同中心的单位运输成本,费用不同.过路费用,房子租用等产生固定成本,可以统计当地实际情况然后来分析问题,建立模型来解决问题.物流配送中心,是为了在供应到消费过程中实现调节跟踪服务的主体结构,是满足订货、储存、包装、加工、配送、运输、结算和信息处理等需要手段和设施.而配送中心布局和选址,对其功能发挥和综合效益影响极大,所以应该根据不同因素展开不同的综合分析.最终使得总成本最小.本节内容主要应用0-1规划的解法来解决实际问题.2.2建立模型设某物流公司在A地有m个接入点,有a个配送点,现在准备建立配送中心,经过实地考察后选取n个地方为备选配送中心.配送中心每天存储量最大是配送中心货物抵达的时候,这时的最大存储量为接入点抵达配送中心的货物量与配送中心到配送点的发货量之和.每个备选配送中心的建设费、设备费、保养费与人工费设备费用都包含在固定费用里.具体情况如下所示： 图2.2.1 给定参数：第个接入点.：第个备选配送中心.：第个配送点.：接入点个数.：备选派送中心个数.：派送点个数.：为可建配送中心的最大数.：从接入点到的单位变动成本.：从到的单位变动成本.：的日平均固定成本.：备选配送中心的最大容量.：每日送到的货物量.：每日送到的货物量.变量参数：选中为1,否则为0.这类问题属于0-1型整数规划,建立模型如下： s.t 或其中：,都是常数；,.,；,.,；,.,.上面的模型,目标函数求费用最小.约束条件,当天进入货物量加上当天配送量应该小于配送中心的最大容积；配送中心建造个数应该大于一小于可建配送中心的最大数；以及的变量要求.2.3整数规划0-1规划算法0-1规划模型必须是下述标准型： 满足 ,.,. 或,对一切.其中,可以是正数、负数或0,所有约束条件方程必须是“”型式.如果不是标准型,使其化成标准型在计算.这里介绍两种算法：第一种,全枚举发.全枚举发就是检查每个变量等于1或0的所有组合,满足所以约束条件,并且使目标函数最优的组合就是0-1规划的最优解.如0-1变量有个,需要检查个变量组合.当时,这几乎是不可能的.第二种,隐枚举法.隐枚举法只要检查全部变量组合中的一部分组合就可以求出最优解.下面介绍一种隐枚举法.利用变量只能取0或1两个值的特性,进行分枝.首先令全部变量取0值,检验解是否可行.如果可行,已得最优解；如果不可行.则令一个变量取值0或1,称此变量为固定变量,这时就将问题分成了两个子域,其余未被指定取值的变量称为自由变量.由于这些自由变量在目标函数中的系数都是正数,因此令自由变量为0与固定变量组成的子域的解使得目标函数值最小.经过几次检验,或者停止分枝,或者将第二个自由变量转化为固定变量,令其值为0或1,将此子域再分成两个子域.如此继续进行,直到没有自由变量或全部子域停止分枝为止,就求出最优解.2.4实例求解例2.4某一物流公司在一地区有两个城市接入点,三个配送点.现在要建立配送中心点,经过详细调查,有三个备选的配送中心满足配送中心的场地要求.物流公司要求实际建立配送中心点必须多于一个而不得超过两个,第一个备选配送中心的最大容积为10,第二个备选配送中心的最大容积为11,第三个备选配送中心的最大容积为8,怎么建造配送中心才能使总成本费用最少.已知调查数据如下：图2.4.1从接入点到备选配送中心的货物量图2.4.2从接入点到备选配送中心的单位成本图2.4.3从备选配送中心送到配送点的货物量图2.4.4从备选配送中心到配送点的单位变动费12310118图2.4.5第备选配送中心的最大容量123403050图2.4.6第个备选配送中心的日固定成本解 由表格中可以知道每日送到备选配送中心1的货物花费成本为：.每日送到备选配送中心2的货物花费成本为：.每日送到备选配送中心3的货物花费成本为：.每日从备选配送中心1送到配送点的货物花费成本为： .每日从备选配送中心2送到配送点的货物花费成本为：.每日从备选配送中心3送到配送点的货物花费成本为：.第1个备选配送中心当天货物库存量与当天货物配送量之和是：. 第2个备选配送中心当天货物库存量与当天货物配送量之和是： .第3个备选配送中心当天货物库存量与当天货物配送量之和是：.根据上面计算,此问题接下来可以写成如下所示：s.t 或(选中为,否则为）,.上述问题属于0-1 整数规划,但不符合标准型,化成标准型为：s.t 或（选中为,否则为）,.用全枚举发计算如下：列出全部的变量组合为：,.因为,所以排除组合和. 代入不满足约束条件,不可行. 代入满足约束条件,是可行解. 代入不满足约束条件,不可行. 代入满足约束条件,是可行解. 代入不满足约束条件,不可行. 代入不满足约束条件,不可行.因为本题是求最小,所以最优解是.即只选中第二个备选配送中心.用隐枚举法计算如下：图2.4.7 隐枚举法分枝图令全部变量取0值,检验结果,不满足约束条件,不可行.进行下一步.将转为固定变量,令其取值为1或0,使问题分成两个子域1和2.子域1中的固定变量取值为1,令自由变量都取0值,检验不可行,此子域的解不可行.对子域1,将取值为1或0,使子域1分成3和4.子域2中的固定变量取值为0,令自由变量都取0值,检验不可行,此子域的解不可行.对子域2,将取值为1或0,使子域2分成5和6.子域3中的固定变量取值为1,令自由变量都取0值,检验可行,此时可行.停止分枝.子域4中的固定变量取值为0,将,带入第一个约束条件,左边的最小值为1大于右端值0所以子域4是不可行子域,不再分枝.子域5中的固定变量取值为1,令自由变量都取0值,检验可行,此子域的解可行.停止分枝.子域6中的固定变量取值为0,将,带入第一个约束条件,左边的仅在时满足约束条件,但是这时不能满足约束条件.所以子域6,是不可行子域,不再分枝.求出可行解,.因为本题中是求最小值，所以最优解是,即选中第二个备选配送中心.2.5本章小结近些年随着电子商务越来越热,物流在中国也得到空前的发展.如何节约物流成本也成了现在学者研究的一个方向.企业的利润源泉随着时代的发展,和企业经营重点的转移而变化.现在降低制造成本的潜力有限,增加销售额也已经走到了尽头.日本的学者西泽修先生提出的理论：物流是第三利润源.非常符合现在经济发展的情况.在我们国家在物流上运营成本上还有很大的空间来节约.接着我们通过了解配送中心的相关信息来确定影响建立配送中心所需花费一些因素.其次把未知变量用字母表示出来,再把与未知变量关系密切的重要的因素来用字母表示确定下来.依据它们的联系来建立模型.对于选址类问题,我们在实际生活中要么选中,要不就不选中,只有这两种可能.所以我们利用整数规划的0-1规划来解决问题.在本节中我们用全枚举法和隐枚举法来解决0-1规划中的问题.全枚举法就是检查全部变量组合,满足所有约束条件,并且使目标函数值最优解.隐枚举法利用自由变量转固定变量的思想解题.隐枚举法只需要检查全部变量组合中的一部分组合就可以求出最优解.隐枚举法的比较全枚举发比较简便.通过对本节内容,我们可以看出运筹学其特点是发展一个科学的系统模型,把现实生活中的各种因素以数学文字表示出来,并且运用这个模型能够预测结果,比较各种决策控制方案所产生的后果,以帮助人们科学地决定方针和行动.3.Dijkstra在配送中的应用3.1物流配送物流配送就是送货,但是不同于一般地送货.物流送货是有确定组织、有制度、有装备的送货,是固定的形式.而一般送货是一种偶然的行为.物流配送与一般送货相比,物流配送更依靠科技的手段,更加先进.比如通过查询物流的网上信息我们可以知道物流配送员的电话联系信息,能及时了解货物的配送信息.物流配送是资源配置的一部分.它的资源配置的作用是最终配置,也是物流的最后一步.货物通过最后的派送才开始消费,即表现其使用价值.物流配送还可以说是接近顾客的配置.可以说每一次配送见到的收件人都是该物流下次消费的潜在顾客.作为物流公司应在已有的设备上最大化的顾客的满意度能最大化使潜在顾客转变为消费顾客.顾客在物流上注重的有以下几点：货物在运输及派送中的安全性、货物的抵达所需时间和费用.在配送这一环节在保证货物安全的条件下,节约人力物力,为公司节约配送成本.具体表现为在顾客时间容忍范围内,规划最短径.最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用、路线容量等.相应地,最短路径问题就成为最快路径问题、最低费用问题等.3.2 Dijkstra算法本小节主要探讨Dijkstra算法在物流配送中配送路线中的应用.也就是通过Dijkstra算法,求出最优路线.Dijkstra算法的主要思路是：建设每个点都有标号（,）,其中是从起源点到点的最短径的长度（从顶点到其本身的是零路也就是没有弧的路,其长度为零）,是从到的最短路径中的前一点.求起源点到点的最短路径算法过程如下：(1) 初始化.起源地设置为：,为空；所有其他点： ,；标记起源点,记,其他所有点设成未标记的.(2) 检验从所有已标记的点到其直接连接的未标记的点的距离,并设置：其中,是点到直接连接距离.(3) 选取下一个点.从所有未标记的结点中选取最小的的点；,所有未标记的点点就被选为最短径中的一点,并设为已标记点.(4) 找到点的前一点.从已标记的点中找到直接连接到点的点,作为前一点,设置：.(5) 标记点.如果所有点已经标记,则算法完全推出,否则,记,转再继续.3.3 Dijkstra算法解决无向路径问题例3.3配送点要向商城送一批货.下面的图3.3.1是配送点到商城的交通路线图.每条边上的数字表两点间的路程或者两点所需时间.求怎么设计路线才能使得路程最短或所需时间最短.3.3.1 交通路线图解 标记起源点(,）,为已标记点,其它为未标记点.与已标记点直接相接的三个未标记点,中,.,最小.所以标记,(,).图 3.3.1.1 与已标记点,直接相接的未标记点,中,.,最小.所以标记,（,).图 3.3.1.2 与已标记点,直接相接的未标记点,中,.,最小.所以标记,(,).图 3.3.1.3 与已标记点,直接相接的未标记点,中,最小.所以标记,(,).图 3.3.1.4 与已标记点,中直接相接的未标记点,中,.,最小,所以标记,(,).图 3.3.1.5 与已标记点,直接相接的未标记点,中,最小.所以标记,(,).图 3.3.1.6 与已标记点,中直接相连的未标记点,标记,(,).图 3.3.1.7 所有点都标记,计算停止.最佳路线为-.最短时间或最短距离为14.3.4 Dijkstra算法解决有向路径问题有向图的路径有着广泛的应用,对求最短径问题有不同的算法,本文用Dijkstra算法有解决有向路径问题.有向路径与无向路径有着本质行的区别,如下图3.4.1所示的链到是一个通道,而到就不通.图 3.4.1在配送中可能遇到单向行车道.本小节主要解决这类问题.例3.4某物流公司的派送点要送货到.下图3.4.2所示为到的路线示意图,每条线段上的数字是他们之间的距离.求从到所需最短距离.图3.4.2 路线示意图解 标记原始点原始点(0,),其余点为未标记点. 图3.4.3与相邻的三个点中,.最小,所以标记,（4,）.图 3.4.4到不通,所以不考虑.与,相邻的两个点中,.最小,标记,(7,）.图 3.4.5最后只剩一个点.,.标记点,(10,).图 3.4.6标记完毕.最短路程为10.路径为.3.5本章小结Dijkstra算法基本的思想是把点固定标记,将为标记点转化为已标记