學術產出-Theses
Article View/Open
Publication Export
-
題名 車輛服務系統之最佳路由策略
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 (日期) 2013 en_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) G1013540171 en_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 (描述) 101354017 zh_TW dc.description (描述) 102 zh_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/#G1013540171 en_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 Systems en_US dc.type (資料類型) thesis en 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
