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

运用动态规划模型解决物流配送中的最短路径问题摘要: 随着现代社会的高速发展, 物流配送成为了连接各个生产基地的枢纽,运输的成本问题也成为了企业发展的关键。运费不但与运量有关, 而且与运输行走的线路相关。传统的运输问题没有考虑交通网络, 在已知运价的条件下仅求出最优调运方案,没有求出最优行走路径。文中提出“网络上的物流配送问题“, 在未知运价,运量确定的情况下, 将运输过程在每阶段中选取最优策略, 最后找到整个过程的总体最优目标,节省企业开支。关键词: 动态规划,数学模型, 物流配送, 最优路径 1引言物流配送是现代化物流系统的一个重要环节。它是指按用户的订货要求,在配送中心进行分货、配货,并将配好的货物及时送交收货人的活动。在物流配送业务中,合理选择配送径路,对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。物流配送最短径路是指物品由供给地向需求地的移动过程中,所经过的距离最短(或运输的时间最少,或运输费用最低),因此, 选定最短径路是提高物品时空价值的重要环节。[1] 经典的 Dijkstra 算法和 Floyd 算法思路清楚,方法简便,但随着配送点数的增加,计算的复杂性以配送点数的平方增加,并具有一定的主观性。我国学者用模糊偏好解试图改善经典方法?? 5,取得了较好的效果。遗憾的是,模糊偏好解本身就不完全是客观的。文献?? 6详细分析了经典方法的利弊之后,提出将邻接矩阵上三角和下三角复制从而使每条边成为双通路径,既适用于有向图也适用于无向图, 但复杂性增加了。为了避免上述方法存在的不足,本文以动态规划为理论,选择合理的最优值函数,用于解决物流配送最短路径问题。动态规划是解决多阶段决策过程最优化问题的一种数学方法。 1951 年美国数学家 Bellman (贝尔曼)等人根据一类多阶段决策问题的特性,提出了解决这类问题的“最优性原理”,并研究了许多实际问题,从而创建了最优化问题的一种新方法——动态规划。动态规划在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用,而且由于动态规划方法有其独特之处,在解决某些实际问题时,显得更加方便有效。由于决策过程的时间参数有离散的和连续的情况,故决策过程分为离散决策过程和连续决策过程。[2] 这种技术采用自底向上的方式递推求值,将待求解的问题分解成若干个子问题,先求解子问题,并把子问题的解存储起来以便以后用来计算所需要求的解。简言之,动态规划的基本思想就是把全局的问题化为局部的问题,为了全局最优必须局部最优。多阶段决策问题是根据问题本身的特点,将其求解的过程划分为若干个相互独立又相互联系的阶段,在每个阶段都需要做出决策,并且在每个阶段的确定后再转移到下一个阶段,在每一个阶段选取其最有决策,从而实现整个过程总体决策最优的目的。[2,4] 适合用动态规划方法求解的问题是一类特殊的多阶段决策问题,具有“无后效性”的多阶段决策问题,一般具有以下特点: (1) 可以划分为若干个阶段,问题的求解过程就是对若干个阶段的一系列决策过程。(2) 每个阶段有若干个可能状态。(3) 一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。(4) 在任一个阶段,最佳的决策序列和该阶段以前的决策无关。(5) 各阶段状态之间的转换有明确定义的费用,而且在选择最佳决策时有递推关系(即动态转移方程)。[3