1、研究方法論研究方法論第五講第五講 占線問題與競爭策略占線問題與競爭策略西安工業大學經濟管理學院西安工業大學經濟管理學院2022-4-72 n現代社會的特征：現代社會的特征：信息多變與不完全信息多變與不完全部分已知部分已知當前決策信息當前決策信息決策問題決策問題全部已知全部已知當前決策信息當前決策信息已知已知未來信息全部未來信息全部知或一無所知知或一無所知未來信息有限預未來信息有限預2022-4-73 占線優化方法占線優化方法通常是在一定的已知（靜通常是在一定的已知（靜態）條件下尋求最優方案態）條件下尋求最優方案或在一定的假設下尋求統或在一定的假設下尋求統計意義上的最優方案。計意義上的最優方案。

2、決策者對未來因素的變化有決策者對未來因素的變化有限預知甚至一無所知情形下限預知甚至一無所知情形下, ,該方法可以給出較好的方案該方法可以給出較好的方案, ,使之與最優方案的差異（比使之與最優方案的差異（比值）總在一定的比例之內。值）總在一定的比例之內。 靜態優化方法靜態優化方法n兩類問題：兩類問題： 離線問題（離線問題（offlineoffline） 占線問題占線問題( (online)online)n決策方法：決策方法：2022-4-74 1966年，年，Graham第一次提出用競爭分析方法解決并第一次提出用競爭分析方法解決并行機器調度問題，提出一個簡單的確定性貪婪算法；行機器調度問題，提出

3、一個簡單的確定性貪婪算法； 1983年，年，R.Tarjan在在 Data Structure and Network Algorithms 中所討論的中所討論的Amotized的方法，就是占線問題的方法，就是占線問題與競爭策略的萌芽；與競爭策略的萌芽； 近年來，在計算機理論科學、管理科學等領域，占近年來，在計算機理論科學、管理科學等領域，占線問題與競爭策略的研究均取得了較好的理論和實踐成線問題與競爭策略的研究均取得了較好的理論和實踐成果，如經典的果，如經典的k-服務器猜想，雪橇租賃問題，及目前研服務器猜想，雪橇租賃問題，及目前研究熱點物流與金融中的占線問題等。究熱點物流與金融中的占線問題等。

4、2022-4-75 考慮一個最小費用問題考慮一個最小費用問題P P， 為為P P 的輸入序列的輸入序列n 是對占線問題是對占線問題P P 所設計應對策略所設計應對策略A A下對應于輸入下對應于輸入R R的費用的費用. . 策略策略A A只能在獲知第只能在獲知第i i時期的輸入后給出第時期的輸入后給出第i i時期的輸出時期的輸出 n 為問題為問題P P所對應的離線問題在確定輸入所對應的離線問題在確定輸入 R R 下的最優解下的最優解 如果如果 成立成立n 稱為策略稱為策略A A的競爭比的競爭比( (competitive ratio). ). 為與輸入序為與輸入序 列無關的常數。列無關的常數。(

5、 )AC R123 , , , nRr r rrL optCRAoptCRc CRc, c占線問題和競爭策略占線問題和競爭策略2022-4-76 1. A. Borodin and R. El-Yaniv, Online computation and competitive analysis M. Cambridge University Press, 1998.2. A. Fiat and G.J. Woeginger, Online Algorithms: The State of the ArtM. Spring-Verlag, Berlin Heidelberg Germany, 1

6、998.3. D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Comm. ACM, 28(2):202-208, 1985.4.4.堵丁柱堵丁柱, k, k車服務問題與競爭算法車服務問題與競爭算法, , 數學的實踐與認識數學的實踐與認識,.4:36-40, ,.4:36-40, 1991.1991.5. R. M. Karp, On-line Algorithms Versus Off-line Algorithms: How Much is it Worth to Kn

7、ow the Future?, International Computer Science Institute Technical Report TR-92-044, Berkeley, CA, 1992.6. P.Keskinocak, R.Ravi., S.Tayur. Scheduling and Reliable Lead-Time Quotation for Orders with Availability Intervals and Lead-Time Sensitive Revenues. Management Science, 47, 2: 264-279,20012022-

8、4-77 經濟管理中的占線問題經濟管理中的占線問題 經濟管理中的占線問題經濟管理中的占線問題 物流管理中的物流管理中的占線問題占線問題 金融管理中的金融管理中的占線問題占線問題 運輸運輸 選址選址 庫存庫存道路交通堵塞問題道路交通堵塞問題 車輛調度問題車輛調度問題物流中心選擇問題物流中心選擇問題 投資投資 理財理財 金融租賃問題金融租賃問題 證券投資問題證券投資問題 優惠卡購買問題優惠卡購買問題 庫存管理問題庫存管理問題 訂單加工處理問題訂單加工處理問題2022-4-78 CBA12 S1 S22022-4-79 假假 定：定：一個需求發生的頂點序列一個需求發生的頂點序列 策策 略：略：就近策

9、略、公平策略就近策略、公平策略 就近策略：由距離服務需求最近的車輛提供服務就近策略：由距離服務需求最近的車輛提供服務 公平策略：讓每輛車的行駛里程差不多公平策略：讓每輛車的行駛里程差不多 CBA12 S1 S2.mABABAB14444 4244444 32022-4-710 n就近策略：就近策略： 一輛車會在一輛車會在A A和和B B之間移動之間移動m-1次，當次，當m m比較比較大時，最優方案則是把大時，最優方案則是把B B移至移至A A，然后，然后C C點移至點移至B;B;這樣就近服務的運行里程與最優值的比值為這樣就近服務的運行里程與最優值的比值為 （m-1）/3, ,隨著隨著m m 增

10、大，比值增大，因此，就近增大，比值增大，因此，就近策略不是競爭算法。策略不是競爭算法。2022-4-711 n公平公平策略（策略（BALBAL） 設設n=k+1，對于每一個車輛對于每一個車輛 si以及該車輛運行以及該車輛運行的路程的路程Di，服務需求服務需求r，移動移動 si 使得使得 最最小。小。 在服務需求為在服務需求為n=k+1的任意度量空間內，的任意度量空間內，BAL策略是策略是k競爭的。競爭的。 但是，在但是，在nk+1的度量空間中，的度量空間中，BAL是非競爭是非競爭策略。策略。 ( , )iiDd s r2022-4-712 n例例， n=4， k2，初始位置初始位置c、d。 服

11、務需求服務需求 最優的策略為：先將最優的策略為：先將c處的車輛調到處的車輛調到b處，處， 移動移動距離為距離為M，然后兩個車輛在每次響應服務需求時，然后兩個車輛在每次響應服務需求時，都只需移動都只需移動m。, , , , , , , ,., , , ,a b c d a b c da b c dMabcdm( , )iiDd s r2022-4-713 2022-4-714 n出租車調度問題出租車調度問題n占線策略：復位策略占線策略：復位策略n競爭比結果：競爭比結果： 如果對于如果對于k-k-車輛調度問題存在競爭比車輛調度問題存在競爭比2 2k-1k-1的占的占線策略，那么對于線策略，那么對于

12、k-k-出租車調度問題的復位策略具出租車調度問題的復位策略具有競爭比有競爭比 2 2k+1k+1。2022-4-715 n出租車調度與個體收益問題出租車調度與個體收益問題 在一個出租車市場上，由政府設定出租車的數量和在一個出租車市場上，由政府設定出租車的數量和收費標準，收費標準，k k輛出租車在一個有限交通網絡上按照統一輛出租車在一個有限交通網絡上按照統一價格進行競爭性載客服務。網絡上每一個乘客需求為價格進行競爭性載客服務。網絡上每一個乘客需求為 r(ar(ai i,b,bi i),),即在即在a ai i有一顧客要求乘出租車到有一顧客要求乘出租車到 b bi i,a,ai i出現的出現的時間

13、、出現的位置和時間、出現的位置和 r(ar(ai i,b,bi i) )的行駛距離不確定。的行駛距離不確定。2022-4-716 n出租車調度與個體收益問題出租車調度與個體收益問題n出租車完成出租車完成r(ar(ai i,b,bi i) )后可按計價規則收費，在空載后可按計價規則收費，在空載行駛和等待服務需求到來的時間段無收益，并需行駛和等待服務需求到來的時間段無收益，并需支付一定費用。支付一定費用。n問題：問題： 假設不考慮每一輛出租車的固定費用，問題是如何假設不考慮每一輛出租車的固定費用，問題是如何度量出租車在時間段度量出租車在時間段T T上的收益，其個體運營方案上的收益，其個體運營方案對

14、其收益將產生怎樣的影響？對其收益將產生怎樣的影響？2022-4-717 n 出租車時間價格函數出租車時間價格函數( )( )ft dtI towvtttT t to o,t,tw w,t,tv v分別表示載客、等待和空載時間分別表示載客、等待和空載時間 時間段時間段T T分割成許多小的時間區間分割成許多小的時間區間 t,t,則出租車在則出租車在每一個每一個 t t內的時間價格是不一樣的內的時間價格是不一樣的2022-4-718 n 出租車時間價格曲線出租車時間價格曲線圖圖1 1 政府定價下的出租車時間價格曲線政府定價下的出租車時間價格曲線載客載客等待等待空載空載起步價起步價正常運價階段正常運價

15、階段空駛補償階段空駛補償階段2022-4-719 車輛在交通網絡上由出發地欲抵達目的地。在出發車輛在交通網絡上由出發地欲抵達目的地。在出發前，決策者綜合考慮交通網絡中各個路段的狀況，選擇前，決策者綜合考慮交通網絡中各個路段的狀況，選擇了一條有效的行駛路徑。但是，在車輛沿著這條路徑的了一條有效的行駛路徑。但是，在車輛沿著這條路徑的行駛過程中，可能遇到一系列的道路堵塞。由于信息獲行駛過程中，可能遇到一系列的道路堵塞。由于信息獲取手段的有限，決策者不可預知或只能有限預知即將遇取手段的有限，決策者不可預知或只能有限預知即將遇到堵塞的信息，那么，當決策者獲知某個堵塞發生的相到堵塞的信息，那么，當決策者獲

16、知某個堵塞發生的相關信息時，決策者應當制定怎樣的行進策略？不同策略關信息時，決策者應當制定怎樣的行進策略？不同策略的執行效果如何？的執行效果如何？OD?2022-4-720 模型構造：模型構造： ：遭遇遭遇k k個堵塞邊時用策略個堵塞邊時用策略A A將貨物從將貨物從O O點點 運到運到D D點的總費用點的總費用 ： 相應的離線最優費用相應的離線最優費用基本假設：基本假設： 1 1）去掉堵塞邊后圖）去掉堵塞邊后圖G G仍是連通的；仍是連通的； 2 2）只有當運輸車走到堵塞邊的起點后，才能發現該邊）只有當運輸車走到堵塞邊的起點后，才能發現該邊 發生堵塞而不能通過；發生堵塞而不能通過； 3 3）堵塞

17、邊一旦產生，這個邊將永遠被堵塞。）堵塞邊一旦產生，這個邊將永遠被堵塞。12( ,)AkCr rrL12( ,)OPTkCr rrL2022-4-721 貪婪策略（貪婪策略（A A） 復位策略（復位策略（B B） 競爭比競爭比2 2k k1 1不能改進，是一般網絡上的堵塞不可不能改進，是一般網絡上的堵塞不可 恢復恢復問題策略競爭比的下界。問題策略競爭比的下界。 11212( ,)(21)( , ,)kAkOPTkCr rrCr rrLM1212( , , )(21)( , , )BkOPTkCr rrkCr rrLL一般網絡上不可恢復問題的應對策略一般網絡上不可恢復問題的應對策略2022-4-7

18、22 一般網絡上不可恢復堵塞問題貪婪策略最壞情形一般網絡上不可恢復堵塞問題貪婪策略最壞情形2022-4-723 問題問題1 1：為什么貪婪策略競爭比顯著高于復位策略，然：為什么貪婪策略競爭比顯著高于復位策略，然 而從日常經驗來說，人們卻往往采用貪婪策略而從日常經驗來說，人們卻往往采用貪婪策略? ? 問題問題2 2：采用貪婪策略是否具有一定合理性呢？：采用貪婪策略是否具有一定合理性呢？對一般網絡上堵塞不可恢復問題貪婪策略的思考對一般網絡上堵塞不可恢復問題貪婪策略的思考2022-4-724 令令r1,r2,.,rk表示表示 k 個堵塞邊，其中個堵塞邊，其中 li表示從堵塞邊表示從堵塞邊ri的起點到

19、終點的起點到終點D的距離的距離(r1,.,ri-1已經堵塞已經堵塞) li表示從堵塞邊表示從堵塞邊ri的起點到終點的起點到終點D的可行距離可行距離則則 且有且有iiill1i1212( , ,., )( , ,., )kAkOPTkC r rrCr rr對一般網絡上堵塞不可恢復問題貪婪策略的思考對一般網絡上堵塞不可恢復問題貪婪策略的思考2022-4-725 日常生活中的貪婪策略日常生活中的貪婪策略2022-4-726 城市交通網絡結構城市交通網絡結構 方格網絡方格網絡2022-4-727 城市交通網絡結構城市交通網絡結構 環形放射式網絡環形放射式網絡2022-4-728 城市交通網絡結構城市交

20、通網絡結構混合式網絡（方格與環形混合）混合式網絡（方格與環形混合）2022-4-729 城市交通網絡結構城市交通網絡結構自由式（山區等沒有一定的幾何形狀）自由式（山區等沒有一定的幾何形狀）2022-4-730 方格網式，環形放射式，自由式和混合式網絡模型方格網式，環形放射式，自由式和混合式網絡模型n交通網絡的分類方式：交通網絡的分類方式：2022-4-731 目的地為目的地為 時時方向貪婪策略路徑示意圖方向貪婪策略路徑示意圖OPTPMPmnv00vmnv optCmn 2DCmn 22DoptCmnCm n方向貪婪策略方向貪婪策略特殊網絡上不可恢復堵塞問題貪婪策略最壞情形特殊網絡上不可恢復堵塞

21、問題貪婪策略最壞情形()! !mnNm n2022-4-732 目的地為目的地為 時時多選擇貪婪策略點多選擇貪婪策略點 可達示意圖可達示意圖 optCmnMPOPTPmnv00v()ijminjvmnv MCmn1MoptCC多選擇貪婪策略多選擇貪婪策略特殊網絡上不可恢復堵塞問題貪婪策略最壞情形特殊網絡上不可恢復堵塞問題貪婪策略最壞情形2022-4-733 n 物流配送網絡由多個配送中心組成，配送中心數量物流配送網絡由多個配送中心組成，配送中心數量隨著未來需求的變化而增加，因此網絡建設需逐步分階隨著未來需求的變化而增加，因此網絡建設需逐步分階段完成。即在前階段已建好的配送中心基礎上，需要增段完成。即在前階段已建好的配送中心基礎上，需要增加若干個配送中心，問題是在不同的建設階段應如何對加若干個配送中心，問題是在不同的建設階段應如何對物流配送中心進行選址，使得在網絡內對服務需求的運物流配送中心進行選址，使得在網絡內對