《图论在物流管理中的应用.docx》由会员分享，可在线阅读，更多相关《图论在物流管理中的应用.docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论在物流管理中的应用 摘要：物流行业是当今世界发展最迅猛的行业之一，它涉及订购、仓储、运输、销售等多个环节。本文针对运输环节进行探讨并以邮政运输问题为例探讨物流运输问题的一般解题思路。通过对邮政网点分布图和相关数据的分析，在满意时间限制和货物装载要求的条件下，求解出访空车率引起的损失费尽可能少的最短路途。本文实行分类探讨的方法，综合运用Floyd算法、TSP算法和动态规划法寻求最优邮路。 关键词：Floyd算法；TSP算法；邮递员问题；动态规划法 物流管理被媒体誉为“21世纪最大的行业”，是提高企业经济效益的重要源泉。它凭借以高新技术为基础的先进经营方式和管理方式，有效地整合资源、降低成本、
2、提高效率，从而大大提高了整个社会生产力和市场竞争力。物流管理的各种理论深化我们的日常生活，邮政运输问题就是最好的实例。下面我们将以此为例，探讨Floyd算法、TSP算法及动态规划算法在物流领域的运用。 一些符号说明如下。W：赋权临街矩阵；R：路径记录矩阵；D：总局；Di：虚拟总局；Zi：第i个支局。其他符号在文中给出说明。 我国的邮政运输网络采纳邮区中心局制，即以邮区中心局作为基本封发单元和网络组织的基本节点。首先由总局将邮件分发到各个支局，再有支局分发到更低级的邮政网点，以此逐层向下，最终到达收件人的手中。 图1是某地区的邮政网点分布图。 D是邮政总局，Zi是该地区的16个邮政支局。若每辆邮
3、车最多容纳65袋邮件，行驶速度均为30km/h，为了加强邮车的保养，规定一天最多行驶6个小时。邮车在各支局卸装邮件耗时5分钟。各邮政网点间的路途长度和各自装卸的邮包量数据见附录1。试问最少须要多少辆邮车才能满意该县的邮件运输需求？同时，为提高邮政运输效益，应如何规划邮路和如何支配邮车的运行？其中，空车率=-邮车运载的邮件量）/邮车最大承运的邮件量，单车由于空车率而削减的收入为。 一、模型分析 依据物流管理的学问我们知道，该题的目标是在满意工作时间小于6小时，完成全部邮件收发任务的前提下，寻求最短路径和花费最优的邮递运输方案。 依据题意，问题可归纳为如下数学模型 minC min1g s.t.P
4、 其中表示邮路方案，C表示空车损失费，1g表示方案的总路径，表示邮路集合。 通过对题中数据的处理我们发觉，寄达16个支局的邮包量为176袋，而收寄的邮包量为173袋。考虑到每辆邮车最多可以装载65袋邮包，因此从总局D至少发出3趟邮车。我们运用分类思想的方法，分别对下列四种状况加以探讨，依据最短路问题，综合运用Floyd算法和动态规划法，最终给出满意问题要求的最优方案 二、模型的建立与求解 通过题目给出各个邮政网点间的距离，我们给出17个邮政网点是直达矩阵A1717，运用Floyd算法，基本思想是：干脆在图的带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵L1，L2，.Lv，使最终得到的矩阵Lv
5、成为图的最短距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。 此算法的主要程序流程如下。 1.输入赋权邻接矩阵W。 2.赋初值：对全部i、j，L1W，ri，jj，k1。 更新L，R：对全部i，j，若L+LL，则LL+L，Rk。 若k=v，停止，输出L、R。 否则kk+1，重复第一步。 通过上述方法求解得各个邮政网点的最短路径。 通过上面的分析，我们知道由于寄达16个支局的邮包量为176袋，而收寄的邮包量为173袋，考虑到每辆邮车最多可以装载65袋邮包，总局D至少发出3趟邮车。为了节约成本，最多发3辆车。 我们分如下几种状况探讨。 方案一：出动1辆，车发3趟 我们视察图形发觉该题类似一个
6、旅行商问题，即从一点动身，通过全部的节点一次且仅有一次，最终回到起点。但该题又与旅行商问题存在一些区分，为了便利问题求解，我们提出“虚拟中转站”的概念。因为运输方案可以总结为 我们把总局D虚化成三个虚拟的总局D1，D2，D3，三个虚拟的总局和其他16个支局的关系继承了总局D与16个支局的关系. 我们假设邮车从D1动身，经过包括D2，D3和其他16个支局的18个点，最终回到D1。这就将16个支局分成了3个划分，每个划分里构成一条邮路。从而将该问题简化成“中国邮递员问题”。 对于“中国邮递员问题”，我们提出下面2种解决方案。 表上作业法 视察网络图，若图中不存在奇点，则过每条边一次且仅有一次的欧拉
7、圈就是最短路途。若图种有奇点，就必需在某些边上重复一次或多次。 1.将途中的奇点两两配对，把每一对奇点之间的一条链的全部边作为重复边加到途中，这样新图种必无奇点，给出一个初始可行方案。 2.视察图中的每个圈，调整方案，使得在最优方案中，图的每一条边上最多一条重复边，且各个圈上的重复边总权不大于该权总权的一半。 动态规划法 我们常常会遇到困难问题不能简洁地分解成几个子问题，而会分解出一系列的子问题。简洁地采纳把大问题分解成子问题并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。 为了节约重复求相同子问题的时间，本文引入一个数组，不管它们是否对最终解有用，把全部子问题的解
8、存于该数组中，这就是动态规划法所采纳的基本方法。 设计一个标准的动态规划算法，通常可按以下几个步骤进行。 1.划分阶段：根据问题的时间或空间特征，把问题分为若干个阶段。留意这若干个阶段肯定要是有序的或是可排序的，否则问题就无法用动态规划求解。 2.选择状态：将问题发展到各个阶段时所处于的各种客观状况用不同的状态表示出来。当然，状态的选择要满意无后效性。 此外还有许多解决此类问题的方法，如遗传算法、粒子群算法、蚁群算法等。鉴于篇幅的限制我们不一一说明，只详细叙述了上面两种求解“中国邮递员问题”的经典算法。 鉴于该问题改进后的网络图存在肯定的困难度，我们运用动态规划编程求解得到该方案的最短里程数为
9、279公里。因为邮车速度是30km/h，时间至少须要9小时，不满意题中最多行驶6小时的要求，所以此方案不行行。 方案二：出动2辆车，各发2趟 该种方案即将16个支局分成4个划分。同样运用方案一中阐述的算法，求解得到该方案的最短里程数是334km。考虑进装卸货全部的时间，得到每辆车的行驶时间为6.4小时，超过了6小时的时间限制，故此方案不行行。 方案三：出动2辆车，1辆车发1趟，1辆车发2辆 运用以上同样的方法可以得到其最短里程数为313km，最高时速30km/h，可得须要626分钟；再加上16个支局的装卸时间为80分钟，以及其中一辆车在县局的装卸时间10分钟，共736分钟。因此平均每辆车耗时3
10、58分钟，恰好满意，时间的限制。再考虑2辆车要送16个支局的因素，则至少有1辆车须要送8个支局。通过运行自己编写的推断程序，可以得到的结论是：在6个小时的时间限制下，这样的邮路是不存在的，因此这种方案也不予考虑。 方案四：出动3辆车，每辆车各发1趟 本方案与方案三所需的最短里程数同为313km，总共需时736分钟，平均每辆车耗时不到239分钟。由于有3辆车，则至少有一辆车须要投送6个支局。再运行上述的推断程序则可以知道这样的邮路是存在的，因此本方案可行。 再依据题中给出的数据得到该问题的最优解。 三、总结 通过邮政路途问题，我们给出了物流问题的一般思路，即通过先进的调度方案和合适的经营管理机制
11、，达到获利最多、成本最小或损失最少的目标。图论中最短路问题、最小费用最大流、中国邮递员问题、最小生成树、安排网络图、关键路径、TSP问题等都给物流管理供应了很好的思路。图论在物流管理中的作用可见一斑。 通过本学期对运筹课程的学习，我们驾驭了单纯性算法、动态规划法、线性规划、非线性规划、排队论、决策论等经典的运筹模型。通过本次论文我们发觉运筹学的探讨与生活中的实际问题有亲密的关联，它帮助我们拓宽了思维，加深了对身边问题相识，运用数学的方法使统筹支配身边的事，达到事半功倍的目的。 参考文献： 1金钢，师群昌，刘小麟.邮政运输网络中的邮路规划和邮车调度J.数学的实践与相识，2022. 2费蓉，崔杜武.中国邮递员问题的动态规划算法探讨J.计算机探讨与发展，2022. 3谢金星，薛毅.优化建模与Lindo/Lingo软件M.北京：清华高校出版社，2022. 4运筹学教材编写组.运筹学M.北京：清华高校出版社，2022. 第8页 共8页第 8 页 共 8 页第 8 页 共 8 页第 8 页 共 8 页第 8 页 共 8 页第 8 页 共 8 页第 8 页 共 8 页第 8 页 共 8 页第 8 页 共 8 页第 8 页 共 8 页第 8 页 共 8 页