一类旅行总费用最小路线模型及其求解策略

维普资讯 http://www.cqvip.com 第ｌ９卷第４期　塔里木大学学报　ＶＯ１．１９　Ｎｏ．４　Ｄｅｃ．２０ｏ７　２００７年１２月　Ｊｏｕｒｎａｌ　ｏｆ　Ｔａｒｉｍ　Ｕｎｉｖｅｒｓｉｔｙ　文章编号：１００９—０５６８（２００７）０４—００２２—０３　一类旅行总费用最小路线模型及其求解策略　王继顺　闫敏伦　王传斌　（连云港师范高等专科学校数学系，江苏连云港　２２２００６）　摘要旅行总费用最小路线问题是生活实际中常见的一类问题，本文建立了该类问题的赋权多阶段有向图模型。多阶段有　向图是应用中常见的一种有向图，有许多运输、工程、管理等的实际问题能转化为有向图最短路问题进行求解，尤其赋权多阶　段有向图对解决该类实际问题更具有重要意义。研究了赋权多阶段有向图的最短路问题，从图上逆序标号法、表上作业法和　动态规划法不同的角度对文中模型给出了赋权多阶段有向图最短路求解策略。　关键词　有向图；赋权多阶段有向图；最短路　中图分类号：Ｏ１５７．５　文献标识码：Ａ　Ａ　Ｓｈｏｒｔｅｓｔ　Ｐａｔｈ　Ｍｏｄｅｌ　ｆｏｒ　ｔｈｅ　Ｍｏｓｔ　Ｅｃｏｎｏｍｉｃａｌ　Ｔｒａｖｅｌｉｎｇ　ａｎｄ　Ｉｔｓ　Ｓｏｌｕｔｉｏｎｓ　Ｗａｎｇ　Ｊｉｓｈｕｎ　Ｙａｎ　Ｍｉｎｌｕｎ　Ｗａｎｇ　Ｃｈｕａｎｂｉｎ’　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ－Ｌｉａｎｙｕｎｇａｎｇ　Ｔｅａｃｈｅｒｇ　Ｃｏｌｌｅｇｅ，Ｌｉａｎｙｕｎｇａｎｇ－Ｊｉａｎｇｓｕ－２２２００６）　Ａｂｓｔｒａｃｔ　Ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｐａｔｈ　ｐｒｏｂｌｅｍ　ｏｆ　ｔｈｅ　ｍｏｓｔ　ｅｃｏｎｏｍｉｃａｌ　ｔｒａｖｅｌｉｎｇ　ｉｓ　ｐｏｐｕｌａｒ　ｐｒａｃｔｉｃａｌｌｙ．Ｔｈｅ　ｍｕｌｔｉ—ｓｔａｇｅ　ｗｅｉｇｈｔｅｄ　ｄｉｒｅｃｔｅｄ　ｇｒａｐｈ　ｍｏｄｅｌ　ｆｏｒ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｉｓ　ｓｅｔ　ｕｐ．Ｍｕｌｔｉ—ｓｔａｇｅ　ｗｅｉｇｈｔｅｄ　ｄｉｒｅｃｔｅｄ　ｇｒａｐｈ　ｉｓ　ｐｏｐｕｌａｒ　ｉｎ　ａｐｐｌｉｃａｔｉｏｎ．Ｍａｎｙ　ｐｒａｃｔｉｃａｌ　ｉｓｓｕｅｓ　ｓｕｃｈ　ａｓ　ｔｒａｎｓ—　ｐｏｒｔ，ｅｎｇｉｎｅｅｒｉｎｇ，ｍａｎａｇｅｍｅｎｔ　ｃａｎ　ｂｅ　ｓｏｌｖｅｄ　ｂｙ　ｔｒａｎｓｆｏｒｍｉｎｇ　ｉｎｔｏ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｐａｔｈ　ｐｒｏｂｌｅｍ．Ｉｎ　ｐａｒｔｉｃｕｌａｒ，ｓｈｏｒｔｅｓｔ　ｐａｔｈ　ｐｒｏｂｌｅｍ　ｏｆ　ｔｈｅ　ｍｕｌｔｉ—ｓｔｇｅ　ｗｅｉｇｈｔａｅｄ　ｄｉｒｅｃｔｅｄ　ｇｒａｐｈ　ｉｓ　ｍｏｒｅ　ｓｉｇｎｉｉｃａｎｃｅ　ｉｆｎ　ｓｏｌｖｉｎｇ　ｓｕｃｈ　ｐｒａｃｔｉｃａｌ　ｐｒｏｂｌｅｍｓ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｗｅ　ｓｔｕｄｙ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｐａｔｈ　ｐｒｏｂｌｅｍ　ｏｆ　ｔｈｅ　ｍｕｌｔｉ—－ｓｔａｇｅ　ｗｅｉｇｈｔｅｄ　ｄｉｒｅｃｔｅｄ　ｇｒａｐｈ　ａｎｄ　ｓｅｖｅｒａｌ　ｓｏｌｕｔｉｏｎｓ　ｔｏ　ｉｔ　ａｒｅ　ｐｒｅｓｅｎｔｅｄ　ｂｙ　ｕｓｉｎｇ　ａｎ　ｅｘａｍｐｌｅ　ｆｒｏｍ　ｄｉｆｆｅｒｅｎｔ　ｐｅｒ・　ｓｐｅｃｔｉｖｅ　ｔｈａｔ　ｉｓ　ｒｅｖｅｒｓｅ　ｌａｂｅｌｉｎｇ　ｍｅｔｈｏｄ　ｏｎ　ｔｈｅ　ｇｒａｐｈ，ｔｈｅ　ｔａｂｕｌａｒ　ｍｅｔｈｏｄ　ａｎｄ　ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ．　Ｋｅｙ　ｗｏｒｄｓ　ｄｉｒｅｃｔｅｄ　ｇｒａｐｈ；ｍｕｌｔｉ—ｓｔａｇｅ　ｗｅｉｇｈｔｅｄ　ｄｉｅｃｔｒｅｄ　ｇｒａｐｈ；ｓｈｏｒｔｅｓｔ　ｐａｔｈ　１　引言　旅行总费用最小路线问题是生活实际中常见的　一工具，用于解决其他的优化问题。　本文主要通过一个旅行总费用最小路线问题，　建立该类问题的赋权多阶段有向图模型，然后从图　类问题，同管道铺设、线路安排、厂区布局、设备更　新等问题一样都可以转化为最短路问题。最短路问　上逆序标号法、表上作业法和动态规划法不同的角　度给出了赋权多阶段有向图最短路的几种求解策　略。　题　是指对任何一个赋权的有向图，指定一个顶点　为始点，一个顶点为终点，在从始点到终点的诸路　中，求解最短路及其长度的问题。最短路问题实质　２　赋权多阶段有向图　已知如图１所示的单行线交通网，每弧旁的数　字表示通过这条单行线所需要的费用。现在某人要　上是一个组合优化问题，它不仅可以直接应用于解　决生产实际的许多问题，而且经常被作为一个基本　①　收稿日期：２００７—０５—３０　基金项目：连云港师专数学的应用与建模科技创新团队课题（编号：ＬＳＺＴＤ２００７０３）　作者简介：王继顺（１９７０一），男，硕士，讲师，研究方向为图论组合优化，计算机辅助几何设与逆向工程。　Ｅ—ｍａｉｌ：ｗａｎ￣ｉｓｈｕｒｄＯ０１＠ｙａｈｏｏ．ｃｏｒｎ．ｃａ　｛为通讯作者　维普资讯 http://www.cqvip.com ；　第ｇ期　王继顺等：一类旅行总费用最小路线模型及其求解策略　从地出发，通过这个交通网到去，求使费用最小的旅　行路线。　Ａ　Ｅ　图１交通网络图　这种求解费用最小的旅行路线问题，一般地可　以用求解最短路的方法如Ｄｉｊｋｓｔｒａ方法解决¨』。本　文将这类问题转化为赋权多阶段有向图模型，然后　从图上逆序标号法、表上作业法和动态规划法不同　的角度给出了赋权多阶段有向图最短路的几种求解　策略　赋权多阶段有向图　就是对一个图的顶点分　成几个部分，把每一部分叫做一个状态，把相邻两个　状态以及它们之间的有向线段所构成的有向边叫做　一个阶段，如果每一条边都赋有一个实数（权，长　度），这样的图就是赋权多阶段有向图（如图２），在　每一个阶段中，所有有向边的始点为该阶段的起始　状态，终点为该阶段的终结状态。　Ａ　Ｅ　３赋权多阶段有向图最短路求解方法　３．１　图上逆序标号法　图上逆序标号法就是从终点开始逐步逆向推　算，将各阶段的每一顶点到终点的最短路和长度标　于图上的方法，它贯彻了Ｄｉｊｋｓｔｒａ方法的思想，所以　这种方法是正确的　。下面对图２阐述该方法实施　步骤：　①首先，与终点Ｅ联接的有三个顶点Ｄ，，Ｄ　和　Ｄ　，从Ｄ。开始计算，Ｄ。到Ｅ只有一条路，因此没有　选择的余地，就是最短的路线，其长度为６，写在顶　点的上方的方框中，并注上从Ｄ。到终点Ｅ的最短　路为Ｄ。一Ｅ；同样，Ｄ　至Ｅ也只有一条路线，故从　Ｄ　到终点Ｅ的最短路为Ｄ：一Ｅ，长度为５，Ｄ，至Ｅ　的最短路为Ｄ　一Ｅ，长度为２；　②再看顶点Ｃ。，与Ｃ。联接的有顶点Ｄ。，Ｄ　，　Ｄ　，Ｃ。一Ｄ。路线长度为５，而Ｄ。至终点Ｅ的最短路　长度为６，因此Ｃ。至Ｄ。再至终点Ｅ的最短路长度　为５＋６＝１１，Ｃ。至Ｄ　再至Ｅ的最短路长度为５＋５　＝１０，Ｃ。至Ｄ　再至Ｅ的最短路长度为４＋２＝６，三　个长度中以６为最小，所以把６写在Ｃ．上方的方框　中，并注上Ｃ。一Ｄ　一Ｅ；同样，顶点Ｃ　至Ｅ终点的最　短路长度为３，最短路即为Ｃ　一Ｄ　一Ｅ；　③同样可得Ｂｌ—Ｃ２一Ｅ，Ｂ２一Ｃ２一Ｅ及Ｂ３一Ｃ２　一Ｅ；最后由顶点Ａ求得Ａ到终点Ｅ的最短路为Ａ　—Ｂ。一Ｅ，其长度为７；这样就得到从Ａ到Ｅ的最短　路长度为７，而最短路为Ａ—Ｂ。一Ｃ　一Ｄ　一Ｅ。　整个过程如图５。　图３　图上逆序标号法求解　通过图上逆序标号法可以看出，各阶段的每一　个顶点到终点的最短路及其长度都已确定下来，但　是当某一阶段其始状态各顶点到终点的最短路长度　有相等的情况时，则前一阶段到终点的最短路将不　止一条，如Ｃ。，Ｃ　到Ｅ的最短路长度都为６，则本多　阶段有向图始点Ａ到终点Ｅ的最短路就为两条：Ａ　—Ｂｌ—Ｃｌ—Ｄ３一Ｅ，Ａ—Ｂｌ—Ｃ２一Ｄ３一Ｅ。　３．２　表上作业法　表上作业法实质就是在半域上运用摹矩阵运算　求解最短路的方法Ｈ　。　①对图１，先写出各阶段的摹矩阵，如第一阶段　ＡＢ，第三阶段ＣＤ写出来就是　Ｂｌ　Ｂ２　Ｂ３　Ｓｔａｇｅ（Ａ，Ｂ）＝Ａ［２　３　７］和　Ｄｌ　Ｄ２　Ｄ３　ｓｓｔ　ａ（ａｇｅ（Ｃ，　）Ｄ）＝　＝　ｌＣ２【　３５　；　】　１　Ｊ，在摹矩阵中应写而未　写的元素都是＋∞。　②下面用表上作业法求得最短路的长度及相　应的最短路（表１）。表中，Ｓｔａｇｅ（Ａ，Ｘ…）由Ｓｔａｇｅ　（Ａ，Ｘｉ）　Ｓｔａｇｅ（Ｘｉ，Ｘ…）所得，这里ｘｉ依次取Ｂ，　Ｃ。Ｄ。　维普资讯 http://www.cqvip.com 塔里木大学学报　第ｌ９卷　表１－１表上作业法求解过程　３．３动态规划法　此可知，最短路的长度为７，最短路为Ａ—Ｂ。一Ｃ：一　Ｄ３一Ｅ。　动态规划是运筹学的一个重要分支，它是专门　研究满足Ｂｅｌｌｍａｎ递推公式的一大类多阶段决策问　题的理论、方法和应用的学问。Ｂｅｌｌｍａｎ递推公式　为　引：　（　）＝ｍｉｎ｛ｇ（　，ｔ）＋　＋ｌ（ｔ）｝ｌ　（Ｉ）　（　）＝０（２）　４　结论　本文建立了求解费用最小的旅行路线问题的赋　权多阶段有向图模型。赋权多阶段有向图模型是应　０　ｎ—　用中常见的一种有向图，研究其最短路问题对解决　实际问题具有重要意义。文中给出了图上逆序标号　法、表上作业法和动态规划法三个不同的角度求解　赋权多阶段有向图中任意一点到终点的最短路的方　法，它们都是基于Ｄｉｊｋｓｔｒａ算法思想的方法，掌握这　些求解方法不但可以很好地理解Ｄｉｊｋｓｔｒａ算法思　其中，式（２）为Ｂｅｌｌｍａｎ递推公式的边界条件。　用Ｂｅｌｌｍａｎ递推公式求解赋权多阶段有向图的　最短路时，ｇ表示图中每一条有向边的权　（　）表示　从状态－『的一个顶点　到终态（如图１—２中的Ｅ）的　最短路的长度，ｔ属于由第＿『＋１个状态的所有顶点构　成的集合。下面对图ｌ从边界条件（４）开始，给出求　解最短路及其长度的步骤：　Ｓｔｅｐｌ，对终态Ｅ，由边界条件得　（Ｅ）＝０；　Ｓｔｅｐ２，对状态３，由　（　）＝ｍｉｎ｛ｇ（　，ｔ）＋　（ｔ）｝　想，也为更好得解决可化为赋权多阶段有向图最短　路问题的生产生活实际问题奠定扎实的理论和方法　基础。　参考文献　［１］　Ｂｏｎｄｙ　Ｊ．Ａ．，Ｍｕｒｔｙ　Ｕ．Ｓ．Ｒ．．Ｇｒａｐｈ　Ｔｈｅｏｒｙ　ｗｉｔｈ　Ａｐｐｌｉｃａ・　ｔｉｏｎｓ［Ｍ］．Ｌｏｎｄｏｎ：Ｔｈｅ　Ｍａｃｍｉｌｌａｎ　Ｐｒｅｓｓ　ＬＴＤ，１９７６．　［２］ＴＲＥＭＢＬＡＧ　ｊ．Ｐ．，ＭＡＮＯＨＡＲ　Ｒ．．Ｄｉｓｃｒｅｔｅ　Ｍａｔｈｅｍａｔｉ・　ｃａｌ　Ｓｔｒｕｃｔｕｒｅｓ　ｗｉｔｈ　Ａｐｐｌｉｃａｔｉｏｎｓ　ｔｏ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　＝ｍｉｎ｛ｇ（　，ｔ）＋　（ｔ）：ｔ∈｛Ｅ｝｝得　（Ｄ１）＝ｍｉｎ｛ｇ（Ｄｌ，Ｅ）＋　（Ｅ）｝＝６，　（Ｄ２）＝ｍｉｎ｛ｇ（Ｄ２，Ｅ）＋　（Ｅ）｝＝５，　（Ｄ３）＝ｍｉｎ｛ｇ（Ｄ３，Ｅ）＋　（　｝＝２　［Ｍ］．Ｎｅｗ　Ｙｏｒｋ：ＭｃＧｒａｗ—Ｈｉｌｌ，１９７５．　［３］甘英爱，天丰，李维铮等．《运筹学》（第三版）［Ｍ］．北　京：清华大学出版社。２００５，６．　Ｓｔｅｐ３，对状态２，同样可得　（Ｃ　）＝６／Ｄ３，　（Ｃ２）＝３／Ｄ３对状态１，可得　（Ｂ１）＝５／Ｃ２　（Ｂ２）＝９／Ｃ２　（Ｂ３）＝６／Ｃ２；　［４］秦裕瑷。秦明复．《运筹学简明教程》［Ｍ］．北京：高等　教育出版社。２０００，１０．　［５］　詹棠森，张三强，唐敏．用矩阵和积求最短路的一种新　算法［Ｊ］．数学的实践与认识，２００６，３６（９）：１７０—１７２．　Ｓｔｅｐ４，对状态０，只含一个顶点Ａ，故ｆｏ（Ａ）＝　ｍｉｎ｛ｇ（　，ｔ）＋　（ｔ）：ｔ∈｛　ｌ，　２，　３｝｝＝７／Ｂｌ；由