不同需求特性下動態車輛派遣策略之研究

Abstract

隨著科技的發展，供應鏈競爭對物流配送要求更快速的服務，而且在現實的情況下，大部份的需求往往是在營運期間內才陸續產生，靜態的路線規劃已無法滿足需求；所以目前大部份的研究轉移針對動態的車輛路線問題。 在動態的車輛路線問題中，雖有不少學者提出不同策略，但大部份的研究僅針對某特定之需求情境，測試策略之優劣，仍未有文獻提出在不同的需求特性下，選擇最合適之車輛派遣策略，故本研究針對動態旅行推銷員問題，在不同需求特性下，建立一快速即時之派遣策略。在需求特性上考慮時間與空間兩方面不同之特性，時間軸上分別考慮均勻連續與尖峰時段兩種需求特性，空間分佈考慮均勻與不同需求密集區域分佈兩種情形。 在本研究中動態派遣策略以2種路線構建原則(NN 與 FCFS)結合5種即時之派遣方式(Basic、Reposition、Diversion、DDR、DFR)，利用 C++ 程式語言來構建整個研究之模擬程式，並利用模擬的方式產生不同情境以及測試各策略於不同情境下之績效表現。 測試結果顯示各策略效果皆有明顯差別，對於不考慮有臨時插單之情況，Reposition 策略雖可降低車輛之回應時間，但相對會增加許多的移動距離，而其移動距離增加的程度高於回應時間節省之比例；而 DDR 策略與 Reposition 策略效果類似，但此策略可節省更多的回應時間，且也可降低移動距離增加的程度。所以在此情況下，若以服務水準為重，則選擇採用 DDR 策略。 另外對於考慮有臨時插單之情況，Diversion 策略在所有情境下皆能同時降低移動距離與節省回應時間；而究 DFR 策略來講，雖然相對會花費移動成本，但回應時間節省之比例卻是所有策略中最高的，為服務水準最高的策略。而在有尖峰時段高需求密度且高密密集區域之權重值之情況下，此策略能同時降低移動距離與回應時間。所以在此情況下，若以服務水準為重，則選擇採用 DFR 策略；若以成本為重時，則選擇採用 Diversion 策略。

Along with the development of technologies, the competitions between supply chain companies rely mainly on their services of fast delivery. In the real-world situation, the demands from customers are often received during the day of operation, and therefore the static route plan may not be able to meet our need. In this context, most researches have focused on the Dynamic Vehicle Routing Problem (DVRP) over the last decades. Different strategies have been proposed by scholars, being compared under specific demand pattern for each strategy, and it makes difficulty in deciding which strategies to be used under a general situation. In this thesis, the Dynamic Traveling Salemans Problem (DTSP) with single vehicle is considered as the basis. We focus on choosing adaptive strategies under different demand patterns, with temporal and spatial characteristics. Temporal characteristics consider uniform and peak time demand intensity over a day of operation, while spatial characteristic are uniform and non-uniform distributions of demands over different parts of the network. In our dynamic dispatching strategies, two kinds of basic route plans, NN (Nearest Neighborhood) and FCFS (First Come First Service), are considered. In combination with the route plans, five real-time dispatching concept (Basic, Reposition, Diversion, DDR, and DFR) are proposed. We use the C++ programming language to construct a simulation model for generating different scenarios of patterns and testing various strategies. The results show that each strategy performs observably differently. For the situation that a vehicle cannot accept another order after dispatched and on the way to reach a customer, the Reposition strategy can reduce the response time efficiently, with increasing the travel cost correspondingly. In contrast, the DDR strategy cuts the response time even more with less increase in overall travel cost. Therefore, the DDR strategy is suggested if the emphasis is on the Quality of Service. When there are no restrictions on the sequences of demand pickups, Diversion strategy is the only one which could simultaneously save both the response time and travel cost, under all demand patterns tested. The DFR strategy would require higher travel cost, but it could save a high percentage of response time among all proposed strategies, and therefore producing the best quality of service. In particular, it can save both the response time and travel cost under the situation of peak time interval and high demand intensity. Therefore, the DFR strategy is suggested if we put emphasis on quality of service, while the Diversion strategy should be used if we want to reduce operation cost. Keywords: Dynamic traveling salemans problem, Vehicle dispatching, Dispatching strategy, Heuristics.