不同需求特性下多運務員動態分區派遣策略之研究

Dynamic Zoning Strategies for Dispatching of Couriers under Different Demand Patterns

岳忠傑(Chung-Chieh Yueh)

指導教授 ： 韓復華

國立交通大學/管理學院/運輸科技與管理學系/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00572

摘要

近年來動態車輛路線問題的研究日益增多，但鮮有考慮顧客需求在不同時間與空間分佈上，對分區派遣策略的影響。本研究即考慮顧客需求於不同時間與空間分佈的影響下，對多位快遞運務員的服務作業問題進行探討。研究問題假設服務範圍固定，且由單一場站指派k位運務員對動態產生的顧客進行取件作業。
本研究在需求面考慮：時間分佈上無尖峰、單尖峰與雙尖峰的情況，而空間分佈上則考慮均勻與群聚的情況。在動態派遣方面，包括動態等待與動態分區兩部份，動態等待策略方面：等待訂單數量的DM與等待時間間隔的DW兩種。完成動態等待條件後，即進入動態分區的部份：以k-medoids法分群，再以Voronoi圖分派每位運務員的責任區域。在方法論方面，以系統模擬建構不分區、固定分區、動態分區等策略，並針對尖離峰時段執行分區派遣策略的模擬。並在各需求面之下，測試二至四位運務員，搭配不同分區派遣策略時，各績效指標：營運成本、服務水準與勞役分配的表現。為避免顧客等待過久，本研究亦限制顧客所能接受的平均等待時間，以不同目標為前提來推薦運務員數量與派遣分區策略。
模擬程式以C#程式語言建構，並在Intel(R) Core(TM)2，CPU為2.00GHz的個人電腦進行測試。研究結果發現在各種情境假設之下，營運成本而言，動態分區最佳，固定分區次之，不分區殿後。服務水準而言，不分區最佳，固定分區次之，動態分區則殿後。勞役分配而言，動態分區最為佳，固定分區次之，不分區殿後。若假設顧客可接受平均等待時間60分鐘以內，無尖峰需求型態下，執行DM與DW為分群條件的動態分區，與不分區相較，最少運務員為目標時，總旅行距離約節省9%~36%，最短總旅行距離為目標時，約節省21%~56%；尖峰需求型態下，針對尖離峰執行不同參數設定的DM策略，與不分區相較，最少運務員為目標時，總旅行距離約節省23%~45%，最短總旅行距離為目標時，約節省26%~48%。

關鍵字

動態分區 ； 動態派遣 ； k-medoids分群法 ； 動態等待 ； 動態多旅行推銷員問題

並列摘要

This research is concerned with the dynamic dispatching of multiple couriers in a fixed region with the demand patterns which are influenced by temporal and spatial characteristics. Although abundant literature can be found on dynamic routing and dispatching problems, little has considered the impact of various demand patterns to the optional dynamic routing and dispatching.
In our research, we consider both temporal and spatial characteristics of different demand patterns. Temporal characteristics include uniform, single peak-hour and double peak-hour distributions over a day of operation; spatial characteristics include uniform and cluster distributions over the service area. The dynamic zoning procedure, as we proposed, starts with a dynamic wait. Two dynamic waiting strategies are considered: DM which waits for M demand calls, and DW which waits a fixed time interval of W. As to the dynamic zoning, we first use the k-medoids method to cluster demand points, and then the Voronoi graphs to define the service zone for each courier. In each service zone, the courier follows the nearest neighbor heuristic to service the customers. In addition, both the “single zone” and “fixed zone” strategies are also considered in order to evaluate the performance of the proposed “dynamic zone” strategy.
Simulation models were built and coded in C# to analyze the performance of the three zoning strategies. We tested on a Intel(R) Core(TM)2 CPU 2.00GHz personal computer. Under various temporal and spatial situations, results showed that the dynamic zoning yielded the lowest average travel distance, and yet the highest average waiting time. On the other hand, the single zone strategy gives the lowest waiting time, and yet the longest average travel distance. If the customer can accept the average waiting time in 60 minutes, dynamic zoning strategies under DM or DW will save significant travel distance more than single zone or fixed zone strategies when the demand is uniformly distribution. In addition, dynamic zoning strategies which wait more at peak hours and wait less at off-peak hours perform better than other strategies in travel distance.

並列關鍵字

Dynamic Zoning ； Dynamic Dispatch ； k-medoids ； Dynamic Wait ； Dynamic mTSP

參考文獻

29. 韓復華、卓裕仁，「包容性深廣度搜尋法在週期性車輛路線問題之應用」，運輸計劃季刊，31卷1期，1至36頁，民國91年3月。

31. 韓復華，「以GIDS求解大規模旅行推銷員問題之研究」，89年度國科會專題研究計畫成果報告(NSC-89-2211-E-009-078)。

1. Brown, G. and B. L. Golden, “Real-Time Dispatch of Petroleum Tank truck”, Management Science, Vol. 27, pp. 19-21, 1981.

3. Branke, J., M. Middendorf, G.. Noeth and M. Dessouky , “Waiting strategies for dynamic vehicle routing”, Transportation Science, Vol.39, No. 3, pp.298-312, 2005.

4. Barrett, W. T., “Waiting Strategies for Anticipating Service Requests from Known Customer Locations” Transportation Science, Vol. 41, pp. 319-331, 2007.