利用动态规划法求解运输问题的最短路径

第2期

2010年2月

文章编号：1001-3997（2010）02-0223-02

机械设计与制造

MachineryDesign＆Manufacture

223

利用动态规划法求解运输问题的最短路径

孙晓燕1李自良1彭雄凤1傅亚力2梁志强2（1昆明理工大学机电工程学院，昆明650093）

（2昆明船舶设备集团有限公司昆船设计研究院，昆明650051）

Thedynamicprogrammingappliedtosolvingtheshortest-pathoftransportationproblem

SUNXiao-yan1，LIZi-liang1，PENGXiong-feng1，FUYa-li2，LIANGZhi-qiang2

（1FacultyofMechanicalandElectricalEngineering，KunmingUniversityofScienceandTechnology，Kunming650093，China）（2KunmingShipDesignandResearchInstituteKunmingShipBuilding

Kunming650051，China）EquipmentCo.Ltd.，

【摘

要】将动态规划思想运用到求解运输问题最短路径中，将运输过程划分为几个阶段，在每阶段

中选取最优策略，最后找到整个过程的总体最优目标即最短径路。给出了动态规划方法的基本原理，建立了动态规划数学模型，通过一个实际应用例子具体说明动态规划求解运输问题最短路径过程，并总结出动态规划在此类问题中的优越性。

关键词：动态规划；最短路径；多阶段决策

【Abstract】TheDynamicProgrammingthoughtisappliedtoSolvingtheShortest-PathofTransporta－finally，findtheentireoptimalstrategyofthewholeprocess.ThebasicprincipleofDynamicProgrammingisintroducedandamathematicalmodelofDynamicProgrammingisestablished.TheprocessofSolvingtheShortest-PathofTransportationProblemisdescribedbyapracticalapplicationcase，whichshowtheadvantageofDynamicProgramming.

Keywords：Dynamicprogramming；Theshortest-Path；Multistagedecision中图分类号：TH16，O221.3文献标识码：A

tionProblem，transportationprocessisdividedtoseveralsections，chooseoptimalstrategyofeachsection，

1引言

针对最短路径问题，最容易想到的方法是穷举法，即列出所有可能发生的方案和结果，针对要求进行比较求出最优方案，对于简单变量少的问题还是可行的，但是对于复杂变量多的问题计算工作量就比较大。最短路径的最优性原理[1]启发我们从最后一步逐步向前推的方法来求解，也就引入了动态规划方法。

动态规划方法是解决多阶段决策过程最优化的一种方法。这一方法最初是由美国数学家R.Bellman等人在2O世纪5O年代提出的[2]，实践证明许多问题用动态规划求解比用线性规划或非线性规划更加有效，特别是对离散性问题，运用解析数学无法解决，而动态规划就成为得力的工具。动态规划方法把一个比较复杂的问题分解为一系列同一类型的更容易求解的子问题，计算过先按照整体最优思想逆序求出各个程单一化便于应用于计算机。

可能状态的最优策略，然后顺序求出整个问题的最优策略和最优路径。由于把最优化应用到每个子问题上，就系统的删减去了所有中间非最优方案使得计算量比穷举法大大减少。将动态规划思想应用到求解运输问题的最短路径中，方法简便，理论可靠，求解结果清晰明了，在实际运用中取得了良好的效果。

2动态规划基本思想

动态规划法是一种强有力的算法设计技术，它被广泛用于求

＊来稿日期：2009-04-11

必须局部最优。阶段的一系列决策过程。

（2）每个阶段有若干个可能状态。某种状态。

最佳决策时有递推关系（即动态转移方程）。

动态规划基本步骤：

①找出最优解的性质，并刻划其结构特征；

解组合最优化问题。这种技术采用自底向上的方式递推求值，将待求解的问题分解成若干个子问题，先求解子问题，并把子问题动态规的解存储起来以便以后用来计算所需要求的解。简言之，划的基本思想就是把全局的问题化为局部的问题，为了全局最优

多阶段决策问题是根据问题本身的特点，将其求解的过程划分为若干个相互独立又相互联系的阶段，在每一个阶段都需要做出决策，并且在一个阶段的决策确定以后再转移到下一个阶段，在每一阶段选取其最优决策，从而实现整个过程总体决策最优的目的[3-4]。适合用动态规划方法求解的问题是一类特殊的多阶段决策问题，具有“无后效性”的多阶段决策问题，一般具有以下特点：

（1）可以划分成若干个阶段，问题的求解过程就是对若干个

（3）一个决策将你从一个阶段的一种状态带到下一个阶段的（4）在任一个阶段，最佳的决策序列和该阶段以前的决策无关。（5）各阶段状态之间的转换有明确定义的费用，而且在选择

224

②递归的定义最优值；

孙晓燕等：利用动态规划法求解运输问题的最短路径

状态转移方程sk+1=sk-xk；

第2期

③以自底向上的方式计算出最优值；

④根据计算最优值时得到的信息，构造最优解。

阶段指标vk表示k阶段与所选择的路段相应的路长；指标函数vkn=Σvi表示k至4阶段的总路长；

i=kk

3动态规划建模

（1）将实际问题的过程划分成恰当阶段，确定阶段变量根据多阶段决策问题的实际过程，将其划分为若干个相互独立又相互联系的部分，每一个部分为一个阶段，划分出的每一个阶段通常就是需要做出一个决策的子问题。阶段通常是按决策

[3]

fk表示第k阶段点sk到终点E的运输成本；递推公式fk=min｛vk+fk+1｝，k=4，3，2，1；xk*表示最优决策；边界条件k=5时，f5=0。

将动态规划的计算结果列表表示，如表1所示。

表1计算结果列表

43

C2C3

2

B1B2B3k

D1D2C1

kEED1D2D1D2D1D2C1C2C3C1C2C3C1C2C3B1B2Bk[***********][***********]4030

knkk+1

30+040+010+3040+4060+3030+4030+3030+4070+4040+7060+6030+4020+7040+6040+4010+7050+6020+11040+7030+80

k[***********]0

kEED1D2D1C1，C2C1C1，C2B2，B3

进行的时间或空间上的先后顺序划分的，阶段变量用表示。

（2）确定状态，正确选择状态变量

在多阶段决策过程中，状态是描述每个阶段所必须的信息，表示每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态，用一个或一组变量来描述，状态变量必须既能描述过程的演变，又要满足无后效性。用表示第个阶段的状态变量。

（3）确定决策变量及允许的决策集合

决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。决策变量用xk表示；允许的决策集合是决策变量的取值范围用D（）表示。Ksk

（4）写出状态转移方程

xk），这里的函数关系TK因问题的不状态转移方程sk+1=T（Ksk，同而不同，如果给定第k个阶段的状态变量sk，则该阶段的决策变量xk一经确定，第k+1阶段的状态变量的值也就可以确定。

（5）列出指标函数

并要求具有可分离性及递推性；指标函数vkn的关系，

（6）写出动态规划函数基本方程，用f（）表示k-n阶段的ksn+1最优策略函数：

fn+1（xn+1）=0（边界条件）

f（）=opt｛vk+fk+1｝，k=n，n-1，…，1ksk

1

A

由表1中我们可以清晰地看出，运费最低的路线为AB2C1

D1E或AB3C1D1E或AB3C2D2E，最低运费为110。

由本实例我们可以总结出动态优化的优越性所在：（1）求解结果清晰明了；

）能得到一族解，有利于分析结果；（2

（3）易于确定全局最优解；（4）能利用经验提高求解效率。

4应用举例

我们将一个实际的运输问题抽象成一个网络图，如图1所示，节点A表示发送点，节点E表示终到点，其余节点为运输过程中可经由点，边线表示可能路径，边线上数值表示其间运输成本。根据上节所给出的动态规划建模方法来建立相应动态规划模型并求解运输过程中的最短路径。

第一阶段

B1

20A

4030

第二阶段70

4060

第三阶段C110

4060C23030C3

30

D2

第四阶段

5结束语

用动态规划解决多阶段决策问题效率是很高的，而且思路清晰简便，同时易于实现，虽然使用动态规划方法也有一定的限制，如状态变量必须满足无后效性，并且只适用一些维数相当低的问题等。但是可以看到，动态规划方法的应用是很广的，已成功解决了许多实际问题，具有一定的实用性。本文将动态规划思想运用到求解运输问题最短路径中，其优点在于思路清晰，方法简便，理论可靠，在实际运用中取得了良好的效果。但是本文只考虑了一个发货中心的应用实例，在实际中有可能存在多个发货中心的情况，因此我们可以考虑将其进行改进或者结合启发式算法，使之更好的运用在实际中，这有待于日后的继续研究。

30

B220

40

D1

30

E

40

4010

50B3

图1运输过程网络图

参考文献

1钱颂迪.运筹学［M］.北京：清华大学出版社，2002

2谬慧芬，邵小兵.动态规划算法的原理及应用［J］.中国科技信息，2005（21）：42

3蒋琦玮，陈治亚.物流配送最短径路的动态规划方法研究［J］.系统工程，2007，25（4）：27～29

4陈理荣.数学建模导论［M］.北京：北京邮电大学出版社，1999

首先根据网络图以及上节提到的建模方法我们可以将运输过程划分成四个阶段，

阶段变量用k表示；

状态变量sk表示k阶段初可能的位置；决策xk表示k阶段初可能选择的路线；