國際快遞業運務員最適取件路線規劃問題

Abstract

For the international express service industry, it is very important to deliver goods or provide services efficiently. The efficiency of pick-up service is mainly influenced by the courier route design. The presence of uncertain customer demands creates the need to design a priori tour instead of finding an optimal tour everyday. We formulate and analyze a probabilistic traveling salesman problem (PTSP) with route length restrictions. The classical PTSP is defined as a problem of finding a prior tour of expected minimum length, with the strategy of visiting a random set of customers in the same order as they appear in the prior tour. Instead of finding a prior tour of expected minimum length as the classical PTSP does, we wish to find a prior tour of minimum probability of that the route length exceeds a given threshold. An evolution heuristic solution method is developed to find a near-optimal solution. The approximation of objective function is estimated by means of Monte Carlo sampling. In test problems for which exact solutions created by enumeration are available, the heuristic solution produces good solutions. The computation procedure appears to hold substantial promise for effective solution of practical applications. 國際快遞業首重遞送物品的「時效性」，對快遞業者而言，延後截件時間及 提早送達的服務承諾，即是時效性的表現，惟有高效率的取件作業，才能實現這 樣的服務承諾；取件作業效率取決於運務員取件路線規劃之良莠。因此，本研究 探討國際快遞業者面對顧客需求不確定因素下，如何就固定責任區域取件的運送 方式，規劃出運務員最適取件路線，降低延遲送達率，實現服務承諾。本研究對 具總路徑旅行時間限制之運務員隨機取件路線規劃問題，提出明確的定義，並建 構其數學模式，同時利用基因演算法求解，及以蒙地卡羅模擬計算模式目標值之 近似值，並以系列測試問題探討求解品質及時間，最後依個案實際資料規劃運務 員最適取件路線。