运用动态规划模型解决最短路径问题

运用动态规划模型解决物流配送中的最短路径问题王嘉俊（盐城师范学院数学科学学院09（1）班）摘要：随着现代社会的高速发展，物流配送成为了连接各个生产基地的枢纽，运输的成本问题也成为了企业发展的关键。运费不但与运量有关，而且与运输行走的线路相关。传统的运输问题没有考虑交通网络，在已知运价的条件下仅求出最优调运方案，没有求出最优行走路径。文中提出“网络上的物流配送问题“在未知运价，运量确定的情况下，将运输过程在每阶段中选取最优策略，最后找到整个过程的总体最优目标，节省企业开支。关键词：动态规划，数学模型，物流配送，最优路径1引言物流配送是现代化物流系统的一个重要环节。它是指按用户的订货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货人的活动。在物流配送业务中，合理选择配送径路，对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。物流配送最短径路是指物品由供给地向需求地的移动过程中，所经过的距离最短（或运输的时间最少，或运输费用最低），因此，选定最短径路是提高物品时空价值的重要环节。［1］经典的Dijkstra算法和Floyd算法思路清楚，方法简便，但随着配送点数的增加，计算的复杂性以配送点数的平方增加，并具有一定的主观性。我国学者用模糊偏好解试图改善经典方法［5，取得了较好的效果。遗憾的是，模糊偏好解本身就不完全是客观的。文献［6详细分析了经典方法的利弊之后,提出将邻接矩阵上三角和下三角复制从而使每条边成为双通路径,既适用于有向图也适用于无向图，但复杂性增加了。为了避免上述方法存在的不足，本文以动态规划为理论,选择合理的最优值函数,用于解决物流配送最短路径问题。动态规划是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家Bellman（贝尔曼）等人根据一类多阶段决策问题的特性，提出了解决这类问题的“最优性原理”，并研究了许多实际问题，从而创建了最优化问题的一种新方法——动态规划。动态规划在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用，而且由于动态规划方法有其独特之处，在解决某些实际问题时，显得更加方便有效。由于决策过程的时间参数有离散的和连续的情况，故决策过程分为离散决策过程和连续决策过程。⑵这种技术采用自底向上的方式递推求值，将待求解的问题分解成若干个子问题，先求解子问题，并把子问题的解存储起来以便以后用来计算所需要求的解。简言之，动态规划的基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优。多阶段决策问题是根据问题本身的特点，将其求解的过程划分为若干个相互独立又相互联系的阶段，在每个阶段都需要做出决策，并且在每个阶段的确定后再转移到下一个阶段，在每一个阶段选取其最有决策，从而实现整个过程总体决策最优的目的。国］适合用动态规划方法求解的问题是一类特殊的多阶段决策问题，具有“无后效性”的多阶段决策问题，一般具有以下特点：可以划分为若十个阶段，问题的求解过程就是对若十个阶段的一系列决策过程。每个阶段有若十个可能状态。一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。在任一个阶段，最佳的决策序列和该阶段以前的决策无关。各阶段状态之间的转换有明确定义的费用，而且在选择最佳决策时有递推关系(即动态转移方程)。［3］2动态规划模型在现实生活的生产运输中，往往出发地与目的地之间有多种路线可供选择，不同的路线所花费的时间与费用也不同，时间与费用决定着企业的发展，这就需要选择最短的路径来提高效率。为了解决这个问题，将动态规划的理论与方法运用于生产运输中，节约了时间，为：企业的发展提供了契机。建立这个规划模型的具体步骤如下：①划分阶段:把所给问题的过程，恰当的划分为若十个相互联系的部分，以便于求解，其中每个部分叫阶段。通常用k表示阶段变量⑵确定状态变量及其取值范围：状态表示在任一阶段所处的，它既是该阶段的起点，又是前一阶段的终点。通常一个阶段有若十个阶段。描述状态的变量称为状态变量。参数*表示第k阶段的状态变量。该阶段所有可能状态的全体称为状态集合，记为飞。状态变量要能描述决策过程演变的状态，又要满足无后效性的要求，而且维数要尽可能地少。确定决策变量及其取值范围：在某一阶段，当状态给定后，往往可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量，用u(s)表示第k阶段当状态为s时的决策变量，它是状态变量s的函数。决策变量的取值范围称为决策集合，通常用气(s「表示第k阶段状态为、时的允许决策集合。显然有七(s「gD(七)。建立状态转移方程：状态转移方程描述由一个状态到另一个状态的演变过程。因为某一阶段的状态变量及决策变量取定后，下一阶段的状态就随之而定。用S=t(s,u)表示k阶段与k+1阶段状态的变换规律⑰指标函数和最优指标函数值：阶段指标(又称阶段效益)是衡量该阶段决策效果的数量指标，它是整个系统效益的一部分，是阶段状态和阶段决策的函数。用d(s,u)表示在第k阶段由状态s和执行决策u(s)所得的效益。kkkkkk指标函数(又称目标函数)是衡量所实现过程优劣的一种数量指标，它表示系统执行某一策略所产生的效益，它是定义在过程(可以是全过程，也可以是后部子过程)上的数量函数，用f表示：f=f(s,u,s,u,••.,s),k=1,2,nk,nk,nkkk+1k+1n+1当初始状态给定时，过程的策略就确定了，因而指标函数也就确定，故指标函数是初始状态和策略的函数，即：f,n=f,n[\，P(\)]，指标函数f的最优值，称为最优指标函数值，记为f(s)，它表示从第k阶k,nkk段由状态s出发到过程结束时所获得的最优指标函数值。在最短路线问题中，f表示从第k阶段的点s至终点G的距离，f(s)表示由点s到G的最短距离，用kkkkd(s,u)表示在第k阶段由点s到点s=u(s)的距离。kkkkk+1kk最后得到动态规划的一般模型为:f(s)=optb(s,u)+f("(s))},

kkkkkk+1kk4I”eD^(：「[f<s)=0,k-n,n-1,1,f(s)为从状态s出发到终点的最优效益，“opt”是optimization(最优化)的缩写kkk[23实例分析为进一步说明该方法的有效性和实用性，先将该方法运用于某物流配送网络中：设某物流配送网络图由9个配送点组成，点人为配送中心，A为终点，试求自人到图中任何配送点的最短距离。图中相邻两点的连线上标有两点间的距离由首先根据网络图以及上面的建模方法我们可以将运输过程划分成三个阶段，分别为：第一阶段人，第二阶段人,人，人，人，第三阶段人，人，A,A，显然两点之间直线013572468路径小于折线路径阶段变量用k表示；状态变量人表示k阶段初可能的位置；决策f^(气)表示k阶段初可能选择的路线；由后向前逐步推移计算最优路径：当k=3时，由人，人，人，人到人只有一条路线，故f(a)=16,f(A)=8,f(A)=4,f(a)=142468932343836当k=2时，出发点有A,A,A,A三个，若从A出发，只有一个选择，至A，所以f(A)=2713571221有两个选择，所以f(A)=min<d有两个选择，所以f(A)=min<d(A,A)+f(A)]23232I_命八d(A,A)+f(A)[-min23434J5+16]=1810+8从A出发，有两个选择，至％A6，所以f(A)=min<d2(A5,A4)+f3(A』.J16+8d(A,A)+f(A)|mm[任+425636J=19从a出发，有两个选择，所以f(A)=min'd(A,A)+f(A)]f11+4]J2/7636|=minJ|=15Id(A,A)+f(A)|112+14TOC\o"1-5"\h\zI27838^最短路线是A7tA6tA9当k=1时，出发点有A一个，若从A出发，至A，所以f(A)=3100110若从a出发，至A，所以f(A)=250310若从a出发，至A，所以f(A)=270510若从a出发，至A，所以f(A)=240710由上面计算得到最优路径f(A)=24,最优路径为A-A-A-A从a出发，有两个选择，所以f(A)=min由本实例我们可以总结出动态规划的优越性所在：求解过程，结果清晰明了；能得到一组解，有利于分析结果；易于确定全局最优解；4结论用动态规划解决多阶段决策问题可以提高效率，而且思路清晰简便，同时易于实现，虽然使用动态规划方法也有一定的限制，如状态变量必须满足无后效性，不考虑路况，天气等不确定因素对行程的影响，并且只适用一些维数相对较低的问题等。但是可以看到，动态规划的应用是很广的，已成功解决了许多实际问题，具有一定的实用性。本文将动态规划思想运用到求解物流配送中的最短路径问题中，其优点在于思路清晰，方法简便，理论可靠，在实际运用中取得了良好的效果。但是本文只考虑了一个起点的应用实例，在实际中有可能存在多个起点的情况，因此我们可以考虑将其进行改进，使之更好的运用在实际中，为企业的发展提供更多的帮助。Usingthedynamicprogrammingmodelis

usedtosolvetheshortestpathproblem

logisticsdistributionWangjiajunAbstract:withtherapiddevelopmentofmodernsociety,thelogisticsdistributionbecameconnectedeachproductionbasehub,transportationcostproblemhasbecomethekeytothedevelopmentoftheenterprise.Freightvolume,andnotonlyfromabouttransportationandwalkingroutesrelated.Traditionaltransportproblemsdidnotconsiderthetrafficnetwork,undertheconditionoftheknownfreightrateonlyfindoutoptimalschedulingsolutions,notaskedtheoptimalwalkpath.Thispaperputforward"Internetlogisticsdistributionproblem",volumeinunknownrate,thecase,willdeterminethetransportationprocessisdividedintoseveralstages,ineachphaseoftheselectionoftheoptimumstrategy,finallyfoundthewholeprocessoftheoveralloptimumtarget,saveenterprisespending.Keywords:dynamicplanning,mathematicalmodel,thelogisticsdistribution,optimalpath［参考文献］［1］蒋琦玮，陈治亚物流配送最短径路的动态规划方法