具轉運點的取送貨途程問題

A Pickup and Delivery Problem with Hub-Exchange

林碧莉(Lili Yanti)

指導教授 ： 周雍強

國立臺灣大學/工學院/工業工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.00634

摘要

此篇有關取送貨問題研究的創新想法在於以集中轉換的方式處理醫院病歷的緊急傳送作業。科別之間的病歷緊急傳送需求發生在病患一天之內接受多於一個科別以上的診療，而集中轉換的作業方式可同時改善傳送者的負擔與病患的等候時間。集中轉換指的是傳送人在中心點將欲送往其它區域的病歷轉交給其它的傳送人負責。
此研究以所蒐集一個月的實際資料比較現行作業方式 (Policy I) 與集中轉換的作業方式 (Policy II) 在三個不同負荷量時段的績效表現， 此績效比較時係以鄰近距離法則進行途程指派，模擬區間設定為 30分鐘，此期間的需求依其地理位置劃分為三組由不同傳送人進行服務。傳送路徑係由中心出發，在完成傳送任務後回到原中心。此研究以不同的評估方式計算Policy I 和 Policy II的途程時間與等候時間，研究的結果顯示集中轉換確實可提高傳送效率，不但可減少傳送人的工作量，並可縮短需求等候完成的時間。

關鍵字

取送貨問題 ； 集中轉換 ； 啟發式法則 ； 鄰近距離法則

並列摘要

The innovation study of Pickup and Delivery Problem (PDP) is to implement Hub-Exchange in handling the Urgent Transfer of Medical Record folders in Hospital. The urgent transfer process from one department to another is necessary for patients who visit more than one department in one day. The Hub-Exchange procedure may reduce the Couriers' workload and Patients' waiting time simultaneously. Hub exchange is the activity when couriers doing the transshipment exchange folders for far regions with another courier in Hub/depot.
The comparison between existing procedure (Policy I) and Hub-Exchange procedure (Policy II) is based on 3 different time periods in one month data for representing different levels of couriers’ workload. The comparison makes use of the heuristics methods of Nearest Neighbor Algorithm. The simulation running 30 minute time interval and the request data will be divided into three groups of couriers’ territory. The route starts from depot and return to depot after completing the job. There are different estimation methods of Complete Tour and Waiting Time calculation between Policy I and Policy II. As the result of Hub-Exchange procedure increases the working efficiency between couriers, which shown by the workload more evenly, decreased of couriers’ workload, and the shorter time needed to complete the job.

並列關鍵字

Pickup and Delivery Problem ； Hub-Exchange ； Heuristics ； Nearest Neighbor Algorithm.

參考文獻

Bodin L., Golden B. (1981) Classification in vehicle routing and scheduling. Networks 11:97-108. DOI: 10.1002/net.3230110204.

[4] Cordeau J.-F., Laporte G. (2007) The dial-a-ride problem: models and algorithms. Annals of Operations Research 153:29-46. DOI: 10.1007/s10479-007-0170-8.

[5] Cordeau J.F., Gendreau M., Laporte G., Potvin J.Y., Semet F. (2002) A guide to vehicle routing heuristics. J Oper Res Soc 53:512-522.

[7] Irnich S. (2000) A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles. European Journal of Operational Research 122:310-328. DOI: Doi: 10.1016/s0377-2217(99)00235-0.

[8] Jaw J.-J., Odoni A.R., Psaraftis H.N., Wilson N.H.M. (1986) A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transportation Research Part B: Methodological 20:243-257. DOI: Doi: 10.1016/0191-2615(86)90020-2.