企業在現今激烈的競爭環境下想要增加獲利，除了提高銷售量及降低生產成本外，另一方面就是提升物流的效率。因此，企業必須提供有效率的物流運籌網路來因應快速的顧客回應需求，考慮具有容量限制回程取貨之車輛途程問題(Capacitated Vehicle Routing Problem with Backhaul, CVRPB)，最主要的目的在於使車隊取貨、送貨、至顧客手上收貨送回供應商的車輛運輸路徑之距離最小化，以達到最低運輸成本以及減少運輸時間浪費的目標。
本研究提出以帝國主義競爭演算法(Imperialist Competitive Algorithm)結合節省法(Saving Method)的啟發式演算法，稱為SavICA演算法，對具有回程取貨與具有容量限制的車輛途程問題(CVRPB)快速提出一個近似最佳解，主要目標在於滿足所有限制條件下，達到總成本（運輸及營運）的最小化。為了驗證所提出的SavICA演算法的效能，本研究與基因演算法做比較，延伸了60組車輛取貨與交貨運途的標竿問題(CVRPPDTW)為回程取貨之車輛途程問題CVRPB問題，在每一組標竿問題中，本研究的SavICA演算法都能找出比基因演算法更好的最佳成本解，總平均成本改善率達到25.21%。相較於基因演算法，本研究所提出的SavICA演算法呈現出具有相當穩健、更快收斂到近似最佳解和有效搜尋全域最佳解的能力。

Enterprises want to make profits in the extremely competitive environment. In addition to expanding sales and reducing manufacturing cost, the efficiency of logistics management is also considered as the additional source of profit. Increasing efficiency of logistics becomes critical in the supply chain due to customer’s quick response requirements. This thesis focuses on the capacitated vehicle routing problem with backhaul (CVRPB) aiming at the shipments in pickup, delivery and go-back’s vehicle transporting distance minimally. The collective effort of CVRPB is to fulfill minimal transport cost and reduce vehicle travel time.
This algorithm, called SavICA, is proposed in thesis to solve the combinatorial optimal solution of the CVRPB problems. The SavICA method is based on the new developed Imperialist Competitive Algorithm combined with the saving method to quickly generate a near optimum solution. Comparisons are made between the proposed method and the Genetic Algorithm (GA) over the experiments of various CVRPB problems, extended from Capacitated Vehicle Routing with Pickup and Delivery with Time Windows (CVRPPDTW) benchmark problems, to validate the performance of the proposed algorithm. Experiment results show that the SavICA algorithm was able to discover new solutions than the GA for all 60 benchmarks problems. Also, the computational results show that the SavICA algorithm is robust, converge fast and competitive with overall improvement of 25.21% over the GA.

Anbuudayasankar, S.P., Ganesh, K., Koh, S.C.L., & Ducq, Y. (2012). Modified savings heuristics and genetic algorithm for bi-objective VRP problem with backhauls. Expert Systems with Applications, 39(1), 2296-2305.
Apte, U.M., & Viswanathan, S. (2002). Strategic and technological innovations in supply chain management. International Journal of Manufacturing Technology and Management, 4, 264-282.
Atashpaz-Gargari, E., & Lucas, C. (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. IEEE Congress on Evolutionary Computation, 4661-4667.
Behnamian, J. & Zandieh, M. (2011). A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadratic tardiness penalties, Expert Systems with Applications, 38(1), 14490–14498.
Casco, D., Golden, B., & Wasil, E. (1988). Vehicle routing with backhauls: Models, algorithms and case studies, in: Golden, A., and Assad, A. (Eds.), Elsevier Science Publishers, Amsterdam, 127-147.
Christopher, M., (1985). Logistics and supply chain management: strategies for reducing cost and improving customer service, Pitman Publishing, Singapore.
Dantzig, G.B., & Ramser, J.H. (1959). The truck dispatching problem, Management Science, 6(1), 80-91.
Deif, I. & Bodin, L., (1984). Extension of the Clarke and Wright algorithm for solving the vehicle routing with backhauling, in: Kidder, A. (Ed.), Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management, Babson Park, 75-96.
Haghani, A., & Jung, S., (2005). A dynamic vehicle routing problem with time-dependent travel times. Computers & Operations Research, 32(11), 2959-2986.
Halse, K., (1992). Modelling and solving complex vehicle routing problems, The Technical University of Denmark.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, MI.
Hsieh, P.F. (2003). Basic information of warehousing and logistics industries. Taiwan Institute of Economic Research, December 16.
Hwang, H. S. (2002). An improved model for vehicle routing problem with time constraint based on genetic algorithm. Computers & Industrial Engineering, 42(2-4), 361-369.
Javadian, N., Khorshidian, H., Rezaeian, J., & Rahmani, K. (2011). Single machine preemptive scheduling by hybridized meta-heuristic approach. 2011 IEEE 3rd International Conference on Communication Software and Networks (ICCSN), 750-753.
Kellegoz, T., Toklu, B., & Wilson J. (2008). Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem, Applied Mathematics and Computation, 199 (2008) 590–598.
Lalonde, B.J., & Zinszer, P.H. (1976). Customer service: meaning and measurement, National Council of Physical Distribution Management, USA.
Laporte, G., Nobert, Y., & Desrochers, M. (1984). Optimal routing under capacity and distance restrictions. Operations Research, 33(5), 1050-1073.
Laporte, G., & Osman, I. H. (1995). Routing problems: A bibliography. Annals of Operations Research, 61, 227-262.
Laporte, G. (2009). Fifty Years of Vehicle Routing, Tranceportation Science, 43(4), 408-416.
Mamaghani, A.S. & Meybodi, M.R. (2011). An application of imperialist competitive algorithm to solve the quadratic assignment problem, IEEE, 11-14.
Mingyong, L., & Erbao, C. (2010). An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows. Engineering Applications of Artificial Intelligence, 23(2), 188-195.
Mosheiov, G. (1998). Vehicle routing with pick-up and delivery: tour partitioning heuristics, Computers & Industrial Engineering, 34(3), 669-684.
Ochi, L.S., Vianna, D.S., Drummond L.M.A., & Victor, A.O. (1998). An evolutionary hybrid metaheuristic for solving the vehicle routing problem with heterogeneous fleet. Lecture Notes in Computer Science, 1391, 187-195.
Pan, S., Ballot, E., Fontane, F., & Hakimi D. (2014). Environmental and economic issues arising from the pooling of SMEs’ supply chains: case study of the food industry in western France, Springer, 26(1), 92-118.
Purnomo, H.D., Wee, H.M., & Praharsi, Y. (2012). Two inventory review policies on supply chain configuration problem. Computers & Industrial Engineering, 63(2), 448-455.
Salhi, S., & Nagy, G. (1999).A cluster insertion heuristic for the single and multiple depot vehiclerouting problems with backhauls. Journal of the Operational Research Society, 50(10), 1034-1042.
Toth, P., & Vigo, D. (2001). The vehicle routing problem. Monographs on Discrete Mathematics and Applications, Philadelphia, PA: SIAM.
Wade, A.C. & Salhi, S., 2002. An investigation into a new class of vehicle routing problem with backhauls, Omega, 30, 479-487.
Zachariadis, E. E., Tarantilis, C. D., & Kiranoudis, C. T. (2010). An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries. European Journal of Operational Research, 202(2), 401-411.