考慮重疊服務區域和隨機需求的最佳派送服務區域劃分問題

Optimal Delivery Districting Planning Problem with Overlapping Service Regions and Stochastic Demands

本研究提出一考慮隨機需求與廣義型重疊服務區域下之最佳區域劃分問題，其在允許多個區域可相互重疊的前提下，求解最小化長期期望營運總成本之服務區域劃分。本研究提出「貪婪演算法」、「禁忌搜尋演算法」及「禁忌搜尋演算法結合最佳計算預算配置法」三種方法進行求解。對於任一重疊區域劃分，乃在長期規劃時程中，先在每日採取蒙地卡羅模擬法實現所有顧客的隨機需求，運用基因演算法求解單日最佳車輛路徑規劃，再以所有單日營運總成本的平均值估算其目標函數值。實驗結果顯示貪婪演算法運算時間最短，且求得解目標函數的平均值也最低，故推薦其為合適的決策輔助工具。本研究亦驗證部分重疊區域劃分能獲得比明確區域劃分更低的營運成本。

This study proposes an optimal district planning problem considering stochastic demands and general overlapping service regions. In the context of allowing multiple regions to overlap with each other, the objective is to determine the optimal districting which minimizes the long-term expected operational cost. Three approaches, namely "Greedy Heuristic", "Tabu Search" (TS) Algorithm, and "Tabu Search Algorithm with Optimal Computing Budget Allocation"(TS+OCBA), are introduced for solving this problem. Each districting that can include overlapping service regions is evaluated by its long-term expected operational cost, an average daily total operating costs (DTOC) of all the days in the planning horizon. To obtain the DTOC of a particular day, this study employs Monte Carlo Simulation to realize all customers’demands and then solves the optimal vehicle routing problems with a genetic algorithm. Experimental results show that the Greedy Algorithm has the shortest computation time and achieves the lowest average objective function value, making it a recommended decision- supporting tool. Additionally, this study validates that partial overlapping districting can achieve a lower operational cost than conventional non-overlapping districting.