啟發式伏格爾法求解多階段決策問題

孫鵬飛，劉建永

(解放軍理工大學 野戰工程學院，南京　210007)

?

啟發式伏格爾法求解多階段決策問題

孫鵬飛，劉建永

(解放軍理工大學 野戰工程學院，南京210007)

摘要：針對動態規劃求解多階段決策問題存在的一些不足，首次創新性地將啟發式伏格爾法運用到求解多階段決策問題中，給出相關定義，列出其算法步驟，并分析其時間復雜度；通過案例具體說明啟發式伏格爾法求解過程，總結該算法優缺點，為研究多階段決策問題提供一種新型并且具有實效的思路方法。

關鍵詞：啟發式伏格爾法；時間復雜度；多階段決策問題

Citation format:SUN Peng-fei，LIU Jian-yong.Heuristic Vogel Method for Solving Multistage Decision-Making Problems [J].Journal of Ordnance Equipment Engineering,2016(3):171-174.

求解多階段決策問題(Multistage Decision-Making Problems)，最常用的求解方法是動態規劃(Dynamic Programming)方法[1-2]。實踐也證明了求解此類問題用動態規劃方法比線性規劃方法或非線性規劃方法更加有效[3-4]。但利用動態規劃求解多階段決策問題，存在著一些條件限制，算法復雜度也較大，并且只適用維數相對較低的問題[5-6]。現實中，在考慮決策靈活機動和方案最優時，并不一定要嚴格采用最優方案，有時決策容易、易于改動的次優方案可能更適合現實需求。本文中考慮是否有較好的啟發式算法(Heuristic Algorithm)[7]，在解決此類問題時更加地靈活機動、易于操作。

查閱國內外文獻資料[8-10]，伏格爾法(Vogel)主要應用于求解運輸問題和指派問題，目前還未有關于伏格爾法在求解多階段決策問題方面的相關研究。本文探索利用啟發式伏格爾法(Heuristic Vogel Method，HVM)求解多階段決策問題，并分析其時間復雜度。

1基于啟發式伏格爾法求解最短路線問題

1.1啟發式伏格爾法基本概念

伏格爾法主要應用于運輸問題求解最低運費，它是確定運輸問題初始調運方案中近似程度最好的一種近似方法，這種方法得出的結果很接近最優調運方案。伏格爾法在最小元素的基礎上考慮，某一產地的產品若不能按照最小運費就近供應，就考慮次小運費，這就產生一個差額，稱為罰金成本。罰金成本越大，說明不按最小運費調運時，運費增加越多。因而對罰金成本最大元素，就應該采用最小運費調運[1]。

啟發式伏格爾法(HVM)可以定義：在可接受的花費(指計算時間和空間)條件下，給出待解決的組合優化問題一個經驗構造或直觀性伏格爾法求解，該可行解與最優解的偏離程度不一定事先可以預計[7]。

1.2啟發式伏格爾法算法步驟

假設每階段所有的狀態點與隨后階段的狀態點間均有路線，如若沒有路線，可假定其路線長度為∞，過程只有一個始點Os和一個終點Oe。

啟發式伏格爾法求解最短路線問題的算法步驟如下：

第1步，確定過程的始點Os、終點Oe、階段數n、狀態總數N，按始點Os至終點Oe順序，為每個狀態點排序，并確定第i狀態屬于哪個階段以及該狀態的決策數目mi；

第2步，計算各個狀態點的決策集中最小值與次最小值的差ci(如若狀態點只有一種決策，即不存在次最小值，則規定其罰金成本為0；若狀態點沒有決策，則不將其計入集合C中)，形成集合C；

第3步，在集合C中找出最大值，并選擇此狀態點為決策點(如若存在多個最大值，則只選取按照狀態點的排序順序最靠前的依次作為決策點)，選取此狀態點的決策集中的最小值作為此狀態點的決策；

第4步，從此階段及下階段中，除去此次決策的起、始狀態點外的其余狀態點，從集合C中除去此次決策的起、始狀態點，更新集合C；

第5步，重復第2、4步工作，直至集合C不再包含任何狀態點的罰金成本，則所有階段中均有且僅有一個狀態已做出決策，形成最終策略。

1.3啟發式伏格爾法時間復雜度

算法第1步主要判斷過程及狀態，時間復雜度為1。

算法第3步時間復雜度計算包括尋找最大值以及為該狀態點做出決策、形成階段路線兩個方面，時間復雜度：(N-1)+1。

2實例應用

2.1實際案例

某工廠自國外進口一部精密機器，由機器制造廠到出口港有3個港口可供選擇，而進口港又有3個可供選擇，進口后可經由兩個城市到達目的地，其間的運輸成本如圖1中所標數字，求出運費最低的路線。

圖1　路線網絡圖

2.2啟發式伏格爾法求解

根據網絡圖以及啟發式伏格爾法算法步驟，可以確定過程的始點為A，終點為E，共有4個階段，10個狀態點。為10個狀態點依次排序，如對狀態點B1，i=2。

第二步，計算各個狀態點的決策集中最小值與次最小值的差。如對狀態點B1，B1共有3條可選路線，其中最小值為40(路線B1→C2)，次最小值為60(路線B1→C3)，二者之差，即c2=20。求出每個狀態點的最小值與次最小值之差，形成集合C，初始的集合C中一共包括[A、B1、B2、B3、C1、C2、C3、D1、D2]這9個狀態點的罰金成本。如圖2中各狀態點上的括號內數值所示：

圖2　初始集合C

從集合C中找出最大值，B3、C1、C23個狀態點的最大值，均為30。按照本文的算法規則，選擇序號在前的狀態點B3作為決策點，并將狀態點B3的3條可選路線中最短路線B3→C2作為該階段路線，如圖3所示。

圖3　狀態B3作為首選點

圖4　更新后的集合C

圖5　路線C2→D2的選擇

圖6　路線A→B3的選擇

圖7　路線D2→E的選擇

從集合C中除去此次決策的起始狀態點D，更新后的集合C中不再包含任何狀態點的罰金成本，即所有階段均有且僅有一個狀態已做出決策， 完成了此過程路線的確定策略。最后得到路線方案：

A→B3→C2→D2→E

2.3結果分析

啟發式伏格爾法方案的路線運輸成本為110，利用動態規劃方法求解進行驗證(具體求解過程未在本文列出)，110為最優結果。

由此總結出啟發式伏格爾法求解的特點：求解結果清晰明了，圖上標示直觀方便；階段越多或狀態決策數目越多時，越是后面的求解過程中，越能體現出其計算時間優越性。與動態規劃求解多階段決策問題的按順序或反序逐個階段進行決策，最后得出從全局出現的最優決策相比，本方法并不能保證從兩端逐個階段進行，而是選取罰金成本最大值的狀態點開始，而此狀態點可能處于中間某個狀態，所以不能保證每次都能求出最優決策，而且無法直觀驗證其結果是否為最佳方案。

3結論

本文將啟發式伏格爾法思想應用到求解多階段決策問題中，方法簡便，理論可靠，而且結果清晰明了，研究前景開闊，在實際運用中取得了良好效果。本文實例比較簡單，在實際中有可能存在多個始、終點的情況，或是狀態不滿足無后效性的情況，在這些特殊情況下，本算法可能會得到很壞的答案或效率極差，這就違背了算法初衷。

本文下一步工作將在兩方面展開深入研究，一是對該算法求解的實效性以及算法復雜度進行研究，改善優化算法；二是完善規范算法步驟，實現算法計算機編程，使其達到在較為復雜的情況下，也能滿足在計算機運行的準確性和穩定性。

參考文獻：

[1]錢頌迪.運籌學[M].3版.北京：清華大學出版社，2005.

[2]BELLMAN R E,DREYFUS S E.Applied Dynamic Programming[M].Princeton University Press,1962.

[3]SVEN D.Nonlinear and Dynamic Programming[M].Springer-Verlag,1975.

[4]KUMAR P,SINGH N,TEWARI N K.A nonlinear goal programming model for multistage,multiobjective decision problems with application to grouping and loading problem in a flexible manufacturing system[J].European Journal of Operational Research,1991,53(2):166-171.

[5]YANG MAO,LI YONG,SU LI.Opportunistic spectrum sharing in software defined wireless network[J].Journal of Systems Engineering and Electronics,2014,25(6):934-941.

[6]LI YONG-YAN,GAO WEN,WU CHUNMING.Deployment of Sensors in WSN:An Efficient Approach Based on Dynamic Programming[J].Chinese Journal of Electronics,2015,24(1):33-37.

[7]EDWARD A，SILVER,VICTOR R.A tutorial on heuristic methods[J].European Journal of Operational Research,1980(5):153-162.

[8] 汪潘義.改進的伏格爾法及其應用[J].統計與決策,2014(15):83-85.

[9]牛斌,趙龍.基于Vogel的車輛調用優化算法研究[J].計算機與現代化,2011(5):7-10.

[10]張敏,張子杰.伏格爾法在退化性運輸問題中的應用方法[J].河北工程技術高等專科學校學報,2009,12(4):21-23.

(責任編輯唐定國)

Heuristic Vogel Method for Solving Multistage Decision-Making Problems

SUN Peng-fei，LIU Jian-yong

(College of Field Engineering, PLA University of Science and Technology, Nanjing 210007, China)

Abstract:To solve the shortages appeared in the process of solving multistage decision-making problems with dynamic programming, Heuristic Vogel method was creatively applied in solving this kind of issues for the first time. Its definitions and algorithm steps were provided and its time complexity was analyzed. This paper illustrated the solving process of Heuristic Vogel method with a case, and summarized its advantages and disadvantages and provided a new and effective method for the research of solving multistage decision-making problems.

Key words:Heuristic Vogel method; time complexity; multistage decision-making problem

文章編號：1006-0707(2016)03-0171-04

中圖分類號：E072

文獻標識碼：A

doi:10.11809/scbgxb2016.03.041

作者簡介：孫鵬飛(1989—)，男，主要從事指揮自動化與戰場環境數字化研究。

收稿日期：2015-09-23；修回日期：2015-10-09

本文引用格式：孫鵬飛，劉建永.啟發式伏格爾法求解多階段決策問題[J].兵器裝備工程學報，2016(3):171-174.

【基礎理論與應用研究】