企业员工通勤交通车路线问题

企業員工通勤交通車路線問題Enterprise-OperatedCommuterBusRoutingProblem韓復華朱政威張淑詩(國立交通大學運輸科技與管理學系所)民國九十六年九月十四日2007作業研究(一)簡報2簡報大綱1.前言2.個案簡介3.通勤交通車路線問題模式4.測試例題構建與模式驗證5.啟發式解法構建與測試6.實例應用7.結論與建議3研究背景與動機(一)許多公司體認到員工福利的重要性，而提供通勤交通車之服務將會是一項不可或缺之勞工福利。24小時全年無休的高科技產業(如:竹科大廠的作業員)企業員工通勤交通車路線問題(CBRP)雖屬於VRP之衍生問題，但其問題特性與VRP問題並不完全相同:車容量、路線時間限制、需求不可分割的特性與VRP相同CBRP路線型態為單向的路徑(HamiltonianPath)狀與VRP路線呈現迴路(Cycle)狀不同傳統VRP方法不適合直接求解CBRP1.前言321487569181716151413121110路線一路線二路線三路線四需求點1場站231487569181716141511131210路線一路線二路線三路線四需求點1（起點）廠區（迄點）VRPCBRP4研究背景與動機(二)校車路線問題(SchoolBusRoutingProblem,SBRP):學校交通車接送學童至學校上學。每個學童於預訂之站牌(起點)上車，所屬之學校(迄點)下車SBRP大部份因學區和學制因素，只考量一個學校(單迄點)CBRP與SBRP類似，但需多考量:通勤交通車接送員工至工作廠區上班。每個員工於預訂之停靠站(起點)上車，所屬之工作廠區(迄點)下車(多迄點)每條路線由不同容量之車種進行服務(多車種)SBRP現有方法也不易應用至CBRP1.前言5CBRP在都市客運之定位1.前言通勤交通車(CommuterBus)都市公車(UrbanTransitBus)員工交通車學校交通車旅客因素服務對象機關團體/企業員工師生一般大眾旅次起迄多對多多對一/多對多多對多起迄型態固定固定變動旅次分佈分散集中分散旅次目的上/下班對稱上/放學對稱不對稱路網可及性中中低路線型態單向單向雙向營運因素場站設置無無有發班頻率單趟單趟多趟車種多單單目標多目標(服務/成本)多目標(服務/成本)多目標(成本/服務)通勤交通車與大眾運輸類似有固定路線及時刻表，但只對特定對象提供服務，故不同於大眾運輸是對大眾提供服務;且通勤交通車無副大眾運輸的彈性路線與可及性，故也不同於副大眾運輸。6本研究重點建立通勤交通車路線問題MIP模式:以最小化總營運成本為目標考量多對多起迄點、多車種之特性MIP模式正確性驗證:小型例題設計與測試啟發式解法構建與測試:起始解構建模組路線改善模組例題測試實例應用:啟發式解法求解結果1.前言7個案公司簡介臺灣積體電路股份有限公司(TSMC):竹科24小全年無休之大廠，有5個工作廠區服務範圍:桃園、新竹、苗栗4班別(DA、DB、NA、NB)之路線有40條總里程數共1433.4km停靠站位共529個作業員工共2653個有3種車型:大巴(43人)中巴(20人)小巴(9人）6.實例應用8個案公司-工作廠區分佈圖6.實例應用7廠3廠5廠2廠12廠9個案公司-停靠站分佈圖6.實例應用10個案研究範圍服務範圍:桃園、新竹起點個數：109迄點個數：2路線數：14服務人數：244問題規模:變數：38,296,776限制式：2,247,204各點服務時間:10秒路線時間限制:65分鐘6.實例應用成本車型固定成本變動成本大巴70712.87*d中巴55110.86*d小巴5085.74*d11變數定義3.通勤交通車路線問題模式決策變數1,ifassigntoroutek0,otherwise1,ifrouteusesbustype0,otherwise1,ifrouteisinuse0,otherwise()()1,ifroutec()oqkmymkvkvkzkkkpij起迄需求量指派變數車型指派變數路線啟動變數versarc0,otherwiseflowofpatternmassignedtorouteonarc())(ijkmxkijij路線指派變數路線流量變數12vvkvkvijijkRvViNjNkRvVMincd數學列式3.通勤交通車路線問題模式0(1),,,(2),,,(3)1,,,(4),kvkijijkvijkvkkvijkvijkjkjNpiNjNkRvViNjNkRvVpiNjNkRvVpzkR0(5),(6),,kjkjNkkijjikjNjNpzkRppziNkRzk每一路線進出入虛擬點的總次數為zk每一路線上進出各點次數一致，且小於或等於,kkvpijkvij若和存在則必存在,kvijkv若存在則必存在,kvkpijij若存在則必存在Subjecttokvkijijkvp13V(7)1,(8),,(9),,(10),,(11),(12)mmkmkRkmkkkmsjjNkkmitiNkkvvkmmmMymMyzkRmMypkRmMypkRmMzkRqy,vkvvVkkR數學列式(續),patternmqkmk若起迄量指派到路線則的迄點必指派到路線1,;0,zzkk表每一路線只使用一種車輛無車輛指派車容量限制,patternmqkmk若起迄量指派到路線則的起點必指派到路線,mqkk若起迄量指派給路線時則路線一定存在OD每個需求量只能指派給一條路線3.通勤交通車路線問題模式140,,(13),(14),,,(15),,,(16),,,kijiijiNjNkmkkmkjiimmmijimmmjNjNkmkijijmMkkmijijmMpstTkRxgqyxhqymMiNkRxBpijNkRpxijNkR數學列式(續),kkmpxijij若存在則一定存在,kmkxpijij若存在則一定存在流量守恆路線時間限制3.通勤交通車路線問題模式15問題規模試算MIP模式:變數:限制式:若有10個起點、2個迄點、3種車型和最大路線數為3條共有10440個變數和5723條限制式問題規模變大啟發式解法222(1)nnnnnRVNMNMVN223325nnnnnnnnnnRVNRMNRMNRRNRM3.通勤交通車路線問題模式16測試例題構建確認本研究數學模式正確性建立標竿題庫MIP模式求解結果可提供後續啟發式解法求解結果比較之基礎，以評估啟發式解法之優劣4.測試例題構建與模式驗證17小型測試例題設計完全性路網(C):走廊形(CC)共8題、非走廊形(CR)共6題非完全性路網(I):走廊形(IC)共7題、非走廊形(IR)共3題路網型態測試例題編號完全性路網(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.測試例題構建與模式驗證18完全性路網求解結果路網型態起迄點個數例題編號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.測試例題構建與模式驗證19非完全性路網求解結果路網型態起迄點個數例題編號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.測試例題構建與模式驗證20啟發式解法架構5.啟發式解法構建與測試1.搜尋種子點2.最近鄰點法3.調整路線內節點順序車型調整路線間節點移轉改善路線內節點交換改善起始路線構建起始解構建路線形成路線改善重要步驟：1.起始解構建2.路線改善21起始解構建模組搜尋離種子點最近之節點i將節點i插入路線k，並將種子點更新為節點i是搜尋離迄點d最遠之未指派節點為種子點檢查節點i插入路線K是否滿足時間與容量限制是否有未指派之節點選擇起、迄點間距離最長的迄點d將其他迄點加入至各路線中K=1調整路線中節點順序否更新路線KK=K+1是否車型調整(縮小)檢查各路線距離是否為最短是否起始解構建完成搜尋種子點最近鄰點法插入調整節點順序與車型調整(縮小)路線構建：1.以最近鄰點法為基礎2.以最大車型之車容輛當作車容量限制5.啟發式解法構建與測試22大型車車容量(C1)中型車實際乘載量(L2)車容量(C3)小型車P1SC1實際乘載量(L1)車容量(C2)SC2P2SC3路線改善模組121,PSCP若將移轉定義可移轉量(P)與剩餘容量(SC):232,PSCP若將移轉5.啟發式解法構建與測試23路線間節點移轉改善否計算每條路線之SC和P計算Δf，選擇(Δf/P)大的路線k先開始檢查Pk是否小於其他路線之剩餘車容量總合是選擇未檢查過且最靠近j之路線l檢查SCl0選擇路線k離迄點最近之起點j否否檢查將k路線之最近點j插入是否滿足STl、SCl是否是j=j+1是停止法則是路線間節點移轉完成檢查Pk=0將k路線之j點插入並將j上之需求移轉更新Pk、SCk、STk、Pl、SCl、STl否步驟1：計算各路線SC、P、△f△f=大車變小車節省之固定成本步驟2：選擇△f/P最大的路線k步驟3：進行節點移轉5.啟發式解法構建與測試24路線內節點交換改善按照路線節點順序，從路線起點開始，將此節點與其下一節點交換，檢查交換後的路線距離是否小於交換前的路線距離，若是，則更新路線；否則路線維持原解。持續進行節點之交換，直至所有節點與其下一節點都交換檢查完畢為止。5.啟發式解法構建與測試25完全性路網測試結果比較路網型態起迄點個數例題編號T0目標值求解時間最佳解啟發式最佳解啟發式完全性路網(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分2