| 标题 | 用ＥＸＣＥＬ解决一类配送路线的制定和优化问题 |
| 范文 | 姚裕华 勇 刚 张 卓 摘要:EXCEL在管理科学领域的应用很多,如线性规划、运输问题、指派问题、网络最优化问题、项目管理、库存管理、预测、排队论和计算机仿真,等等。运用EXCEL建立模型,求解模型,能对管理者的决策提供很好支持。配送路线的制定和优化问题在实际物流操作中有着广泛的应用,也是非常困难的问题,借助EXCEL工具来辅助制定和优化配送路线,主要是对起点和终点相同的一类路径规划问题做出分析。 关键词:配送路线;优化;描述法;节约法;EXCEL 中图分类号:O227文献标识码:A Abstract: EXCEL has extensive use in management science, such as linear programming, transportation problem, distribute problem, network optimization, program management, inventory management, anticipate, queue theory and compute emulate etc. It's a good support to the decision of manager, using EXCEL to establish and solve models. The choosing and optimization of distribute route is very useful in logistics operation and also very difficult. In this text, we mostly use EXCEL to solve the problem of routing programming with same start and end point. Key words: distributing route; optimizing; describling method; saving method; EXCEl 0引言 美国物流管理协会(Council of Logistics Management)把物流定义为迎合顾客需求而对原材料、半成品、产成品以及相关信息从产地到消费地高效率、低成本流动和存储而进行的规划、实施和控制过程。并且认为一个典型的物流系统组成要素包括:客户服务、需求预测、分拨系统管理、库存控制、物料搬运、定单处理、零配件和服务支持、工厂和仓库选址、区位分析、采购、包装、退货处理、废弃物处理、运输管理、仓储管理。从中我们可以看出运输时是物流决策的关键所在,除了采购成本以外,一般来讲,运输成本比其他任何物流活动的成本所占的比重都高。其中配送路线的选择和优化是运输决策中的一项重要决策。 尽管路线选择问题种类繁多,但我们可以将其分为几个基本类型:一是起点和终点不同的单一路径规划:二是多个起点和终点的路径规划:三是起点和终点相同的路径规划。 起点和终点不同的单一路径规划这类运输路径规划问题可以通过特别设计的方法加以解决,最简单最直接的方法就是最短路径法;多个起点和终点的路径规划这类问题经常发生在多个供应商,工厂或仓库服务于多个顾客的情况下,可以用一类特殊的线性规划算法,即运输方法来解决;起点和终点相同的路径规划这类问题在企业拥有自己的运输工具时就相当普遍了。 在这篇文章里,我们将介绍起点和终点相同的路径规划的这类问题。 1提出问题 首先我们来看一个具体的问题,某物流公司有一配送中心(P)就有右图形状的配送路线。A～J表示收货站,括号内的数据为发送量(吨),路线上的数字表示道路距离(公里)。这时,为使行驶尽量少,应该如何去求配送路线?假设能利用的车是2吨和4吨两种,并限制车辆一次运行的初步距离在30公里内。 该问题在起点和终点相同的路径规划的这类问题中具有代表性,这类问题的优化方法有扫描法和节约法。 扫描法的步骤为:(1)在地图或方格图中确定所有站点的位置(含仓库)。(2)至仓库始沿任一方向外划一条直线,沿顺时针或逆时针方向旋转该方向直到与某一站点相交。考虑:如果在某线路上增加该站点,是否会超过车辆的载货能力?如果没有,继续旋转直线,直到与下一个站点相交,再次计算累计货运量是否超过车辆的运载能力(先使用最大的车辆),如果超过就剔除最后的哪个站点,并确定路线。随后,从不包含上一条线路上的站点开始,继续旋转直线以寻找新路线,继续该过程直到所有站点都被安排到路线中。(3)排定各路线上每个站点的顺序使行车距离最短,排序时可用“水滴法”或求解“流动推销员”问题的任何算法。 节约法是由克拉克?怀特发现的,它能够灵活地处理许多现实中的约束条件,对站点数量不大的问题能够较快地算出结果,且结果与最优解很接近,该方法能过同时确定路线和经过各站点的顺序。节约法的目标是使所有车辆的行使总里程最短,并进而为所有站点提供运输的车数最少。该方法首先假定每一个站点都由一辆虚拟的卡车提供服务,随后返回仓库,如右图所示。 这时的路线是最长的,下一步将两个站点合并到同一条行车路线上,减少一辆运输车,相应地缩短运输距离,不过合并一定要注意满足约束条件。合并后缩短的距离减少了dAO+dOB-dAB。只要条件满足就可以继续合并,直到所有的站点的路线都完成。 2用EXCEL辅助解决问题 对于上面的具体问题的分析步骤如下: 第一步:绘出最短距离距阵图,从配送网络图中计算出配送中心与收货点及收货点之间的最短距离矩阵: 用EXCEL的求解方法如下: 用FLOYD算法需要进行11步迭代计算,令该网络图的全矩阵为 Dd,当两点间没有直达路时,d为无穷大,这里令d=100足以解决问题。算法基本步骤为: (1)输入权矩阵D=D (2)计算D=dk=1,2,…,11 其中,d=mind,d+d (3)D=d中元素d就是从配送网络图中计算出配送中心与收货点及收货点之间的最短距离矩阵。 (4)D0为权矩阵,数据要自己输入,D1到D11为每步迭代中产生的矩阵,D11为从配送网络图中计算出配送中心与收货点及收货点之间的最短距离矩阵,F0到F10为辅助矩阵,他们在表格中位子如下: 根据FLOYD算法,下面介绍用EXCEL的分析步骤: (1)建立结构。 Dii=0,…,11的结构为: Fii=0,…,10的结构为: (2)输入权矩阵D0的数据。 (3)选中矩阵D1中B17单元格输入公式“=IFB3>P3,P3,B3”,当鼠标移至单元格右下角时变成实心加号,此时按住左键,朝各个方向拖拉可以将整个矩阵用公式覆盖,这时你可以点击该矩阵内的任一单元格,如单元格E21就会显示公式“=IFE7>S7,S7,E7”。 if函数中有三项,第一项为逻辑运算式,如果它的值取true函数就返回第二项值,否则就返回第三项值,用以计算d=mind,d+d。 选中D1中的公式区B17∶L27,用Ctrl+C复制,然后用Ctrl+V将其中的公式粘贴到D2到D11的对应公式区中。 (4)对辅助矩阵Fii=1,…,10,进行从F0到F10的依次计算。这里只介绍F0,其他的依此类推。 对于F0: (a)先将D0的第一行的数值赋给F0的横填充区,将D0的第一行列的数值赋给F0的竖填充区,可先赋一个值,然后进行拖拉;要是对于Fi,就要将Di的第i+1行和列的数据分别赋予Fi的横填充区和竖填充区。 (b)在o2单元格中填入公式=n2+o1;要是对于Fi就要在对应的单元格中填入公式=该单元格左边的单元格 +该单元格上面的单元格。 (c)用模拟运算表进行求和运算:选中黑框内区域。 在“数据”菜单中选择“模拟运算表”项,会弹出下图的对话框,将o2单元格左边的单元格填入到“输入引用行的单元格”,将o2单元格上边的单元格填入到“输入引用列的单元格”,然后按确定,这样就得到矩阵F0;对于Fi可以对应操作。 当从F0到F10都运算好之后,就会得到从配送网络图中计算出配送中心与收货点及收货点之间的最短距离矩阵,以上完成了第一步。 第二步:绘出节约里程项目图,从最短距离矩阵中计算收货点相互间的节约里程。将最短路矩阵的第一行和第一列复制到行竖填充区中,并在单元格B2内填入公式,用模拟运算表进行求和运算的到下面表格: 然后将矩阵中的数据与最短距离矩阵D11中的数据对应相减,就得到节约里程项目(图中三角形部分)。 第三步:节约项目的分类,把节约项目有大到小顺序排列。如下表: 第四步:组成配送路线,从节约项目表中,按节约里程大小的顺序组成路线图。 (1)初次解。 线路数:10总行走距离:148公里车辆台数:2吨车10台 (2)二次解。按节约里程由大到小的顺序,连接A-B,A-J,B-C连接线。 线路数:7总行走距离:109公里车辆台数:2吨车6台4吨车1台 (3)三次解。其次,节约里程最大的是C-D和D-E。C-D和D-E两者都有可能与二次解的线路甲相连接,但由于甲的车辆载重与行走距离有限,不能再增加收货点,为此,略去C-D而连接D-E。 线路数:6总行走距离:99公里车辆台数:2吨车5台4吨车1台 (4)四次解。接下来节约里程最大的是A-E和E-F。由于A已组合在完成的线路甲中,所以略去A-E而将E-F连接在线路乙上。 线路数:5总行走距离:90公里车辆台数:2吨车3台4吨车2台 (5)五次解。按上面的方法继续即得到五次解。 线路数:4总行走距离:85公里车辆台数:2吨车2台4吨车2台 (6)六次解。按上面的方法继续即得到6次解。 线路甲:4吨车总行走距离:27公里装载量:3.6吨 线路乙:4吨车总行走距离:30公里装载量:3.9吨 线路丙:2吨车总行走距离:23公里装载量:1.3吨 3结束语 在这篇文章里,我们介绍了起点和终点相同的路径规划的这类问题。用EXCEL工具来辅助配送路线的选择问题的决策,能够达到比较好的效果。EXCEL在管理科学领域的应用很多,如线性规划、运输问题、指派问题、网络最优化问题、项目管理、库存管理、预测、排队论和计算机仿真,等等。运用EXCEL建立模型,求解模型,能对管理者的决策提供很好支持。 参考文献: [1] Ronald H. Ballou(美). 企业物流管理——供应链的规划、组织和控制[M]. 王晓东,胡瑞娟,等译. 北京:机械工业出版社,2002:145-197. [2] 弗雷德里克?S?希利尔,马克?S?希利尔,杰拉尔德?S?利伯曼(美). 数据、模型与决策[M]. 任建标,译. 北京:中国财政经济出版社,2001. [3] 胡运权. 运筹学教程[M]. 北京:清华大学出版社,2000:241-242. [4] 晶辰工作室. Excel2000预测分析和目标求解实例指南[M]. 北京:电子工业出版社,2001:1-24. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。