結合機器學習與模擬退火演算法求解機率旅行推銷員問題

Combining Machine Learning and Simulated Annealing for the Probabilistic Traveling Salesman Problem

機率性旅行推銷員問題(Probabilistic Traveling Salesman Problem, PTSP)為旅行推銷員問題之延伸，目標是找出一先驗路徑使期望距離最小。由於PTSP複雜性提升，求解難度困難許多，大多使用啟發式演算法求解。為更有效率計算期望距離，本研究以近似估算方法(approximate procedure)取代目標式值的精確算法；機器學習(Machine Learning, ML)的方法被運用於求解組合最佳化問題，輔助啟發式演算法進行參數預測或搜索區域的篩選。本研究利用深度神經網路(Deep Neural Network, DNN)，針對先驗路徑之期望值近似估算法進行參數設定，並將此估算方法應用於模擬退火演算法(Simulated Annealing, SA)的目標式值計算，以降低求解計算時間。經由測試文獻中均質及異質標竿例題，並與其他求解方法比較，所提的方法可以得到不錯的結果。未來可使用於物流業，減少新進人員學習時間。

The probabilistic traveling salesman problem (PTSP), a variant of the traveling salesman problem (TSP), only requires a subset of customers to be visited. Each customer is associated with a presence probability representing the likelihood that the customer will require a service within a given realization. The objective is to find a prior tour that minimizes the expected total travel distance. Due to PTSP’s NPhardness, most of the researches developed metaheuristic algorithms to solve the problem. In solving the PTSP, one difficulty is the computational complexity of the a priori expected length. Thus, we would apply an approximate procedure to estimate the objective function value and use machine learning (ML) to develop an approximate solution evaluation procedure to reduce the computational effort. Deep neural network (DNN) is used to estimate the needed parameter values. Combining DNN and simulated annealing (SA) algorithm is tested with homogeneous and heterogeneous PTSP benchmark instances. The results are compared with other heuristics from the literature. The results indicate that our proposed algorithm can obtain good results with less computational time. We hope the proposed algorithm can save times in training new drivers.