




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
企業(yè)員工通勤交通車(chē)路線問(wèn)題
Enterprise-OperatedCommuterBusRoutingProblem
韓復(fù)華朱政威
張淑詩(shī)(國(guó)立交通大學(xué)運(yùn)輸科技與管理學(xué)系所)
民國(guó)九十六年九月十四日2007作業(yè)研究(一)簡(jiǎn)報(bào)1簡(jiǎn)報(bào)大綱1.
前言2.個(gè)案簡(jiǎn)介3.
通勤交通車(chē)路線問(wèn)題模式4.
測(cè)試?yán)}構(gòu)建與模式驗(yàn)證5.
啟發(fā)式解法構(gòu)建與測(cè)試6.實(shí)例應(yīng)用7.
結(jié)論與建議2研究背景與動(dòng)機(jī)(一)許多公司體認(rèn)到員工福利的重要性,而提供通勤交通車(chē)之服務(wù)將會(huì)是一項(xiàng)不可或缺之勞工福利。24小時(shí)全年無(wú)休的高科技產(chǎn)業(yè)(如:竹科大廠的作業(yè)員)企業(yè)員工通勤交通車(chē)路線問(wèn)題(CBRP)雖屬於VRP之衍生問(wèn)題,但其問(wèn)題特性與VRP問(wèn)題並不完全相同:車(chē)容量、路線時(shí)間限制、需求不可分割的特性與VRP相同CBRP路線型態(tài)為單向的路徑(HamiltonianPath)狀與VRP路線呈現(xiàn)迴路(Cycle)狀不同傳統(tǒng)VRP方法不適合直接求解CBRP1.前言VRPCBRP3研究背景與動(dòng)機(jī)(二)校車(chē)路線問(wèn)題(SchoolBusRoutingProblem,SBRP):學(xué)校交通車(chē)接送學(xué)童至學(xué)校上學(xué)。每個(gè)學(xué)童於預(yù)訂之站牌(起點(diǎn))上車(chē),所屬之學(xué)校(迄點(diǎn))下車(chē)SBRP大部份因?qū)W區(qū)和學(xué)制因素,只考量一個(gè)學(xué)校(單迄點(diǎn))CBRP與SBRP類(lèi)似,但需多考量:通勤交通車(chē)接送員工至工作廠區(qū)上班。每個(gè)員工於預(yù)訂之??空?起點(diǎn))上車(chē),所屬之工作廠區(qū)(迄點(diǎn))下車(chē)(多迄點(diǎn))每條路線由不同容量之車(chē)種進(jìn)行服務(wù)(多車(chē)種)
SBRP現(xiàn)有方法也不易應(yīng)用至CBRP
1.前言4CBRP在都市客運(yùn)之定位1.前言通勤交通車(chē)與大眾運(yùn)輸類(lèi)似有固定路線及時(shí)刻表,但只對(duì)特定對(duì)象提供服務(wù),故不同於大眾運(yùn)輸是對(duì)大眾提供服務(wù);且通勤交通車(chē)無(wú)副大眾運(yùn)輸?shù)膹椥月肪€與可及性,故也不同於副大眾運(yùn)輸。5本研究重點(diǎn)建立通勤交通車(chē)路線問(wèn)題MIP模式:
以最小化總營(yíng)運(yùn)成本為目標(biāo)考量多對(duì)多起迄點(diǎn)、多車(chē)種之特性MIP模式正確性驗(yàn)證:
小型例題設(shè)計(jì)與測(cè)試啟發(fā)式解法構(gòu)建與測(cè)試:
起始解構(gòu)建模組路線改善模組例題測(cè)試實(shí)例應(yīng)用:啟發(fā)式解法求解結(jié)果1.前言6個(gè)案公司簡(jiǎn)介臺(tái)灣積體電路股份有限公司(TSMC):竹科24小全年無(wú)休之大廠,有5個(gè)工作廠區(qū)服務(wù)範(fàn)圍:桃園、新竹、苗栗4班別(DA、DB、NA、NB)之路線有40條總里程數(shù)共1433.4km??空疚还?29個(gè)作業(yè)員工共2653個(gè)有3種車(chē)型:大巴(43人)中巴(20人)小巴(9人)6.實(shí)例應(yīng)用7個(gè)案公司-工作廠區(qū)分佈圖6.實(shí)例應(yīng)用7廠3廠5廠2廠12廠8個(gè)案公司-??空痉謥褕D6.實(shí)例應(yīng)用9個(gè)案研究範(fàn)圍服務(wù)範(fàn)圍:桃園、新竹起點(diǎn)個(gè)數(shù):109迄點(diǎn)個(gè)數(shù):2路線數(shù):14服務(wù)人數(shù):244問(wèn)題規(guī)模:變數(shù):38,296,776限制式:2,247,204各點(diǎn)服務(wù)時(shí)間:10秒路線時(shí)間限制:65分鐘6.實(shí)例應(yīng)用成本車(chē)型固定成本變動(dòng)成本大巴70712.87*d中巴55110.86*d小巴5085.74*d10變數(shù)定義3.通勤交通車(chē)路線問(wèn)題模式?jīng)Q策變數(shù)11數(shù)學(xué)列式3.通勤交通車(chē)路線問(wèn)題模式Subjectto12數(shù)學(xué)列式(續(xù))3.通勤交通車(chē)路線問(wèn)題模式13數(shù)學(xué)列式(續(xù))3.通勤交通車(chē)路線問(wèn)題模式14問(wèn)題規(guī)模試算MIP模式:變數(shù):限制式:若有10個(gè)起點(diǎn)、2個(gè)迄點(diǎn)、3種車(chē)型和最大路線數(shù)為3條共有10440個(gè)變數(shù)和5723條限制式問(wèn)題規(guī)模變大啟發(fā)式解法
3.通勤交通車(chē)路線問(wèn)題模式15測(cè)試?yán)}構(gòu)建確認(rèn)本研究數(shù)學(xué)模式正確性建立標(biāo)竿題庫(kù)MIP模式求解結(jié)果可提供後續(xù)啟發(fā)式解法求解結(jié)果比較之基礎(chǔ),以評(píng)估啟發(fā)式解法之優(yōu)劣4.測(cè)試?yán)}構(gòu)建與模式驗(yàn)證16小型測(cè)試?yán)}設(shè)計(jì)完全性路網(wǎng)(C):走廊形(CC)共8題、非走廊形(CR)共6題非完全性路網(wǎng)(I):走廊形(IC)共7題、非走廊形(IR)共3題路網(wǎng)型態(tài)測(cè)試?yán)}編號(hào)完全性路網(wǎng)(C)(共14題)走廊形(CC)CC1、CC2、CC3、CC4、CC5、CC6、CC7、CC8非走廊(CR)CR1、CR2、CR3、CR4、CR5、CR6非完全性路網(wǎng)(I)(共10題)走廊形(IC)IC1、IC2、IC3、IC4、IC5、IC6、IC7非走廊(IR)IR1、IR2、IR34.測(cè)試?yán)}構(gòu)建與模式驗(yàn)證17完全性路網(wǎng)求解結(jié)果路網(wǎng)型態(tài)起迄點(diǎn)個(gè)數(shù)例題編號(hào)T0(路線時(shí)間)最佳解求解時(shí)間完全性路網(wǎng)(C)走廊型(CC)8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CC1861752.71小時(shí)14分15秒CC2991752.72小時(shí)23分16秒CC31061524.56分26秒CC41131524.57分49秒8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CC5671705.43分1秒CC6831705.46小時(shí)3分59秒8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CC71262328.22天18小時(shí)6分25秒CC8138179121分53秒非走廊型(CR)8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CR1671683.72小時(shí)15分39秒CR2711683.76小時(shí)13分6秒8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CR3611599.821小時(shí)28分33秒CR465135544分09秒8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CR5561772.419分54秒CR6601772.410小時(shí)28分08秒4.測(cè)試?yán)}構(gòu)建與模式驗(yàn)證18非完全性路網(wǎng)求解結(jié)果路網(wǎng)型態(tài)起迄點(diǎn)個(gè)數(shù)例題編號(hào)T0(路線時(shí)間)最佳解求解時(shí)間非完全
性路網(wǎng)(I)走廊型(IC)12個(gè)起點(diǎn)
2個(gè)迄點(diǎn)IC1411677.4515分IC2471677.456分26秒IC3571617.4711分57秒IC4631617.4716分38秒12個(gè)起點(diǎn)
2個(gè)迄點(diǎn)IC5461959.3217分19秒IC6551870.3318分14秒IC7611870.3329分37秒非走廊型(IR)12個(gè)起點(diǎn)
2個(gè)迄點(diǎn)IR1401682.0510分5秒IR2481586.191小時(shí)11分42秒IR3531586.1941分27秒4.測(cè)試?yán)}構(gòu)建與模式驗(yàn)證19啟發(fā)式解法架構(gòu)5.啟發(fā)式解法構(gòu)建與測(cè)試重要步驟:1.起始解構(gòu)建2.路線改善20起始解構(gòu)建模組搜尋種子點(diǎn)最近鄰點(diǎn)法插入調(diào)整節(jié)點(diǎn)順序與車(chē)型調(diào)整(縮小)路線構(gòu)建:1.以最近鄰點(diǎn)法為基礎(chǔ)2.以最大車(chē)型之車(chē)容輛當(dāng)作車(chē)容量限制5.啟發(fā)式解法構(gòu)建與測(cè)試21路線改善模組定義可移轉(zhuǎn)量(P)與剩餘容量(SC):5.啟發(fā)式解法構(gòu)建與測(cè)試22路線間節(jié)點(diǎn)移轉(zhuǎn)改善步驟1:計(jì)算各路線SC、P、△f△f=大車(chē)變小車(chē)節(jié)省之固定成本步驟2:選擇△f/P最大的路線k步驟3:進(jìn)行節(jié)點(diǎn)移轉(zhuǎn)5.啟發(fā)式解法構(gòu)建與測(cè)試23路線內(nèi)節(jié)點(diǎn)交換改善按照路線節(jié)點(diǎn)順序,從路線起點(diǎn)開(kāi)始,將此節(jié)點(diǎn)與其下一節(jié)點(diǎn)交換,檢查交換後的路線距離是否小於交換前的路線距離,若是,則更新路線;否則路線維持原解。持續(xù)進(jìn)行節(jié)點(diǎn)之交換,直至所有節(jié)點(diǎn)與其下一節(jié)點(diǎn)都交換檢查完畢為止。5.啟發(fā)式解法構(gòu)建與測(cè)試24完全性路網(wǎng)測(cè)試結(jié)果比較路網(wǎng)型態(tài)起迄點(diǎn)個(gè)數(shù)例題編號(hào)T0目標(biāo)值求解時(shí)間最佳解啟發(fā)式最佳解啟發(fā)式完全性路網(wǎng)(C)走廊型(CC)8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CC1861752.71752.71小時(shí)14分15秒0.16秒CC2991752.71752.72小時(shí)23分16秒0.14秒CC31061524.51524.56分26秒0.14秒CC41131524.51524.57分49秒0.14秒8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CC5671705.41705.43分1秒0.1秒CC6831705.41705.46小時(shí)3分59秒0.15秒8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CC71262328.22328.22天18小時(shí)6分25秒0.15秒CC81381791179121分53秒0.17秒非走廊型(CR)8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CR1671683.71683.72小時(shí)15分39秒0.15秒CR2711683.71683.76小時(shí)13分6秒0.17秒8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CR3611599.81599.821小時(shí)28分33秒0.11秒CR4651355135544分09秒0.12秒8個(gè)起點(diǎn)2個(gè)迄點(diǎn)CR5561772.41772.419分54秒0.1秒CR6601772.41772.410小時(shí)28分08秒0.12秒5.啟發(fā)式解法構(gòu)建與測(cè)試25非完全性路網(wǎng)測(cè)試結(jié)果比較路網(wǎng)型態(tài)起迄點(diǎn)個(gè)數(shù)例題編號(hào)T0目標(biāo)值求解時(shí)間最佳解啟發(fā)式最佳解啟發(fā)式非完全
性路網(wǎng)(I)走廊型(IC)12個(gè)起點(diǎn)
2個(gè)迄點(diǎn)IC1411677.451677.4515分0.21秒IC2471677.451677.456分26秒0.29秒IC3571617.471617.4711分57秒0.29秒IC4631617.471617.4716分38秒0.21秒12個(gè)起點(diǎn)
2個(gè)迄點(diǎn)IC5461959.321959.3217分19秒0.37秒IC6551870.331870.3318分14秒0.33秒IC7611870.331870.3329分37秒0.31秒非走廊型(IR)12個(gè)起點(diǎn)
2個(gè)迄點(diǎn)IR1401682.051682.0510分5秒0.21秒IR2481586.191586.191小時(shí)11分42秒0.23秒IR3531586.191586.1941分27秒0.31秒5.啟發(fā)式解法構(gòu)建與測(cè)試26啟發(fā)式解法測(cè)試結(jié)果分析以啟發(fā)式解法求解:24題測(cè)試?yán)}皆可求出最佳解求解效率比較:5.啟發(fā)式解法構(gòu)建與測(cè)試27實(shí)例應(yīng)用-啟發(fā)式解法求解結(jié)果6.實(shí)例應(yīng)用*服務(wù)容量為各車(chē)型實(shí)際容量的80%28成本與乘載率分析6.實(shí)例應(yīng)用成本分析
:乘載率分析:29改善前路線圖90分鐘﹑承載率67.4%80分鐘﹑承載率65.1%30結(jié)果路線圖(一)6.實(shí)例應(yīng)用路線距離最長(zhǎng)之路線(以實(shí)際容量限制)
:64分鐘﹑承載率88.9%31結(jié)果路線圖(二)6.實(shí)例應(yīng)用路線距離最長(zhǎng)之路線(以服務(wù)容量限制)
:60分鐘﹑承載率60%32結(jié)論本研究針對(duì)通勤交通車(chē)問(wèn)題構(gòu)建出一個(gè)明確之?dāng)?shù)學(xué)模式,並經(jīng)過(guò)驗(yàn)證,可供後續(xù)研究之參考。本研究設(shè)計(jì)24題小型測(cè)試題(CC、CR、IC、
IR),並分別以數(shù)學(xué)規(guī)劃方式及啟發(fā)式解法求解,可做為通勤交通車(chē)路線問(wèn)題之測(cè)試題庫(kù),以供後續(xù)研究參考比較。本研究針對(duì)多對(duì)多起迄點(diǎn)、多車(chē)種之通勤交通車(chē)路線問(wèn)題以啟發(fā)式解法求解,其求解效率良好,可供實(shí)務(wù)上之應(yīng)用,解決傳統(tǒng)以人工方式規(guī)劃費(fèi)時(shí)又費(fèi)力之缺點(diǎn)。7.結(jié)論與建議33建議本研究以總營(yíng)運(yùn)成本最小化為目標(biāo),後續(xù)研究可考慮以服務(wù)品質(zhì)為目標(biāo)或考量多重目標(biāo)。本研究之啟發(fā)式解法乃根據(jù)問(wèn)題之特性設(shè)計(jì),後續(xù)研究可嘗試?yán)镁藜瘑l(fā)式解法加以求解7.結(jié)論與建議34謝謝聆聽(tīng),敬請(qǐng)指教!!!聯(lián)絡(luò)方式:韓復(fù)華教授Email:Tel:03-5731680朱政威博士生 Email:zucw.Tel:
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 設(shè)計(jì)創(chuàng)新成果管理辦法
- 監(jiān)理公司證件管理辦法
- 證券行業(yè)資質(zhì)管理辦法
- 開(kāi)源信息保密管理辦法
- 成都交易資金管理辦法
- 高考網(wǎng)高一數(shù)學(xué)試卷
- 高中高三數(shù)學(xué)試卷
- 肝病中醫(yī)治療課件
- 高三春招復(fù)習(xí)數(shù)學(xué)試卷
- 東莞市高三二模數(shù)學(xué)試卷
- 收樓驗(yàn)房知識(shí)培訓(xùn)課件
- 林草行業(yè)安全生產(chǎn)
- 防中暑課件部隊(duì)
- 《洗紅領(lǐng)巾》(教案)-2024-2025學(xué)年二年級(jí)上冊(cè)勞動(dòng)蘇科版
- 《從偶然到必然:華為研發(fā)投資與管理實(shí)踐》第1,2章試題
- 2025年公安輔警招聘知識(shí)考試題(附含答案)
- 辦公家具采購(gòu)項(xiàng)目投標(biāo)方案投標(biāo)文件(技術(shù)方案)
- 電子商務(wù)數(shù)據(jù)分析實(shí)戰(zhàn)題庫(kù)
- 中醫(yī)基礎(chǔ)知識(shí)津液課件
- 義務(wù)教育物理課程標(biāo)準(zhǔn)
- 國(guó)家開(kāi)放大學(xué)本科《商務(wù)英語(yǔ)4》一平臺(tái)在線形考(單元自測(cè)1至8)試題及答案2025珍藏版
評(píng)論
0/150
提交評(píng)論