臺灣博碩士論文加值系統

在物流派車問題中，我們對車隊分配與路程規劃做最佳化的求解。
k-mean 分群法為群集式演算法，而在車隊分配問題中，我們希望以每輛車的配送負擔平均為目標求其最佳解，故以此演算法為基礎，在其對點做分配的的步驟中增加了對群體內個數做限制及對資料點的篩選條件。

接著對k群分別求經過群體內的所有點的最短路徑，即旅行推銷員問題(TSP)。此問題為一 NP-Hard 問題，精確解須以分支定界法或窮舉法求得，因此我們先以「對角線完全算法」建構出一條可行的漢彌爾頓路徑，再由二邊逐次修正法及 Feiring 矩陣逐次修正法修正得到近似解。
其中若群體內的點數量為n，則二邊逐次修正法的計算量為O( n^2)且其演算法過程無法平行化，所以我們考慮兩種方法改良了二邊逐次修正法的演算法，使其演算法可利用MPI做平行計算，若使用p個處理器，則計算量可預期減少至O( n^2/p)。

We consider finding the near-optimized solution of logistic''s vehicle routing problem includes grouping of customers and travelling salesman problem.
We try to balance the number of customers for each vehicle. According to k-mean clustering algorithm, we add restrictions of the number of each cluster and conditions of distributing each customer to achieve our target.

After that, we want to find a near-shortest route passing through all the customers for each cluster. This problem is a travelling salesman problem, has been proved to be an NP-hard problem that exact solution should be got by exhaustion method or branch and bound method. Therefore, we use Diagonalize Complete Algorithm to construct a feasible Hamiltonian path, and then using 2-opt and Feiring algorithm to get a shorter path. Among these algorithm, if the number of cluster is n, then the computing of $2$-opt algorithm is O( n^2 ) and can not be parallelable, so we consider two different way to modify the algorithm to do parallel computing with MPI. That is, if we use p processes in MPI, then it can reducing the computing to O( n^2/p ).

論文審定書
序言或誌謝iii
摘要iv
Abstract v
目錄v
1 Introduction 1
2 Problem Statement 2
2.1 Vehicle Routine Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3 Clustering Algorithm 4
3.1 K-mean Clustering Algorithm . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Modified k-mean Clustering Algorithm . . . . . . . . . . . . . . . . . . 5
4 Travelling Salesmen Problem 8
4.1 Diagonalize Complete Algorithm . . . . . . . . . . . . . . . . . . . . . . 8
4.2 2-Opt Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2.1 2-Opt Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2.2 Parallelable 2-Opt Algorithm with Evaluating the Maximum Difference.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2.3 Parallelable 2-Opt Algorithm with Counting the Number of Intersection
Point. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3 Feiring Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
vi
5 Numerical Result 23
5.1 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

[1]Clarke G, Wright J., Scheduling of vehicles from central depot to a number of delivery
points, 1964, 12:568 581.
[2] Dantzig, Geroge Bernard and Ramser, John Hubert., The Truck Dispatching Problem,
Management Science, 1959.
[3] Feiring, An efficient procedure for obtaining feasible solutions to the n-city traveling
salesman problem. Mathematical and Computer Modelling, 1990.
[4] Fisher M L., Handbooks in Operations Research and Management Science, 1995.
[5] Holland J, Adaptation In Natural and Artificial Systems, 1975.
[6] Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman
problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
[7] William J. Cook,William H. Cunningham,William R. Pulleyblank, Alexander Schrijver,
Combinatorial Optimization, John Wiley & Sons.
[8] 龔劬, 圖論與網絡最優化, 重慶大學出版社, 1998.
[9] 江林翰, Accelerating the search of near-optimal solutions of vehicle routine problems
with parallel computation, master thesis, 2014.