企業(yè)員工通勤交通車路線問題_第1頁
企業(yè)員工通勤交通車路線問題_第2頁
企業(yè)員工通勤交通車路線問題_第3頁
企業(yè)員工通勤交通車路線問題_第4頁
企業(yè)員工通勤交通車路線問題_第5頁
已閱讀5頁,還剩31頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

企業(yè)員工通勤交通車路線問題

Enterprise-OperatedCommuterBusRoutingProblem

韓復華朱政威

張淑詩(國立交通大學運輸科技與管理學系所)

民國九十六年九月十四日2007作業(yè)研究(一)簡報1簡報大綱1.

前言2.個案簡介3.

通勤交通車路線問題模式4.

測試例題構建與模式驗證5.

啟發(fā)式解法構建與測試6.實例應用7.

結論與建議2研究背景與動機(一)許多公司體認到員工福利的重要性,而提供通勤交通車之服務將會是一項不可或缺之勞工福利。24小時全年無休的高科技產業(yè)(如:竹科大廠的作業(yè)員)企業(yè)員工通勤交通車路線問題(CBRP)雖屬於VRP之衍生問題,但其問題特性與VRP問題並不完全相同:車容量、路線時間限制、需求不可分割的特性與VRP相同CBRP路線型態(tài)為單向的路徑(HamiltonianPath)狀與VRP路線呈現迴路(Cycle)狀不同傳統(tǒng)VRP方法不適合直接求解CBRP1.前言VRPCBRP3研究背景與動機(二)校車路線問題(SchoolBusRoutingProblem,SBRP):學校交通車接送學童至學校上學。每個學童於預訂之站牌(起點)上車,所屬之學校(迄點)下車SBRP大部份因學區(qū)和學制因素,只考量一個學校(單迄點)CBRP與SBRP類似,但需多考量:通勤交通車接送員工至工作廠區(qū)上班。每個員工於預訂之停靠站(起點)上車,所屬之工作廠區(qū)(迄點)下車(多迄點)每條路線由不同容量之車種進行服務(多車種)

SBRP現有方法也不易應用至CBRP

1.前言4CBRP在都市客運之定位1.前言通勤交通車與大眾運輸類似有固定路線及時刻表,但只對特定對象提供服務,故不同於大眾運輸是對大眾提供服務;且通勤交通車無副大眾運輸的彈性路線與可及性,故也不同於副大眾運輸。5本研究重點建立通勤交通車路線問題MIP模式:

以最小化總營運成本為目標考量多對多起迄點、多車種之特性MIP模式正確性驗證:

小型例題設計與測試啟發(fā)式解法構建與測試:

起始解構建模組路線改善模組例題測試實例應用:啟發(fā)式解法求解結果1.前言6個案公司簡介臺灣積體電路股份有限公司(TSMC):竹科24小全年無休之大廠,有5個工作廠區(qū)服務範圍:桃園、新竹、苗栗4班別(DA、DB、NA、NB)之路線有40條總里程數共1433.4km停靠站位共529個作業(yè)員工共2653個有3種車型:大巴(43人)中巴(20人)小巴(9人)6.實例應用7個案公司-工作廠區(qū)分佈圖6.實例應用7廠3廠5廠2廠12廠8個案公司-??空痉謥褕D6.實例應用9個案研究範圍服務範圍:桃園、新竹起點個數:109迄點個數:2路線數:14服務人數:244問題規(guī)模:變數:38,296,776限制式:2,247,204各點服務時間:10秒路線時間限制:65分鐘6.實例應用成本車型固定成本變動成本大巴70712.87*d中巴55110.86*d小巴5085.74*d10變數定義3.通勤交通車路線問題模式決策變數11數學列式3.通勤交通車路線問題模式Subjectto12數學列式(續(xù))3.通勤交通車路線問題模式13數學列式(續(xù))3.通勤交通車路線問題模式14問題規(guī)模試算MIP模式:變數:限制式:若有10個起點、2個迄點、3種車型和最大路線數為3條共有10440個變數和5723條限制式問題規(guī)模變大啟發(fā)式解法

3.通勤交通車路線問題模式15測試例題構建確認本研究數學模式正確性建立標竿題庫MIP模式求解結果可提供後續(xù)啟發(fā)式解法求解結果比較之基礎,以評估啟發(fā)式解法之優(yōu)劣4.測試例題構建與模式驗證16小型測試例題設計完全性路網(C):走廊形(CC)共8題、非走廊形(CR)共6題非完全性路網(I):走廊形(IC)共7題、非走廊形(IR)共3題路網型態(tài)測試例題編號完全性路網(C)(共14題)走廊形(CC)CC1、CC2、CC3、CC4、CC5、CC6、CC7、CC8非走廊(CR)CR1、CR2、CR3、CR4、CR5、CR6非完全性路網(I)(共10題)走廊形(IC)IC1、IC2、IC3、IC4、IC5、IC6、IC7非走廊(IR)IR1、IR2、IR34.測試例題構建與模式驗證17完全性路網求解結果路網型態(tài)起迄點個數例題編號T0(路線時間)最佳解求解時間完全性路網(C)走廊型(CC)8個起點2個迄點CC1861752.71小時14分15秒CC2991752.72小時23分16秒CC31061524.56分26秒CC41131524.57分49秒8個起點2個迄點CC5671705.43分1秒CC6831705.46小時3分59秒8個起點2個迄點CC71262328.22天18小時6分25秒CC8138179121分53秒非走廊型(CR)8個起點2個迄點CR1671683.72小時15分39秒CR2711683.76小時13分6秒8個起點2個迄點CR3611599.821小時28分33秒CR465135544分09秒8個起點2個迄點CR5561772.419分54秒CR6601772.410小時28分08秒4.測試例題構建與模式驗證18非完全性路網求解結果路網型態(tài)起迄點個數例題編號T0(路線時間)最佳解求解時間非完全

性路網(I)走廊型(IC)12個起點

2個迄點IC1411677.4515分IC2471677.456分26秒IC3571617.4711分57秒IC4631617.4716分38秒12個起點

2個迄點IC5461959.3217分19秒IC6551870.3318分14秒IC7611870.3329分37秒非走廊型(IR)12個起點

2個迄點IR1401682.0510分5秒IR2481586.191小時11分42秒IR3531586.1941分27秒4.測試例題構建與模式驗證19啟發(fā)式解法架構5.啟發(fā)式解法構建與測試重要步驟:1.起始解構建2.路線改善20起始解構建模組搜尋種子點最近鄰點法插入調整節(jié)點順序與車型調整(縮小)路線構建:1.以最近鄰點法為基礎2.以最大車型之車容輛當作車容量限制5.啟發(fā)式解法構建與測試21路線改善模組定義可移轉量(P)與剩餘容量(SC):5.啟發(fā)式解法構建與測試22路線間節(jié)點移轉改善步驟1:計算各路線SC、P、△f△f=大車變小車節(jié)省之固定成本步驟2:選擇△f/P最大的路線k步驟3:進行節(jié)點移轉5.啟發(fā)式解法構建與測試23路線內節(jié)點交換改善按照路線節(jié)點順序,從路線起點開始,將此節(jié)點與其下一節(jié)點交換,檢查交換後的路線距離是否小於交換前的路線距離,若是,則更新路線;否則路線維持原解。持續(xù)進行節(jié)點之交換,直至所有節(jié)點與其下一節(jié)點都交換檢查完畢為止。5.啟發(fā)式解法構建與測試24完全性路網測試結果比較路網型態(tài)起迄點個數例題編號T0目標值求解時間最佳解啟發(fā)式最佳解啟發(fā)式完全性路網(C)走廊型(CC)8個起點2個迄點CC1861752.71752.71小時14分15秒0.16秒CC2991752.71752.72小時23分16秒0.14秒CC31061524.51524.56分26秒0.14秒CC41131524.51524.57分49秒0.14秒8個起點2個迄點CC5671705.41705.43分1秒0.1秒CC6831705.41705.46小時3分59秒0.15秒8個起點2個迄點CC71262328.22328.22天18小時6分25秒0.15秒CC81381791179121分53秒0.17秒非走廊型(CR)8個起點2個迄點CR1671683.71683.72小時15分39秒0.15秒CR2711683.71683.76小時13分6秒0.17秒8個起點2個迄點CR3611599.81599.821小時28分33秒0.11秒CR4651355135544分09秒0.12秒8個起點2個迄點CR5561772.41772.419分54秒0.1秒CR6601772.41772.410小時28分08秒0.12秒5.啟發(fā)式解法構建與測試25非完全性路網測試結果比較路網型態(tài)起迄點個數例題編號T0目標值求解時間最佳解啟發(fā)式最佳解啟發(fā)式非完全

性路網(I)走廊型(IC)12個起點

2個迄點IC1411677.451677.4515分0.21秒IC2471677.451677.456分26秒0.29秒IC3571617.471617.4711分57秒0.29秒IC4631617.471617.4716分38秒0.21秒12個起點

2個迄點IC5461959.321959.3217分19秒0.37秒IC6551870.331870.3318分14秒0.33秒IC7611870.331870.3329分37秒0.31秒非走廊型(IR)12個起點

2個迄點IR1401682.051682.0510分5秒0.21秒IR2481586.191586.191小時11分42秒0.23秒IR3531586.191586.1941分27秒0.31秒5.啟發(fā)式解法構建與測試26啟發(fā)式解法測試結果分析以啟發(fā)式解法求解:24題測試例題皆可求出最佳解求解效率比較:5.啟發(fā)式解法構建與測試27實例應用-啟發(fā)式解法求解結果6.實例應用*服務容量為各車型實際容量的80%28成本與乘載率分析6.實例應用成本分析

:乘載率分析:29改善前路線圖90分鐘﹑承載率67.4%80分鐘﹑承載率65.1%30結果路線圖(一)6.實例應用路線距離最長之路線(以實際容量限制)

:64分鐘﹑承載率88.9%31結果路線圖(二)6.實例應用路線距離最長之路線(以服務容量限制)

:60分鐘﹑承載率60%32結論本研究針對通勤交通車問題構建出一個明確之數學模式,並經過驗證,可供後續(xù)研究之參考。本研究設計24題小型測試題(CC、CR、IC、

IR),並分別以數學規(guī)劃方式及啟發(fā)式解法求解,可做為通勤交通車路線問題之測試題庫,以供後續(xù)研究參考比較。本研究針對多對多起迄點、多車種之通勤交通車路線問題以啟發(fā)式解法求解,其求解效率良好,可供實務上之應用,解決傳統(tǒng)以人工方式規(guī)劃費時又費力之缺點。7.結論與建議33建議本研究以總營運成本最小化為目標,後續(xù)研究可考慮以服務品質為目標或考量多重目標。本研究之啟發(fā)式解法乃根據問題之特性設計,後續(xù)研究可嘗試利用巨集啟發(fā)式解法加以求解7.結論與建議34謝謝聆聽,敬請指教!!!聯(lián)絡方式:韓復華教授Email:Tel:03-5731680朱政威博士生 Email:zucw.Tel:

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論