隨著無線通訊技術和手持智慧裝置的快速發展，人們可以隨時隨地的獲取他們所需要的商品資訊，並進行購買。這樣子的消費模式使得越來越多貨物需要透過物流業者來做配送，同時也帶動了物流業的營收，使得城市物流規劃受到關注，並開始研究該如何規劃出適合的物流路徑。在城市物流規劃中，除了要能在營業時間內完成收送貨需求，還必須在顧客所指定的時間拜訪客戶，更重要的是減少所使用的車輛以及縮短行駛路徑，盡可能有效率的完成規劃及需求。關於城市物流規劃這個議題，過去已有不少學者提出根據不同的狀況限制提出方法，為了能將成本減少到最低，大多研究方法採用迭代式演算法，經過長時間的計算，記錄過程中所計算的路徑趨勢，找出最低成本的路徑。然而即使能找出近似最佳解的路徑，對於要及時運算產生路徑的狀況時，迭代類型的演算法無法有效的收斂並規劃出成本較低的路徑。因此本研究中提出了兩種方法，皆能在極短的時間內盡可能減少物流成本，規劃出有效率的物流路徑。據我們所知，現行台灣物流業者將收送需求分為兩階段處理，由於人手限制，並無法在顧客所指定的時間內拜訪，為了探討此種收送類型的物流規劃，本研究首先在沒有時間窗限制需求下，提出一個三階段的規劃架構，將配送貨物需求分群，並進行路線規劃，最後再將收貨需求安插到適合的路徑順序中，各個階段皆有多種策略提供規劃。另外探討帶有時間窗的收送規劃，本研究提出一個基於遞迴架構的方法，當中採用了不同策略用以挑選顧客在路徑中的拜訪順序，並設計了調整機制，記錄挑選成本有利於更改已完成規劃的拜訪順序。在實驗評估上，採用了嘉里大榮提供的點位資料，為求完整欄位進行部分欄位模擬，用以評估各種方法中不同策略的成本結果，採用最佳策略，在調整物流參數的設定下與其他物流規劃的方法進行比較，本研究的方法在規劃速度與品質上皆有出色的成果。

As urban people get increasingly busy, more and more people prefer online shopping. The online shops provide a convenient platform and usually launch some promotion activities for people receive product information and buy them anytime anywhere. The change of shopping behavior leads to a large number of goods need to be transported and grows up the revenue of logistics. Therefore, there is a topic named Urban Logistics attracts the attention from companies. As the amount of goods increase, the quality of service may decrease with a worse routing planning. Moreover, people live in urban get busier. Considering the specified time of customers, it is difficult to find a high quality solution. In Urban Logistics, the tasks are to distribute the goods to corresponding customers efficiently, pick-up goods from customers in their specified time window and finish requirements of customers in business hours. The objective is to minimize the logistics cost which consists of used vehicles and travel distances as much as possible. As we know in the Taiwan urban logistics environment, it is difficult to visit customers in their specified time window under limited resources. Therefore, we propose two efficient approaches to solving Urban Logistics under time constraint or not and compare with some routing strategies. In this thesis, we design Partition-Routing-Insertion Navigator (PRI-Navigator) and Pool-based Recursive Constructor (PRC) for finding high quality logistics routes by considering real logistics constraints. In PRI-Navigator, we design various strategies and algorithms for goods partition, route planning and goods insertion. PRC consists of an urgent value measurement, several customer selection strategies and a pool-based mechanism. We use them to calculate the cost of each customer and select the most suitable customer for route constructing, recursively. To evaluate the performance of algorithms we proposed, we have two phase experiments based on four semi-real logistics datasets which are collected from KERRY TJ Logistics. The experimental results show that the performance of PRI-Navigator and PRC under various customer selection strategies all outperforms the other routing strategies in terms of route’s quality.

[1] A. Bortfeldta, T. Hahnb, D. Mannela and L. Monch, "Hybrid Algorithms for The Vehicle Routing Problem with Clustered Backhauls and 3D Loading Constraints," European Journal of Operational Research, vol. 243, no. 1, pp. 82-96, 2015.
[2] J. Belloso, A. A. Juan, J. Faulin and A. Serrano, "Using Multi-Start Biased Randomization of Heuristics to Solve The Vehicle Routing Problem with Clustered Backhauls," Lecture Notes in Management Science, vol. 7, pp. 15-20, 2015.
[3] R. Bent and P. V. Hentenryck, “A Two-Stage Hybrid Algorithm for Pickup and Delivery Vehicle Routing Problems with Time Windows,” Computers & Operations Research, vol. 33, pp. 875-893, 2006.
[4] A.-L. Chen, G.-K. Tang and Z.-M. Wu, "Hybrid Discrete Particle Swarm Optimization Algorithm for Capacitated Vehicle Routing Problem," Journal of Zhejiang University-SCIENCE A, vol. 7, pp. 607-614, 2006.
[5] R.-M. Chen, F.-R. Hsieh and D.-S. Wu, "Heuristics Based Ant Colony Optimization for Vehicle Routing Problem," in ICIEA, pp.1039-1043, 2012.
[6] G. B. Dantzig and J. H. Ramser, "The Truck Dispatching Problem," Management Science, vol. 6, pp. 80-91, 1959.
[7] T.A. Feo and M.G.C. Resende, “Greedy Randomized Adaptive Search Procedures,” Journal of Global Optimization, vol.6, pp. 109-133, 1995.
[8] M. Goetschalckx and C. J. Blecha, "The Vehicle Routing Problem with Backhauls," European Journal of Operational Research, vol. 42, no. 1, pp. 39-51, 1989.
[9] R. A. Jarvis, "On The Identification of The Convex Hull of A Finite Set of Points in The Plane," Information Processing Letters, vol. 2, pp. 18- 21, 1973.
[10] KERRY TJ Logistics, http://www.kerrytj.com/en/default.aspx.
[11] M. Lai, M. Battarra, M. D. Francesco and P. Zuddas, "An Adaptive Guidance Meta-Heuristic for the Vehicle Routing Problem with Splits and Clustered Backhauls," Journal of the Operational Research Society, vol. 66, pp. 1222-1235, 2015.
[12] K. Menger, "Das Botenproblem," Ergebnisse Eines Mathematischen Kolloquiums, vol. 2, pp. 11-12, 1932.
[13] L. Mingyong and C. Erbao, “An Improved Differentail Evolution Algorithm for Vehicle Routing problem with Simultaneous Pickups and Deliveries and Time Windows,” Engineering Applications of Artificial Intelligence, vol. 23, pp. 188-195, 2010.
[14] M. Nawaz, E. Enscore, I. Ham, “A Heuristic Algorithm for the m Machine, nJob Flow Shop”. OMEGA: The International Journal of Management Sciences, vol.11, No.1, pp. 91-95, 1983.
[15] I. H. Osman, "Metastrategy Simulated Annealing and Tabu Search Algorithms for The Vehicle Routing Problem," Annals of Operations Research, vol. 41, pp. 421-451, 1993.
[16] M.W.P. Savelsbergh, M. Sol, “The General Pickup and Delivery Problem,” Transportation Science, vol. 29 , pp. 17-29, 1995
[17] B. Tunjongsirigul and P. Pongchairerks, "A Genetic Algorithm for A Vehicle Routing Problem on A Real Application of Bakery Delivery," in ICECT, pp. 214-217, 2010.
[18] Web Services of Google Maps APIs, https://developers.google.com/maps/web-services/
[19] C. Wang, D. Mu, F. Zhao and J. W. Sutherland, “A Parallel Simulated Annealing Method for the Vehicle Routing Problem with Simultaneous Pickup-Delivery and time Windows,” Computers & Industrial Engineering, vol. 83, pp. 111-122, 2015.
[20] H.-F. Wang and Y.-Y. Chen, “A Genetic Algorithm for the Simultaneous Delivery and Pickup Problems with Time Window,” Computer & Industrial Engineering, vol. 62, pp. 84-95, 2012
[21] B. Yu, Z.-Z. Yang and B. Yao, "An Improved Ant Colony Optimization for Vehicle Routing Problem," European Journal of Operational Research, vol. 196, pp. 171-176, 2009.
[22] T. Zhang, W. A. Chaovalitwongse and Y. Zhang, “Integrated Ant Colony and Tabu Search Approach for Time Dependent Vehicle Routing Problems with Simultaneous Pickup and Delivery,” Combinatorial Optimization, vol.28, pp. 288-309, 2014.