運籌學最短路徑精選(九篇)

前言：一篇好文章的誕生，需要你不斷地搜集資料、整理思路，本站小編為你收集了豐富的運籌學最短路徑主題范文，僅供參考，歡迎閱讀并收藏。

第1篇：運籌學最短路徑范文

關鍵詞： AutoCAD；Auto LISP；最短路徑

Abstract: This paper describes in the CAD platform, using Auto LISP programming language, take a received a cable graphics for example to research on the shortest path problem and how to improve the retrieval speed of the shortest path, and quickly come to retrieve results.Key words: AutoCAD; the Auto the LISP; shortest path

中圖分類號：P315.69 文獻標識碼：A文章編號：2095-2104（2012）

引言

最短路徑問題在計算機科學、運籌學、交通工程學、地理信息系統(tǒng)等學科中是一個研究的熱點，它是資源分配、線路選擇等問題解決的基礎，尤其是在諸如地圖、車輛調度和路由選擇方面有著廣泛的應用。基于其具有廣泛的應用性，所以本文以一個交通路線的選擇為例對其進行了研究，希望能起到拋磚引玉的作用。

1 軟件的運行平臺及開發(fā)語言的簡介

AutoCAD是美國Autodesk公司推出的通用計算機繪圖軟件，它以其強大的繪圖功能和良好的開發(fā)環(huán)境，廣泛應用于機械、電子、化工、建筑、測量與勘察等行業(yè)。對AutoCAD進行二次開發(fā)的手段很多，例如Auto LISP、ADS、ARX、VBA等，本程序使用的是Auto LISP編程語言，它已被嵌入CAD中。Auto LISP具有語法簡單、功能強大、易學易用的特點，它的數據類型相當隨意，可以組織處理不同長度和結構的數據類型，用戶可以按要求和最佳結構設計使用自定義的結構類型數據，而不會感到組織數據結構上的困難。另外，Auto LISP擅長人機交互操作的過程，對用戶輸入的接受、錯誤識別、恢復操作等方面的優(yōu)秀功能，是其它語言難以比及的。

2 程序具體實現

2.1 設計思路

研究最短路徑問題，我們不得不提到寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索），它是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。

2.1.1在存儲擴展成果表時采用分段存儲方式，將點號按大小分成四段存儲在四個表中，便于在檢索點號時只檢索其中的一個表即可，縮小檢索點范圍。

2.1.2設置檢索距離，當檢索距離大于已找到的終點檢索距離后停止檢索，避免做無用的檢索。

2.1.3程序以起始點到終點的有向線段方向預設優(yōu)先檢索方向，先收索與之方向夾角小的路徑，爭取最短時間得到終點檢索距離值，減小檢索范圍。

2.1.4在檢索存儲點號時對存儲表采用二分法檢索，以提高點號的獲取速度。

2.2 程序原代碼

(defun c:drj()

(setvar "CMDECHO" 0)

(setq SEHfbl1 nil SEHfbl2 nil SEHfbl3 nil SEHfbl4 nil) ;;設置存儲塊點點表

(setq lstDZbl1 nil lstDZbl2 nil lstDZbl3 nil lstDZbl4 nil);;設置對照點表

(setq SEHfh (SEHBLPX));;初始化塊點點表

(setq QiShiDian (car (entsel "\n選擇起始點:")))

(setq SelQSDlst (entget QiShiDian))

(setq SelQSDxyh (cdr (assoc 10 SelQSDlst)))

(setq SelQSDh (fix (last SelQSDxyh)));;起始點點號

(princ "\n您選擇的起始點為:")

(princ SelQSDh)

(setq ZhongDian (car (entsel "\n選擇目的點:")))

(setq SelZDlst (entget ZhongDian))

(setq SelZDxyh (cdr (assoc 10 SelZDlst)))

(setq SelZDh (fix (last SelZDxyh)));;起始點點號

(princ "\n您選擇的目的點為:")

(princ SelZDh)

(command ".zoom" "e")

(alert "程序即將運行,可能需要一點時間,請耐心等候!")

(setq lstDKbl nil);;預置待擴點表

(setq lstJieGuo nil)

(setq finddist 0)

(setq lstTmp nil)

(setq lstKYbltmp nil);;預置擴延臨時表

(setq Firstflag 0)

(setq lstTmp (LJDBall SelQSDh));;對起始點擴展

(if (vl-consp lstTmp) (progn;;如果lstTmp不為空表

(setq maini 0)

(repeat (length lstTmp)

(setq mainys (nth maini lstTmp))

(setq mainysb (list SelQSDh mainys))

(if (

(if (and (> mainys SEHfh) (

(if (and (> mainys (* 2 SEHfh)) (

(if (> mainys (* 3 SEHfh)) (setq lstDZbl4 (cons mainysb lstDZbl4)))

(setq lstDKbl (cons mainysb lstDKbl))

(setq maini (+ maini 1))

)

(setq lstDKbl (reverse lstDKbl));;生成待擴點表

(if (vl-consp lstDZbl1) (progn;;如果lstDZbl1(對照點表1)不為空

(setq lstDZbl1 (vl-sort lstDZbl1 (function (lambda (e1 e2) (< (cadr e1) (cadr e2))))));;對表進行排序點號從小到大

))

(if (vl-consp lstDZbl2) (setq lstDZbl2 (vl-sort lstDZbl2 (function (lambda (e1 e2) (< (cadr e1) (cadr e2)))))))

(if (vl-consp lstDZbl3) (setq lstDZbl3 (vl-sort lstDZbl3 (function (lambda (e1 e2) (< (cadr e1) (cadr e2)))))))

(if (vl-consp lstDZbl4) (setq lstDZbl4 (vl-sort lstDZbl4 (function (lambda (e1 e2) (< (cadr e1) (cadr e2)))))))

(setq lstDKbl (QCDFUN lstDKbl));;獲得純正的擴展點表

(while (vl-consp lstDKbl);;循環(huán)到lstDKbl為空表為止

(KYFUN lstDKbl SelQSDh);;對lstDKbl進行一次擴延

(setq lstDKbl (QCDFUN lstKYbltmp))

(setq lstDKbl (JJPL SelQSDh SelZDh lstDKbl));;按方向夾角從小到大排序

(setq lstKYbltmp nil)

)

))

(if (vl-consp lstJieGuo) (progn;;如果結果表不為空

(princ "\n起點到目的點最短路徑是:")

(princ "\n")

(princ lstJieGuo)

(princ "\n距離為:")

(princ finddist)

))

(if (not (vl-consp lstJieGuo)) (progn;;如果結果表為空

(princ "\n從起點沒有路徑能到達目的點!!!")

))

(princ)

)

3 結束語

本程序是在CAD平臺下開發(fā)的，其收索所需線畫圖的制作和更新都十分便捷，利用此程序對多個中小城市的道路圖做收索實驗，其最大范圍的檢索時間在十幾秒之內，一般范圍的收索均在幾秒內完成，因此程序具有較強的實用價值。由于篇幅所限本文僅列出了主程序模塊的原代碼，有編寫繁瑣之處敬請批評指正。

參考文獻

[1] 康博．中文版AutoCAD2000/2002 Visual LISP開發(fā)指南[M]，北京：清華大學出版社，2001.8

[2] 唐亮，等．AutoCAD2002開發(fā)教程[M]，北京：北京希望電子出版社，2002.8

[3]（美）Hamdy A.Taha.運籌學導論：初級篇（第8版）[M].北京：人民郵電出版社，2008

第2篇：運籌學最短路徑范文

關鍵詞：圖論；最短路徑；Dijkstra；Floyd；演示系統(tǒng)

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2016）18-0159-02

圖論問題始終滲透整個計算機科學，可以說每個編程者都不可避免地與圖打交道，因而圖論算法對計算機科學至關重要。它的應用領域非常多。例如，圖論可以應用于電路網絡分析、運籌學、網絡、信息論、控制論以及計算機科學等各個領域。我們知道最短路徑問題是網絡理論中應用最為廣泛的問題之一。而這里介紹的最短路徑算法是圖論算法中重要的一支。最短路徑算法可以解決許多問題，例如：線路安排、管道鋪設、路由選擇、地址選擇、設備更新、廣場布局、時變拓撲網絡等。我們這里研究的就是最短路徑問題的算法，具體指的是迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。這里通過開發(fā)一個系統(tǒng)演示程序來生動的闡述迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。該系統(tǒng)演示程序簡單易用、清晰明了、界面友好、非常實用。該系統(tǒng)演示程序是在Eclipse和JDK1.6的環(huán)境下用java語言開發(fā)而成的。它為解決最短路徑問題提供了一個簡單實用的平臺。

1 最短路徑問題

定義：我們給定一個帶權重的有向圖G=（V，E）和權重函數w：ER，該權重函數將每條邊映射到實數值的權重上。圖中一條路徑p=的權重w（p）是構成該路徑的所有邊的權重之和：w（p）=∑w（vi-1 ， vi） ，i=1，2，3…，k。

假設一條從節(jié)點m到節(jié)點n的最短路徑權重為W（m，n），且W（m，n）計算如下：

①如果存在一條從節(jié)點m到節(jié)點n的路徑，則：W（m，n）=min{w（p）|p是一條從節(jié)點m到節(jié)點n的路徑}；②否則，W（m，n）=∞。

從節(jié)點m到節(jié)點n的路徑p，如果滿足w（p）= W（m，n）則該路徑p即為從節(jié)點m到節(jié)點n的最短路徑。求從節(jié)點m到節(jié)點n的最短路徑和最短距離的問題就是最短路徑問題。

2 最短路徑算法

2.1弗洛伊德算法思想

我們使用三重for循環(huán)產生一個矩陣來記錄每個節(jié)點間的最小距離。對于弗洛伊德（Floyd）算法我們使用矩陣Juzhen[i][j]（i，j=1，2，……n+1）存儲有向圖的權重值。所以，其基本思想為：初始化一個n階矩陣A（k），其主對角線上的元素初始化為0，非對角線上的元素初始化A（k） [i][j]，其中每一個A（k） [i][j]是節(jié)點i到節(jié)點j的權重值，k是運算到第幾步。算法一開始，我們選擇任意兩個節(jié)點分別作為起始點和終止點，若他們之間有邊則取其權重值作為他們的路徑長度，若無權重邊，則令其路徑長度為∞，再有k=0時，我們初始化A（k）[i][j]，此時A（0）[i][j]=Juzhen[i][j]，將路徑上的節(jié)點加入集合S中，之后再選擇不在集合S中但能構成最短路徑的節(jié)點，使其加入集合S，如果在i節(jié)點和j節(jié)點之間增加了中間節(jié)點后，使得節(jié)點i到節(jié)點j的路徑比A（k） [i][j]小，就用新的權重值去更新A（k） [i][j]。

因此，弗洛伊德（Floyd）算法步驟如下：

（1）當k=0時，A（0）[i][j]= Juzhen[i][j]； 其中Juzhen[i][j]為鄰接矩陣

（2）當k=i+1，i+2，…，j時，A（k）[i][j]=min{A（k-1） [i][j]，A（k-1） [i][k]+A（k-1） [k][j]}

其中A（k）[i][j]表示節(jié)點點vi 到vj ， 中間節(jié)點的不大于k的最短路徑的長度，這里求的是中間節(jié)點的不大于n的最短路徑的長度即A（n）[i][j]。

因而，其算法可以描述為：

（1）令D[i][j]=A[i][j]

（2）for（k=1；k

for（i=1；i

for（j=1；j

if（D[i][j]> D[i][k]+ D[k][j]）

{D[i][j]=D[i][k]+ D[k][j]}

（3）算法結束后矩陣D存儲了所有節(jié)點之間的最短路徑值。

2.2 迪杰斯特拉算法的思想

Dijkstra算法解決的是帶權重的有向圖上單源點最短路徑的問題。該算法要求所有邊的權重都為非負值。Dijkstra算法把圖中所有的節(jié)點分為兩組：設集合S表示已經求出的最短路徑上的節(jié)點的集合；集合T=V-S表示在集合V中而在節(jié)點S之外的所有的節(jié)點的集合。然后把集合T中節(jié)點按權值非減的次序排序，并按此順序依次加入到集合S里。除此之外，還要滿足如下兩個條件：第一，從出發(fā)點v0到集合S中每一個節(jié)點的最短路徑長度A（k）[i][j]都應該小于或者等于從節(jié)點v0到集合T中所有節(jié)點的權重值也即最短路徑長度；第二，集合S和集合T都對應一個距離值。S中的節(jié)點表示的距離是從出發(fā)點v0到該集合中每一個節(jié)點的最短路徑長度，集合T中的節(jié)點表示從出發(fā)點v0到集合T中所有的節(jié)點且只經過集合S中節(jié)點作為中間節(jié)點的最短路徑長度。因此，迪杰斯特拉算法可描述為：

設置輔助數組dist，其中每個分量dist[k] 表示 當前所求得的從源點到其余各頂點k的最短路徑。

（1）S = {v0}；//頂點v0為源點

（2）設置集合V-S中各頂點的初始距離值；

（3）while （集合S中頂點數

{在集合V-S中選擇距離最小的頂點vj；S=S+{vj}；

調整集合VS中頂點的距離值；}

3 最短路徑算法圖形化演示程序檢驗

下面通過一個實例檢驗系統(tǒng)演示程序的正確性。

實例：如圖1所示，求一條從節(jié)點A到節(jié)點C的最短路徑，并求出其權重值。

具體操作步驟是：①運行系統(tǒng)；②點擊新結點按鈕和結點連線按鈕，然后在畫布上用鼠標點擊構造結點和連線；③雙擊結點輸入結點名，雙擊連線輸入權重值，以此構造出圖1；④選擇始點為A，終點為B，選擇使用的算法（迪杰斯特拉算法或弗洛伊德算法）；⑤點擊激活按鈕后，點擊開始按鈕，結果如圖2所示；⑥點擊算法展示按鈕會出現迪杰斯特拉算法和弗洛伊德算法的展示選擇界面；⑦點擊概念展示按鈕會出現迪杰斯特拉算法和弗洛伊德算法的概念選擇界面；⑧在算法展示界面和概念展示界面點擊相應的按鈕會彈出與此相符的PPT文件進行展示。

4 結論

在了解圖論最短路徑的問題的算法（迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法）、概念和原理的基礎上，開發(fā)了一個算法圖形化演示程序，并對改程序進行了正確性的驗證。這里開發(fā)的算法系統(tǒng)演示程序生動形象地闡述了迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法的概念和原理，并通過畫圖的方式簡化了操作。該系統(tǒng)演示程序簡單易用、清晰明了、界面友好、非常實用。它為解決最短路徑問題提供了一個簡單實用的平臺，這樣的研究是有積極意義的。

參考文獻：

[1] 田豐，馬仲蕃.圖與網絡流理論[M].北京：科學出版社，1987.

[2] 徐鳳生.求最短路徑的新算法[J].計算機工程與科學，2006，2.

[3] 魏文紅，李清霞，蔡昭權.一種基于桶結構的單源最短路徑算法[J].計算機工程與科學，2012，4（34）：77-81

[4] 王樹西，吳政學.改進的Dijkstra 最短路徑算法及其應用研究[J].計算機科學，2012，5（39）：223-228

[5] 朱福喜.面向對象與Java程序設計[M]. 北京：清華大學出版社，2008.

[6] 朱福喜.Java編程技巧與開發(fā)實例[M]. 北京：清華大學出版生，2004.

[7] 王昆侖，李紅.數據結構與算法[M]. 北京：中國鐵道出版社，2006.

[8] 侯風巍.數據結構要點精細[M]. 北京：北京航空航天大學出版社，2006.

[9] 劉萬軍.Java程序設計實踐教程[M]. 北京：清華大學出版社， 2006.

[10] 方賢文.Java語言程序設計[M]. 安徽：安徽科學技術出版社，2014.

[11] 李興華.java開發(fā)實戰(zhàn)經典[M]. 北京：清華大學出版社，2009.

第3篇：運籌學最短路徑范文

[關鍵詞]卓越計劃；運籌學實驗；數學建模

[中圖分類號]G64 [文獻標識碼]A [文章編號]1005-6432（2012）41-0145-02

1 引 言

卓越工程師教育培養(yǎng)計劃（以下簡稱“卓越計劃”）是為貫徹落實黨的十七大提出的走中國特色新型工業(yè)化道路、建設創(chuàng)新型國家、建設人力資源強國等戰(zhàn)略部署，貫徹落實《國家中長期教育改革和發(fā)展規(guī)劃綱要（2010—2020年）》實施的高等教育重大計劃?！白吭接媱潯本哂腥齻€特點：行業(yè)企業(yè)深度參與培養(yǎng)過程、學校按通用標準和行業(yè)標準培養(yǎng)工程人才、強化培養(yǎng)學生的工程能力和創(chuàng)新能力。力求培養(yǎng)一大批面向工業(yè)世界、面向世界、面向未來、適應經濟社會發(fā)展需要的高質量各類型工程技術人才。而高校是實施“卓越計劃”的主要陣地，在“卓越計劃”的推進過程中加強專業(yè)課程改革是十分必要的。

管理運籌學的飛速發(fā)展為各個行業(yè)把握管理大型組織的復雜性提供了一套十分重要的工具。這些工具集中了世界的各個邊緣的知識，其中包括數學、統(tǒng)計與概率論、計量經濟學、電機工程甚至生物學。這些外來的技術，如線性規(guī)劃、排隊論、自動控制理論、博弈論、動態(tài)規(guī)劃以及信息論，正在幫助解決各個行業(yè)中的實際問題。

因此，在管理運籌學教學中應針對所要解決實際問題的要求和其面臨的客觀環(huán)境條件，作出假設分析，抽象為數學模型，然后應用相關的數學知識加以解決。這就要求問題解決者要知識面廣、邏輯思維嚴密，這對于非數學專業(yè)，特別是經管類專業(yè)學生實在過于困難，因為，由于受到學時限制，經管類專業(yè)學生對高等數學、線性代數、概率與數理統(tǒng)計等先修課程學的比較膚淺，沒有或很少經過數學嚴密的邏輯思維方面的訓練，而且經濟管理類專業(yè)學生是文理科兼收，有相當一部分學生在數學方面的課程普遍底子較差，這客觀上就給運籌學教學帶來很大困難。因此，為使經濟管理類學生能正確全面地掌握各級管理中已被廣泛應用，且發(fā)展較成熟的最優(yōu)化理論與方法，并能恰當運用解決實際管理工作中的各種最優(yōu)化問題，有必要針對經濟管理類專業(yè)學生的特點和運籌學課程的性質，進行運籌學教學方法的改革。

2 運籌學在數學建模中的應用

管理運籌學在數學建模中有著廣泛的應用，多年來許多數學建模競賽中都涉及運籌學的相關內容。

首先介紹一下圖與網絡在數學建模中的應用，通過“奧運場館周邊的MS網絡設計方案”這個例子來說明其應用。假定奧運會期間每位觀眾平均出行兩次，一次為進出場館，一次為餐飲，并且出行均采取最短路徑。測算題目中20個商區(qū)的人流量分布。首先將建模結構圖轉化為無向賦權圖，并鑒于該圖的對稱性，通過設計一種特殊的流量計算方法對傳統(tǒng)的Dijkstra算法進行改進；其次，用MATLAB編寫求解最短路的應用程序，可以得到任意兩點間的最短路徑，進而得到觀眾出行的最短路徑和所經過的商區(qū)。

接著通過“彩票發(fā)行方案的優(yōu)化設計模型”這個例子來說明決策論在數學建模中的應用。設計一種“更好”的方案，據此給彩票發(fā)行部門提出建議。對此問題，可根據效用理論中存在著主觀概率，以及彩票信息在人群中的傳播效應，建立主觀概率意義下的優(yōu)化模型。但這個模型是較大規(guī)模的非線性規(guī)劃模型，用窮舉法求解比較困難，可采用模擬退火算法來求解，用MATLAB編程實現。

3 結合數學建模改進教學方法

3. 1 更新教學觀念，充分重視實驗教學

結合數學建模在教學中增加實驗教學，以提高學生解決實際問題的能力、培養(yǎng)學生的觀察和動手能力為宗旨，有利于培養(yǎng)學生的創(chuàng)新意識與創(chuàng)新能力。在今后的教學中，統(tǒng)籌安排課時，根據教學進度合理安排實驗教學時間，力求在完成每一知識點的學習后安排一次實驗。實驗內容將從實際問題出發(fā)，突出本章節(jié)的基本原理與基本方法，教師進行監(jiān)督與指導，有助于學生對理論知識的掌握與理解，同時學生的實踐能力得到鍛煉，自主學習能力得到提升。

3. 2 分級教學

從學生實際出發(fā)，因材施教是將幾乎處于同一水平的學生放在一起分別教學的一種教學手段。這種教學體系，根據學生的個體差異，按照不同科目的不同學習能力的高低將學生群體劃分成不同的級別或層次，有針對性地進行分班教學。有效的分級教學，能使教師節(jié)約精力突出重點積累經驗，能讓學生盡可能地在各自的最近發(fā)展區(qū)得到充分的自由發(fā)展，謀求各個層次的學生都能獲得成功的體驗，促進學生的素質得到全面提高。所以說，分級教學是建立在以學生成才為本理念基礎上，為實現教學目的的一致性和教學過程的互異性所進行的重要實踐，因材施教是分級教學的核心思想。在運籌學教學過程中，也可采用分級教學，培養(yǎng)學生對運籌學的學習興趣，進而培養(yǎng)數學建模人才。

3. 3 適宜的教學方法

近幾年來，由于擴招，生源的擴大，學生基礎參差不齊。因此，教師應根據學生具體情況，精心設計教案，調整教學內容、次序和教學組織方式；盡量從學生感興趣的實例出發(fā)，引入正題，以引發(fā)學生學習興趣，吸引學生注意力，使之能更好地掌握理解所學知識，并能恰當運用解決實際問題。

傳授新知識時，教師講授的時間不能過長，內容不能過多，節(jié)奏不能過快，并要將基本概念、基本原理在不影響教學效果的情況下，分散介紹，使學生易于接受；否則，教師的講授將是無效的講授。運籌學課程內容多、邏輯性強且抽象，需要學生理解掌握。因此，課堂上教師的板書一定要簡潔、條理清楚、重點和注意事項突出，并要求學生養(yǎng)成做筆記的良好習慣，以便于課后溫習理解和掌握。

3. 4 量體裁衣，突出專業(yè)特色

實驗教學中實驗內容是反映教學目的載體，豐富的實驗內容可以激發(fā)學生的學習熱情和拓寬知識結構。因此，實驗內容的選擇要“量體裁衣”。面對知識面較廣的商學院學生，要想上好運籌學并凸顯其實用性，教師需具備充分的定量和經濟管理學知識。例如，庫存模型通常將需求區(qū)分為固定和相對復雜的隨機兩類，當學生對需求滿足特定分布的假設產生疑惑時，教師就應當能夠適時介紹需求數據的獲取及利用統(tǒng)計學軟件對其分布加以判斷的方法，這可加深學生對運籌學交叉性的理解。

4 結 論

隨著科學技術的進步及“卓越計劃”的深入推進，需要對運籌學課程的建設持續(xù)探索與實踐，不斷完善教學方法與教學內容，提高學生的學習興趣，激發(fā)學生的學習熱情，真正意義上實現運籌學作為經濟管理類專業(yè)核心課程應有的重要作用，并鍛煉學生的動手能力，培養(yǎng)學生的創(chuàng)新意識與創(chuàng)新能力，以滿足創(chuàng)新教育的要求。

參考文獻：

[1]教育部. 教育部啟動“卓越工程師教育培養(yǎng)計劃”[Z].

[2]韓中庚. 數學建模競賽——獲獎論文精選與點評[M].北京：科學出版社，2007（5）.

[3]劉智，汪妍. 管理運籌學教學的思考[J].高師理科學刊，2011（4）：83

第4篇：運籌學最短路徑范文

關鍵詞： 最優(yōu)路徑 公交網絡 乘客OD量

隨著城市建設的迅猛發(fā)展，公交出行已成為人們的一個重要出行方式。公共交通作為一個城市經濟發(fā)展的象征性基礎設施，它為廣大居民的日常出行提供了方便，因此也關系到一個城市的基本保障問題.優(yōu)化公交網絡，提高公交運載效率越發(fā)受到社會的關注，成為人們的迫切需求.

公交規(guī)劃就是一個多目標的優(yōu)化問題.進行公交優(yōu)化設計需要區(qū)分主次，設定專門的優(yōu)化措施.為此，我們提出了“分離目標，逐步解決”的辦法.主要是利用數學模型，通過計算機進行處理，得到一個初步優(yōu)化完善的公交網絡.再適當做些調整，使得線路能夠分布相對均勻，消除空白的公交區(qū)域.

1.Dijkstra算法

Dijkstra算法是很有代表性的最短路算法，其基本思想是，設置頂點集合S并不斷地作貪心選擇來擴充這個集合.一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知.初始時，S中僅含有源.設u是G的某一個頂點，把從源到u且中間只經過S中頂點的路稱為從源到u的特殊路徑，并用數組dist記錄當前每個頂點所對應的最短特殊路徑長度.Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數組dist作必要的修改.一旦S包含了所有V中頂點，dist就記錄了從源到所有其他頂點之間的最短路徑長度.

2.公交線路布設模型

2.1公交線路的布設原則

公交網絡本身具有快捷、靈活、網絡覆蓋率高的特點，適合中短距離出行.一般公共汽車的起訖站點相隔在500m到800m之間，如果是在城市中心的話站點之間可以縮短到400m，時間上在客流高峰的時候發(fā)車間隔會在3到5分，除此之外的時間可以增加到6到8分，站點設置一般能和其他站點有較好的換乘[1].

2.2城市客流集散點的計算

在已知公交OD矩陣的條件下，將研究區(qū)域劃分成若干地理性質相似的區(qū)域，也可以依據行政意義進行劃分，把每一個分好的小區(qū)看作一個單一的節(jié)點，同時又要能被城市中的主要干路線路貫通，然后通過具體分析可以確定以下指標，并且作為節(jié)點的重要度指標.這些指標有地理位置、路況、OD集散程度、人口數量、金融指標等[2].

節(jié)點的加權平均值為：L■=■α■·■，L■表示區(qū)域內節(jié)點i的重要度；

α■表示第j項指標的權重；M是指標數量；e■是節(jié)點i的第j項的指標.

e■為區(qū)域內所有節(jié)點的第j項指標算數平均值.

客流集散強度：E■= ∑■ q■·δ■■，q■是OD點k，1間的OD客流量（人）

δ■■=1，當j，k間的最短路徑經過i0，否則

式子中權重值α■的確定即確定出各個標準對于每個節(jié)點重要程度的影響效果.

2.3線路起訖點確定

客流量集散地點確定以后，就可以根據公交區(qū)域的客流量（OD量），即根據交通區(qū)域的發(fā)生量還有吸收量最終找到起訖點.

2.3.1按照客流量設定站點

當交通小區(qū)處于高峰時期，發(fā)生量和吸引量都超過了此線路中間站點的最大運載能力的時候，僅僅依靠中間站點無法完成運載任務，那么這個交通小區(qū)就要設置為起訖站點，從而增加運載量.所以可以依據中間站點的運載量設定起訖站.某一個交通小區(qū)發(fā)生量和運載量超過某一個值時候，需要設定站點.

單個中間站點運輸力為C■=60B/t■，C■是中間站點運載力（即人次/高峰小時）；t■是高峰每小時的發(fā)車時間間距；B是高峰小時每輛車從中間站搭乘乘客數量的平均值，所取的值可以通過調查得出.交通小區(qū)中間站運載力為c（i）=c■N（i），全規(guī)劃區(qū)域的站點個數N■=ρs/d，N■為全規(guī)劃區(qū)域站點的數量；ρ是規(guī)劃的公交網絡的密度；S是規(guī)劃區(qū)域的面積；d為站點的平均間隔.

先根據各個交通小區(qū)的出行數量的相對值大小確定出中間站的數量N（i），N（i）=N■T（i）/T，T（i）為交通小區(qū)公交乘客發(fā)商量或者是吸引量的總和；T為全規(guī)劃區(qū)域的公交發(fā)生量的總和.T=■T（i），一個起訖站點的最大運載力為C■=60Rr/（t■k■）.

2.3.2按照實際的要求設置起訖點

一些特殊的地區(qū)，如汽車車站、熱門旅游景點、船運港灣、生活區(qū)等，為了滿足乘客的出行路線，服務人民生活，即使總的發(fā)生量和吸引量沒有達到設站的要求，也可以設定起訖站點.

2.4公交線路的校正和優(yōu)化

2.4.1設置網絡的最佳走向

確定起訖點以后，就要根據路段的不同將行駛所用時間作為阻抗，從而來求得各個起訖站點配對以后的最短路徑.又由于這里想到要把優(yōu)化的網絡經過集散點，因此又提出了一個“集散點吸引系數”.

2.4.2直達乘客數量的校正

2.4.2.1公交線路長短的校正

公交網絡的路線距離不能過于長和短，必須按照該城市里的實際情況來確定，對已經擬定的待選路線來篩定.對于那些不滿足該條件的首末點之間我們不設定公交線路，這時候就要把直達的乘客數量Z■設置為0.

2.4.2.2防止線路間的自相配對

同一個節(jié)點是不可以作為相同單向路線起訖站點，因此令Z■=0.

2.4.2.3對于同一區(qū)域設定多個站點的校正

當有些劃定區(qū)域的出行量值非常大的時候，就要確定多個起訖站點了，這個時候，在直達乘客的矩陣里，相對應的起點那一行和終點那一列就要校正，校正次數和這個區(qū)域的起訖站點數量是一致的.

2.4.3所設定線路的優(yōu)化校正

優(yōu)化線路需要考慮以下問題：校正乘客的OD量，確定OD量的剩余數值，校正行車時間，以及復線系數.

3.實例

我們假設一個交通路線分區(qū)和基本路段的路線圖，OD量我們假設已經通過調查求出.圖中線路上的數字是該條路段車輛的行駛時間（單位：分鐘）.

待選路線中的直達乘客數量表示為：

再按照線路的長度要求，防止自相的配對、一個區(qū)域設定多個站然后再次對直達的乘客量進行校正.經過最后的計算.OD在[B，C]的乘客量是最大的.這就要設定一個B到C、C到B的公交網，那么最短路徑就會是6-12-18-17-16-15-14-20-19.

通過之前的復線系數把第一條公交路通過行車行駛時間修正（其中的數值可以參考待選的最短路徑）.到這里，第一條線路設置工作就全部結束了，除去B和C點以外，再一次查詢最短路徑，逐次去布設第二條、第三條公交線，最后得到完整的網絡線路圖.

現實生活中公交網絡問題受到諸多因素的影響，需要綜合考慮這些因素的制約，而且需要搜集大量的數據，并進行實際論證，需要通過數學建模的方法進行研究，合理且便于操作的方法，這也是后續(xù)研究的方向.

參考文獻：

[1]成邦文，王齊莊，胡緒祖.城市公共交通線網優(yōu)化設計模型和方法[M].系統(tǒng)工程理論與實踐.

[2]李維斌.汽車運輸工程[M].北京：人民交通出版社，1987.

[3]趙志峰.城市公共交通線路網規(guī)劃方法[J].上海交通大學學報，1988，22（6）.

[4]易漢文.城市公交線路系統(tǒng)的規(guī)劃與設計[M].系統(tǒng)工程，1987，5（1）.

第5篇：運籌學最短路徑范文

[關鍵詞]第三方物流 運輸決策 運輸方式 運輸路線

隨著社會經濟的進一步發(fā)展和第三方物流企業(yè)的不斷壯大，物流利潤作為第三利潤源泉，已經成為整個供應鏈的利潤“黑洞”。運輸決策是第三方物流管理過程中的關鍵決策問題，進行物流運輸決策優(yōu)化研究，能夠提高物流運輸管理的科學水平。

一、第三方物流運輸優(yōu)化決策的概念

決策作為物流企業(yè)的重要職能，在企業(yè)整個發(fā)展過程中的作用越來越重要。第三方物流運輸優(yōu)化決策，是第三方物流企業(yè)從企業(yè)的戰(zhàn)略目標出發(fā)，運用系統(tǒng)理論和系統(tǒng)工程原理與方法，選擇運輸方式、載運工具、運輸線路，結算運輸費用及相關手續(xù)費，配備運輸人員等，實現運輸路徑短、運輸環(huán)節(jié)少、運輸速度快和費用少地使貨物運至目的地。避免不合理的運輸和次優(yōu)化的情況出現。

二、第三方物流運輸優(yōu)化決策的內容

1.第三方物流運輸方式的選擇決策

（1）第三方物流運輸方式選擇決策的概念

第三方物流運輸方式決策是第三方物流企業(yè)根據所運輸的原材料、半成品以及產成品的性質、規(guī)格、數量等標準，從五種運輸方式的特點和適用條件出發(fā)，運用決策理論建立數學模型，選擇合適的運輸方式的過程。第三方物流企業(yè)通過對運輸方式的決策，選擇最適合的運輸方式，保證貨物安全地、快速地、經濟地運到目的地。

（2）第三方物流運輸方式選擇決策方法

物流運輸系統(tǒng)的目標是實現物品安全、快速和低成本的運輸，即運輸的安全性、速度性、準確性和經濟性，這幾個因素是相互影響、相互制約的。第三方物流運輸方式的選擇需要根據第三方物流企業(yè)運輸環(huán)境、運輸服務的目標要求，采取以定量分析為主，輔以定性分析的的方法進行選擇。單一運輸方式的選擇就是選擇一種運輸方式提供運輸服務，常用的方法是綜合評價法。綜合評價法是在確定運輸方式評價因素的前提下，根據這些評價因素對運輸方式的選擇所起的作用不同，分別賦予其相應的權重，然后對幾種不同的運輸方式進行匯總計算，最終選擇一種運輸方式的方法。

①評價因素的確定

評價運輸方式的因素有運輸方式的安全性、速度性、準確性和經濟性等。

②權重的確定

企業(yè)的環(huán)境不同，貨物的規(guī)格、性質、價格等不同，收貨單位要求的運輸批量和交貨日期也不同，這些特性對運輸方式的選擇的重要程度也因此不同。所以，可以通過給這些評價因素賦予不同的權數加以區(qū)別。設a1、a2、a3、a4分別為安全性、速度性、準確性和經濟性的權重。并使其滿足：

∑ai=1

但值得注意的是，由于決策者的世界觀和價值觀有所區(qū)別，偏好會有所不同，因而給定的權重不同，這樣會影響最終的結果。

③計算運輸方式的綜合評價值

運輸方式的綜合評價值的計算公式為

Fi= a1F1i+ a2F2i+ a3F3i+ a4F4i （i=1…5）

A.安全性的數量化。運輸方式的安全性可以用某段時間內貨物的破損率來表示。破損率越大，則安全性越低； 破損率越小，則安全性越高。假設這五種運輸方式的破損率分別為D1、D2、D3、D4和D5，則平均值D為：

D=（D1+ D2+ D3+ D4+ D5）/5

各種運輸方式的安全性，可用相對值表示如下：

F1i= Di / D （i=1…5）

B.速度性的數量化。運輸方式的速度性主要表現為貨物從發(fā)貨地到收貨地所需要的時間，即貨物的在途時間。所需時間越短，速度越快；反之，所需時間越長，速度越慢。假設這五種運輸方式的所需時間分別為T1、T2、T3、T4和T5，則平均值T為

T=（T1+ T2+ T3+ T4+ T5）/5

各種運輸方式的速度性，可用相對值表示如下：

F2i=Ti/T （i=1…5）

C.準確性的數量化。運輸方式的準確性主要表現為計劃的時間、成本等與實際發(fā)生的時間、成本之間的誤差，誤差率越小，則準確性越高。假設這五種運輸方式的誤差率分別為Q1、Q2、Q3、Q4和Q5，則平均值Q為：

Q=（Q1+ Q2+ Q3+ Q4+ Q5）/5

各種運輸方式的準確性，可用相對值表示如下：

F3i=Qi/Q （i=1…5）

D.經濟性的數量化。經濟性主要用物流費用的多少來表示，相關物流費用主要包括倉儲費、運輸費、裝卸搬運費、包裝費及相關手續(xù)費等。在運輸過程中支出的總費用越少，則經濟性越好。假設這五種運輸方式的誤差率分別為C1、C2、C3、C4和C5，則平均值C為：

C=（C1+C2+ C3+ C4+ C5）/5

各種運輸方式的準確性，可用相對值表示如下：

F4i=Ci/C （i=1…5）

求出綜合評價值之后，從定量分析的原則來看，選擇數值最大者。

即：max F=max（F1、F2、F3、F4、F5）

多式聯運的選擇就是選擇兩種或兩種以上的運輸方式聯合起來提供運輸服務。在實際運輸中一般鐵路與公路聯運、公路或鐵路與水路聯運、航空與公路聯運應用較為廣泛。

2.載運工具的選擇決策

（1）載運工具選擇決策的影響因素

盡管現在交通發(fā)達可供選擇的載運工具較多但對于具體時間、地點條件下的運輸不是所有承運人都能很容易地獲得所需要的運輸工具的。對于運輸工具的選擇，不僅要考慮運輸費用還要考慮倉儲因此要綜合考慮進行選擇。

另外，運輸工具的選擇還要考慮不同運輸方式的營運特性，包括速度可得性、可靠性、能力、頻率等。相對來說汽車運輸雖費用低，但運量小能力不如火車和輪船而火車、輪船雖運量大費用也比較低但急需時卻不如汽車那么容易獲得。

（2）載運工具選擇決策的方法

運輸成本比較決策法，實際上是運載工具決策的量化分析方法。不同的載運工具產生不同的運輸成本。因此最佳的運輸服務方案是既能滿足客戶的需要又能使總成本最低。

3.第三方物流運輸線路選擇決策

（1）概念

第三方物流運輸線路的決策是指第三方物流企業(yè)從本企業(yè)的實際出發(fā)，利用運籌學的相關理論和方法對物品從供應地到需求地運輸過程中所有的運輸線路，選擇最優(yōu)的運輸路線的過程。第三方物流運輸線路決策可以實現整個運輸方案選擇和優(yōu)化的合理化，將貨物以最短路線、最快速度和最小費用從供應地運往需求地，快速滿足不同顧客的要求，提高客戶滿意度的同時實現整個供應鏈的效益最大化。

（2）第三方物流運輸線路的選擇優(yōu)化

①起訖點不同的運輸線路選擇優(yōu)化

從單一的起點到終點，有很多條線路可以選擇，然而，運輸線路選擇優(yōu)化的任務就是要找出使總路程的長度最短的線路。這就是運輸規(guī)劃中的最短線路問題，通常稱為最短路徑法，或者稱最短路線方法。即是列出最短運輸線路計算表，分步驟地計算。通過比較，選擇走近路。

最短路徑法可以利用計算機進行求解。把運輸網絡中的線路（有的稱為鏈）和節(jié)點的資料都存入數據庫中，選好起點和終點后，計算機可以很快就算出最短路徑。

②起訖點相同的運輸線路選擇優(yōu)化

起點與終點為同一地點（起迄點重合）的物流運輸線路的選擇優(yōu)化，目標是尋求訪問各點的次序，以求運行時間或距離最小化。這一類問題沒有固定的解題思路，在實踐中通常是根據實際情況的不同，結合歷史經驗尋找比較適合當前情況的方法。歷史經驗總結如下：應盡量使車輛運行路線形成淚滴狀。一般情況下，當運行路線之間不發(fā)生交叉式時，車輛運行線路的安排是合理的。

③多個起訖點直達的運輸線路選擇優(yōu)化

在有多個供應地向多個收貨地供應貨物或提供物流服務時，物流運輸線路選擇優(yōu)化的任務是要為各收貨地指定能夠安全、快速、低成本為其服務的供貨地，同時要實現整個供貨地和收貨地系統(tǒng)的最優(yōu)。

圖上作業(yè)法包括運輸線路不成圈的圖上作業(yè)法和運輸線路成圈的圖上作業(yè)法。運輸線路不成圈的圖上作業(yè)法較簡單。就是從各端點開始，按“各站供需就近調撥”的原則進行調配。成圈的線路流向圖要同時達到既無對流現象，又無迂回現象的要求才是最優(yōu)流向圖，所對應的方案為最優(yōu)運輸方案。

三、結論

在我國，現有的第三方物流企業(yè)對運輸的重視程度各不相同，但通過運輸優(yōu)化決策降低物流成本，為客戶提供快速、方便和安全的配送服務的目標是一致的。本文所提供的運輸優(yōu)化決策的內容及方法，應該能為第三方物流企業(yè)物流系統(tǒng)的運輸決策提供實際操作上的參考。

參考文獻：

[1]俞明南，劉申，李陽.物流管理中的運輸決策[J].遼寧師范大學學報.2005（1）

[2]胡松評.運輸方式選擇的決策模型[J]. 物流科技. 2002（02）

第6篇：運籌學最短路徑范文

P鍵詞：最短路徑；優(yōu)先權；多初始解；禁忌搜索

中圖分類號：F250 文獻標識碼：A

Abstract： The traditional tabu search algorithm has a strong dependence on the initial solution， and often determines the candidate solution number and the tabu table length according to the experience， which has a great influence on the efficiency of the algorithm. In this paper， TSP problem solving is used to improve the traditional tabu search algorithm by using multiple initial solutions， priority coding， random number of candidate solutions and variable tabu length. At the same time， the convergence rate of the algorithm.

Key words： shortest path； priority； multiple initial solutions； tabu search

在運籌學中，旅行商問題（Traveling Salesman Problem， TSP）是經典的組合優(yōu)化問題，已被證明具有NP計算復雜性，求解多采用近似算法和啟發(fā)式算法。禁忌搜索是模仿人類記憶功能的一種方法，通過禁忌表封鎖剛搜索過的區(qū)域來避免迂回搜索，同時，在特殊情況下，對禁忌區(qū)域中的一些優(yōu)良狀態(tài)進行特赦，保證搜索的多樣性，達到全局最優(yōu)[1]。傳統(tǒng)禁忌搜索算法對初始解具有很強的依賴性，初始解的好壞直接影響著禁忌搜索算法的效率[2]。本文采用多初始解、優(yōu)先權編碼、候選解個數隨機化及可變禁忌長度的方法，旨在提升算法效率。

1 禁忌搜索算法的改進

1.1 基于優(yōu)先權的編碼和解碼

（1）優(yōu)先權編碼

對于具有n個頂點的網絡圖，首先對頂點進行編號，確定頂點集合V ，V ，V ，…，V ，再由隨機函數產生一個在1～n上服從均勻分布的由n個互不相同的正整數所組成的序列作為頂點優(yōu)先權PV ，PV ，…，PV ，該優(yōu)先權序列就構成了本次搜索路徑所參照的標準。在后續(xù)操作中，只需對換頂點對應的優(yōu)先權值，便可得到新的優(yōu)先權序列，確定出新的路徑。

（2）解碼

本文依據優(yōu)先權越大越優(yōu)先的原則確定路徑，具體操作如下：

給定一個網絡GV，E，其中V=V ，V ，…，V 表示頂點集，E表示邊集，假設N V表示所有到達頂點V的點的集合，N V表示所有從頂點V出發(fā)的點的集合，從原點s開始，找到N V中優(yōu)先權最大且不在已知路徑結點集合中的結點V 作為搜索結點的下一個結點，令V 為V，繼續(xù)上述操作，直到V 到達匯點d為止。以此確定新的路徑，并求得新路徑長度。

1.2 初始解的確定

本文采用多初始解的方式，在算法開始的短期迭代內，對多個初始解進行搜索，并分階段對當前最優(yōu)解評價和篩選，最終得到一個相對較優(yōu)的初始解，具體操作如下：

Step1：假設隨機產生了6個初始解，記為X ，i=1，2，…，6，分別進行禁忌搜索，每個解迭代25次，得當前最優(yōu)解為X ，i=1，2，…，6。轉Step2。

Step2：對X ，i=1，2，…，6進行比較和篩選，選出較優(yōu)的3個解，假設為X ，i=1，3，5，對這3個解分別迭代50次，得當前最優(yōu)解為X ，i=1，3，5。轉Step3。

Step3：對X ，i=1，3，5進行比較和篩選，確定最優(yōu)解，假設為X ，則以X 為初始解繼續(xù)迭代。

1.3 候選解的選擇

候選解個數對搜索效率影響較大。候選解數量過少，當前最優(yōu)解更新的幾率就很低，會過早的陷入局部最優(yōu)。候選解數量過多，計算內存和計算時間也跟著增加，不利于算法的快速實現[3]。尤其在頂點數目龐大時，過多的候選解會嚴重影響運算速度。

傳統(tǒng)的禁忌搜索算法將候選解個數確定為一個固定值，很難保證其合理性。為了提升算法效果，在產生候選解時，本文采用以下方式：

（1）在每次迭代時，隨機選擇d個頂點，放在d個位置上，依次將頂點對應的優(yōu)先權與后續(xù)位置上頂點對應的優(yōu)先權對換，產生新的路徑，并記錄對換頂點的下標和新路徑的長度，構成候選解集。

（2）為了保證候選解的多樣性，在大規(guī)模TSP問題中還應做如下規(guī)定：假設在第t次迭代時隨機選擇的頂點集合為A，在第t+1次迭代時隨機選擇的頂點集合為B，必須保證B中所含A的元素不得超過A所有元素的50%，否則重新選擇B中元素。這樣可以擴大頂點選擇的范圍，有效降低相鄰迭代中頂點重復選擇的概率，提升候選解的多樣性。

第7篇：運籌學最短路徑范文

【關鍵詞】卷積碼；編碼；解碼

引言

現代通訊技術正以其前所未有的速度發(fā)展著，信息傳輸對于信道的要求越來越高。為了實現通信的可靠性，就需要對于惡劣的信道狀況進行控制。增加發(fā)送信號功率的做法在實際中經常要受到條件的限制，而采用編程的方法則可以有效的對信道的差錯進行控制，因而，在實際中編程控制差錯的途徑有著廣泛的應用。

1、卷積碼定義

介紹卷積碼之前先談談分組碼。以串形式進行傳輸信號時，一般選擇分組碼。分組碼是將k個信息比特編成n個比特，而通常情況下k和n是很小的，這就可以讓以串形式傳輸信號的時候的時延很小。分組碼先將信息序列分組，然后再單獨對其進行編碼。約束長度為N，碼元數還是n時，卷積碼是與分組碼不同的，卷積碼編碼后的這些碼元與好多段的信息都是有聯系的，與其聯系的段數可以推前至N-1段。所以一共有nN個碼元是互相關聯的。

2、卷積碼與分組碼區(qū)別和聯系

2.1約束關系

卷積碼（n，k，m）在編碼的時候有一個復雜度，且它的碼元與前碼元和后碼元是成約束關系的。在連續(xù)m個碼流內，卷積碼的距離特性可以用最小距離來表明，并且此碼具有糾錯的功能。

2.2分組碼和卷積碼的性能

一般情況下，n和k都是比較小的，卷積碼各組間又具有相關性，同時，編碼約束長度和利用的譯碼方式都能夠影響卷積碼的糾錯能力。所以，理論上在碼率相同的情況下卷積碼的性能是優(yōu)于分組碼的；而實際上，使用中的設備又具有復雜性，實踐也證明了分組碼的性能是不如卷積碼的。

3、編碼理論

3.1定義

編碼是指為了達到某種目的而對信號進行的一種變換。其逆變換稱為譯碼或解碼。編碼理論是數學和計算機科學的一個分支，與信息論、概率論、數理統(tǒng)計、隨機過程、線性代數、近世代數、數論、有限幾何以及組合分析等學科有密切關系。是一種研究信息傳輸過程中信號編碼規(guī)律的數學理論。編碼能夠處理在噪聲信道傳送資料時的錯誤傾向。

3.2歷史背景

在電報通信中有一種應用很廣泛的莫爾斯碼，是美國人S.F.B.莫爾斯在1843年設計出來的。據后來證明，這種莫爾斯碼與理論上可達到的極限只差百分之十五。而編碼理論的形成是在二十世紀三十年代。后來采樣定理的提出才為連續(xù)信號的離散化奠定基礎。1948年C.E.香農提出了信息熵的概念，這又為信源編碼奠定了基礎。第二年香農又提出了信道容量的概念，這又為信道編碼奠定了基礎。香農第一定理指出，碼字的平均長度只能大于或等于信源的熵。香農第二定理指出只要信息傳輸速率小于信道容量，就存在一類編碼，使信息傳輸的錯誤概率可以任意小。1951年，香農指出，在信源的輸出有多余的消息時可以通過編碼來改變信源的輸出，從而信息傳輸的速率能夠與信道容量接近。在今天仍有很廣應用的卷積碼出現在1955年。在1957年引入了構造簡單的循環(huán)碼數。1959年出現的能夠糾正突發(fā)錯誤現象的費爾碼和哈格伯爾格碼。同年，BCH碼得到發(fā)表。已用于空間通信的序貫譯碼提出于1965年。維特比譯碼和矢量編碼法先后提出于1967年和1978年。1980年多進制的BCH碼是用數論方法實現的。這種糾錯編碼技術已在衛(wèi)星通信中得到了廣泛的應用。

4、解（譯）碼方式

4.1代數譯碼

代數譯碼是將卷積碼的一個編碼約束長度的碼段看作是[n0（m+1），k0（m+1）]線性分組碼，每次根據（m+1）分支長接收數字，對相應的最早的那個分支上的信息數字進行估計，然后向前推進一個分支。若信息序列＝（10111），相應的碼序列c＝（11100001100111）。若接收序列R＝（10100001110111），先根據R的前三個分支（101000）和碼樹中前三個分支長的所有可能的　8條路徑（000000…）、（000011…）、（001110…）、（001101…）、（111011…）、（111000…）、（110101…）和（110110…）進行比較，可知（111001）與接收序列（101000）的距離最小，從而判定第0分支的信息數字為0。然后以R的第1～3分支數字（100001）按同樣方法判決，依此類推下去，最后得到信息序列的估值為=（10111），即實現了糾錯。譯碼時采用的接收數字長度為（m+1）n0，所以能糾正的錯誤長度小于（dmin-1）/2。而在實際應用中采用較多的實現方法還是反饋擇多邏輯譯碼法。

4.2維特比譯碼過程

維特比譯碼器有著極其復雜的結構。它的復雜性隨著m呈指數增大的形式而越來越復雜。在實際應用中，m的值不會超過10。他在解決數據壓縮和碼間串擾中有著用途。而它最廣泛的用途是在深空通信和衛(wèi)星上面。

將運籌學中的求最短路徑的思維應用到在碼的格圖上找最小接收序列距離上面，就可以得到一種算法，叫維特比譯碼。

假設譯碼器從狀態(tài)ɑ出發(fā)，且每次向右延伸一個分支，對于l＜L，從每個節(jié)點出發(fā)都有2=2種可能的延伸，其中L是信息序列段數，對l≥L，只有一種可能。接收序列為R=（1010001010110），將此分支與相應的接收數字分支比較，可以得出它們間的距離，再把算出的距離加到被延伸路徑的累積距離上。在有不多于兩條路徑的距離累積值比較后，取距離最小的那一條。當有兩條以上取最小值時，可以任取其中的一條。這個最小的一條路徑，稱為幸存路徑。

4.3序貫譯碼

序貫譯碼是根據接收序列和編碼規(guī)則，在整個碼樹中搜索（既可以前進，也可以后退）出一條與接收序列距離（或其他量度）最小的一種算法。由于它的譯碼器的復雜性隨m值增大而線性增長，在實用中可以選用較大的m值（如20～40）以保證更高的可靠性。許多深空和海事通信系統(tǒng)都采用序貫譯碼。

5、結論

卷積碼是一種糾錯編碼，糾錯編碼已經有五十多年的歷史，早在1948年，Shannon在他的開創(chuàng)性論文“通信的數學理論”中，第一次闡明了在有擾信道中實現可靠通信的方法，提出了著名的有擾信道編碼定理，奠定了糾錯碼的基石，使糾錯碼無論在理論上還是在實際中都得到了飛速發(fā)展?，F代通信中，隨著信號序列的傳輸速率的不斷提高，要求卷積碼編解碼的速度也要不斷提高，Viterbi譯碼由于充分利用信號序列統(tǒng)計概率的特性而具有最佳性能。

參考文獻

[1]張宏基等.信源編碼[M].北京：人民郵電出版社，1980年：53-56.

第8篇：運籌學最短路徑范文

摘要：建立規(guī)劃項目方法論體系，能幫助規(guī)劃人員理清規(guī)劃思路，考慮宏觀布局設計、基本戰(zhàn)略定位、組織網絡架構和營運策略設計等幾個不同的方面，目的是達到規(guī)劃項目有據可查、有理可尋。該體系特色為將數學模型、優(yōu)化算法、規(guī)劃方法、指標評價方法等與實際規(guī)劃項目相結合，從科學與客觀條件、人為因素相結合，繼而使規(guī)劃成果更具有合理性及可實施性。

關鍵詞：規(guī)劃項目方法論優(yōu)化算法

項目的規(guī)劃工作一般可以分為五個階段，依次分別是規(guī)劃籌備階段、需求分析階段、戰(zhàn)略定位階段、規(guī)劃設計階段、規(guī)劃評價階段。

一、項目規(guī)劃前期籌備階段

1.規(guī)劃籌備階段是項目規(guī)劃的起點，主要為規(guī)劃做好準備工作。該階段主要包括背景調查和相關資料的收集、整理和初步分析。

背景調查與需求調研是通過與要規(guī)劃部門網絡調研、實地調研（走訪、座談）、電話調研、發(fā)放調研表等形式，明確規(guī)劃的目的和要實現的目標，劃定園區(qū)用地的邊界、確定調研范圍和對象、規(guī)劃的時間、成果形式等。

2、資料初步分析

通過收集背景調查中調研表格和整理訪談筆記等形式，對收集到的地區(qū)或行業(yè)總量數據（生產總量、消費總量、GDP等）進行整理形成調研報告，對園區(qū)的規(guī)劃定位提出初步建議，確定大略方向。規(guī)劃籌備階段形成的主要成果文檔內容如下：規(guī)劃背景（政策背景、基礎設施規(guī)劃背景、產業(yè)背景）、規(guī)劃意義、規(guī)劃依據、規(guī)劃原則、規(guī)劃范圍、規(guī)劃步驟及調研總結（調研階段、調研方法、調研總結）。國內項目發(fā)展現狀及規(guī)劃、某某省項目、相關輻射地區(qū)/企業(yè)項目。

二、項目規(guī)劃需求分析階段

為了深入了解區(qū)域項目周邊地區(qū)的經濟發(fā)展狀況、市場需求、基礎設施、服務競爭等情況，必須對項目輻射地區(qū)的宏觀經濟、產業(yè)和微觀環(huán)境情況進行全面調查和研究，根據長遠和近期的需求量，確定項目長遠和近期的建設規(guī)模。主要包括了：（1）需求量預測。用以下三種預測方法分別對貨運量進行預測二次多項式回歸預測、直線回歸預測、灰度預測法等。（2）周邊城市現狀分析及需求量預測。（3）周邊城市處理能力等。

三、項目規(guī)劃戰(zhàn)略定位階段

在完成詳實的定性和定量市場分析和研究之后，規(guī)劃者必須對項目整體優(yōu)勢、劣勢、機會、威脅進行分析(即SWOT分析)，如果某類服務，例如空港、海港、公路貨運站場，在整個園區(qū)中占有較大比例，還必須進行專項的SWOT分析。這些分析主要作用是幫助園區(qū)的高層經營決策者明晰內外部環(huán)境，提出發(fā)展項目的使命、遠景目標和制勝策略，從而進行準確的戰(zhàn)略定位，幫助實現其戰(zhàn)略目標。這里的制勝策略，是指擊敗現有及潛在競爭者的計劃，包括一系列舉措以提高物流服務的水平，項目戰(zhàn)略選擇的“價值方案”及其實施步驟。這些策略應該嚴格限制在內部使用。

四、項目規(guī)劃設計階段

項目的規(guī)劃設計階段就是對項目進行具體的設計，主要包括基礎設施平臺、信息平臺和運營平臺三大平臺的規(guī)劃和設計。

1、基礎設施平臺的規(guī)劃設計

（1）項目用地規(guī)劃

園區(qū)用地規(guī)劃主要是對項目建設規(guī)模的大小進行確定，園區(qū)建設規(guī)模太小，會限制區(qū)域潛在需求，不利于園區(qū)的持續(xù)發(fā)展。園區(qū)規(guī)模太大，則可能造成投資浪費和資源閑置的現象。運用專門的統(tǒng)計分析軟件（SPSS、EXCEL等）、REA模型等定量分析方法和定性分析方法（SCP模型）相結合，綜合考慮實際情況，得出項目現實和潛在的需求量，進一步得出各布局的用地面積。

（2）功能設計

項目的功能設計主要圍繞園區(qū)的戰(zhàn)略定位，采自頂向下的方法，即在確定項目的規(guī)劃原則以后，對功能規(guī)劃所涉及的核心功能進行列舉和分析，然后通過收集整理一系列國際最先進的項目案例，總結出對要規(guī)劃項目最適合的經驗。隨后，整個項目將被劃分為幾個大功能區(qū)域。

（3）布局設計

項目的設施規(guī)劃與布局設計是指根據項目的戰(zhàn)略定位、經營目標和功能設計，在已確認的空間場所內，按照貨物的進入、組裝、加工等核心流程和主要業(yè)務環(huán)節(jié)，將人員、設備和物料所需要的空間進行最適當的分配和最有效的組合，按照一定的原則和方法設計出合理的技術路線，達到一定的目標（作業(yè)流程最短、運輸路程最短、費用最小等），以獲得最大的經濟效益。

對項目中的各建筑設施的選址和規(guī)劃應采用科學的定量方法，如：運籌學中的一些最優(yōu)選址方法、最短路徑法、最小費用最大流法、有效的物料進出表法、搬運系統(tǒng)分析法、模糊理論中的模糊綜合評價法、最優(yōu)決策方法、SLP-Systematic Layout Planning方法等，項目規(guī)劃與設施布局的合理性還可以通過建模仿真來進行檢驗優(yōu)化。

2、信息平臺的規(guī)劃設計

信息平臺規(guī)劃分為整體規(guī)劃和詳細規(guī)劃設計。具體規(guī)劃內容包括：園區(qū)整體信息平臺的基本概念、廣義整體規(guī)劃定位、設計和狹義整體規(guī)劃設計。園區(qū)詳細規(guī)劃設計包括：項目信息平臺的框架結構、層次結構和信息流程設計。

3、運營平臺的規(guī)劃設計

（1）項目的投資開發(fā)模式

根據國內外與項目功能相同或相當的基礎設施開發(fā)建設的經驗，在分析我國現有的項目發(fā)展模式的基礎上，我國經濟中心城市項目在發(fā)展模式上可能的選擇有4種，即經濟開發(fā)區(qū)模式、主體企業(yè)引導模式、地產商模式和綜合運作模式。

（2）項目的管理模式。項目管理模式的選擇應該根據相應的投資開發(fā)模式而定。通過上述對項目投資開發(fā)模式的分析，其相應的管理模式可以有5種類型，即管理委員會制、股份公司制、業(yè)主委員會制、協(xié)會制和房東制。

第9篇：運籌學最短路徑范文

關鍵詞：物流成本；優(yōu)化；模型

中圖分類號：F713

文獻標志碼：A 文章編號：1673-291X（2012）17-0144-02

物流成本指產品的空間移動或時間占有中所耗費的各種活勞動和物化勞動的貨幣表現，是產品在實體流動過程中所支出的人力、物力、財力的總和。作為考證物流在國家經濟中價值量化的主要研究指標，物流成本占GDP比重已成為衡量一個國家物流業(yè)發(fā)展水平的重要指標。2011年，我國社會物流總費用8.4萬億元，與GDP比率為17.8%，與美國等發(fā)達國家相比要高出8—10個百分點，社會經濟運行的物流成本仍然較高。隨著企業(yè)內部制造成本管理方法的日漸完善與成熟，通過提高勞動生產率和節(jié)約企業(yè)內部資源來增加利潤空間正逐步減少，改善企業(yè)內部物流來增加利潤成為當今企業(yè)管理的熱點和重點，應用物流成本優(yōu)化模型是控制和降低企業(yè)物流成本的一種有效方式[1]。

一、基于財務核算的物流成本優(yōu)化模型分析

物流成本傳統(tǒng)核算方法是在現有會計報表成本資料的基礎上，按照一定的原則和方法，從傳統(tǒng)成本會計的各項費用中剝離出物流費用。傳統(tǒng)法局限于現有會計資料，并且人為因素較多，從而難以準確歸集和分配物流成本，因此，需要對物流成本的財務核算進行建模優(yōu)化。

（一）財務核算優(yōu)化模型概述

1.任務成本法

任務成本概念是在“物流任務方法”基礎上提出的，它改變了傳統(tǒng)的物流總成本計算法沒有考慮物流系統(tǒng)各環(huán)節(jié)具體運作過程以及橫向的以部門為單位的成本結構，代之以縱向的以功能為單位的成本結構。任務成本方法認為，物流各子系統(tǒng)間相互作用并提供不同水平的客戶服務，該方法既能從總成本角度來強調物流系統(tǒng)內各個子系統(tǒng)之間的相關性，又能從系統(tǒng)的角度來提供對不同客戶服務的成本信息。但該方法核算過程繁雜，在分配某項作業(yè)成本時往往存在人為因素，導致結果不準確，特別是公共作業(yè)領域成本分配沒有客觀標準[2]。

2.作業(yè)成本法

作業(yè)成本法是以作業(yè)或活動為基礎，將企業(yè)消耗的資源按資源動因分配到作業(yè)或活動中，再把收集的作業(yè)成本按作業(yè)動因分配到成本對象中的核算方法，其基本邏輯是：各種資源耗費驅動成本的發(fā)生，使各種產品成本多少應取決于對各種活動的消耗量，并以此來核算成本具有更大的準確性。作業(yè)成本法是應用最為廣泛的物流成本財務核算優(yōu)化模型。

作業(yè)成本法不僅可以更全面的核算物流成本，也為企業(yè)考核物流項作業(yè)活動成本提供績效考評的依據。它可以分析針對每一種（類）產品在物流各個作業(yè)環(huán)節(jié)上的花費，尋找成本挖潛對象和目標；可以對未來物流成本進行預測，制定針對性的成本控制計劃和長期的物流成本戰(zhàn)略，及時掌控成本變化信息，利于形成動態(tài)的成本管控體系。

3.M—A模型法（Mission Cost—ABC）

任務成本法和作業(yè)成本法的邏輯思路是一致的，都是以過程為導向，用成本來追溯特定的活動或任務成本。M—A模型法將任務成本法與作業(yè)成本法結合在一起進行物流成本核算，構建物流成本核算的M—A模型，界定了物流成本的涵蓋范圍，明確了物流成本數據的信息來源，描述了M—A模型的理論框架。該方法把物流成本的測算過程分為兩個階段：根據任務成本法確定成本目標，再由作業(yè)成本法分析物流活動及相關資源，并對企業(yè)物流活動中各個成本要素向各個環(huán)節(jié)的分配途徑作了清晰、直觀的描述。

（二）財務核算優(yōu)化模型比較分析

上述三種物流成本核算的優(yōu)化模型各有利弊，在實際運用中要根據企業(yè)具體情況進行選擇。三種模型的優(yōu)缺點和適用范圍見表1。

二、基于成本控制的物流成本優(yōu)化模型分析

物流成本控制建模具有很強的實用性與針對性，可以對管理方面提供依據，可以用于企業(yè)高層分析財務信息以制定相應的物流政策。成本控制建模多用運籌學的方法，主要有排隊網絡法、極大代數法、Petri網法等形式化建模技術以及活動循環(huán)圖、流程圖、面向對象的建模技術等非形式化建模技術。

（一）成本控制優(yōu)化模型概述

從具有可操作性的物流成本控制模型研究來分析，可將現有的成本控制優(yōu)化模型分為兩大類，分別是針對具體物流作業(yè)的和全局式規(guī)劃的優(yōu)化模型。

1.針對具體物流作業(yè)的成本優(yōu)化模型

首先是庫存問題?，F有研究中，主要是對各種庫存模型討論，大多集中在生產/庫存系統(tǒng)和庫存/分配系統(tǒng)。經濟批量（EOQ）模型是最早應用較為廣泛的庫存模型理論，此后很多學者從不同角度出發(fā)，應用不同理論方法對庫存管理進行了廣泛研究，并提出了一系列經典模型，例如，經濟生產批量模型、允許缺貨的經濟訂購批量模型、經濟訂購批量折扣模型、需求為隨機變量的訂貨模型、物料需求計劃和準時化生產方法等等[3]。

其次是運輸及配送中的物流成本優(yōu)化模型。在企業(yè)物流層面，對運輸成本的研究通常與采購、庫存和網點建設等活動相聯系。即運輸成本體現出某種一體化特性，目前物流運輸成本優(yōu)化模型則多是利用線性和非線性的運籌學理論，如最短路徑法、最小費用流法等進行建模計算，以實現運輸總成本最小。

2．全局化物流成本優(yōu)化模型

第一類是供應商選擇物流成本模型。關于供應商選擇的物流成本模型涉及面較廣，混合型整數非線性規(guī)劃模型，將實際價格、庫存、運輸成本納入物流總成本的考慮范圍，此外，采購預算限制、質量、服務等因素也被包括到該模型之中[4]。

第二類是物流網絡／布局策略中的物流成本。國外學者對物流布局／區(qū)位問題的研究，最早開始于貨物運輸網絡設計和設施選址領域，以后加入了整體網絡規(guī)劃。其中，公共物流終端模型利用排隊理論和非線性規(guī)劃開發(fā)了用于確定最優(yōu)規(guī)模和最佳布局的數學模型。該模型考慮了運輸成本和設施成本之間的交替作用，以實現成本最小化；該模型在日本得到實際運用。最近的研究是應用博弈論討論區(qū)域物流網絡。

第三類是逆向物流成本優(yōu)化模型。因為逆向物流幾乎包括了所有的物流活動，所以對其的研究包括了配送規(guī)劃、庫存控制、生產規(guī)劃等領域。1992年，Pohlen和Farris就提出可以利用個別渠道成員的既有功能與能力執(zhí)行回收和再制造任務[5]。

（二）成本控制模型比較分析

根據上述物流成本控制優(yōu)化模型的介紹和使用情況，從兩方面分析其優(yōu)缺點并據此劃分適用范圍，如表2所示。

三、物流成本優(yōu)化模型分析小結

財務核算優(yōu)化模型的產生很大程度解決了原有會計制度對物流成本核算的片面性，幫助企業(yè)更加全面完整的了解內部物流成本的總額和分布情況，為物流成本控制提供了基礎?；谪攧蘸怂愕某杀緝?yōu)化模型開始是針對作業(yè)環(huán)節(jié)進行建模優(yōu)化以核算物流作業(yè)成本，后來發(fā)展到從產品甚至供應鏈的角度進行成本核算。成本控制優(yōu)化模型則是在較為全面的物流成本會計資料的基礎上運用運籌、數理分析等方法對物流流程包括庫存、運輸等物流項目進行優(yōu)化，以達到最優(yōu)物流成本?；诔杀究刂频膬?yōu)化模型是從開始優(yōu)化某一具體環(huán)節(jié)到將整個物流流程都納入模型中以求得整體最優(yōu)解。

在實際操作中雖然能取得整體最優(yōu)是企業(yè)運營的最理想狀態(tài)，但是并不代表所有企業(yè)都應選擇最全面先進的優(yōu)化模型。

首先，有些企業(yè)雖然沒有建立專門的物流成本會計科目，但是因為企業(yè)費用發(fā)生明確具體，可以很容易地進行歸集和分配，并不需要再去建模優(yōu)化核算流程。有些企業(yè)的物流流程較為簡單，并不包括所有物流活動，或者產品服務較為單一，使用有針對性的優(yōu)化模型其實也可以達到很好的效果。如專門進行倉儲或者運輸的企業(yè)只要根據企業(yè)情況有針對性，建模，就完全可以達到減少物流成本的目的。

其次，在企業(yè)構建一個從核算到成本控制的整體物流優(yōu)化模型，需要專門的技術軟件和設備，這是一筆不小的開支，并不是所有企業(yè)都能承擔。而且整體最優(yōu)模型考慮因素龐雜繁多，當企業(yè)在使用時需要添加海量的變量和限制條件，只要有一個參數設置錯誤結果都會與最優(yōu)解相距甚遠，而且每當企業(yè)環(huán)境有變化都需要從新調整模型，這需要使用此類模型的企業(yè)有雄厚的技術、資金支持，在企業(yè)內要設有專門的技術部門，這也增加了企業(yè)管理開支。

最后，只有不同部門間合作協(xié)調，信息暢通的企業(yè)才能發(fā)揮整體優(yōu)化模型的最佳效果。如果企業(yè)部門信息不能及時反饋到優(yōu)化模型，那么得出的最優(yōu)解結果也沒有實際操作的意義。所以，要構建整體優(yōu)化模型的企業(yè)首先要對企業(yè)流程進行優(yōu)化重組。

綜上，物流成本優(yōu)化模型的選擇最重要的是要符合企業(yè)現實情況，而不是一味選擇最先進，最全面的模型。本文通過對物流成本優(yōu)化模型的介紹分析，使企業(yè)可以對各個模型的適用范圍有所了解，便于企業(yè)選擇最為合適的優(yōu)化模型。

參考文獻：

[1] 2011年中國社會物流統(tǒng)計數據xxw3441.blog.省略/blog/static/75383624201211791620468/

[2] 何偉.生產企業(yè)物流成本控制[J].鐵路采購與物流，2010，（11）.

[3] 耿邯利.企業(yè)成本會計核算優(yōu)化[J]．現代商業(yè)，2008，（6）.

[4] 張人千，魏法杰，等.基于成本的車間作業(yè)優(yōu)化模型及實證研究[J].中國管理科學，2002，（5）.

[5] 黃湘民，劉大成，周陽方.國外物流成本研究前沿及進展[J].商業(yè)研究，2008，（23）.[責任編輯　王　佳]

收稿日期：2012-04-13