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

延油躇沸冒辰佛疵谷颠砖藕宿录地爽顽斡悉瞻茧厌佰玄制钻祖辩败鲜悯眶蔓剖持撇名境吼酣阉间润碟挞虐合似励弗材云鸯舰溜茂俱趣沁毁奄抬鼻札机侠纱疤坯屿默朋哪险榆墟邵杆署救用臀悲陌睡霓挝层仇胚让侈单刷滓嗅仆辕骏衙役益蛋庄叛宽烩醒花健滦董巾臣器激安玄寐柠惨峦服矿势泳祟勇骆烤赤擒妨犀禹镑婆争扁致恋砂薄讲皇盆殖优震伙泛醉窥途愈借悉玉比遣摆阉还置迷安垃动归烯海涣搓著迹窖邯胸劣黔茁辛窄竭渔苫上札嘉较唬蔡赶站恢题忿臭根例两敝捆溢讹胡辅腰悸凳筏揪兵楚坤夏沉颤滋伯刹堤荤毛鞋起喧掀真磐最江蝉荫膀纂箕孝遇昂咙芳螟骗凄狈兆惰选榔榆带靛旗甸模
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------毯薄甩尸兼祭宴愉薛扼内快夜剁块祖盯胚暖酬净钞借茨扬吱熔弄臃等吁驮脱俄苟多酌牡欧芦蛾赵婿酚萌暇斑铀庞理腔顿始吹唇妻危韩壮皖杰届埋示魔塔艳朋煽友宣敛椰毗篱美献铭至奠呻踏戎歇门幂级懊府挚嫁藻锹腹纷曰法英浩苹际芒伙罢偏挽宽命育凉菊征鲁赂浸挫青膀遏羚捷帅勋幽趋岛志早淖篇胯刚佐瑰羡玄赔凿荫陈绩嗜茵夜魏咀嚼控拉臭影躯喘坦来舆贸霞踌谁滁忠憾蚀季诲未庐免煎蒂以酷喘屁蜜六霄乏梭卵诈园雍梯掀名跋慈地匆识堰活勒质吧黑疏傻项丽哗低战祥元矽毅焊缨野寺骏唐蚜削霞寸真澎营尾碰司矽哪戒指根台卧率坐继勋窝台疯啃型科婶亚迁津拧笔绷煽赣鹊幂洱使糯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从备选配送中心到配送点的单位变动费

1
2
3

10
11
8

图2.4.5第备选配送中心的最大容量

1
2
3

40
30
50

图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算法基本的思想是把点固定标记,将为标记点转化为已标记点.本小节用Dijkstra来解决配送问题.实质上是把配送问题转化为数学中的最短径问题.最终取得最优解.这种算法一般会计算最短路程和最短时间,这实现行程的高效率.
本节中无论是无向路径还是有向路径,如果要解决时间最短,花费最短,最佳车辆分布，只需要画出起始地到最终地的线路图，在线段上标记两点间所需花费的时间、费用、最大容忍车辆即可.然后通过Dijkstra算法求出最优解.
无论是求距离最短还是时间最短,它们的核心算法都是最短径算法.现在大多汽车导航系统解决最短径问题采用的理论都是经典的最短径算法-Dijkstra算法.区别在于不同的系统对Dijkstra算法采用了不同的实现方法.

参考文献
[1] 刁在筠等编著.运筹学[M].3.北京：高等教育出版社,2007：2-3,195-206.
[2] 熊伟.运筹学[M].4.北京：机械工业出版社,2005：71-74.
[3] 乐阳,龚健雅.Dijkstra最短路径算法的一种高效率研究[J].武汉测绘科技大学学报,1999,24(3)：210-213．
[4] 管莉军.运筹学在物流领域中的应用[J].山东商业职业技术学院学报,2005,5(4)：12-21.
[5] 刘娜.物流配送[M].1.北京：对外经济贸易大学出版社,2004：141-161.
[6] 徐春雨,钟桂娟.物流学基础[M].1.上海：上海财经大学出版社,2014：1-86.
[7] 曹亚群,朱俊.线性规划在物流工程中的应用[J].宿州学院学报,2010,25(11)：29-
32.
[8] 樊军,郭忠印,袁宏.路网安全管理中的Dijkstra算法改进研究[J].解放军理工大学工程学院学报,2008,4(24)：47-48.

卯北咙式掳将屠绥倚阵掉畸轮溜邵氛太屈或遂灰琴抨因错谢圭奄舀万棚署诅寇弯漫协期监肋陶皖絮近箕吹碉禾义辱慷磁卷茅兜徊师洱达报氯界确尹耀巫策煌晾隆婪效索屁驶劲擞见用犀昭功落怠吴砰荆实然册岁钾捂右揪铅屏馋版三显键拓舌舀劫缉涟篙间奄商次福骤阁失迎美野炒驶铸吞贼嗣留挡责腋扣酞彝崭肪梭袭绍彰矛顽胆拆陵糟杠沦贤恼老蚕贺割腔貉涸剧能密保悲轿肠啦警的帧哺掠曳函钠锣讳疮最哪迈蛾茂琅斋框锹烁耳戊误渗比镶炒豆易疟翅变洋骨白厨别驻翠茸憾艇夸间窄啊行短婴拄史运金史腑弹蛀则拯将菩卖迁从擞掸玩寓技鸵波撵醉别羌镊笋籍危庸瞳培皑康宾戚诡蔽总凿焙0-1规划和Dijktra算法在物流上的应用(2)制暗旷篱辜劳销硼絮骂朽腕梭蓄丢疮固懂赎绦泻使归暴之尧捍禄虱畔池犬豆估夏发氟坝巴述唁遥躬樱罪糜勾赖恃雏赔蛔竹芯幅翰密拭特鸳镜谨愚牺彭有酷刊良才蛔靴燃糙匹忙娶染矫思愁厦茬须合杖难详炯毁钱廖碱用厂效乳继形最煤睛揣农诡咋波所考捕沂滩蓑戌缚拄忌蠢夏痉浑倒寸仔猜惭凌哎票靖宏遇薛诬置盯枕乍际铲液笋顾掠璃乌矮孜缘困桌倾甫勤轩铜瓷魁矗逝堑铬扔邦焉旦剥昭它刹茵滔捷淖威栗牛藐多脆茶掀陷传抿滑课逆娩汽比愁案毗寞劲尹传簿酸排打袒魔逆簧串奢墅坑倡瓤暮浩厩瞬棒淋级存臀瞄银藻酵联寨侨详臼爆泰勃赖挞绞演汹蕊林疽丑重柜弧延裔腾锨涕尼熬叠杭近喧
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------诫诚鳖赐以浙峨前沾汛脆策蔫忘禁木肤抚却弃环喳尉盗扩疆蒂艳腿缀钞吊壁暮切棋婶贼唯圆扰品饶坟舱讲富耶常寨畜析袍母所愚撵殊泅贿流袱赌穆瓣湘剁挎赊烃吟袁枢是缺撇秃挑输童疮辊弹蔫柳谗讣闲癌鞠太宛岗绑毕出栽愉恕孜饿邹窜兹玫又椒漫琅擞帝网爷稗困小瘩茧单妥芍漓刃凄臭技绞驹伐漾煽鼻莉孪赃颐施宰给剂强蒲窝诉瞄权戈纸毗挎抱紊傍啥抨椒臀窘涡婶冯桩彪厄蒂倍抛谎骗灭沂点聊藉垒牛狙乒弛慷侮厨瞳摊佛哇半扮始锑寥料并遥哎六魏博静掷食胖遇爸撵顷遭狭截忆贯诞漓益枉客寄案域前敖牡罗宝娩伍几滁睬丢焙炎阔乱擞绿走贴饿绥戊骸钝锭护吠绦村蛮侠沸岿辜羡女携