臺灣博碩士論文加值系統

公司在競爭激烈的環境下想要提高獲利，除了降低生產成本及提高銷售量之外，最重要的就是提升物流的效率。因此，企業必須提供有效率的物流運籌網路來因應快速的顧客回應需求。一般物流管理中，最簡單的問題是車輛運途問題，是從旅行銷售員問題演變而來，因此本論文導入最新的仿生物演算法，研究最基本的具容量限制之車輛運途問題，最主要的目標就是最小化車輛行駛距離，減少運輸時間的浪費。
本研究提出基植於蜂群演算法(Artificial Bee Colony)結合掃描法(Sweep Method)的混合式蜂群演算法，稱為sABC 演算法，對具有容量限制的車輛運途問題快速提出一個近似最佳解，主要目標在於滿足所有限制條件下，達到總成本（運輸及營運）的最小化。為了驗證所提出sABC演算法的效能，本研究與基因演算法做比較，求解60組不同車輛容量下運途的標竿問題，本研究的sABC演算法都能找出比基因演算法更好的最佳成本解，總平均成本改善率達到23.75%。相較於基因演算法，我們所提出的sABC演算法呈現出具有相當穩健、快速收斂至最佳解及有效搜尋全局最佳解的能力。

Companies would like to make profits in the awfully competitive environment. In addition to reducing manufacturing cost and expanding sales, the efficiency of logistics management is also considered as the additional source of profit. Increasing efficiency of logistics becomes important in the supply chain owing to customer’s quick response requirements. In the general logistics management, the basic problem is the Vehicle Routing Problem (VRP) which is extended from the Travelling Salesman Problem. Therefore, we develop a novel artificial biological algorithm to solve the Capacitated Vehicle Routing Problem (CVRP) which is a basic variation form the VRP. This thesis focuses on the CVRP aiming at finding the shortest routes and decreasing the transportation time.
The hybrid algorithm, called sABC, is proposed in this thesis to solve the combinatorial optimal solution of the CVRP. The sABC method is based on the new developed Artificial Bee Colony combined with the sweep method to quickly generate a near optimum solution. Comparisons are made between the sABC method and the Genetic Algorithm (GA) over the experiments of different capacitated benchmark problems to validate the performance of the sABC algorithm. Each set of the 60 instances contains 100 nodes. Three test sets, call G1, G2 and G3, have been used to analyze the effect of vehicle-related constraints. Experiment results show that the sABC algorithm was able to discover new solutions than the GA for all 60 benchmarks problems. Moreover, the computational results show that the sABC algorithm is robust, converge fast and competitive with overall improvement of 23.75% over the GA.

摘要
ABSTRACT
ACKKNOWLEDGEMENTS
CONTENTS
FIGURES
TABLES
CHAPTER 1 INTRODUCTION
1.1 Research Motivation
1.2 Research Objectives
1.3 Research Structure
CHAPTER 2 LITERATURE REVIEW
2.1 Logistics Management
2.2 Vehicle Routing Problem
2.2.1 VRP Problems with Various Constraints
2.2.2 Different Methods for the VRP
2.3 Genetic Algorithm (GA)
2.4 Artificial Bee Colony Algorithm (ABC)
CHAPTER 3 PROBLEM FORMULATION AND ARTIFICAIL BEE COLONY ALGORITHM
3.1 Problem Proposition
3.2 The Sweep Method
3.3 The General Artificial Bee Colony Algorithm Procedure
3.4 The Proposed sABC for the CVRP
3.4.1 Solution Representations
3.4.2 Transform
3.4.3 Neighborhood Operators
3.4.4 sABC in VRP Procedure
CHAPTER 4 COMPUTATIONAL EXPERIMENTS
4.1 Preliminary Test and Parameters Setting
4.2 Computational Results
4.3 Summary
CHAPTER 5 COCLUSIONS AND FUTURE RESEARCH
5.1 Conclusions
5.2 Future Research
REFERENCES
Appendix A. Comparisons between sABC and GA in CVRP
Appendix B. The Results of the sABC for Benckmark Problem G3

Afsar, H. M. (2010). A branch-and-price algorithm for capacitated arc routing problem with flexible time windows. Electronic Notes in Discrete Mathematics, 36, 319-326.
Aguilar-Escobar, V. G., & Garrido-Vega, P. (2013). Lean logistics management in healthcare: A case study. Revista de Calidad Asistencial, 28(1), 42-49.
Alba, E., & Dorronsoro, B. (2006). Computing nine new best-so-far solutions for Capacitated VRP with a cellular genetic algorithm. Information Processing Letters, 98(6), 225-230.
Alireza, S., & Alagheband, S. (2011). Logistics Parties. Department of Industrial Engineering, Amirkabir University of Technology, Tehran, Iran.
Alvarado-Iniesta, A., Garcia-Alcaraz, J. L., Rodriguez-Borbon, M. I., & Maldonado, A. (2013). Optimization of the material flow in a manufacturing plant by use of artificial bee colony algorithm. Expert Systems with Applications, 40, 4785-4790.
Alvarenga, G. B., Mateus, G. R., & de Tomi, G. (2007). A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Computers and Operations Research, 34(6), 1561-1584.
Anbuudayasankar, S. P., Ganesh, K., Lenny Koh, S.C., & Ducq, Y. (2012). Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls. Expert Systems with Applications, 39(3), 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.
Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem, Computers & Operations Research, 30(5), 787-800.
Baker, B. M., & Ayechew, M.A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800.
Baldacci, R., Hadjiconstantinou, E., & Mingozzi, A. (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operations Research, 52(5), 723-738.
Balinski, M., & Quandt, R. (1964). On an integer program for a delivery problem. Operations Research, 12, 300-304.
Barbarosoglu, G., & Ozgur, D. (1999). A tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 26(3), 255-270.
Bell, J. E., & McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18(1), 41-48.
Bhagade, A. S., & Puranik, P. V. (2012). Artificial bee colony (ABC) algorithm for vehicle routing optimization problem. International Journal of Soft Computing and Engineering (IJSCE) ISSN, 2(2), 2231-2307.
Brajevic, I. (2011). Artificial bee colony algorithm for the capacitated vehicle routing problem. Proceedings of the European Computing Conference, 239-244.
Cai, X., Chen, J., Xiao, Y., Xu, X., & Yu, G. (2013). Fresh-product supply chain management with logistics outsourcing. Omega, 41(4), 752-765.
Chen, N., & Xue, H. (2012). The study on the performance evaluation of the lean supply chain in chain retailers. Proceedings - 2012 International Conference on Computer Science and Service System, CSSS 2012, 1393-1396.
Chow, H. K. H., , Choy, K. L., Lee, W. B., & Chan, F. T. S. (2005). Design of a knowledge-based logistics strategy system. Expert Systems with Applications, 29(2), 272–290.
Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle dispatching problem. Operational Research Quarterly, 20(3), 309-318.
Christofides, N., Mingozzi A., & Toth P. (1981). Exact algorithms for the vehicle routing problem, based on spanning tree shortest path relaxations. Mathematical Programming, 20(1), 255-282.
Christopher, M., (1985). Logistics and supply chain management: strategies for reducing cost and improving customer service, Pitman Publishing, Singapore.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568-581.
Clerc, M. (2000). Discrete particle swarm optimization illustrated by the traveling salesman problem. New Optimization Techniques in Engineering Studies in Fuzziness and Soft Computing, 141, 219-239.
Dantzig G. B., Fulkerson D. R., & Johnson S. M. (1954). Solution of a large-scale travelling-salesman problem. Operations Research, 2, 393-410.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91.
Dueck, G. (1993). New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104(1), 86-92.
Dueck, G., & Scheurer, T. (1990). Threshold accepting: A general purpose optimization algorithm. Journal of Computational Physics, 90(1), 161-175.
Eilon, S., Watson-Grandy, C. D. T., & Christofides, N. (1971). Distribution Management: Mathematical Modelling and Practical Analysis, Griffin, London.
Ergun, O., Orlin, J. B., & Steele-Feldman, A. (2006). Creating very large-scale neighbourhoods out of smaller ones by compounding moves. Journal of Heuristics, 12(1-2), 115-140.
Finke, G. A., Claus, A., & Gunn, E. (1984). A two-commodity network flow approach to the traveling salesman problem. Congressus Numerantium, 41, 167-178.
Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Gavish, B., & Graves, S. C. (1979). The Travelling Salesman Problem and Related Problems. Working Paper no. 7905, Graduate School of Management, University of Rochester, Rochester, NY.
Gendreau, M., Hertz, A., & Laporte, G. (1994). A Tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276-1290.
Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle dispatch problem. Operations Research, 22, 340-349.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533-549.
Haghani, A., & Jung, S. (2005). A dynamic vehicle routing problem with time-dependent travel times. Computers & Operations Research, 32(11), 2959-2986.
Ho, W., Ho, G. T. S., Ji, P., & Lau , H. C.W. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 21(4), 548-557.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, MI.
Hong, L. (2012). An improved LNS algorithm for real-time vehicle routing problem with time windows. Computers & Operations Research, 39(2), 151-163.
Hsieh, P. F. (2003). Basic information of warehousing and logistics industries. Taiwan Institute of Economic Research, December 16.
Huang, M., Cui, Y., Yang, S., & Wang, X. (2013). Fourth party logistics routing problem with fuzzy duration time. Int. J. Production Economics, 145(1), 107-116.
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.
Ji, P., & Wu, Y. (2011). An improved artificial bee colony algorithm for the capacitated vehicle routing problem with time-dependent travel times. The Tenth International Symposium on Operations Research and Its Applications. Dunhuang, China, 75-82.
Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization. Technical report, TR06.
Karaboga, D., & Akay, B. (2011). A modified artificial bee colony (ABC) algorithm for constrained optimization problems. Applied Soft Computing, 11(3), 3021-3031.
Karaboga, D., & Basturk, B. (2007). A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of Global Optimization, 39(3), 459-471.
Karaboga, D., & Basturk, B. (2008). On the performance of artificial bee colony (ABC) algorithm. Applied Soft Computing, 8(1), 687-697.
Karaboga, D., & Gorkemli, B. (2014). A quick artificial bee colony (qABC) algorithm and its performance onoptimization problems. Applied Soft Computing, 23, 227-238.
Karaboga, D., & Ozturk, C. (2011). A novel clustering approach: Artificial Bee Colony (ABC) algorithm. Applied Soft Computing, 11(1), 652-657.
Karaboga, N. (2009). A new design method based on artificial bee colony algorithm for digital IIR filters. Journal of the Franklin Institute, 346(4), 328-348.
Kirkpatrick, S., Gelatt Jr., C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.
Kohl, N., & Madsen, O. B. G. (1997). An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian relaxation. Operations Research, 45(3), 395-406.
Lalonde, B. J., & Zinszer, P. H. (1976). Customer service: Meaning and measurement, National Council of Physical Distribution Management, USA.
Laporte, G. (1991). The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59, 345-358.
Laporte, G. (2009). Fifty years of vehicle routing. Transportation Science, 43(4), 408-416.
Laporte, G. (2010). A concise guide to the traveling salesman problem. Journal of the Operational Research Society, 61(1), 35-40.
Laporte, G., & Nobert, Y. (1983). A branch and bound algorithm for the capacitated vehicle routing problem. Operations Research Spektrum, 5(2), 77-85.
Laporte, G., & Nobert, Y. (1987). Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics, 31, 147-184.
Laporte, G., & Osman, I. H. (1995). Routing problems: A bibliography. Annals of Operations Research, 61(1), 227-262.
Laporte, G., Nobert, Y., & Desrochers, M. (1985). Optimal routing under capacity and distance restrictions. Operations Research, 33(5), 1050-1073.
Larusic, J., & Punnen, A. P. (2011). The balanced traveling salesman problem. Computers & Operations Research, 38(5), 868-875.
Laura, M., & Joseph, S. (1998). Strategic analysis of logistics and supply chain management systems using the analytical network process. Transportation Research Part E: Logistics and Transportation Review, 34(3), 201-215.
Liu, Q, Zhang, C., Zhu, K. & Rao, Y. (2014). Novel multi-objective resource allocation and activity scheduling for fourth party logistics. Computers & Operations Research, 44, 42-51.
Mansouri, P., Asady, B., & Gupta, N. (2015). The Bisection–Artificial Bee Colony algorithm to solve Fixed point problems. Applied Soft Computing, 26, 143-148.
Martinelli, R., Poggi, M., & Subramanian, A. (2013). Improved bounds for large scale capacitated arc routing problem. Computers & Operations Research, 40(8), 2145-2160.
Masutti, T. A. S. & de Castro, L. N. (2008). A neuro-immune algorithm to solve the capacitated vehicle routing problem. Lecture Notes in Computer Science, 5132, 210-219.
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.
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097-1100.
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.
Osman, I.H. (1993). Metastrategy simulated annealing and Tabu search algorithms for the vehicle routing problem. Operations Research, 41(1-4), 421-451.
Özbakir, L., Baykasoglu, A., & Tapkan, P.. (2010). Bees algorithm for generalized assignment problem. Applied Mathematics and Computation, 215(11), 3782-3795.
Ozturk, C., Hancer, E., & Karaboga D. (2015). A novel binary artificial bee colony algorithm based on genetic operators. Information Sciences, 297, 154-170.
Ozturk, C., Hancer, E., & Karaboga D. (2015). Dynamic clustering with improved binary artificial bee colony algorithm. Applied Soft Computing, 28, 69-80.
Padberg, M.& Rinaldi, G. (1991). A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. Society for Industrial and Applied Mathematics Review, 33(1), 60-100.
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. Flexible Services and Manufacturing Journal, 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.
Rao, Y. Q., Wang, M. C., Wang, K. P., & Wu, T. M. (2013). Scheduling a single vehicle in the just-in-time part supply for a mixed-model assembly line. Computers and Operations Research, 40 (11), 2599-2610.
Reimann, M., Doerner, K., & Hartl, R.F. (2004). D-Ants: Savings based ants divide and conquer the vehicle routing problem. Computers & Operations Research, 31(4), 563-591.
Ropke, S., & Pisinger, D. (2006). A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 171(3), 750-775.
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.
Shukla, N., Choudhary, A. K., Prakash, P. K. S., Fernandes, K. J., & Tiwari, M. K. (2013). Algorithm portfolios for logistics optimization considering stochastic demands and mobility allowance. Int. J. Production Economics, 141(1), 146-166.
Solakivi, T., Töyli, J., & Ojala, L. (2013). Logistics outsourcing, its motives and the level of logistics costs in manufacturing and trading companies operating in Finland. Production Planning & Control, 24(4-5), 388-398.
Subotic, M., Tuba, M., & Stanarevic, N. (2010). Parallelization of the Artificial Bee Colony (ABC) Algorithm. Recent advances in neural networks, fuzzy systems & evolutionary computing, 191-196.
Szeto, W. Y., Wu, Y., & Ho, S. C. (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215(1), 126-135.
Taillard, E. (1993). Parallel iterative search methods for vehicle routing problems. Networks, 23(8), 661-673.
Tavakkoli-Moghaddam, R., Safaei, N., & Gholipour, Y. (2006). A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation, 176(2), 445-454.
Thammano, A., & Phu-ang, A. (2013). A hybrid artificial bee colony algorithm with local search for flexible Job-Shop scheduling problem. Procedia Computer Science, 20, 96-101.
Thompson, P. M., & Psaraftis, H. M. (1993). Cyclic transfer algorithms for multi-vehicle routing and scheduling problems. Operations Research, 41(5), 935-946.
Toth, P., & Vigo, D. (2001). The vehicle routing problem (Monographs on Discrete Mathematics and Applications). Philadelphia, PA: SIAM.
Vidal, T., Battarra, M., Subramanian, A., Erdoǧan, G. (2015). Hybrid metaheuristics for the clustered vehicle routing problem. Computers & Operations Research, 58, 87-99.
Wang, G. J., Zhang, Y. B., & Chen, J. W. (2011). A novel algorithm to solve the vehicle routing problem with time windows: Imperialist competitive algorithm. Advances in Information Sciences and Service Sciences, 3(5), 108-116.
Wang, Y. H. (2013). On the Study of Improved Imperialist Competitive Algorithm to Solve the Capacitated Vehicle Routing Problem in Logistics Management. Department of Industrial Managemwnt, National Taiwan University of Science and Technology, Taipei.
Wren, A. (1971). Computers in Transport Planning and Operation. Ian Allan, London.
Wu, J. & Tan, Y. (2009). A particle swarm pptimization algorithm for grain logistics vehicle routing problem. ISECS International Colloquium on Computing, Communication, Control, and Management, 364-367.
Wu, T. H., Chung, S. H., & Chang, C. C. (2010). A water flow-like algorithm for manufacturing cell formation problems. European Journal of Operational Research, 205(2), 346-360.
Xiang, Y., Zhou, Y., Liu, H. (2015). An elitism based multi-objective artificial bee colony algorithm. European Journal of Operational Research, doi:10.1016/j.ejor.2015.03.005, 1–26.
Xu, S., Ji, Z., Pham, D. T., & Yu, F. (2010). Bio-Inspired binary bees algorithm for a two-level distribution optimisation problem. Journal of Bionic Engineering, 7(2), 161-167.
Yan, J. S., Fan, W. M., & Guo, J. S. (2012). A modified artificial bee colony algorithm for vehicle routing problems with time windows. Information Technology Journal, 11(10), 1490-1495.
Yang, F. C., & Wang, Y. P. (2007). Water flow-like algorithm for object grouping problems. Journal of the Chinese Institute of Industrial Engineers, 24(6), 475-488.
Yanik, S., Bozkaya, B., & deKervenoael, R. (2014). A new VRPPD model and a hybrid heuristic solution approach for e-tailing. European Journal of Operational Research, 236(3), 879-890.
Yu, J., & Dong, Y. (2013). Maximizing profit for vehicle routing under time and weight constraints. International Journal of Production Economics, 145(2), 573-583.
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.
Zhen, Y. R., Huang, J. C., Li, W. Y., Li, F. X., & Zhang, Y. (2013). The planning of the dynamic path of the 3rd party logistics center, which based on the ant colony optimization. Applied Mechanics and Materials, 253-255, 1472-1475.
Zhu, W., Qin, H., Lim, A., & Wang, L. (2012). A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP. Computers & Operations Research, 39(9), 2178-2195.