非線性車輛路線問題之近似全域最佳化解法

Abstract

本篇文章提出一種方法, 在非線性車輛路線問題□, 求得近似全域最佳解 。首先, 先將非線性車輛路線問題所含之零壹變數轉換成連續變數, 再導 入 penalty function 的觀念, 而後再以 Multi-Level Single Linkage 為基礎, 找尋區域最佳解直到信賴水準為 99.5%以上。此種演 算法再結合平行處理的觀念, 使其於合理時間內求得近似全域最佳解。 A method has been proposed here for finding the global minimum of nonlinear vehicle routing problems. We first transform a nonlinear vehicle problem containing binary variables into a nonlinear program with continuous variables, based on the fact "iff x is a 0-1 variable then x - x2 = 0". Such a nonlinear program is then converted into a penalty function program. A stochastic global approach of searching most of the local optima in the penalty function program, based on the Multi- Level Single Linkage method, is performed to successfully find the approximated global optimum of the original nonlinear vehicle routing problem at a significant level of 99.5%. The solution algorithm is performed by parallel processes to reach approximately global optimal solution at reasonable time.