運用基因演算法及最佳化資源分配法求解隨機需求之長期車輛問題

Abstract

自從Dantzig和Ramser於1959年提出車輛路線問題(Vehicle Routing Problem, VRP)後，許多學者均致力研究該問題及其相關變形，然而由於實務中存在許多不確定性，故近年來越來越多的研究均將研究重心轉向於求解含隨機性的車輛路線問題(Stochastic Vehicle Routing Problem, SVRP) 根據本研究訪談台灣某一國際快遞業者之結果，為了避免顧客被遺漏服務而發生責任歸屬不明的情形，其營運方式主要採責任分區制，亦即每位運務員會針對自己被分配到的服務區，進行路線規劃，以滿足該責任區之內所有顧客之需求。值得注意的是，在現實世界中，每個顧客的需求是一個隨機變數，並非固定不變的，因此可能發生當日需求為零的情形，如此運務員則不須拜訪該顧客點，可直接前往下一據點取件，以節省相關運輸成本。再者，每台車輛有容量的限制，一旦顧客需求超出車輛容量上限時，就必須採取補救措施，進而產生額外的成本。然而每天重新依實際情形規劃拜訪路線相當耗費成本，且由行為面向而言，運務員偏好每天拜訪順序固定，如此可更了解該責任區，也更加安全。故本研究欲運用一套更有系統的決策方法協助進行路線規劃，建議國際快遞業之運務員在長期之下一條固定的最適服務路線，使平均運輸總成本達最低。 針對本研究之情境，本研究建立一數學模式，提出運用基因演算法(Genetic Algorithm, GA)求解最佳拜訪順序，且由於本研究含隨機性，故運用蒙地卡羅模擬法以驗證實驗結果(Monte Carlo Simulation, MCS)，並結合最佳化計算資源分配法(Optimal Computing Budget Allocation, OCBA)提升求解效率。研究結果顯示本研究提出之求解演算法之求解品質較最近鄰點法(Nearest Neighbor, NN)好，最後依數值測試結果提出實務上之建議。

Since Vehicle Routing Problem (VRP) was introduced by Dantzig and Ramser in 1959, numerous research efforts have been devoted to it and its variants. However, as there are full of uncertainties in real world, more and more researches have focus on stochastic versions of the VRP in recent years. According to one of global forwarding companies in Taiwan, in case of not knowing who should be responsible for some customers being omitted, each driver has been assigned a “responsible region” to satisfy every customer’s demands in his region. Besides, in practice, customer’s demand is a random variable, which means it may be zero in a certain day, in order to save traveling cost, driver doesn’t need to visit those who have zero demand, just heading to next customer directly to save traveling cost. Moreover, cars have capacity limits, whenever customer’s demand exceeds car’s capacity, we called it route failure, which will cause extra cost to take recourse action. However, it will cost a lot if global forwarder want to reschedule driver’s visiting route based on the actual situation every day. In addition, stochastic models also arise naturally in situations where routes are planned for a long planning horizon but executed repeatedly during that horizon. Therefore, in this research, we focus on a single responsible region (single vehicle) and customers have stochastic demands, under this scenario, we formulate a mathematical modal and propose a hybrid algorithm which is combined with Genetic Algorithm (GA), Monte Carlo Simulation (MCS) and Optimal Computing Budget Allocation (OCBA) trying to find a near optimal solution in a reasonable time which can suggest the global forwarder a fixed visiting route to save total cost. According to the results of numerical test, we found this algorithm preforms much better than nearest neighbor algorithm, and based on these results, we give some suggestions to the real world.