A Study on Solution Strategies for the Real-time Pickup and Delivery Routing Problem with Time Windows

[[abstract]]近年來貨運業逐漸將資訊通訊技術運用在車隊管理、車輛指派、調度系統營運作業上，使得具時間窗限制收送貨車輛路線問題（Pickup and Delivery Problem with Time Windows, PDPTW）的相關研究不再侷限於傳統的靜態問題，而是逐漸走向利用即時資訊的即時具時窗限制的收送貨路線問題(Real-Time Pickup and Delivery Problem with Time Windows, RT-PDPTW)，以更貼近現況與利於實務運用。本研究建立一模擬模式，並在滾動平面法架構下，比較文獻中常用的兩種RT-PDPTW求解策略：固定時間更新，與批次更新。這兩種求解策略下的演算法架構相同，都是利用最小成本插入法與交換法進行車輛路線更新，不同之處在於前者的滾動週期長度固定，後者的滾動週期長度則視隨機需求抵達的頻率而定。本研究在所建立的模擬系統中，探討不同臨時需求發生頻率、數量以及不同批次處理量與滾動週期長度對於這兩種求解策略的影響。模擬實驗結果顯示，在臨時需求抵達頻率與一般實務情形相當時，採用不同策略對於問題求解績效有顯著差異，整體而言，固定時間間隔更新策略之績效較批次更新績效差，但比批次更新策略較為穩定。此一系統化的比較分析，將有助於瞭解這兩種更新策略於不同情境下的適用性，以提供後續研究發展混合型求解策略之依據，並作為宅配物流業者推動商用車輛營運智慧化的參考。[[abstract]]Various solution algorithms have been proposed in the literature for solving the real-time vehicle routing problem. Most of them adopted the solution strategy of either batch updating or fixed-time-interval updating, while none of them intended to compare the performance of the two strategies. This study develops a simulation model to perform a systematic comparison of the two strategies in solving the real-time pickup and delivery (routing) problem with time windows (RT-PDPTW). The numerical results show that, in most cases, the batch updating mode provides better performance, while the solution quality of the fixed-time-interval updating mode is more stable