導語：如何才能寫好一篇運籌學最短路徑，這就需要搜集整理更多的資料和文獻，歡迎閱讀由公務員之家整理的十篇范文，供你借鑒。

篇1

［關鍵詞］動態規劃；最優性原理；無記憶性；記憶性

在運籌學的分支體系中，動態規劃因其應用的廣泛性而占有十分重要的地位。但動態規劃僅僅是解決某類特殊的多階段決策問題的一種方法，不具有統一的數學模型和算法步驟[1]，而且概念多，因此學生普遍反應“動態規劃真的有用但確實難學”。本文以最短路問題為案例，對動態規劃相關概念、最優性原理、無記憶性等進行了闡釋。

一、案例的選擇

可用動態規劃求解的問題很多，如最短路、資源分配、生產與存儲等，而最短路問題因其空間特征明顯，易于劃分階段、易于描述每階段開始和結束時的狀態，以及在每個狀態之下做出的決策、每次決策產生的決策指標值等，因此，對初學者而言，最易接受和理解的例子還是最短路問題。本文以最短路問題作為引例，幫助學生們理解和掌握動態規劃的相關概念及基本方程、最優性原理等。

二、相關概念的解釋

動態規劃相關概念繁多，從階段、狀態開始，到過程指標函數，剛接觸時，不少學生感到一頭霧水，十分茫然。而借助于最短路問題，將動態規劃的相關概念與最短路問題中大家耳熟能詳的名稱相對應，則十分有助于學生對動態規劃基本概念的把握。

三、最優性原理的解釋教材[1]

對最優性原理作了如下表述：無論過去的決策和狀態如何，對前面的決策所形成的當前狀態而言，余下的決策序列必須構成最優策略，即最優策略的子策略總是最優的。

四、無記憶性與記憶性

在動態規劃一章中，教師經常會提到“無記憶性”與“記憶性”兩個看似完全矛盾的概念，不少學生也感到十分茫然。其實，這兩個概念在動態規劃中得到了完美的統一?！盁o記憶性”指的是可用動態規劃方法求解的多階段決策問題，在劃分階段時，狀態必須滿足的一個特性，也稱為無后效性或馬爾科夫性。其實質是：某階段的狀態一旦確定，則此后過程的演變不再受此前各狀態及決策的影響。即“未來與過去無關”，當前的狀態是此前歷史的一個完整總結，此前的歷史只能通過當前的狀態去影響過程未來的演變。[1]“記性性”指的是用動態規劃方法求解多階段決策問題時（以逆序為例），為求得第K步最優子策略fk（Sk），必須先計算出從第K＋1階段的各狀態出發所對應的最優子策略fk＋1（Sk＋1），并由第K＋1步的最優子策略fk＋1（Sk＋1）去求取第K步最優子策略fk（Sk）。這些后續狀態對應的最優子策略實際上構成了一張查找表（LookupTable）。[3]為更好地理解無記憶性與記憶性，仍以最短路問題為例進行說明。假設有一個可分為10個階段的最短路問題，每階段有10個狀態可供選擇?！盁o記憶性”指的是當游客在第k階段處于狀態Sk時，則該游客從Sk出發到終點的最短路徑（K步最優子策略）只與Sk相關，而與Sk之前的狀態、決策無任何關系?！坝洃浶浴敝傅氖钱斢脛討B規劃方法求解最短路問題時，第K步最優子策略是由第K步的決策和第K＋1步的最優子策略共同決定的，而第K＋1步的最優子策略已在之前求出并存放于內存之中，這就是記憶性。動態規劃的記憶性可節省大量的計算時間，但會占用較多的計算機內存，即常用的“空間換時間”策略。以上題為例，10個階段每階段10個狀態的最短路問題，如果采用窮舉法，則需要計算的路徑條數（相當于動態規劃中的全策略）為109條，每條路徑需要進行10次加法運算；在109條路徑中找出最短路徑需要進行109－1次比較運算，則總的基本運算是11＊109－1次。而采用動態規劃方法時，每階段的每個狀態需要進行10次加法運算和9次比較運算，則總的基本運算次數為1539次（其中加法運算810次，比較運算729次），和窮舉法比較可節省大量的計算時間。從該例題的分析可知，一個多階段決策問題之所以可采用有“記憶性”的動態規劃方法求解，恰恰是因為該問題在劃分階段時，各階段的自然特征（即狀態）滿足“無記憶性”。因此，我們說，“記憶性”與“無記憶性”在動態規劃中得到了完美的統一。

五、結束語

經教學實踐證明，在動態規劃教學中以最短路為引例，有利于學生對動態規劃相關概念的理解，尤其有利于學生掌握最優性原理和無記憶性、記憶性這些晦澀難懂的原理與性質，為學生學好、用好動態規劃打下了良好基礎。

［參考文獻］

［1］胡運權.運籌學教程（第四版）［M］．北京：清華大學出版社，2012：191-232．

［2］［M］．普林斯頓大學出版社，1957：58-92．

［3］北京：人民郵電出版社，2008：744-754．

［4］《運籌學》教材編寫組.運籌學（第三版）［M］．北京：清華大學出版社，2005：194-215．

篇2

關鍵詞：最短路徑，Dijkstra算法，優化

 

最短路徑問題是指在一個非負權值圖中找出兩個指定節點間的一條權值和最小的路徑，是一類受到普遍重視和研究的網絡優化問題，廣泛應用于計算機科學、交通工程、通信工程、運籌學等眾多領域。實際生活中的許多問題都可歸結為最短路徑問題。郵政自動分揀機、計算機網絡結點上的路由選擇、人工智能游戲設計、交通咨詢系統等都是最短路徑問題的現實應用。由于帶權圖中權值所代表的意義不同，最短路徑也不僅僅局限于地理意義上的距離最短，還可以引申為最少費用、最短時間、延時最短、吞吐量最大等[4]。

Dijkstra算法是典型的最短路徑算法，用于計算一個結點到其他所有結點的最短路徑。。主要特點是以起始點為中心向外層擴展，直到擴展到終點為止。Dijkstra算法的基本思想是以源點為圓心，按最短路徑長度遞增的順序通過對路徑長度迭代得到從源點到其他各目標結點的最短路徑。

1 Dijkstra算法原理

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算非負權值圖中一個結點到其他所有結點的最短路徑，是一個非常經典的貪心算法例子。?；舅枷胧牵喊褞鄨D中所有結點分成兩組，第1組包括已確定最短路徑的結點，第2組為未確定最短路徑的結點。按最短路徑長度遞增的順序逐個把第2組的結點加入第1組中，直到從源點出發可到達的所有結點都包含在第1組中[2]。

2 Dijkstra算法描述

根據Dijkstra算法的基本思想，引入如下狀態變量：

1）輔助向量D，可用數組實現，其每一個分量D[i]用來存放源點到其他結點的最短路徑長度；

2）集合V和S，其中V集合用來存放未確定最短路徑的結點，S集合用來存放已確定最短路徑的結點。S的初始狀態為空集，V則包含帶權圖中的所有結點。

3）輔助變量path_matrix，可用二維數組實現，用來記錄源點到其他各個結點的最短路徑所經過的頂點。

由于Dijkstra算法是按照最短路徑長度遞增的順序逐個確定源點到各個結點的最短路徑的，所以源點到各結點的最短路徑或者是源點到此結點的弧，或者是中間只經過已確定了最短路徑的頂點（即S集合中的結點）而最終到達此結點的路徑。

根據以上分析，得到如下的算法描述[1]：

1）初始化集合V、S，同時利用帶權圖的鄰接矩陣arcs初始化數組D，即若源點到相應結點有弧，對應的分量取值為弧上的權值，否則對應的分量取值為∞；

2）選擇D中最小的數組分量，假設為D[i]，則i就是已求得源點到其最短路徑的終點，故將S=S∪{i},即將已確定最短路徑的結點i加入S集合；

3）根據結點i修改更新數組D中源點到集合V-S中的結點k所對應的分量，即若D[i]+arcs[i][k]<D[k]，則D[k]=D[i]+arcs[i][k]；

4）重復2）、3）操作，直至所有的結點確定最短路徑，即集合V為空。

對下圖G施行Dijkstra算法，假設源點V1，求解V1到其他各個結點的最短路徑。

圖G

假設源點為v1，則第一個選擇的頂點是v1，路徑長是0，D[]={0，50，10，∞，16}；

Step1 S={v1}，V={v2，v3，v4，v5}，S點集擴充，v3為下一個最短路徑頂點，路徑長為10，D[]={0，50，10，25，16}；

Step2 S={v1，v3}，V={v2，v4，v5}，S點集擴充，v5為下一個最短路徑頂點，路徑長為16，D[]={0，50，10，21，16}；

Step3 S={v1，v3，v5}，V={v2，v4}，S點集擴充，v4為下一個最短路徑頂點，路徑長為21，D[]={0，41，10，21，16}；

Step4 S={v1，v3，v4，v5}，V={v2}，S點集擴充，v2為下一個最短路徑頂點，路徑長為41，D[]={0，41，10，21，16}；

Step5 S={v1，v2，v3，v4，v5}，V={}，V點集為空，結束算法。至此，得到從源點到其他各個結點的最短路徑。

3 Dijkstra算法優化策略分析

Dijkstra算法是計算最短路徑的經典算法,但在實際使用過程中，該算法耗費大量的計算時間和存儲空間，在某些實際應用中產生冗余。所以需要進行優化。在評判一個算法優劣時，通常研究該算法的時間復雜度和空間復雜度?？梢?，可以從影響Dijkstra算法效率的關鍵“存儲空間和時間效率”進行優化。

3.1 權值排序優化策略

問題：S集合中未確定最短路徑的頂點無序存放在數組中，每一次選擇權值最小的弧段必須將所有未選擇頂點對應的數組元素完全掃描才能找到，在數據量較大的情況下，計算速度受到嚴重制約。

優化策略：將要掃描的結點按其對應弧的權值進行順序排列，每循環一次即可得到符合條件的結點，大大提高了算法的執行效率[5]。

3.2 A*算法優化策略

問題：Dijkstra算法基于廣度優先搜索策略，即從源點出發，通過權值迭代遍歷所有其他結點后，最后得到從源點到其他各結點的最短路徑。整個搜索好似一個圓形向外展開，直到到達目的地，這樣的搜索方式是盲目的。很明顯這樣求解一定能找到最優解，但節點展開的數量和距離成級數增加，會導致大量無效點的搜索，大大的降低搜索的效率。

優化策略：采用改進的Dijkstra算法——A*算法。A*算法是人工智能運用在游戲中的一個重要實踐,它主要是解決路徑搜索問題。A*算法實際是一種啟發式搜索。。所謂啟發式搜索，就是利用一個估價函數judge（）評估每次決策的價值，決定先嘗試哪一種方案。這樣可以極大地優化普通的廣度優先搜索。從Dijkstra算法到A*算法是判斷準則的引入，如果這個判斷條件不成立，同樣地，只能采用Dijkstra算法。所以A*算法中的估價函數是至關重要[3]。

3.3 扇形優化策略

問題：Dijkstra算法的搜索過程好似以源點為圓心的一系列同心圓向外展開，搜索過程中沒有考慮到終點所在方向或位置，搜索是盲目的。這樣導致大量的無用臨時結點被反復搜索，成為實際應用中的瓶頸。

優化策略：從盡量減少最短路徑分析過程中搜索的臨時結點數量，限制范圍搜索和限定方向搜索考慮進行優化。那么這種有損算法是否可行呢？我們知道，現實生活中行進，不會向著目的地的相反方向行進，否則就是南轅北轍。所以，當所研究的網絡可以抽象化為平面網絡的條件下，也不必搜索全部結點，可以在以源點到終點所在直線為軸線的扇形區域內搜索最短路徑。這樣，搜索方向明顯地趨向終點，提高了搜索速度，雖然拋棄了部分結點，但基本上不影響搜索的成功率[5]。

3.4 鄰接點優化策略

問題：Dijkstra算法在提取最短路徑結點時需要訪問所有的未確定最短路徑的結點，算法的時間復雜度為O（n2），如果只希望找到從源點到某一特定的終點的最短路徑也不例外。結點數n越大，算法的計算效率和存儲效率越低。

優化策略：只對最短路徑上結點的鄰接點作處理，不涉及其他結點。即（1）只從源點的鄰接點集合中選擇權值最小的結點作為轉接點，將此轉接點加入已確定最短路徑的結點集合S中；（2）對此轉接點的鄰接點集合與S的差集中的結點的權值進行更新；（3）從S中所有結點的鄰接點集合的并集與S的差集中選擇權值最小的結點作為下一個轉接點，并將此轉接點加入S中。重復（2），（3）操作，直至所有的結點確定最短路徑。優化算法在更新最短路徑值與選擇最短路徑值最小的結點時，僅僅涉及相關結點的鄰接點集合及S集合中所有結點的鄰接點集合與S集合的差集，時間復雜度取決于轉接點的鄰接點的數量多少，減少了計算次數與比較次數[4]。

4 總結

在詳細分析求解最短路徑問題的經典算法Dijkstra算法的基礎上，針對Dijkstra算法存在的問題介紹了幾種優化策略。Dijkstra算法在不同的現實應用中，可以具體情況具體分析，從而得到算法的高效率實現。

參考文獻：

[1] 嚴蔚敏，吳偉民. 數據結構（C語言版）[M]. 北京：清華大學出版社，1997，186～190.

[2] 謝柏青，佘曉歌. 算法與數據結構[M]. 北京：高等教育出版社，2001，230～232.

[3] 陳益富，盧 瀟，丁豪杰. 對Dijkstra算法的優化策略研究[J]. 計算機技術與發展，2006，16（9）：73～75.

[4] 章永龍. Dijkstra最短路徑算法優化[J]. 南昌工程學院學報，2006，25（3）：30～33.

[5] 胡樹瑋，張修如，趙 洋.扇形優化Dijkstra算法[J]. 計算機技術與發展，2006，16（12）：49～51.

篇3

關鍵詞： 智慧旅游； 導覽； 線路規劃； 個性化游覽線路

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2016）20?0092?05

Abstract： Personalized tour route planning is one of cores of intelligent guiding to visitors， and the formalizing denotation of the information of scenic regions and view spots is the fundament of personalized automatic planning of touring routes. A method of generating the route automatically is given in this paper for automatic planning of touring route based on directed graph， H?RVT and users′ preference. On the basis of analyzing the related factors， a method of how to express the information of scenic regions and view spots is given in this paper. A expressive method of view spot information is proposed according to the table of maximum relative price. An automatic planning method of personalized tour route is offered， which considers the selection of start point， end point， view spots and visiting time control. The method of formal representation for scenic regions， view spots and routing generation provide a theory support for realization of route planning.

Keywords： wisdom tourism； guiding to visitor； rout planning； personalized tour route

0 引 言

智能導覽是智慧旅游研究與建設的關鍵內容之一，也是物聯網技術的重要應用[1?2]。參觀游覽路線是否科學合理在很大程度上影響到整個游覽過程的用戶體驗。對游客而言，科學合理的游覽路線能夠使其在較短的時間、較小的路程代價下獲得較好的游覽體驗，同時，對旅游服務提供者來說，高效的游覽路線也能使得相同服務資源代價的情況下獲得游客更高的服務評價，從而促進旅游及其服務業的健康持續發展和進步[3?4]。

實際情況下，游客的游覽時間有限，不足以完整地游覽當前景區中所有的景點。游客的真實需求是在有限的時間內個性化地對當前景區內景點進行游覽。因此，如何安排游覽路線，成為智能導覽系統中急需解決的一大問題，生成的游覽路線是否可行有效且滿足游客的偏好，對用戶體驗至關重要。

游覽路線的規劃設計工作本質是依據游客當前的位置信息和待參觀的景區景點信息，根據一定的策略篩選合適的路線和景點，并將之有序排列在具體游覽行程路線的過程中。完整的游覽路線應當包括起點、景點集合、景點間的路徑集合以及終點。因此，對景區內最佳游覽路線問題模型的建立以及路線生成策略的設計是決定游覽路線優劣程度的關鍵所在。

面向智能導覽的個性化線路自動規劃本質上是解決在有限約束下的最短路徑應用問題，它是運籌學、地理信息學以及計算機網絡等學科中的研究熱點，比如求單源且無負邊權的“一對多”的Dijkstra算法[5]、用于求多源且無負權邊的“一對一”最短路徑的Floyd算法[6]、求多個備選優化路徑的K最短路徑算法[7]以及靜態路網中較為有效的“直接搜索”A*算法[8]等。同時，隨著經典圖論和計算機數據結構的有效結合，使得各類最短路徑算法不斷涌現以解決不同特征的實際問題，它們在時間復雜度、空間復雜度、應用范圍以及易實現等性能上各具特色[9?10]。國內有學者專門就最短路徑算法的分類體系以及研究進展[11]方面進行過較為全面的總結與研究分析。文獻[12]提出了一種利用線圖以及頂點賦權圖的最優完全子圖的方案解決中國郵遞員問題中如何生成最優郵遞路線的問題。該方法與通常圖的相關概念的區別在于其為圖中的節點（也稱頂點）賦加了權值，最終求出一條能訪問到圖中所有節點且具有最小權值的環游。文獻[13]提出了一種解決圖中受K頂點數限制的所有最短路徑BCSP算法以及其改進的ICSP算法，運用圖的廣度遍歷算法以及逆鄰接表、指針等數據結構知識生成擴展最短路徑樹。

1 問題背景

在游覽過程中，以有限的時間條件為前提，從游客需求的角度出發，有如下三點直觀的要求：優先參觀景區內游覽價值大的景點；要求所步行的路程最少，即花費在步行過程中的時間短；在不超出限定時間的前提下，盡可能充分地利用限定的時間。

以現實中大量游客對景區的參觀游覽行為過程的總結為基礎，描述游客游覽某一景區的一般活動流程為：

Step1：根據當前的位置尋找到該景區最近的入口，從入口處進入景區。

Step2：若游覽時間足夠長，則從當前位置開始按距離的遠近開始按序游覽景區內景點，直至景區內所有景點都游覽完畢，結束游覽活動。若時間有限，不能完整游覽整個景區內所有景點，則執行Step3。

Step3：以當前位置為參考，在限定時間內，選擇相對游覽價值最高的未被游覽的景點（即該景點知名度高且對其進行游覽花費時間少）。

Step4：步行到達待參觀的景點并花費一定時間完成對該景點的參觀。此時，檢查剩余時間是否可繼續游覽活動。若剩余時間可繼續游覽活動，則返回Step3，若剩余時間無法滿足繼續游覽要求，則執行Step5。

Step5：從當前景點位置行至距離最近的景區出口，離開景區結束對該景區內景點的游覽，完成本次游覽活動。

因此，解決最佳游覽路線生成問題需要完成工作為：

（1） 尋找或設計最短路徑算法，以無向圖中任意某一節點為起點，根據其余節點的權值、價值以及該節點與其余各節點之間的最短路徑，得到在當前位置狀態下，滿足時間限制條件的最佳下一個待游覽節點。

（2） 當需要游覽的節點集合選定之后，在無向圖[G]中根據邊信息以及邊的權值數據確定最佳的游覽路線，生成選定節點集合中節點的最終游覽序列。

2 景區模型抽象與景點屬性表示

2.1 建立無向圖處理模型

旅游景區由多個出入口、內部景點集、公共服務點及內部相互之間的路徑組成，游覽路線的生成工作即根據約束條件按序選擇合適的景點集合與路徑集合。本文以無向圖作為景區及景點的表示模型，將景區相關信息抽象成如圖1所示附加節點值的帶邊權的無向圖模型。

由圖1可知，將某景區的平面示意圖轉換為無向圖[G]，將景區中的景點以及出入口轉換為無向圖[G]中的頂點，景點之間的路徑轉換為無向圖中的邊。

定義1：無向圖[G]由一個二元組[V，E]組成，其中集合[V]稱為無向圖[G]的節點集合，記為[V={v0，v1，v2，…，vn}，（n∈N*）]，[V]中每個元素對應代表實際景區中一個景點；集合[G]稱為無向圖[G]的邊集，是由集合[V]中的元素組成的無序對[vi，vjvi∈V，vj∈V]組成，記為[E=ei，jei，j=vi，vj或ei，j=vj，vi，vi∈V，vj∈V，][E]中每個元素表示實際情況下景區景點之間的一條路徑。

2.2 景點信息表示策略

2.2.1 節點相對價值

在無向圖[G]中，以[vi]為起點，[vj]為終點的一條路徑[px（vi，vj）]的定義，以及該路徑的路徑代價[Wpx（vi，vj）]的定義。一般情況下，從節點[vi]出發到節點[vj]的路徑并不惟一，并且不同的路徑代價一般各不相同。根據每條路徑的路徑代價大小，節點[vi]到節點[vj]的所有路徑的集合[Pij]中必定存在一條路徑代價最小的路徑。

對表1的幾點說明：

（1） 目標節點表示以節點[vi]為起點出發需要達到的節點。節點vi的相對價值表中目標節點中包含無向圖[G]中除vi以外的所有節點。

（2） 路徑時間代價表示vi與目標節點之間最短路徑之中所有路徑的權值之和，即從vi出發達到目標節點過程中經過的路徑所用的路程時間。

（3） 節點時間代價表示目標節點的時間代價，即游覽目標節點對應景點所需要的時間。

（4） 節點價值表示目標節點的價值，為目標節點對應景點的自身固有價值。

（5） 是否已加入路線標記目標節點，是否已經被加入到最佳路線中，1代表該目標節點已加入到最佳路線中，0代表未加入。

（6） 最大相對價值表示目標節點在以[vi]為起點的情況下的最大相對價值。在最佳路線的生成過程中，優先選擇表[H-RVT（vi）]中相對價值高的目標節點加入到最佳路線中。

在表示景點和路徑信息的無向圖[G]中，所有節點都有其最大相對價值表，每一張表中都包含了以該節點為起點，到其他所有節點的最大相對價值。

3 條件約束與個性化路線生成

游覽時間分為路程中花費的時間以及對景點進行參觀游覽花費的時間，游覽價值取決于路線中所有景點的價值高低。從宏觀上描述最佳游覽路線的要求為“在限定的時間內，最高效地利用有限的時間，尋找游覽價值最高游覽路線”；從路線生成過程中描述最佳游覽路線的要求為“保證每次加入到游覽路線中的景點都是當前條件下最值得游覽的景點”。

3.1 路線起點選擇

3.3 路線終點選擇

生成最佳路線的整個流程，首先生成最佳路線的起點，也就是選擇進入景區的入口；第二步是生成最佳游覽路線的主要內容，不斷的在為圖中未加入最佳路線的節點集合中按照加入之后的“效益”大小的順序以及是否滿足時間限制條件來選擇下一個最值得加入路線；當圖中未加入最佳路線的節點集合中沒有滿足時間限制條件的節點時，為最佳路線按照選擇終點，即選擇離開景區的出口，生成完整的最佳路線并輸出結果。

4 結 論

本文針對在有限時間生成最佳游覽路線的問題，從游客的實際需求分析著手，設計了使用無向圖數學模型，總結出在時間限定條件下影響景點與路徑選擇的三個主要因素，并根據分析結果為每個節點生成各自H?RVT表，從而成功實現了生成最佳的游覽路線。

參考文獻

[1] OWAIED H H， FARHAN H A， AL?HAWAMDEH N， et al. A model for intelligent tourism guide system [J]. Journal of applied sciences， 2011， 11（2）： 342?347.

[2] GAVALAS Damianos， KENTERIS Michael. A web?based pervasive recommendation system for mobile tourist guide [J]. Personal and ubiquitous computing， 2011， 15（7）： 759?770.

[3] 廖川榮.校園最佳游覽路線問題的數學模型分析[J].大學數學，2012，28（6）：78?82.

[4] 姜西瑞.基于GPS和GSM/GPRS的定位系統的設計與實現[D].北京：中國科學院計算機技術研究所，2006.

[5] 章永龍.Dijkstra最短路徑算法優化[J].南昌工程學院學報，2006，25（3）：30?33.

[6] 赫自軍，何尚錄.最短路問題的Floyd算法的若干討論[J].重慶工學院學報（自然科學版），2008，22（5）：156?159.

[7] 徐濤，丁曉璐，李建伏.K最短路徑算法綜述[J].計算機工程與設計，2013，34（11）：3900?3906.

[8] 劉浩，鮑遠律.A*算法在矢量地圖最優路徑搜索中的應用[J].計算機仿真，2008，25（4）：253?257.

[9] ZHAN F B， NOON C E. Shortest paths algorithms： an evaluation using real road networks [J]. Transportation science， 1998， 32（1）： 65?73.

[10] CHERK ASSKY B V， GOLDBERG A V， DIZK T R A. Shortest paths algorithms： theory and experimental evaluation[J]. Mathematical programming， 1996， 73（2）： 129?174.

[11] LU Feng. Shortest path algorithms： taxonomy and advance in research [J]. ACAT geodaetica cartographica， 2001， 30（3）： 269?275.

篇4

關鍵詞：管理；運籌學；教學改革

中圖分類號：G642.3 文獻標識碼：A 文章編號：1002-4107（2013）08-0050-02

運籌學是一門集應用數學和形式科學為一體的跨領域學科，它利用統計學、數學模型和算法等優化方法，去尋找復雜問題中的最佳或近似最佳的結果。它也是管理類專業的一門重要專業基礎課，其主要教學目的是使學生掌握各種模型及其求解方法，為今后解決實際決策優化問題打下扎實的基礎。因此，做好運籌學的課堂教學對管理類專業的學生做好學習鋪墊至關重要。

一、運籌學課堂教學現狀

課堂教學是教育教學中普遍使用的一種手段，它是教師給學生傳授知識和技能的全過程，也是教學的主要渠道。它主要包括教師講解，學生問答，教學活動以及教學過程中使用的所有教具，而“教師講解”環節占整個過程的比重最大。在現階段運籌學課堂教學中，主要存在以下幾個問題。

（一）學生主動意識薄弱

長期以來，在傳統教育思想影響下，通常把教師當做教學的主體，把學生當做客體，過分強調教師的權威性，而在一定程度上忽視了學生作為學習主體的存在；過分強調了知識傳授的灌輸性，而忽視了師生之間的互動性，這樣的形式削弱了學生主動參與學習的積極性，容易導致知識掌握不牢固的結果，影響教學的有效性。

（二）差等生難以融入課堂

現代的高等教育已經發展到大眾教育階段，同一個班級的學生的學習興趣、學習欲望、學習成績有很大的差別，學習不良、成績落后的學習障礙學生人數比重大為增加，這會直接影響整個班級的學習氛圍。運籌學對數學底子薄、注意力不集中的學生來講，很容易脫離課堂教學節奏，最后放棄學習，站到“差等生”的隊列。因此，控制差等生的比重或提高差等生的學習積極性對改善整體學習狀況非常有利。

（三）學習效果評價手段單一

現階段運籌學教學結果的評價一般采用傳統的閉卷筆試的考試方式，其中尤以期終考試卷面成績為主，占80%―100%。導致學生將學習重點放在對知識的死記硬背上，難以將其“活學活用”。

二、管理類運籌學課堂教學改革實踐

（一）教學目標定位

聯合國教科文組織提出，21世紀的教育支柱，即是學會求知，學會做事，學會共處，學會做人。在這些人類生存所必須具備的素質中，學會做人最重要。因此，教師在教學中不僅要讓學生掌握課程中的知識點，還要注重對學生學習方法及學習興趣的培養、創新能力的培養以及人格的教育。

（二）教學內容優化

運籌學是一門具有較多分支的學科，因課時限制，教師在教授課程中不可能做到面面俱到，對教學內容，應堅持適用性的原則適當調整：難度較大、應用性不強的內容，應少講或不講；對于純理論的數學推導可以少講，會運用其推導結論即可；應用性較強的內容應多講、詳講。例如，對數據包絡分析、非線性規劃、動態規劃等較復雜的內容可以不講；對存貯論、對策論等讓學生理解原理、能運用結論即可；物流管理專業的授課對運輸問題、圖與網絡分析可詳講，并適當加深難度；工程管理專業的授課應增加網絡計劃的內容。

（三）教學模式改革

1.讓學生成為課堂的主人。在教學實踐中，多創造機會讓學生參與教學，成為課堂的主人。教師在教學中可以通過與學生互換角色來調動其學習主動性、積極性，達到良好的學習效果。教師將教學內容分為簡單的、復雜的兩類，復雜的由教師自己講授，簡單的則分給愿意承擔的學生，這樣就把學生當作了教學的主體，學生在這種壓力情況下會將課前預習的效果發揮到極致。鼓勵學生之間的合作，進行團隊學習，承擔不同的角色，如PPT制作，黑板板書，卡片制作、上臺講析等，各自發揮長處，并且能夠培養團隊精神。如運籌學中圖與網絡分析、網絡計劃前面的基本知識部分就可以通過這種形式進行教學，在學生的教學活動結束時教師再做適當的補充。

課堂練習題等也可以作為學生參與教學的部分，可以讓更多的學生參與其中，通過自己的嘗試，體會講課的過程才會更加理解教師的勞動成果，更加用心聽課，形成良性循環；學生參與課堂練習的分析也會促進課后復習的效果。如在單純形法、指派問題等章節中鼓勵學生評講課堂練習題或者課后習題；讓學生參與期末課程總復習的指導。

2.全員參與式教學。成績處于中上水平的學生比較配合教師的教學，能夠緊跟課堂教學的節奏，而成績靠后的學生則很難融入進來。在課堂教學中應該讓差等生也能參與其中，改善班級整體學習氛圍。在這種情況下，可以通過黑板板書、畫圖等比較簡單的形式讓成績略差、缺乏學習熱情的學生也能參與到課堂教學中，并對他們進行適當表揚，提高他們的學習興趣，逐漸脫離“差等生”的隊伍。

篇5

關鍵詞：蟻群算法；物流配送；路徑優化；數學模型

DOIDOI：10.11907/rjdk.161974

中圖分類號：TP319

文獻標識碼：A 文章編號文章編號：16727800（2016）011014004

基金項目基金項目：

作者簡介作者簡介：袁文濤（1993-）男，安徽馬鞍山人，上海理工大學光電信息與計算機工程學院碩士研究生，研究方向為模式識別與智能系統；孫紅（1964-）女，上海人，上海理工大學光電信息與計算機工程學院副教授、碩士生導師，研究方向為模式識別與智能系統、 控制理論與控制工程、企業信息化系統與工程。

0 引言

解決組合優化問題的最優化求解算法有多種現代人工智能算法方案，優化算法用來處理問題最優解的求解，該問題通常由多個變量共同決定。當前，求解最短路徑問題是圖論研究中的一個典型求解組合優化算法問題，旨在尋找圖表（由節點和路徑構成）中兩節點或多節點之間的最短路徑。常用的最優化路徑求解方法有Bellman-Ford算法、Dijkstra算法、A*算法和蟻群算法。這些算法都有自身的優點和不足。在對不同算法作出比較后，可以得出蟻群算法在解決網絡路由和城市交通系統的問題中是相對有利的。

就目前研究來看，隨著實際組合問題的變化，基本的智能算法已經不能滿足解決這類組合優化問題，同時其優勢也在減弱[1]。本文采取改進后的組合優化蟻群算法以彌補傳統蟻群算法易陷入局部最優解的不足，加快了求全局最優解的構造速率。

蟻群算法（Ant Colony Optimization， ACO），是一種模擬螞蟻群體智能行為的進化仿生類優化算法，在求解性能上具有強魯棒性、優良的分布式計算能力、便于與其它算法相結合等優點[2-3]。通常作為一種用來在多變量組合優化問題的多候選解中尋找最優化路徑的機率型算法。它由Marco Dorigo于1992年在其博士論文《Ant system： optimization by a colony of cooperating agents》中首先提出，其靈感來源于通過對蟻群社會的長期跟蹤觀察后發現，雖然單個螞蟻沒有視力、智慧程度低、工作方式簡單，但它們卻有強大的執行能力和協同工作能力，依靠復雜群體的自組織協同能力發揮出超出單個個體累加的智能，是一種超個體（superorganism，又稱超有機體）存在現象。蟻群是在這樣的超個體案例中最有名的例子。雖然蟻群算法的嚴格理論基礎和實際應用尚未成熟，國內外相關研究暫處于實驗階段，但這并不妨礙人們對蟻群算法的研究已經由當初單一的解決商旅問題（TSP）發展到解決調度問題、網絡通信等多個方向的最優化求解應用。

目前，蟻群優化算法已廣泛應用于多種求組合最優化問題，在面臨路例如作業安排調度問題和路由車輛的二次分派問題上表現出了良好的性能，也經常被用來求旅行推銷員問題的擬最優解。它在圖表動態變化情況問題的求解上相比螢火蟲算法和遺傳算法具有絕對優勢：蟻群算法的最大優點在于可以連續運行并適應實時變化；缺陷是在處理較大規模和復雜數據問題時，容易存在運算耗時長、收斂速度慢、得不到全局最優解等問題。

在求最優解的歷次迭代中，單個螞蟻會根據給定的規則和限定條件選擇從一個城市（節點）轉移到另一個城市（節點）：它必須對所有城市訪問一次，而相對距離越遠的城市被選中為下一個訪問點的機會越少（能見度低）；相反，在兩個城市（節點）邊際的一邊形成的信息素越濃烈，則該邊際作為路徑被選擇的概率越大；在較短路程情況下，短時間內更多螞蟻會在所有走過的路徑上留下更多信息素，在每次迭代更新后，信息素軌跡濃度會按百分比揮發從而反饋給下一只途經的螞蟻并影響它作出路徑選擇。

1 車輛路徑問題

傳統的車輛路徑問題也叫VRP（Vehicle Routing Problem）問題，是關系到現代物聯網發展過程中物流配送系統的一個關鍵問題，屬于NP難題。一直以來，該問題也是管理科學和物流運輸方面的重要課題[4]，受到國內外學者的廣泛關注。

VRP問題描述如下：在一些由于經濟或者地理限定的條件約束下，組織一個車隊，從一個或者多個初始點出發，規定達到多個不同的地點，設計一個成本最小、路程最短的路線集，使得：① 每個城市只能被一輛車訪問，只訪問一次；②所有送貨車輛必須從起始點出發再回到起始點；③某些特定的約束條件需要被滿足。

VRP的數學模型表示如下：一共有k個客戶，第i個客戶的貨物需求為gi，配送中心派出車輛承擔運輸任務，其載重為q。設gi

如果前提有約束條件用于車輛本身，即容量限制和總長限制，則稱為有能力約束的車輛路徑問題（Capacitated Vehicle Routing Problem）。此模型是車輛路徑問題的基本模型，這類VRP問題叫作CVRP問題[5]。

設每個客戶點只允許被訪問一次，車輛所訪問的客戶點的需求總和不能超過車輛的負載能力，且總行駛的路程也不得超過其最大的行駛距離，達到用最少的車輛最短的路徑完成既定任務。

。

2 可約束蟻群算法實現

2.1 算法實現方式

當前蟻群算法領域存在MPDACO局部更新和MPDACO全局更新兩種方式。前者指當單個螞蟻從一個節點到達下一個節點完成轉移后就立刻更新螞蟻通過路徑時所留下的的信息素，后者是當螞蟻遍歷完所有給定節點后再更新整條路徑上的信息素，不再是對所有的螞蟻，而是僅對全局最優的螞蟻得到的路徑使用。從兩種更新方式得到的結果作對比可以得出，全局信息素更新方法雖然可以加快收斂速率，但是存在著一定的缺陷和不足，易使路徑更快地集中于單一解，易陷入局部最優，這些缺點限制了它的廣泛傳播及應用。

本文綜合上述兩種更新方法的優點和不足，列出了一種新的組合疊加更新方法：在路徑搜索的前十次循環中，采用局部最優解更新，十次固定循環結束后，再采用全局最優解進行更新，這種更新方式可以有效避免蟻群搜索得到的路徑沉入局部最優解中，有利于發現更多較優解。

2.2 算法實現步驟

根據改進的蟻群算法，將優化后的蟻群算法應用于CVRP問題的實現步驟如下：

（1）參數初始化。設迭代次數 Nc=0；每條路徑上的信息素濃度Δτij（0）=c（c為常數），并且Δτij=0；隨機將m個螞蟻放置到初始點上。

（2）更新迭代（循環）次數，即Nc=Nc+1。

（3）初始化禁忌表，螞蟻禁忌表的索引號k=1。

（4）更新螞蟻數目k=k+1。

（5）判斷路徑是否在搜索熱區內。按照式（a）～（f）計算出每只螞蟻應當轉移至下一個城市（節點）的概率并完成移動。

（6）當螞蟻從i城市（節點）出發到達j城市（節點）時，對其所經過的路徑上的信息素進行更新，并修改禁忌表，將禁忌表指針按照當前狀況進行修改，即將新城市（節點）j置于禁忌表tabuk中。

（7）執行步驟（b）～（f），直到所有螞蟻都找到了一條包含所有城市（節點）的可行路徑解。

（8）在新生成的所有可行解中找到一條最短路徑作為本次迭代中的最優路徑解。

（9）判斷循環次數是否小于十次，若小于十次，則對螞蟻找到的最優路徑按照本次迭代最優值進行信息素更新；若循環次數超過十次，則按照全局信息素進行更新。

（10）對所有螞蟻經過的路徑，按式（1）進行一次全局更新。

（11）循環執行（b）～（j），直到連續多次的迭代中得到的解已收斂或循環次數Nc的值已經達到給定的最大迭代次數的情況下選取當前輸出值作為本次最優解。

3 實驗仿真

設存在一個物流中心有4輛運輸車， 單輛車最大載重為1 000kg， 現需要同時向7個隨機分布的客戶點派送貨物， 蟻群算法的初始化參數為： 螞蟻總數為20只， 算法的最大迭代數為100次， α和β分別為1，2， 信息素的揮發速度為0.75， 實驗重復運行100次， 求得的平均結果為最終結果。同時初始時刻各邊上的信息痕跡為1，殘留信息的相對重要度為1，設置預見度為5。原始數據進行處理結果分析如圖3所示。按本文提出的優化蟻群算法求解CVRP后的處理仿真結果如圖4所示。

觀測圖3、圖4的收斂曲線，可以知道蟻群算法優化后的結果相比之前的行車路徑有大幅度優化[810]，如圖5所示。針對每個收斂的點結合數據可以看出，傳統蟻群算法的平均路徑在迭代次數為45時可以得到最優解，而改進后的蟻群算法可以在第5次左右得到最優解，相當于收斂速度提高了近80%。

4 結語

在當今應用數學和理論計算機科學的領域中，組合優化（Combinatorial Optimization）是在一個有限的對象集中找出最優對象的一類重要課題，屬于運籌學的一個重要分支。在很多組合優化問題中，窮舉搜索/枚舉法是不可行的。組合優化問題的特征為可行解的集是離散或者可以簡化到離散的，并且目標是找到最優解。解決組合優化問題一般采用智能算法，而這些算法都有自身的優點和缺點。組合優化的難處，主要是加進來拓撲分析，在不同的拓撲形態下，算法也需隨著不同部分的約束關系作出相應調整。從目前研究來看，隨著實際組合問題的變化，基本的智能算法已不能解決這類組合優化問題。

蟻群算法作為一種仿生類進化算法在求路徑最優化解方面具有很好的效果。本文首先引出蟻群算法可以用于解決這一類問題，然后介紹了約束車輛路徑問題，也即CVRP問題，說明了其約束模型；接著研究了基本的蟻群算法步驟，并對其中信息素更新和改進了啟發因子，解析并改良了蟻群算法應用于CVRP問題的實現步驟和處理方法。

本文提出的組合疊加更新方法可有效克服傳統蟻群算法收斂質量低、耗時長、易陷入局部最優解等缺陷，使蟻群算法的全局優化能力得到大幅度提高。對比實驗前數據可以看出，蟻群算法找到最短路徑的收斂速度比傳統方法快了80%左右，確實是一種求解最短物流配送路徑的有效算法。

參考文獻：

[1] 陳昌敏.基于蟻群算法的物流配送路徑優化研究與應用[D].成都：西華大學，2012（4）：1154.

[2] 宋留勇，王銳，周永旺，等.動態城市交通網絡優化模型研究及算法設計[J].測繪科學，2011，36（1）：134136.

[3] 鐘石泉，賀國光.有時間窗約束車輛調度優化的一種禁忌算法[J].系統工程理論方法應用，2005，14（6）：523527.

[4] CHAO YIMING.A tabu search method for the truck and trailer routing problem[J].Computer and Operations Research，2002，29（1）：3351.

[5] 楊中秋，張延華.改進蟻群算法在交通系統最短路徑問題的研究[J].科學計算與信息處理，2009，32（8）：7678.

[6] 李松，劉興，李瑞彩.基于混合禁忌搜索算法的物流配送路徑優化問題研究[J].鐵道運輸與經濟， 2007， 29（3）：66 69.

[7] 陶波， 朱玉琴.改進的7動態規劃法在車輛最短路徑問題中的應用[J].重慶工學院學報， 2009，23（1）：2427.

[8] 李軍，郭耀煌.物流配送車輛優化調度理論與方法[M].北京：中國物資出版社， 2001：101113.

[9] 張萬旭，林健良，楊曉偉.改進的最大最小螞蟻算法在有時間窗車輛路徑問題中的應用[J].計算機集成制造系統，2005，11（4）：572576.

[10] 余h，胡宏智.基于改進遺傳算法的物流配送路徑求解[J].計算機技術與發展，2009，19（3）：5255.

[11] 朱慶保，蟻群優化算法的收斂性分析[J]. 控制與決策，2006，21（7）：3016.

[12] 鄭松，侯迪波，周澤魁，動態調整選擇策略的改進蟻群算法[J].控制與決策，2008，23（2）：13.

[13] 夏亞梅，程渤，陳俊亮，等.基于改進蟻群算法的服務組合優化[J].計算機學報，2012，35（2）：311.

篇6

Abstract: Through the analysis of path optimization of emergency logistics distribution, the article establishes its model, proposes the solving method on this basis. Finally, through an example application of path optimization of emergency logistics distribution, the solving process are described, and the results are further discussed.

關鍵詞：物流；應急配送；路徑優化

Key words: logistics；emergency distribution；path optimization

中圖分類號：F253 文獻標識碼：A 文章編號：1006-4311（2011）28-0025-02

0 引言

隨著市場經濟的發展和競爭的加劇，市場呈現多品種、小批量產品多樣化、消費多樣化的趨勢，物流配送就是為適應這種趨勢而產生的一個重要環節，它是指對局域范圍內的客戶進行的多客戶、多品種的按時聯合送貨活動。配送的“送”就是送貨運輸。從這個角度來看，物流配送中送貨路線的選擇，是影響物流成本的一項重要因素。從降低物流成本的途徑來看，提高物流速度，可以減少資金占用和，縮短在物物流周期，降低儲存費用，從而節省物流成本。所以，在應急物流配送過程中，要使得各物資需求點能在最短時間內得到物資補充，物流中心就需要選擇最優的保障方式，將物資送達各個需求點。

1 影響物流中心選址的因素及物資需求問題描述

在整個物流系統中，配送中心地點的選擇更是物流系統優化的一個具有戰略意義的問題。傳統意義上的物流配送中心（或分銷中心）是商品從供應商（制造商）至零售商之間的中間儲存點，具有集中和分散物資，促進商品迅速流轉的功能。物流中心的位置的選擇，根本目的應以費用低、服務好、社會效益高為目標，以物資運輸合理、方便用戶、投資少、有利于適應經濟發展的需要為基本原則。物流中心的選址需要對多種因素綜合考慮包括：自然資源的特點、客戶的分布、運輸服務條件、建設費用、城市建設的整體規劃、外部環境因素等，此外對物流中心未來的發展應仔細研究，使決策具有前瞻性。它包括物流中心在此處有沒有發展前途和大的作為，以及一定時期內城市經濟發展的變化，以便使物流中心能適應未來發展的需要。

在滿足物流中心開設地點要求和綜合各物資需求點之間距離的前提下，物流中心與各物資需求點之間就不可避免地存在一定的距離。由于各物資需求點的周圍客戶量不同，物資的銷售情況也必然不同，必然會導致物資需求產生的偶然性，而物資需求點相對分散。物流中心收到來自這些分散的位置的物資配送申請后，對這些物資需求點進行物資配送，模型就是要解決在物流中心現有運輸力量前提下，以最優的方式將物資送達每一個需求點，由此產生了物資需求問題。

2 應急物流配送路徑優化問題建模

2.1 物流中心與物資需求點的實際關系 由于物資需求點產生的偶然性，使得物流中心和物資需求點關系如圖1所示。以五個物資需求點的情況為例，各點編號分別為1、2、3、4、5，物流中心編號為0?，F實情況是這樣的，各需求點之間以及需求點與物流中心之間，可能是可以不經過第三點直達的（如需求點1、需求點2及物流中心之間都是可直達），也可能是必須經過第三點才可以到達（如需求點5與物流中心之間）。若可以直達，則以連線表示兩點之間的支路。無論怎樣，需求點與物流中心之間總可以找到一條路，即是可達的。若某個需求點與物流中心之間沒有路，則表明該點與物流中心不可達，則該點也就沒有存在的必要。

2.2 現實情況的完全加權圖表示 將圖1所示的現實情況轉化為完全加權圖形式后得到如圖2所示的關系形式。圖2中0點為物流中心，其他為物資需求點，實線為實際支路，虛線表示虛擬支路。則物流中心應急物流配送問題可以描述為：找到從0點出發不重復的遍歷所有節點的最短閉合回路。由此，可以看出物流中心物資輸送問題實質上為一個TSP問題。

2.3 所求最優回路中的組成支路的權值的確定 解決該問題的目標是找到從0點出發不重復的經過所有節點的最短閉合回路。也就是使得這條閉合回路的組成支路的權值之和最小。所以，求得最優路徑的問題依賴于各條組成支路的權值的確定。在現實情況下，各路徑的權值是綜合考慮物流中心到各需求點間的距離、道路狀況以及各道路安全性等因素得出的結果，因此在對實際支路賦權的過程中，會出現違背三角不等式的情況，在此對具體的賦權規則不做研究，而假設各實際支路的權值已得出。在對實際支路賦權完畢后，進行虛擬支路的賦權，各虛擬支路的權值均為實際支路權值之和的m倍，m為無窮大的自然數，即虛擬支路不可通行。

2.4 設計求解最優路徑問題的流程 物流中心應急物流配送問題抽象后實質為一個N個節點的TSP問題。因此，總能找到一條最優路徑。現在假設找到了此問題的一條最優路徑L。L若不包含虛擬支路，則表示從物流中心出發，確實存在一條最優的配送路徑，從距離、路況及安全性角度綜合分析是最優的配送路徑；若L中包括至少一條虛擬路徑，則表示在現有路徑下不存在符合條件的最優路徑。即現有條件下的最短路徑中某些節點至少需要經過兩次。因此，為求得較優路徑對圖作如下處理。

假設L中某一虛擬路徑為（a，b），則總可以從點a到點b找到（a，K1，K2，…，Kn，b）這樣一條最短路，其中ki為最初的N個節點之一，且路（a，K1，K2，…，Kn，b）必不含虛擬路徑路，稱路（a，K1，K2，…， Kn，b）為虛擬路徑（a，b）的最短代替路徑。在已有節點之外新增加k個節點（A1，A2，…，Ak），新增節點的規則是節點Ak與Ki具有完全相同的屬性，即Ak到任何節點的權值與Ki到任何節點權值相同，特別的Ak到與Ki具有相同屬性的節點的權值為0。對L中每條虛擬路徑都按照（a, b）的方式處理。

完畢后則全部節點數目增加到N+A，其中N個是最初的實際節點，A個為新增節點。此時，對于N+A個節點來說已經找到了一條回路L*，L*只包括這N+A個節點，且這N+A個節點在L*上出現且僅出現一次，同時L*上不含虛擬路徑。說明這N+A個節點的TSP問題存在最優解。

根據以上分析，對物流中心應急物流配送問題設計的求解流程如圖3。

3 模型的實例應用

3.1 實例分析 以四個需求點為例進行實例說明。假設需求點與物流中心的完全加權圖表示如圖4所示，各支路權值已給出。

①求這四個點的TSP問題，最優解為（0，2，1，4，3，0），路的長L=12+M，其中包含虛擬路徑（2，3）。

②尋找（1，4）的最短代替路徑為（1，2，0，3，4）。

③增加點A，B，C，則原圖變為圖5。

④求這八個點的TSP問題，最優解為（0，2，1，C，B，3，4，A，0）。

3.2 關于求得的解的討論和實際意義解釋 以上通過增加虛擬點的方法建立的求解模型，最終求得的最優路徑L可以分為兩種情況。情況一：最優路徑L中除起點和終點外，不包含其它與起點具有相同屬性的點，說明在實施應急物流配送過程中，運輸車隊從物流中心出發后經過路徑L所示的各個需求點，物資送達完畢返回物流中心，各個需求點都得到供應。選擇該運輸路徑，可以減少運輸車隊的使用，只組織一支物資運輸車隊，就可以達到完成運輸任務的目的，有效地節約了運輸資源。情況二：最優路徑L中除起點和終點外還包含其它與起點具有相同屬性的點。這說明在實施應急物流配送過程中，運輸車隊從物流中心出發后，中途要返回物流中心，再到其他未配送的需求點，最后遍歷所有需求點后回到物流中心。解決此種情況的辦法的，根據中途回到物流中心的次數n，在可行的情況下，將整體運輸力量分成n+1支配送小分隊，各小分隊對相應的若干需求點進行物流配送，完畢后返回物流中心。這樣，在總路徑不增加的前提下，對所有物資需求點展開了并行的物流配送，使得對所有需求點的最長物流配送時間減少，配送的效率更高。

4 結束語

物流中心是物資供應體系中的一個重要的環節。研究應急物流配送路徑優化問題，對提高物流中心配送效率具有重要意義。文章對物流中心應急物流配送路徑問題進行了分析研究，建立了應急物流配送路徑優化問題的模型，設計了模型的求解流程，最后通過實例對應急物流配送路徑優化問題求解過程進行了詳細說明。并結合現實情況，對求得的解進行了進一步分析討論，提出了物流中心應急物流配送策略可能的改進意見，供物流中心決策參考。

參考文獻：

[1]殷劍宏，吳開亞．圖論及其算法[M]．北京：中國科技大學出版社，2003．

篇7

關鍵詞：TSP模型；循環取貨；德邦物流

中圖分類號：F224 文獻標識碼：A 文章編號：1009-2374（2014）02-0021-03

第三方物流的迅速發展，為零擔運輸企業提供了更多的市場機會，但同時也使市場競爭更加激烈。由于行業進入的壁壘較低，許多小企業或個人進入零擔運輸市場，使得價格競爭非常激烈，對規范的市場競爭不利。第三方物流企業大打“價格戰”，各企業利潤空間狹小、生存壓力大，如何降低企業成本是企業經營者長期思考的問題。

1 TSP模型及求解

1.1 TSP簡介

旅行商問題（TSP），也稱為貨郎擔問題、巡回銷售問題。該問題是一個典型的組合優化問題，可以簡單地描述為：設有N個城市以及設定城市之間的旅行費用，找一條走遍所有城市且費用最低的旅行路線。旅行商問題是單回路運輸問題中最為典型的一個問題。

配送路徑優化問題可以說是對旅行商問題加以一定限制而形成的，這些限制包括：客戶有一定的貨物需求（貨供應）數量且要求貨物在一定的時間范圍內送達（或取走）、配送車輛的裝載量限制及一次配送的最大行駛距離限制等，即車輛路徑優化問題是一個多約束的旅行商問題。

單回路運輸問題是指在運輸路線優化時，在一個節點集合中，選擇一條合適的路徑遍歷所有的節點，并且要求閉合。單回路運輸模型在運輸模型中，主要用于單一車輛的路徑安排，目標是在該車輛遍歷所有用戶的同時，達到所行駛距離最短，這類問題的兩個顯著特點：（1）單一性，只有一個回路；（2）遍歷性，經過全部用戶，不可遺漏。

1.2 TSP數學模型

TSP問題的模型可以描述為：在給出的一個有n個定點網絡（有向或者無向）要求找出一個包含n個定點的具有最小消耗的環路。任何一個包含網絡中所有n個定點的環路被稱為回路。在旅行商問題中，要設法找到一條最小耗費的回路。既然回路是包含所有定點的一個循環，故可以把任意一個點作為起點（也是重點），這也是TSP模型的一個特點。

TSP模型的數學描述為：

假設連通圖H，起定點集A。

定點間的距離為：

滿足：

決策變量：

求解TSP模型時，如果要得到精確的最優解，最簡單的方法是枚舉法。對于小型問題，這也是一種十分有效的方法。但是對于大型問題，由于枚舉法的列舉次數為（n-1）次，若用枚舉法將是無法想象的。

另外，運籌學領域的證書規劃的方法也可以用于結局部分TSP模型，其中分支定界法是一種比較實用的算法，但是該算法也是只能對一部分中小規模問題的TSP模型進行求解，對于大多數問題的求解都存在一定的難度。由于此次研究是針對德邦某門店的循環取貨實證研究，主要采用Lingo軟件求解。該門店的特點如下：（1）需要規劃的取貨點少，規模不大；（2）取貨方式滿足旅行商問題的條件；（3）Lingo軟件能夠對小規模旅行商問題求解。

2 Lingo軟件程序及建模

2.1 Lingo程序簡介

Lingo全稱是Linear Interactive and General Optimizer的縮寫―交互式的線性和通用優化求

解器。

Lingo是使建立和求解線性、非線性和整數最佳化模型更快、更簡單、更有效率的綜合工具。而且Lingo能夠提供強大的語言和快速的求解引擎來闡述和求解最佳化模型。

2.2 Lingo建模

簡單的模型表示：

model：

sets：

cities/1..7/：level；！level（?。?the level of city；

link（cities，cities）：

distan

ce，

x；！x（i，j）=1 if we use link i，j；

endsets

data：

distance=

enddata

n=@size（cities）；！the model size；

min=@sum（link（i，j）|i #ne# j：distance（i，j）* x（i，j））；

@FOR（cities（i）：

@sum（cities（j）|j #ne# i：x（j，i））=1；

@sum（cities（j）|j #ne# i：x（i，j））=1；

@for（cities（j）|j #gt# 1#and# j #ne# i：

level（j）>=level（i）+x（i，j）-（n-2）*（1-x（i，j））+（n-3）*x（j，i）；

）；

）；

@for（link：@bin（x））

@for（cities（i）|i#gt#1：

level（i）

3 實證研究

3.1 德邦物流簡介

德邦是國家“AAAAA”級物流企業，主營國內公路運輸業務。截至2013年10月末，公司已開設直營網點4200多家，服務網絡遍及全國，自有營運車輛7200余臺，全國轉運中心總面積超過88萬平方米。

德邦物流始終以客戶為中心隨時候命、持續創新，始終堅持自建營業網點、自購進口車輛、搭建最優線路，優化運力成本，為客戶提供快速高效、便捷及時、安全可靠的服務體驗，助力客戶創造最大的價值。

3.2 德邦物流某網點現狀

本文將以德邦物流某網點的上門取貨路徑做實證

研究。

該網點目前有一名門店經理、三名營業員以及一名駕駛員。門店訂單來源主要來源于客戶上門訂單、電話訂單和網絡訂單。對于需要上門取貨的客戶，門店經理根據排班表由一名營業員陪同司機駕車外出取貨。而為了達到較高的客戶滿意度，門店都是在客戶有需求的時候上門，一次出門提取的商家只有2～3家，并且出門時間不確定，完全根據客戶的需求。這樣的做法導致的結果是多次上門取貨汽車行駛距離長，燃油成本高，并且駕駛員需要全天處于待崗狀態，休息時間不確定，行車安全存在隱患。

3.3 路徑優化實證

通過與服務商家協商制定配送時間表，保證取貨及時以及減少燃油成本，同時駕駛員也能有足夠的休息時間，確保行車安全。

本文選取了門店的幾個長期服務商家進行實證研究，其中①點為門店所在位置，③點為工業園區，其中包含十余家企業，因距離近合并為一點。

各個節點之間的距離如表1所示。

各個節點之間的行車時間如表2所示。

將表1和表2中的數據輸入模型，應用Lingo軟件建模運行求解得到該問題的最短路徑為①②③⑤⑥⑧⑦④①，最短距離為56.6公里。

通過與相關商家協商，安排了如表3所示的行車時間表：

表3

節點 停留時間

① 14∶00（出發時間）

② 14∶04～14∶09

③ 14∶13～14∶53

⑤ 14∶09～15∶14

⑥ 15∶35～15∶40

⑧ 15∶46～15∶51

⑦ 15∶54～15∶59

④ 16∶26～16∶31

① 16∶45（回程時間）

注：根據對每次取貨流程耗費時間的記錄，一般耗時4分鐘，我們選取五分鐘作為一個節點的標準時間；由于節點③處于工業區，周邊有十余家服務商家，停留時間為40

分鐘。

通過實證研究，循環取貨路徑得以優化，行車距離減少，企業燃油成本能夠大幅減少，并且通過與商家協商，加強了伙伴關系，也提高了服務質量。

參考文獻

[1] 趙春英，張鈴.求解貨郎擔問題（TSP）的佳點

集遺傳算法[J].計算機工程與應用，2001，37

（3）：83-84.

[2] 蔣長兵，吳承建，彭揚.運輸與配送管理建模與仿

真[M].北京：中國物資出版社，2011.

[3] 謝金星，薛毅.優化建模與LINDO/LINGO軟件

篇8

[關鍵詞] 礦井 高壓供電網絡 區域選擇性聯鎖 短路保護 保護配置策略

中圖分類號：TD611 文獻標識碼：A 文章編號：

1 煤礦井下高壓供電網絡中存在的問題

在我國煤礦企業安全生產事故中，由礦井供電直接或者間接引發的安全事故不斷呈現上升趨勢[1]。據相關資料顯示，煤塵爆炸與瓦斯等嚴重危害煤礦的安全事故中，有2/3以上與礦井供電系統問題有關[2]。

煤礦企業安全生產對煤礦井下供電工作提出了較高要求，要求100%安全生產和安全生產零事故[3，4]。當前，多數煤礦企業建礦較早，且多次更新井下采煤設備，由于采礦工作面過度延伸，造成了高壓供電網絡過多分級，導致了礦井下高壓供電系統多發短路現象，繼電保護出現越過多級、拒動或者誤動跳閘，致使停電事故頻繁發生，嚴重時會威脅到礦井安全生產。通過考察研究我礦井生產的實際情況，發現我礦供電系統的實際結構與煤礦井下巷道的走向和分布有一定關系，在很大程度上影響了煤礦供電系統構建[5]。本文結合圖論，統一規劃了礦井下的高壓供電網絡，通過使用網絡通訊技術實現煤礦礦井高壓供電網絡繼電保護信息的一致共享，通過開關智能控制器的統一控制及綜合判斷，實現了煤礦井下供電線路繼電之間的保護閉鎖，從本質上解決煤礦井下高壓供電系統中存在的越級跳閘問題。

2 圖論在礦井供電網絡中的應用

圖論是一種運籌學分支，近年來得到了廣泛應用，可以使用圖論方法解決電力系統的狀態估計、可靠性分析及規劃等問題。通常情況下，圖論研究抽象圖形可以用施工流程、運輸系統或者電氣圖形等形式表示。當前，電力系統設計規劃中較多應用的是最小費用流問題、最大流問題、最短路徑問題等[6]。

本文結合圖論，針對煤礦井井下高壓供電網絡系統提出了安全可行的網絡化供電系統保護策略。主要介紹如下：

⑴在煤礦井下供電系統中使用網絡優化技術，實現了多級繼電保護裝置間的聯鎖保護；⑵采用礦井供電網絡優化與保護配置相互結合的供電線路級數設計策略，盡量將煤礦井下供電線路級數減少到最低；⑶減小供電系統回路中出現的低壓誤動：通過改變欠電壓釋保護放回路的低壓動作值來實現；⑷以保障選擇性為前提，盡可能縮短各保護間的時間級差，即改變過負荷保護、無時限電流速斷和限時電流速斷間的時間級差，將0. 5s改成100～300ms[7]。

3 智能控制模塊的工作原理及構成

本文中所述智能控制模塊由光纖耦合器、光纖通信元件及單片機等主要元件構成。其中，單片機成功輸入、輸出各種信號，通過分析各種信號，發出跳閘或者自鎖信號。信號轉換工作由光纖耦合器和光纖通信元件共同完成，且網絡通信在上、下級之間進行。跳閘信號或系統故障信號的開合都可以由單片機系統的控制開關（I/O）裝置的分勵線圈回路控制，借此實現跳閘操作。

4 煤礦井下高壓供電網絡區域的選擇性聯鎖保護

煤礦井下高壓供電網絡的三級區域選擇性保護聯鎖的基本結構如圖2所示，即將一個智能控制模塊安裝在原有開關裝置上，使之配合原有繼電保護裝置當中的電流速斷保護工作，以順利實現區域選擇性的聯鎖保護。原有電流速斷保護的信號回路中串聯有該智能控制模塊，所以不會改變原有的繼電保護裝置功能。

圖2中所示的各級繼電保護裝置中動作閉鎖功能的原理如下：在各級繼電保護裝置中的電流速斷保護中使用智能控制模塊，并對其進行延時閉鎖，在各級保護間進行可行的信息傳遞和通信聯絡，也就是在發生故障后，智能控制模塊能及時接到速斷保護信號，在有效延時時間內行聯絡閉鎖通信，將各級保護間的操作時間安排好。如果故障線路上安裝的保護裝置未能在在規定的延時時間內接到由下級繼電保護裝置中智能控制模塊發過來的閉鎖信號，則需要將本保護裝置發來的閉鎖信號解除，接著由本級保護裝置發出的速斷保護動作來執行。而系統末端開關裝置中所安裝的智能控制模塊無需延時閉鎖。

區域選擇性聯鎖保護優化方案發揮作用的關鍵是要完成煤礦井下各種智能控制模塊的成功通信，對各種智能控制模塊控制程序的綜合性判斷要依據控制模塊自身及各級模塊傳來的信號進行，并發出跳閘或者自鎖的控制信號，然后結合硬件和軟件，以順利實現煤礦井下高壓供電網絡區域的選擇性保護聯鎖功能，依此來解決供電系統中存在的越級跳閘問題[8]。

由以上內容可以看出，當出現線路故障時，可以借助上下級通信信號，安排各級保護裝置所具有的速斷保護動作，實現保護裝置的保護聯鎖，避免越級跳閘現象的出現以及事故擴大；三級線路可以承受的最大短路能量沖擊時間是0.2s，既降低了三級線路所承受的內部應力及較重電動力，又減少了故障電流帶來的沖擊，因此達到了較好的保護效果[2，5]。

5 結語

綜上所述，區域選擇性聯鎖保護方案指將一個智能控制模塊安裝到原有的礦用開關上，從而與原有速斷保護裝置配合工作，借此實現

煤礦井下高壓供電線路的閉鎖保護。該智能控制模塊在僅串聯在速斷保護脫扣信號回路中，不改變保護裝置的傳統功能。該方案既能降低短路電流對供電網絡系統的影響，又能實現工作配合的完全選擇性，值得將其應用于煤礦井下高壓供電網絡中。

參考文獻

[1]劉士光. 煤礦井下高壓供電系統過電壓的分析與預防[J]. 科技創新導報，2013，19：23.

[2]余存泰. 一種區域選擇性聯鎖保護裝置的設計[J]. 低壓電器，2011，03：18-21.

[3]王光超，史世杰，張根現，鄒有明. 煤礦井下高壓供電網絡優化[J]. 中州煤炭，2011，06：80-81.

[4]高鋒. 煤礦井下3.3 kV供電網絡漏電故障保護研究[J]. 科學技術與工程，2012，29：7525-7531.

[5]衛小兵. 煤礦井下高壓供電系統繼電保護配置分析[J]. 科技與企業，2013，13：150.

[6]任憲友. 煤礦井上、下高壓供電方式的改造[J]. 電子世界，2013，11：57.

篇9

關鍵詞：復雜網絡；關聯性風險；無標度網絡；小世界網絡

中圖分類號：F83

文獻標識碼：A

doi：10.19311/ki.16723198.2016.30.051

1引言

伴隨金融自由化、復雜化趨勢的發展，金融機構之間更緊密地相互聯系在一起，這種相互聯系增加了金融危機迅速蔓延的可能性，由次貸危機所引發的全球金融危機顯示了金融傳染的危害性。研究表明，金融系統的微觀特征以及展現的宏觀結構對于系統內部風險傳染的程度具有重要影響。近年來，統計物理學領域在復雜網絡的形成及特征等方面獲得顯著進展，在諸多領域中，基于復雜網絡結構理論分析個體間結構及關聯性卓有成效，這為本文的研究提供了堅實的理論基礎和有益的借鑒。

作為貨幣市場的核心以及銀行間業務的重要組成部分，同業拆借市場平穩運行具有重要意義。同業拆借市場的平穩運行對于調節機構之間的流動性以及貨幣政策的實施至關重要。同業拆借市場因其市場化的運作以及高效率的機制使得同業拆借利率及時、靈敏地反映了市場資金的供求。因此在貨幣政策執行中，中央銀行將同業拆借利率作為反映金融系統中資金供求狀況重要指標，同業拆借利率成為貨幣市場上的基準利率之一。同時，銀行同業拆借市場也是商業銀行之間進行短期資金借貸的場所，是一國金融體系的重要組成部分。銀行主要依靠同業拆借市場進行流動性管理，銀行間市場的發展為銀行間資金調劑提供了順暢渠道.作為貨幣市場的核心部分，中國同業拆借市場進入了穩定發展階段，市場規模逐步擴大，2013年同業拆借市場總規模超過45萬億元，其中銀行與銀行之間拆借交易成交量占整個市場成交量的80%以上。然而，同業間風險暴露也使得銀行間的關聯性風險增大。因此，基于同業拆借產生的銀行間的關聯性風險是危機傳染的重要渠道之一。

為了提高分析結果的穩健性，在基于同業拆借市場分析的基礎之上，利用上市銀行股票收益的格蘭杰因果檢驗進一步分析銀行體系網絡結構特征。

2文獻綜述及理論分析

由于銀行之間存在復雜的債權債務關系，導致銀行之間形成緊密的內在關聯性，一旦某個銀行倒閉，銀行間的信貸關系使得破產危機在銀行之間傳染。要實現對系統性風險有效監管，對關聯性風險進行有效評估至關重要。國際貨幣基金組織在《全球金融穩定報告》（2009）介紹了評估系統性關聯風險的四種方法：網絡傳導分析法、共同風險模型法、困境依賴矩陣法以及違約強度模型法。金融系統是由多子系統、多種性質參與主體以及復雜交互作用關系構成的復雜網絡系統，這使得基于單個機構的分析無法有效評估整個金融系統所面臨的風險。復雜網絡金融理論認為，金融體系的內部結構必然與其功能以及運行狀態有緊密的關聯性。復雜網絡的拓撲結構通常可以描述金融系統的共同特征，復雜網絡理論通過研究金融系統結構的拓撲特征，從而對金融系統運行規律進行有效的揭示并達到控制風險的目的。該理論將金融網絡用抽象圖來替代，就是用抽象的節點來表示金融網絡中的個體，并用兩個節點間的連線表示個體之間的某種關聯性，金融系統中個體之間的關聯性通常是基于債權債務關系而產生。通過分析反映金融網絡結構特征一些參數指標，可以揭示金融系統的結構與特征。伴隨復雜網絡結構理論的發展，將復雜網絡的研究方法運用到金融領域問題的研究得到了極大的發展，尤其是針對系統性風險問題，復雜網絡金融理論基于系統論視角分析金融體系內部關聯性風險，二者之間在邏輯關系上存在一致性。

利用網絡結構理論研究關聯性風險主要包括微觀路徑和宏觀路徑兩種方法。在微觀路徑研究中，主要是運用風險管理、復雜網絡等領域的知識，并結合金融風險的發生機制研究穩定性較高的金融網絡所需具備的微觀特征。該領域的早期研究關注銀行間的連接方式及連接的緊密程度，Allen和Gale（2000）假設流動性沖擊來自于存款者取款時間的不確定性，當網絡處于完全連接狀態，網絡系統具有較高的穩定性，而當網絡處于不完全連接狀態時，系統會變得較為脆弱。Gai（2010）借鑒其他學者研究復雜網絡的數學方法，通過模擬金融網絡的形成過程分析穩健性的金融網絡應具備的特征，得出的結論是最短路徑長度應適當偏長。部分學者嘗試利用運籌法判斷最優微觀結構，Leitner（2005）運用運籌學理論，得出最優金融網絡的規模特征即每個小群體內最優節點數量為5。在宏觀路徑研究中，主要基于節點度、聚類系數、最短路徑長度等微觀指標研究金融網絡所呈現的宏觀結構。Hajime Inaoka等（2004）利用銀行交易結算數據分析了銀行網絡結構特征，研究表明銀行網絡具有自相似以及無標度特征。此外，并從理論上分析了不同網絡結構特征下的穩定性。該文將沖擊分為隨機性沖擊與選擇性沖擊兩種類別。對于隨機網絡，隨機性沖擊與選擇性沖擊的效應趨于一致，而對于無標度網絡，選擇性沖擊的效應遠遠大于隨機性沖擊。Michael Boss、Helmut Elsinger等（2004）基于同業拆借數據，并利用最小交互熵方法對奧地利銀行間市場網絡結構特征進行了分析，研究表明少數銀行具有大量關聯性，而多數銀行具有較少的連接。此外，奧地利銀行網絡呈現出群體結構特征，群體內部關聯性緊密，而群體之間的連接較為稀疏。Giulia Iori等（2008）利用隔夜拆借數據分析了意大利銀行間網絡結構特征及其演化特征。研究表明銀行間網絡具有隨機網絡的特征，并且呈現出度增加而強度減弱的狀態，研究還發現不同規模主體行為具備差異性。Nier（2007）研究表明銀行網絡集中度對關聯性風險產生的影響并不是單調的，在一定的閾值范圍內，集中度增加⒌賈鹿亓性風險增大，但當集中度超過一定的閾值范圍后，集中度增加反而會降低關聯性風險。Simone Lenzu（2012）基于市場主體的行為探討了銀行網絡形成的內生機制，并基于模擬分析風險傳染的特征。該文基于關聯形成的內生機制形成了隨機網絡與無標度網絡，為了研究不同網絡的穩健性，對網絡進行隨機性沖擊模擬，結果發現無標度網絡比隨機網絡具有更高的脆弱性。李守偉等（2010）通過構建有向網絡模型，通過分析隨機性攻擊與選擇性攻擊對網絡成分的影響研究銀行間網絡的穩定性。研究結果表明，銀行間網絡對于選擇性攻擊具有較低的穩定性，而對于隨機性攻擊具有較高的穩定性。

上述研究表明，金融網絡的微觀特征以及展現的宏觀結構對于分析金融系統的關聯性風險具有重要意義。本文以復雜網絡結構理論為基礎，基于銀行間市場同業拆借關系以及上市銀行股票收益的格蘭杰因果檢驗分析了銀行體系網絡結構特征及關聯性風險。具體結構安排如下：第三部分主要介紹矩陣法網絡模型及因果網絡模型；第四部分對銀行網絡結構特征進行實證分析；最后一部分內容對于本文的主要觀點與結論進行總結，并闡述了相關的政策啟示。

3研究設計

3.1基于矩陣法構建銀行網絡模型

首先基于最大熵的方法估計銀行間同業拆借矩陣，并利用RAS算法進行優化，該方法意味著各銀行盡量可能均勻分布資產；然后利用閾值法構建銀行網絡模型，由于在實際拆借行為中不可能任意兩個銀行間都存在雙向信用拆借關系，因此假設只有兩個銀行之間拆借規模超過一定閾值水平才認為兩個銀行之間存在拆借關系；最后計算度、聚類系數以及平均路徑長度等相關指標進而揭示銀行間同業市場網絡結構特征及關聯性風險。

由于只能獲取各個銀行同業拆借的總資產和總負債數據，無法獲得各個銀行相互之間交易的具體數據，因此需要基于總資產和總負債數據利用熵最優化法測算銀行同業拆借矩陣。銀行間市場同業拆借關系可以用矩陣X=（xi，j）N×N表示。其中，xi，j表示銀行i對銀行j的同業資產頭寸，N表示銀行數量。設ai表示銀行i對其他銀行的資產總額，ai=∑Nj=1xi，j，lj表示銀行對其他銀行的負債總額，lj=∑Nj=1xi，j。在一個具有N家銀行的系統中，X包含N2個元素，xi，j的具體值是未知的，但是ai和lj是已知的，在缺少其他約束l件下可以選擇最大化雙邊交易不確定性分布（信息熵最大化）。通過標準化，X視為聯合分布函數f（a，l）的實現值，而a和l可視為邊際分布函數f（a）和f（b）的實現值。如果f（a）和f（b）相互獨立，通過最大熵的方法可以得出xi，j=ai×lj。這種方法意味著i銀行對j銀行的資產額度取決于i銀行對其他銀行的資產總額以及j銀行對其他銀行的負債總額。通過上述方法可以計算出矩陣X，但是銀行不能與自身發生借貸關系，也就意味著xi，i=0，因此需要對矩陣X進行修正，修正后的矩陣為X*。求解X*等同于如下問題求解：

min∑Ni=1∑Nj=1x*i，jln（x*i，j/xi，j）

s.t.ai=∑Nj=1x*i，j，lj=∑Nj=1x*i，jx*i，j≥0

上述最優化的解可以利用RAS法計算獲得，從而得到銀行間同業拆借矩陣。在銀行間同業拆借矩陣的基礎上，本文采用閾值法構建銀行網絡特征。由于大部分銀行的銀行間資產、負債占所有銀行間資產、負債的比例在區間（0，0.01）之間，因此，我們將閾值c界定在（0.00001，0.0001）之間。如果當兩銀行之間同業拆借比例大于閾值c，則認為兩銀行之間存在拆借關系，在復雜網絡理論中意味著兩節點之間存在邊進行連接。本方法利用各個銀行的合并報表的拆借數據進行實證分析。我們使用兩組數據進行分析，一組是73家銀行2015年的同業拆借數據，另外一組是16家上市銀行2008-2015年間的同業拆借數據。

3.2因果網絡模型

在一個由n個金融機構構成的金融體系中，Ri表示金融機構i的股票收益率，Rm表示市場回報率，Rf表示無風險利率，則資本資產定價模型可以表示如下：

Ri―Rf=βi（Rm―Rf）+εii=1，2，……，n

則余項εi反映公司i特定風險溢價，本文定義Li=εi反映金融機構i所承擔的公司風險。由于金融時間序列數據通常具有波動集聚現象，本文利用GARCH（1，1）模型來描述公司風險的動態相關性。

Li，t=μi+σi，tZi，t

σ2i，t=wi+αiu2i，t-1+βiσ2i，t―1

其中，μi表示條件均值，σi，t表示條件標準誤，Zi，t表示白噪聲過程，ui，t=σi，tZi，t。

如果時間序列Zi，t包含時間序列Zj，t的有效信息，有助于提高Zj，t預測精度，則認為Zi，t是Zj，t的格蘭杰原因。

Zj，t+1=ajZj，t+bjiZi，t+ej，t+1

Zi，t+1=aiZi，t+bijZj，t+ei，t+1

如果bji顯著不為0，則Zi，t是Zj，t的格蘭杰原因。類似，如果bij顯著不為0，則Zj，t是Zi，t的格蘭杰原因。基于因果關系檢驗結果界定金融機構之間的網絡關系，如果存在因果關系，則表明代表金融機構的節點之間存在有向邊所連接。本方法利用16家上市銀行2015年股票收益數據分析銀行體系的因果網絡結構。

4實證分析

4.1銀行網絡節點度分布

為了分析銀行間市場網絡節點度分布情況，將閾值設定為0.00001、0.00003、0.00005、0.00007四種狀態，分別計算每一對應閾值狀態下各個節點的度，為了能夠更清晰地反映度的分布特征，我們將各節點度劃分到若干等距區間，即[0，9][10-19][20-29][30-39][40-49]，然后分別計算每一區間的概率，利用各個區間的概率分布來描述節點度分布狀況。圖1揭示了不同閾值水平下節點度分布狀況，我們發現節點度分布具備冪律分布的基本形態。

上述結論是建立在一定假設前提的基礎之上得出的，為了驗證該方法的有效性，我們可以從另外一個角度分析銀行市場的無標度網絡特征。我們分析了16家上市銀行2008年―2015年的同業拆借的總量，實際數據表明16家銀行借入資金總量與借出資金總量呈現出穩步上升趨勢，如圖2所示。而且根據2015年的完整數據，16家銀行同業拆借的總量占樣本73家銀行同業拆借的總量的比例達到38%。通過以上分析，進一步說明銀行間市場網絡存在一些中心銀行，銀行間同業拆借業務主要發生在這些銀行之間以及這些銀行與其他銀行之間。這些處于中心的銀行一旦出現危機，很容易通過他們的高連接狀態而影響整個銀行體系。H.A.Degryse（2004）將銀行間市場的這種結構稱作貨幣中心結構，從風險傳染的角度來看，決定整個銀行體系穩定性的是處于核心地位的銀行，而其他規模較小的銀行影響有限。根據H.A.Degryse（2004）研究表明，當處于貨幣中心地位的銀行倒閉時，貨幣中心型的市場結構比完備型的市場結構具備更強的傳染性，而當處于中心地位的銀行平穩運營時，貨幣中心型的市場結構更具穩健性。

因此，我們可以得出結論，銀行間市場網絡具有無標度網絡特征，即少數銀行具有較大的度，絕大多數銀行具有較小的度。無標度網絡特征意味著銀行間市場對于隨機性沖擊具有較強的穩健性，而對于選擇性沖擊具有脆弱性。因為絕大多數銀行具有較小的度，因此無標度網絡在遭受隨機沖擊時，這些具有較小度的銀行最容易遭到破壞，但這些銀行又只有較少的連接，所以這些銀行的危機對整個銀行體系的影響有限。但當銀行系統中具有較大度的銀行面臨危機時，局部危機會迅速擴散到整個銀行體系進而產生系統性危機。

4.2銀行網絡聚類系數及平均路徑長度分析

理論分析表明，如果一個網絡同時具有較大的集聚系數和較小的平均路徑長度，那么這樣的網絡稱為小世界網絡。在上文分析的基礎上，利用同業拆借矩陣計算不同閾值水平下的平均路徑長度與聚類系數。為了獲得因果網絡結構，需要對16家上市銀行股票收益數據兩兩之間進行格蘭杰因果關系檢驗。首先，基于資本資產定價模型計算β系數；其次，利用殘差數據，基于GARCH（1，1）模型進行參數估計；最后，在顯著水平為10%的條件下進行格蘭杰因果關系檢驗。表1為兩種不同方法所計算出來的平均路徑長度和聚類系數。

從上述數據可以看出，銀行間市場網絡具有較大的聚類系數和較小的平均路徑長度，這說明銀行間市場具有典型的小世界網絡特征。小世界網絡特征意味著一旦一個銀行出現嚴重危機，就會迅速傳導給并無直接關聯的其他銀行，從而導致整個銀行體系陷入危機狀態。因此，銀行間市場小世界網絡特征是導致關聯性系統性風險的重要原因。需要說明的是，在兩種不同的分析方法下，平均路徑長度趨于一致，但是聚類系數相差較大，這是由于相關指標值受閾值水平的影響較大。但根據網絡結構理論表明，即使是0.21的聚類系數水平仍然可以顯示網絡結構的無標度特征。

5結論及政策啟示

5.1銀行同業市場網絡結構特征及系統性風險分析

本文由復雜網絡金融理論與系統性風險管理之間的內在聯系出發，探討網絡結構對銀行間關聯性風險產生的重要影響，基與銀行間資產負債數據，通過理論與實證相結合的分析方法得出以下幾點結論：

（1）基于系統論的視角，進一步明確了系統性風險的內涵。系統性風險主要表現在兩個方面：一是金融系統作為整體與實體經濟相互作用過程中，導致系統性風險積聚；二是金融體系內部的關聯性風險，尤其表現為金融機構之間的風險溢出效應。

（2）各個銀行的同業拆借規模存在很大差異性，以中、農、工、建為代表的16家上市銀行形成了同業拆借網絡的中心，其他銀行之間雖然也存在業務往來，但規模較小，對銀行間市場的影響有限。

（3）實證上，通過閾值法對度、平均路徑長度以及聚類系數等相關指標進行分析，研究結果表明銀行間網絡具備小網絡特征以及無標度特征。這意味著銀行間市場對于隨機性沖擊具有較強的穩健性，而對選擇性沖擊具有較大的脆弱性。

5.2本文結論對金融監管的有效啟示

銀行間同業市場處于核心地位的銀行數量雖然較少，但與大多數銀行之間存在信貸關聯，一旦這些銀行出現危機，會迅速傳播到整個網絡，威脅銀行同業拆借市場的穩定。因此，加強對銀行間市場具有系統重要性銀行的監管有助于維護銀行間市場的穩定，確保銀行系統平穩運行。系統重要性銀行監管的首要問題是系統重要性機構的界定，需要根據我們國家的實際情況確定有效的指標體系，并選擇合理的方法進行量化以及相關指標的合成，減少執行操作的難度。

相關研究表明（馬君潞，2007），單一系統重要銀行產生的影響較為有限，如果處于網絡中心的眾多銀行同時出現危機，則會對金融體系產生重大沖擊。由于經濟波動的周期性以及其他共同風險暴露因素可能會導致多家銀行同時倒閉，從而引發更為嚴重的傳染?，F階段我國經濟形勢較為復雜，在全球經濟復蘇進程緩慢的背景下，我們正處在產業結構調整的關鍵時期，經濟增長下行壓力較大。從金融體系改革與監管的層面來看，需要處理好以下幾方面的問題：

（1）實現金融和實體經濟的有效結合。次貸危機表明，只有正確處理金融發展與實體經濟的關系，才能有效預防危機發生。中國在金融體系快速發展過程中，出現了金融脫離實體經濟的狀態，尤其是表現為房地產價格泡沫。針對金融發展過程中脫離實體經濟的苗頭，需要有效的預警機制，并通過相應的措施化解潛在的金融失衡風險。

（2）構建危機預警指標。陳雨露（2011）提出“金融失衡指數”這一指標對金融體系的失衡進行描述，用以構建“金融失衡指數”的基本指標包括：社會融資總量、投資、企業杠桿、利差水平、房地產價格和股票價格。該方法為構建危機預警指標提供有益引導，但關于預警指標的選擇與測度方法需要進一步深入研究。

（3）穩步推進金融混業經營。面對全球范圍內金融業混業經營大趨勢，為了提高中國金融體系的穩定性與效率，推進金融混業經營勢在必行。但在現階段金融監管滯后、內外約束機制尚不健全的狀況下，混業經營的推進要保持效率與穩定之間的動態平衡。

參考文獻

[1]IMF.Global Financial Stability Report：Responding to the Financial Crisis and Measuring Systemic Risk[R].working paper，April，2009.

[2]Allen F，Gale D.Financial contagion[J].The Journal of Political Economy，2000，（108）：133.

[3]Gai，P.，Kapadia， S. Contagion in Financial Networks[J].Proceedings of the Royal Society A，2010，466（2120）：24012433.

[4]Leitner，Y.Financial Networks： Contagion，Commitment，and Social Coordination[J].The Journal of Finance，2005，60（6）：29252953.

[5]Hajime Inaoka， Hideki Takayasu.Self-similarity of banking network[J].Physica A，2004，（339）：621634.

[6]Boss，M.，Elsinger，H.，Summer，M. Network Topology of the interbank Market[J].Quantitative Finance，2004，4（6）：677684.

[7]Giulia Iori，Giulia De Masi.A network analysis of the Italian overnight money market[J].Journal of Economic Dynamics & Control，2008，（32）：259278.

[8]Nier，E.，Yang，work Models and Financial Stability[J].Journal of Economic Dynamics & Control，2007，31（6）：20332060.

篇10

關鍵詞：離散數學；輻射作用；輻射體系；編譯原理；數據庫

中圖分類號：TP3-4

離散數學是現代數學的一個重要分支，也是計算機科學與技術的理論基礎，所以又稱為計算機數學[1]。離散數學研究離散量的結構及其相互關系，通過離散數學的學習，不但可以掌握離散結構的描述工具和方法，為后續課程的學習創造條件，而且可以提高抽象思維和邏輯推理能力，為將來參與創新性的研究與開發工作打下堅實的基礎。

離散數學課程所傳授的思想、方法與工具，廣泛地體現在計算機相關專業的諸領域，從科學計算到數據處理，從計算機科學理論基礎到計算機應用技術，從計算機軟件與理論到計算機硬件及體系結構，從人工智能到知識系統與工程，無不與離散數學密切相關。由于計算機本身是一個離散結構，它只能處理離散的或離散化了的對象及對象關系，因此，無論計算機科學理論本身，還是與計算機應用密切相關的現代科學的其它研究領域，都面臨著如何對離散結構進行數學建模的問題；當然，也需要考慮如何將已建立的離散數學模型進行計算機應用的問題。

隨著計算機專業研究生入學考試中專業課程統考的實行，很多高校的計算機專業對離散數學的教學投入開始縮減，減少課時，降低難度，避重就輕；學生也無法認識與理解離散數學在整個計算機專業課程體系中的重要性，致使離散數學的教學與學習在計算機專業越來越邊緣化。實際上，離散數學在各學科領域，特別在計算機相關專業領域有著廣泛的應用；離散數學是計算機專業許多專業基礎課程，如數據結構、操作系統、編譯原理、人工智能、數據庫系統原理、算法設計與分析、理論計算機科學基礎、軟件工程等必不可少的先行課程[2]。

作為計算機相關專業數學基礎的離散數學，對其它計算機專業基礎課程有很強的知識輻射作用。本文致力于從一些計算機專業基礎課內容中還原離散數學知識，從而體現離散數學核心內容在計算機專業系統知識中的輻射作用。通過對離散數學輻射作用的介紹，讓計算機相關專業的本科生重新認識到離散數學對計算機專業系統知識學習的重要性，從而提高本科生學習離散數學的興趣，重視自己數學理論基礎的鞏固和形式思維能力的培養。

1 離散數學輻射體系

離散數學是計算機及相關專業的一門核心課程，它不是一門純數學課程，而是計算機學科的專業基礎課程。離散數學是應計算機科學的發展而形成的一門交叉課程，主要內容涵蓋了計算機相關專業對數學的一些基本要求。廣義的離散數學主題包括集合論、數理邏輯、關系理論、圖論、代數結構、數論、信息論、組合數學等，甚至包含拓撲學、運籌學的內容。有些高校將除拓撲學、運籌學等內容外的主題分為三門課程，即集合論與圖論、代數結構與組合數學、數理邏輯。本文談到的離散數學內容只涉及到數理邏輯、關系理論、集合論、圖論以及代數結構。

離散數學課程與后續的計算機相關專業基礎課程有著千絲萬縷的聯系，對其它專業基礎課程的影響極其深遠，在很多計算機專業課程內容中都會涉及到離散數學知識。無論計算機軟件系列專業基礎課程，還是計算機硬件相關基礎課程，例如編譯原理、數據結構、數據庫、操作系統、軟件工程和計算機組成原理。本文選擇這六門計算機相關專業基礎課程來闡述離散數學在專業系統知識中的輻射作用，如圖1所示的離散數學輻射體系。

在圖1中，編譯原理的課程內容中就可以還原出全部的離散數學知識結構；數據庫的課程內容則可還原出離散數學內容中的關系理論、代數結構、集合論與圖論等內容；操作系統、軟件工程、數據結構和計算機組成原路中都有離散數學知識輻射的印跡。

2 離散數學輻射作用

2.1 編譯原理中的離散數學

編譯原理是計算機相關專業的一門重要專業基礎課[3]，旨在介紹編譯器構造的一般原理和基本方法，課程內容除了形式文法、有窮自動機等編譯原理所涉及的基礎知識外，其它內容基本上圍繞處理程序設計語言的編譯器應該具有的各功能模塊展開，包括詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優化和目標代碼生成。

離散數學的數理邏輯中最重要的內容就是邏輯推理，由前提事實出發，采用相應的邏輯恒等式、永真蘊涵式、推理規則、推理方法等進行不停的推導演繹，最終得到想要的結論，這是一個嚴格的演繹分析過程。在編譯原理中，與這一演繹分析過程相對應的則是語法自上而下分析方法，即從形式文法的開始符號（前提）出發，利用文法規則產生式（永真蘊涵式），采用相應的推理方法（最左或最右推導），最終得到想要的句型或句子（結論）。在推理證明中還有一種常用的證明方法，那就是從要求證的最終結論出發，依次為其找到相應的邏輯恒等式、永真蘊涵式、推理規則等作為最終結論或中間結論的依據，即從結論出發追本溯源到前提事實，這是一種典型的歸納邏輯。在編譯原理的語法分析中，自底向上的語法分析方法則是歸納過程的代表，即從要得到的句型或句子出發，利用文法產生式規則和推理方法，進行不停的歸約，一直到開始符號或失敗至，這是一直明顯的歸納邏輯推理過程，對應最右推導。

在離散數學的關系理論中，等價關系尤為重要。而在編譯原理中，處處有等價原理輻射的痕跡，例如形式文法等價、有窮自動機等價、中間代碼表示形式等價等。在編譯原理的內容中，有關等價的部分還包括正規文法與正則表達式的等價性、正則表達式與有窮自動機的等價性、正規文法與有窮自動機的等價性。實際上，有窮自動機等價是進行非確定有窮自動機確定化、確定有窮自動機化簡的理論基礎。

編譯原理的很多內容中都使用了形式化技術，最典型的就是狀態圖刻畫有窮自動機、語法樹表示語法分析過程，當然在LL（1）文法FIRST集與FOLLOW集計算、算符優先文法的優先函數關系圖以及基本塊有向圖中都體現了離散數學的集合論與圖論。在編譯原理全部內容中都貫穿了符號串運算，符號串與其上的運算則構成了一個完整的代數系統。

2.2 數據庫中的離散數學

數據庫技術和系統已經成為信息基礎設施的核心技術和重要基礎，數據庫技術作為數據管理的最有效的手段，極大的促進了計算機應用的發展[4]。數據庫的數據模型中的關系模型就經典地體現了離散數學中的關系理論，尤其是關系模型中的參照完整性。數據庫概念模型描述中使用的實體-聯系模型（圖）更是生動地呈現了實體型之間的關系。在離散數學中，函數是一類特殊關系，而關系數據理論中的函數依賴則描述了關系模式屬性（集）之間的語義關聯。數據庫中的查詢處理與優化的理論基礎則是離散數學中等價原理，查詢被處理或優化前后在功能和語義上必須滿足等價關系。

與關系模型緊密相連的則是關系代數，這是一類典型的代數系統。關系數據結構是其運算對象，關系操作則是定義在關系上的具體運算，如選擇、投影、連接、除等，這些運算都滿足封閉性，關系操作的輸入與輸出則都是表示關系數據的集合，因此集合運算中的并、交、差、笛卡爾積等也是關系操作的一部分。關系數據模型中常用的SQL語言則是關系代數的一種具體實現，即一種具體的代數系統。

數據庫理論中被集合論與圖論輻射到的內容包括：（1）一個關系數據庫是關系模式（二維表）的集合；（2）一個關系模式（二維表）就是一個實體集，表中每一個就是一個具體的實體元素；（3）在概念世界中描述實體型以及實體型間關系的實體-聯系圖；（4）關系查詢處理與優化中的查詢樹。

2.3 其它課程中的離散數學

數據結構是計算機程序設計的重要理論技術基礎[5]，也是計算機存儲與組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合，因而，數據結構課程中很多具體的數據結構都是集合，如隊列、棧、線性表等。數據結構除描述集合中數據元素的特性外，還要刻畫集合中數據元素之間的關系，因此，一般認為，一個數據結構是由數據元素依據某種邏輯聯系組織起來的，對數據元素間邏輯關系的描述稱為數據的邏輯結構。數據結構課程內容中的樹、二叉樹以及圖等結構則是離散數學圖論內容的延續，基于圖結構的各種算法，如最短路徑、最小生成樹、關鍵路徑等，在離散數學和數據結構中都有不同深度的描述。

操作系統課程中的進程狀態圖為典型的圖論內容；操作系統在對進程等對象進行管理時，很多內容涉及到對象間關系，如死鎖中進程間時序上的先后關系；操作系統中很多算法都使用到了集合概念，如死鎖的解鎖算法等。離散數學的核心內容輻射到了操作系統的管理與控制中。

軟件工程最終的產物是軟件系統，既然是軟件系統，在進行軟件系統分析與設計時，不可避免要研究系統各部分之間的關系。在結構化分析方法中，有自頂而下和自底而上兩類分析方法，自頂而下對應數理邏輯中的演繹邏輯，而自底而上則表示數理邏輯中的歸納邏輯。軟件工程內容中同圖論有關的包括軟件開發模型、軟件模塊間關系表示、軟件測試等。

計算機組成原理作為計算機專業硬件方面的基礎課，在學生對計算機的認知方面有著舉足輕重的作用。計算機硬件的基礎組成單元“邏輯門”等以離散數學中的命題邏輯為基礎；計算機處理器的結構形式化等都離不開集合論與圖論的參與。實際上，在讓學生認知軟件與硬件的功能等價性時，則充分體現了軟硬件的邏輯等價原理。

3 結論

針對離散數學課程在計算機專業課程體系中越來越邊緣化的問題，本文以編譯原理、數據庫、數據結構、操作系統、軟件工程和計算機組成原理計算機專業基礎課為例，論述了離散數學在計算機專業綜合知識體系中的輻射作用，從而體現離散數學在計算機專業教育中的重要性和必要性。

參考文獻：

[1]傅彥，顧小豐，王慶先等.離散數學及其應用[M].北京：高等教育出版社，2007.

[2]耿素云，屈婉玲，王捍貧.離散數學教程[M].北京：北京大學出版社，2002.

[3]張素琴，呂映芝，蔣維杜等.編譯原理（第二版）[M].北京：清華大學出版社，2005.

[4]王珊，薩師煊.數據庫系統概論（第4版）[M].北京：高等教育出版社，2006.

[5]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，2011.

作者簡介：胡慧君（1976-），女，講師，研究方向：智能信息處理；劉茂福（1977-），男，教授，研究方向：自然語言處理。