快遞產業的車輛路線最佳服務分區設計

Abstract

本研究針對國際快遞業者之取貨服務過程中，運務員由倉庫出發進行取件服務並返回倉庫的作業情境進行探討。在分區問題方面，本研究依照每一分區的服務量均衡以及平均服務量的上限之原則，將歸屬於倉庫之顧客點劃分為數個服務分區，每一分區僅由負責之單一運務員駕駛單一車輛進行服務。在路線規劃方面，每一顧客點僅歸屬於單一服務分區，且顧客需求量具有隨機性、車輛具有容量上限，且對於當日沒有需求的服務據點，運務員不需進行拜訪而直接前往下一個據點。本研究乃希望為國際快遞業者進行服務分區及車輛路線進行最佳長期性規劃，針對每一運務員設計一個專屬之服務分區，且單一分區內包含一條長期 (如：半年或一年) 固定之最適車輛路線，希望能達到最小化平均期望總成本的目標。針對上述情境，本研究建立決策對應之數學模式，提出結合「運用禁制搜尋法求解分區問題」及「運用混合式基因演算法與最佳化計算資源分配法(有效分配蒙地卡羅模擬所需之計算資源) 求解隨機性車輛路線問題」的整合性求解演算架構。本研究運用文獻標竿範例，進行數值測試顯示本研究提出整合性求解演算架構相對於起始解，都有約10％以上之改善率，而對於小型的R型（需求點均勻分配）例題，改善幅度最為顯著，顯示本研究的啟發式演算法之搜尋效能良好。

This study focuses on the pick-up process of an international courier company, in which a courier starts a tour from the depot and ends by picking up the demand of the last customer point in a designated route. For the service-area districting aspect, we take into account the loading balance between each depot and a restriction of an upper bound on the service loading of a depot. Also, we divide the service area of a depot into many sub-service areas, and a courier pairing with a single vehicle conducts the pick-up service in each sub-service area. For the vehicle routing aspect, we assume that a demand point belongs to only one sub-service area, the customers’ demand is stochastic, an upper bound applies to the vehicle loading capacity, and the courier may go to the next demand point in the route without visiting a demand point with zero demand for a particular day. This study assists an international courier company in its long-term planning of the optimal service-area districting of each deport and the optimal vehicle route corresponding to each sub-service area. A courier uses an optimal route, which is fixed for a long period of six months to a year, for the pick-up service in each sub-service area to minimize the expected average total costs incurred in the responsible sub-service area. For our decision-making scenario above, we formulate the corresponding mathematical models, and propose an integrated solution approach that employs (1) a tabu search algorithm for solving the optimal districting problem and (2) a hybrid Genetic Algorithm (GA) utilizing an Optimal Computing Budget Allocation (OCBA) procedure, that effectively allocates the computing loading as evaluating solutions using Monte Carlo Simulation. Taking the benchmark instances in the literature, we tested the effectiveness of the proposed integrated solution approach. Our numerical results show that our approach is able to achieve an improvement for more than 10% from its initial solution, and the improvement is notable, especially for those small-size R-type problems (in which the demand points are evenly distributed geographically in the planning region). We conclude that the proposed integrated solution approach serves as a good one for the optimal service-area districting and vehicle routing for the pick-up service of an international courier company.