多個快遞運務員動態分區派遣策略之研究

Abstract

本研究針對多位快遞運務員的服務作業問題進行探討，研究問題假設服務範圍固定、顧客需求為均等分佈且由單一場站指派k位運務員對動態產生之顧客進行取件之作業，即所謂k位快遞運務員服務問題(K-Dynamic Couriers Service Problem, K-DCSP)。此性質的問題屬於動態多旅行推銷員問題(Dynamic mTSP)。有關動態車輛路線問題方面的研究日益增多，但鮮有考慮運務員的責任分區對派遣策略的影響，本研究即探討如何應用動態分區的策略來派遣多位運務員，達到系統目標最佳化，系統績效的指標包括：營運成本、服務水準和勞役分配。 本研究以模擬的方式，建構三種分區策略(不分區、固定分區、動態分區)評估在不同需求密度下的績效表現。「不分區策略」即所有運務員都服務共同的範圍;「固定分區策略」即事先劃定好責任分區，每個分區固定由一位運務員服務;「動態分區策略」則依實際需求做動態性的調整運務員的服務分區。動態分區採用動態等待(Dynamic Wait)的概念，首先等待至M個需求點產生後，採用k-medoids之方法對產生之需求點進行分群，再以Voronoi圖形方法劃分出各個分區開始展開服務，然後每隔 時距重複上述分群與分區之方式，做動態性調整直至需求結束。本研究以最近鄰點法做為各運務員在其分區內之指派方式。 本研究以C#程式語言建構模擬程式，並在Intel(R) Core(TM)2，CPU為2.00GHz的個人電腦進行測試。研究結果發現在不同的需求密度下，以營運成本而言，動態分區的表現最佳，固定分區次之，不分區殿後。反之，以服務水準而言，不分區表現最佳，固定分區次之，動態分區則殿後。再以勞役分配而言，不分區最為佳，其次為動態分區，最差為固定分區，但其差異不明顯。一般而言，本研究提出之動態分區派遣策略在需求密度較低或容許等待時間較長的條件下，將可有效節省近40%系統之營運成本，該成效會隨著參數M與 增加而遞增，隨著需求密度增加而遞減。本研究亦對不同需求密度的環境下，多位運務員適合的數目進行討論。

This research is concerned with the dynamic dispatching of multiple couriers in a fixed region with uniformly distributed demand point, i.e. K-Dynamic Couriers Service Problem, K-DCSP. The problem concerned is essentially a dynamic mTSP. Although abundant literature can be found on dynamic routing and dispatching problems, little has been discussed on the application of dynamic zoning strategies. This paper proposed a new dynamic zoning method, and showed its potential in dealing with the dynamic dispatching of multiple couriers. The dynamic zoning procedure, we proposed, starts with a dynamic wait. We first hold the couriers, and wait until M demand calls before we start the service. We then use the k-medoids method to divide the M points into m clusters, and define the service zone for each courier using Voronoi graphs. In each service zone, the courier follows the nearest neighbor heuristic to service the customers. Such a procedure is repeated every time interval until the end of demand arrivals. 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. 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. We found that the dynamic zoning strategy would perform best when the demand density is low and the allowed waiting time is high. Under such conditions, the dynamic zoning may yield 20% and 40% savings in the distance traveled as compared to the fixed zone and single zone scenarios respectively. Finally, the optimal numbers of dispatchers under different scenarios were discussed.