需求可分割車輛途程問題(Split Delivery Vehicle routing Problem, SDVRP)是傳統車輛途程問題(Vehicle routing Problem, VRP)的一種變型，他放寬了VRP問題中的限制條件，需求點的容量將可大於車輛的容量，且需求點能被不同車輛拜訪。每部車輛從廠站出發，最終回到場站，且所有需求點均需被拜訪，嘗試找出一個車輛路徑集合，每部車輛所載運量不超過車子容量限制且總距離成本最小。需求可分割車輛途程問題(SDVRP)目前已被證明為NP-Hard問題，一般的解決方法包含最佳解法(Exact Method)與啟發式法(Heuristic Method)。
本研究使用巨集啟發式演算法(Meta-Heuristic)求解SDVRP問題，針對不同啟發式演算法之特性結合與利用。第一階段先利用集群分析(Clustering Analyzing)將所有需求點依照相對位置加以分群，再利用基因演算法與蟻群演算法之優點所產生之改良式基因演算法，最佳化SDVRP問題中各路徑排序以求得起始可行解。第二階段使用禁制搜尋演算法、模擬退火演算法之概念，組合成三種不同的鄰域搜尋尋優演算法，逐步改進起始可行解求解需求可分割車輛途程問題。

Split Delivery Vehicle Routing Problem (SDVRP) is a variations of Vehicle Routing Problem (VRP). The vehicle must start from a specific depot and end at the exact same depot .Contrary to what is usually assumed about the Vehicle Routing Problem (VRP), each customer can be visited more than once and the demand of each customer may be greater than the vehicle capacity. The problem is trying to find a set of vehicle routes that serves all the customers with each route not exceeding the capacity of the vehicle and making the distance traveled at a minimum.
In this thesis, we proposed a meta-heuristic method to solve the Split Delivery Vehicle Routing Problem. For the benefits of heuristic algorithm, we try to combine and use it to solve our problem. In the first step, we use the concept of clustering analyzing to clustering the customer, then we use an algorithm that combine with Genetic Algorithm and Ant Algorithm to optimize each route in SDVRP. Next, we try using the concept of Tabu Search Algorithm and Simulated Annealing Algorithm to develop three new method to solve our problem. With the first and second steps, we are able to solve the Split Delivery Vehicle Routing Problem.

[1] Dantzig G.B. and Ramser J.H. The Truck Dispatching Problem Management Science, Vol.6,pp.80–91, 1959
[2] M. Dror, P. Trudeau. Savings by split delivery routing. Transportation Science,23: 141-145, 1989
[3] Archetti, C., M.W.P. Savelsbergh and M.G. Speranza. Worst-case analysis for split delivery vehicle routing problems. Transportation Science, Vol. 40, No. 2, pp. 226–234, 2006
[4] Archetti, C., M.W.P. Savelsbergh and M.G. Speranza. To split or not to split: That is the question. Transportation Research Part E, Vol. 44, No. 1, pp. 114-123, 2008
[5] S. Kumar and R. Panneerselvam. A Survey on the Vehicle Routing Problem and Its Variants. Intelligent Information Management, Vol. 4 No. 3, pp. 66-74, 2012
[6] Archetti, C., R. Mansini and M.G. Speranza,. Complexity and reducibility of the skipdelivery problem. Transportation Science, Vol. 39, No. 2, pp. 182-187, 2005
[7] C.G. Lee, M.A. Epelman, C.C. White III, Y.A. Bozer. A shortest path approach to the multiple-vehicle routing problem with split pick-ups. Transportation Research B, 40: 265–284, 2006.
[8] M. Jin, K. Liu, R.O. Bowden. A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem. International Journal of Production Economics, 105: 228–242, 2007
[9] Jin, M., Liu, K., Eksioglu, B. A column generation approach for the split delivery vehicle routing problem. Operations Research Letters 36, 265–270, 2008
[10] Archetti, C., Bouchard, M., Desaulniers, G. Enhanced branch-and-price-and-cut for vehicle routing with splitdeliveries and time windows. Transportation Science, 2011
[11] Archetti, Claudia; Bianchessi, Nicola; Speranza, M. Grazia. Branch-and-cut algorithms for the split delivery vehicle routing problem , European Journal of Operational Research. Vol. 238.2014, 3, p. 685-698, 2014
[12] C. Archetti and M. G. Speranza. Vehicle routing problems with split deliveries. International Transactions in Operational Research, 19,pp.3-22, 2012
[13] Archetti, C., A. Hertz and M.G. Speranza. A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science, Vol. 40, No. 1, pp. 64–73, 2006
[14] M.Boudia, C.Prins, and M.Reghioui. An Effective Memetic Algorithm with Population Management for the Split Delivery Vehicle Routing Problem. In Hybrid metaheuristics, T. Bartz-Beielstein,M.Blesa Aguilera, C. Blum , B. Naujoks, A.Roli, G.Rudolph, M. Samples, eds.,4771 of Lecture Notes in Computer Science , Springer,Berlin,Heidelberg,pp.16-30, 2007
[15] Chen, S., B. Golden and E. Wasil. The split delivery vehicle routing problem:Applications, algorithms, test problems, and computational results. Networks, Vol. 49, No. 4,318–329, 2007
[16] Aleman, R.E., X. Zhang and R.R. Hill. An adaptive memory algorithm for the split delivery vehicle routing problem. Journal of Heuristics, Vol. 16, No. 3, pp. 441-473, 2010
[17] E. Mota, V. Campos, A. Corb´eran. A new metaheuristic for the vehicle routing
problem with split demands. in Evolutionary Computation in Combinatorial Optizmization, C.Cotta and J,van hemert,eds.,vol.4446 of Lecture Notes in Computer Science ,Springer, Berlin,heidelberg,pp.121-129, 2007
[18] J.H.Wilck IV and T.M.Cavalier. A construction heuristic for the split delivery vehicle routing problem ,American Journal of Operations Research,2 pp.153-162, 2012
[19] Belenguer, J.M., Martinez, M.C., Mota, E. A lower bound for the split delivery vehicle routing problem.Operations Research 48, 801–810, 2000
[20] 陳家慧 「結合改良式基因演算法和蟻群演算法求解推銷員旅行問題」國立臺灣科技大學資訊管理研究所論文 民國101年
[21] Ho, S. and D. Haugland. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computer and Operational Research, Vol. 31, No. 12, pp.1947–1964, 2004