1. NCCU Academic Hub
  2. Publications
  3. College of Commerce
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 車輛服務系統之最佳路由策略
Optimal Routing for General Vehicle Service Systems
作者 林建佑
貢獻者 洪英超
林建佑
關鍵詞 車輛路由策略
系統穩定性
佇列
吞吐量
日期 2013
上傳時間 14-Jul-2014 11:30:16 (UTC+8)
摘要 在本文中我們探討具有K座服務站的車輛平行處理系統(Parallel processing system)，並且對於系統的假設更加一般化。車輛在抵達該區域時會面臨選擇服務站的問題，所以路由策略的使用對於系統中車輛滯留時間的表現值顯得更加重要。我們藉由系統的穩定條件(Stability conditions)來比較文獻中常見的車輛路由策略以及我們提出的動態策略(Dynamic policy)之間的差異性，並且探討隨機車輛服務系統(Stochastic vehicle service system)的輸入強度之表現。我們提出一種全新的車輛路由策略：“最小加權佇列長度策略”(Join-the-Weighted-Shortest-Queue Policy)，並且證明了在系統的一般性假設之下此策略可以維持系統的強穩定性，間接也證明了本策略為一種最大吞吐量策略。其證明方式主要是以偏離分析(Drift analysis)作為基礎，並搭配相關的定理結果來證明。此外，我們也對於不同的最大吞吐量策略之下的車輛滯留時間平均值與第九十五百分位數的表現做出評估。最後，我們會對於各種不同的車輛輸入強度以及行駛速度之下，提出路由策略的建議方針。
參考文獻 [1] B. Hajek (1982). Hitting time and occupation time bounds implied by drift analysis with applications. Adv. Appl. Prob., 14(3), pp.502-525.
[2] D. Bertsimas and D. Nakazato (1995). The distributional Little`s law and its applications. Operations Research, 43(2), pp. 298-310.
[3] D. J. Bertsimas and G. Van Ryzin (1991). A stochastic and dynamic vehicle routing problem in the Euclidean plane. Operations Research, 39(4), pp.601-615.
[4] D. J. Bertsimas and G. Van Ryzin (1993). Stochastic and dynamic vehicle routing with general demand and interarrival time distributions. Advances in Applied Probability, pp.947-978.
[5] D. L. Iglehart and W. Whitt (1970). Multiple Channel Queues in heavy traffic, I. Adv. Appi. Prob, 2, pp.150-177
[6] E. Leonardi, M. Mellia, F. Neri and M. Ajmone Marsan (2001). On the stability of input-queued switches with speed-up. Networking, IEEE/ACM Transactions on, 9(1), pp.104-118.
[7] F. Jensen and N. E. Petersen (1982). Burn-in: an engineering approach to the design and analysis of burn-in procedures.
[8] H.N. Psaraftis (1988). Dynamic vehicle routing problems. Vehicle routing: Methods and studies, 16, pp. 223-248.
[9] J.G. Dai (1995). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. The Annals of Applied Probability, 5(1), pp.49-77.
[10] J. Walrand (1988). Introduction to queueing networks. Englewood Cliffs, Prentice Hall.
[11] R. Pemantle and J.S. Rosenthal (1999). Moment conditions for a sequence with negative drift to be uniformly bounded in . Stochastic Processes and their Applications, 82(1), pp.143-155.
[12] R.W. Wolff (1982). Poisson arrivals see time averages. Operations Research, 30(2), pp. 223-231.
[13] S. L. Bell and R. J. Williams (2001). Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy. The Annals of Applied Probability, 11(3), pp.608-649.
[14] S. P. Meyn (1996). Stability and optimization of queueing networks and their fluid models. The Mathematics of Stochastic Manufacturing Systems, pp.17-21.
[15] Y. C. Hung and C.C. Chang (2008). Dynamic scheduling for switched processing systems with substantial service-mode switching times. Queueing systems, 60(1-2), pp.87-109.
[16] Y. C. Hung and G. Michailidis (2008). Modeling, scheduling, and simulation of switched processing systems. ACM Transactions on Modeling and Computer Simulation (TOMACS), 18(3), 12.
[17] Y. C. Hung and G. Michailidis (2012). Stability and control of acyclic stochastic processing networks with shared resources. Automatic Control, IEEE Transactions on, 57(2), pp.489-494.
描述 碩士
國立政治大學
統計研究所
101354017
102
資料來源 http://thesis.lib.nccu.edu.tw/record/#G1013540171
資料類型 thesis
dc.contributor.advisor 洪英超zh_TW
dc.contributor.author (Authors) 林建佑zh_TW
dc.creator (作者) 林建佑zh_TW
dc.date (日期) 2013en_US
dc.date.accessioned 14-Jul-2014 11:30:16 (UTC+8)-
dc.date.available 14-Jul-2014 11:30:16 (UTC+8)-
dc.date.issued (上傳時間) 14-Jul-2014 11:30:16 (UTC+8)-
dc.identifier (Other Identifiers) G1013540171en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/67474-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 統計研究所zh_TW
dc.description (描述) 101354017zh_TW
dc.description (描述) 102zh_TW
dc.description.abstract (摘要) 在本文中我們探討具有K座服務站的車輛平行處理系統(Parallel processing system)，並且對於系統的假設更加一般化。車輛在抵達該區域時會面臨選擇服務站的問題，所以路由策略的使用對於系統中車輛滯留時間的表現值顯得更加重要。我們藉由系統的穩定條件(Stability conditions)來比較文獻中常見的車輛路由策略以及我們提出的動態策略(Dynamic policy)之間的差異性，並且探討隨機車輛服務系統(Stochastic vehicle service system)的輸入強度之表現。我們提出一種全新的車輛路由策略：“最小加權佇列長度策略”(Join-the-Weighted-Shortest-Queue Policy)，並且證明了在系統的一般性假設之下此策略可以維持系統的強穩定性，間接也證明了本策略為一種最大吞吐量策略。其證明方式主要是以偏離分析(Drift analysis)作為基礎，並搭配相關的定理結果來證明。此外，我們也對於不同的最大吞吐量策略之下的車輛滯留時間平均值與第九十五百分位數的表現做出評估。最後，我們會對於各種不同的車輛輸入強度以及行駛速度之下，提出路由策略的建議方針。zh_TW
dc.description.tableofcontents 第一章 緒論 1
第二章 系統描述與假設 3
第2.1節 系統描述 3
第2.2節 系統穩定性(System Stability) 6
第三章 路由策略 10
第3.1節 最近服務站策略(Routing to the Nearest Station Policy) 10
第3.2節 循環服務策略 (The Round Robin Policy) 10
第3.3節 最大服務率策略(Maximum Service Rate Policy) 11
第3.4節 其他路由策略 12
第四章 系統穩定性證明 14
第五章 系統的滯留時間表現值評估 20
第5.1節 系統模擬設定 20
第5.2節 滯留時間平均值 21
第5.3節 滯留時間第九十五百分位數 25
第5.4節 系統繁忙的模擬表現值 28
第六章 結論與討論 31
參考文獻 33		zh_TW
dc.format.extent 1044665 bytes-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G1013540171en_US
dc.subject (關鍵詞) 車輛路由策略zh_TW
dc.subject (關鍵詞) 系統穩定性zh_TW
dc.subject (關鍵詞) 佇列zh_TW
dc.subject (關鍵詞) 吞吐量zh_TW
dc.title (題名) 車輛服務系統之最佳路由策略zh_TW
dc.title (題名) Optimal Routing for General Vehicle Service Systemsen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] B. Hajek (1982). Hitting time and occupation time bounds implied by drift analysis with applications. Adv. Appl. Prob., 14(3), pp.502-525.
[2] D. Bertsimas and D. Nakazato (1995). The distributional Little`s law and its applications. Operations Research, 43(2), pp. 298-310.
[3] D. J. Bertsimas and G. Van Ryzin (1991). A stochastic and dynamic vehicle routing problem in the Euclidean plane. Operations Research, 39(4), pp.601-615.
[4] D. J. Bertsimas and G. Van Ryzin (1993). Stochastic and dynamic vehicle routing with general demand and interarrival time distributions. Advances in Applied Probability, pp.947-978.
[5] D. L. Iglehart and W. Whitt (1970). Multiple Channel Queues in heavy traffic, I. Adv. Appi. Prob, 2, pp.150-177
[6] E. Leonardi, M. Mellia, F. Neri and M. Ajmone Marsan (2001). On the stability of input-queued switches with speed-up. Networking, IEEE/ACM Transactions on, 9(1), pp.104-118.
[7] F. Jensen and N. E. Petersen (1982). Burn-in: an engineering approach to the design and analysis of burn-in procedures.
[8] H.N. Psaraftis (1988). Dynamic vehicle routing problems. Vehicle routing: Methods and studies, 16, pp. 223-248.
[9] J.G. Dai (1995). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. The Annals of Applied Probability, 5(1), pp.49-77.
[10] J. Walrand (1988). Introduction to queueing networks. Englewood Cliffs, Prentice Hall.
[11] R. Pemantle and J.S. Rosenthal (1999). Moment conditions for a sequence with negative drift to be uniformly bounded in . Stochastic Processes and their Applications, 82(1), pp.143-155.
[12] R.W. Wolff (1982). Poisson arrivals see time averages. Operations Research, 30(2), pp. 223-231.
[13] S. L. Bell and R. J. Williams (2001). Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy. The Annals of Applied Probability, 11(3), pp.608-649.
[14] S. P. Meyn (1996). Stability and optimization of queueing networks and their fluid models. The Mathematics of Stochastic Manufacturing Systems, pp.17-21.
[15] Y. C. Hung and C.C. Chang (2008). Dynamic scheduling for switched processing systems with substantial service-mode switching times. Queueing systems, 60(1-2), pp.87-109.
[16] Y. C. Hung and G. Michailidis (2008). Modeling, scheduling, and simulation of switched processing systems. ACM Transactions on Modeling and Computer Simulation (TOMACS), 18(3), 12.
[17] Y. C. Hung and G. Michailidis (2012). Stability and control of acyclic stochastic processing networks with shared resources. Automatic Control, IEEE Transactions on, 57(2), pp.489-494.		zh_TW