簡易檢索 / 詳目顯示

回結果列表
研究生： 林韋樺
Wei-Hua Lin
論文名稱： 應用人工蜂群最佳化於智慧物流管理中具載重限制、回程取貨與接駁式轉運之車輛運途問題
An Artificial Bee Colony Optimization to Solve the Capacitated Vehicle Routing Problem with Backhaul and Cross-docking in Intelligent Logistics Management
指導教授： 羅士哲
Shih-Che Lo
口試委員: 蔡鴻旭
none
曹譽鐘
none
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2016
畢業學年度： 104
語文別： 英文
論文頁數： 68
中文關鍵詞： 接駁式轉運 、智慧物流 、蜂群演算法 、車輛路徑問題 、k-means分群法
外文關鍵詞： Cross-docking, Intelligent Logistics management, Artificial Bee Colony, Vehicle routing problem, K-means method
相關次數： 點閱：433  下載：6 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  •  上一筆

    • 任何企業的主要目標不外乎就是增加其獲利，除了降低生產成本及提高銷售量外，其提升物流的效率也是極其重要的一環。在工業4.0的架構之下，智慧物流系統的建構與整合更形重要。因此，企業導入接駁式轉運中心的物流運籌網路，可以快速並有效率的回應顧客的需求，並能大大的降低庫存成本。本論文主要考慮具車容量、接駁式轉運與回程取貨之車輛途程問題(Capacitated Vehicle Routing Problem with Backhaul, CVRPB)，最主要的概念就是讓車隊於取貨、送貨兼併處理回收及退貨回供應商的過程中同時抵達，避免轉運中心有存貨產生，並將綠色物流的概念帶入本研究，降低車輛運輸成本，並且最小化車輛路徑距離，達到最低運輸成本與快速回應的目標。
    本研究提出以蜂群最佳化(Artificial Bee Colony Optimization, ABC)演算法並結合k-means分群法，稱為kABC演算法，對具有車輛載重限制、回程取貨與接駁式轉運之車輛途程問題(CVRPBCD)快速提出一個近似最佳解，主要目的在滿足所有限制條件下，達到總成本（運輸成本）最小化。為了驗證本文所提出的kABC演算法之效能，本研究所提出之演算法與基因演算法進行效能比較，以60組車輛取貨與交貨之標竿問題(CVRPBCD)進行運輸成本最佳化分析。實驗結果顯示，相較於處理離散型問題的基因演算法而言，kABC演算法在組合型最佳化問題上有著不錯的效能。

    The main objective of any enterprise is nothing more than to increase profitability, apart from reducing production cost and increasing sales profit, the efficiency in improving logistics is also an important part. In the infrastructure of Industry 4.0, the construction and integration of Intelligent Logistics system becomes more essential. Therefore, the enterprise implements the Cross-docking (CD) logistics operation network, which can rapidly and effectively respond to customer demand and can dramatically reduce the inventory cost. This thesis mainly considers vehicle capacity, Cross-docking and Capacitated Vehicle Routing Problem with Backhaul (CVRPB), the first and the important concept is to let the vehicle fleet to arrive at the same time in the course of Pick-up, Delivery with Backhaul and Go-back, so as to avoid the generation of inventory in distribution center. Besides, the concept of green logistics is imported into this thesis. It reduces the vehicle transportation cost and minimizes the vehicle routing distance to achieve the objective of minimum transportation cost and rapid response.
    We proposed an Artificial Bee Colony (ABC) Optimization with k-means clustering approach, called kABC algorithm to generate quickly a near-optimal solution for the Capacitated Vehicle Routing Problem with Backhauling and Cross Docking (CVRPBCD). The goal is to minimize total costs (transportation cost) under various constraints. In order to verify the efficiency of the kABC algorithm, comparisons were made between the proposed algorithm and the genetic algorithm (GA). Experimental analysis is conducted for 60 benchmark problems. Comparing with the GA handling discrete-variable problem as well, the ABC algorithm has successfully implement in combinatory optimization problems.

    摘要 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.1.1 Green Logistics Management 2.2 Vehicle Routing Problem 2.2.1 VRP with Backhaul 2.2.2 Cross-docking System 2.2.3 VRP Problems with Various Constraints 2.3 Solving Methods for the VRPs 2.3.1 Exact Algorithms 2.3.2 Classical Heuristics 2.3.3 Meta-heuristics 2.4 Clustering Methods 2.5 Genetic Algorithm (GA) 2.6 Artificial Bee Colony Algorithm (ABC) CHAPTER 3 PROBLEM FORMULATION AND ARTIFICAIL BEE COLONY ALGORITHM 3.1 Capacitated Vehicle Routing Problem with Backhaul and Cross-docking System 3.2 K-means clustering 3.3 The process of Artificial Bee Colony optimization 3.3.1 Behavior of Bees in Nature 3.3.2 Initialization 3.3.3 Three Types of Bees 3.4 Neighborhood Search Operator 3.5 The Proposed kABC for the CVRPBCD CHAPTER 4 COMPUTATIONAL EXPERIMENTS 4.1 Preliminary Test 4.2 Computational Results 4.3 Summary CHAPTER 5 CONCLUSIONS AND FUTURE RESEARCH 5.1 Conclusions 5.2 Further Research REFERENCES Appendix A. The Solution of the kABC for Instance 17P1 Pick-up Route and Delivery. Appendix B. The Solution of the kABC for Instance 28P1 Pick-up Route and Delivery. Appendix C. The Solution of the kABC for Instance 51P1 Pick-up Route and Delivery.

    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.
    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.
    Apte, U. M., & Viswanathan, S. (2002). Strategic and technological innovations in supply chain management. International Journal of Manufacturing Technology and Management, 4, 264–282.
    Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem, Computers and 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.
    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, 2(2), 2231–2307.
    Bowersox, D. J., & Closs, D. J. (1996). Logistics Management, McGraw–Hill.
    Casco, D., Golden, B., & Wasil, E. (1988). Vehicle routing with backhauls: Models, algorithms and case studies, Studies in Management Science and Systems, Vehicle Routing: Methods and Studies, 16, 127–147.
    Chen, M. (2014). Improved genetic algorithm for emergency logistics distribution vehicle routing problems. Security, Pattern Analysis, and Cybernetics, 385–388.
    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.
    Deif, I., & Bodin, L. (1984). Extension of the Clarke and Wright algorithm for solving the vehicle routing with backhauling. Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management, Babson Park, 75–96.
    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.
    European Commission, (2015). http://ec.europa.eu/environment/waste/weee/index_en.htm. (valid on May 2, 2016)
    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.
    Flood, M., M. (1956). The traveling–salesman problem. Operations Research, 4(1), 61–75.
    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 and Operations Research, 13(5), 533–549.
    Gomez, A., & Salhi, S. (2014). Solving capacitated vehicle routing problem by artificial bee colony algorithm, Computational Intelligence in Production and Logistics Systems, 48–52.
    Haghani, A., & Jung, S. (2005). A dynamic vehicle routing problem with time–dependent travel times. Computers and Operations Research, 32(11), 2959–2986.
    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 and Operations Research, 39(2), 151–163.
    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.
    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., & 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 on optimization problems. Applied Soft Computing, 23, 227–238.
    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. (2009). Fifty years of vehicle routing. Transportation Science, 43(4), 408–416.
    Laporte, G., & Osman, I. H. (1995). Routing problems: A bibliography, Annals of Operations Research, 61, 227–262.
    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., & Desrochers, M. (1985). Optimal routing under capacity and distance restrictions. Operations Research, 33(5), 1050–1073.
    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.
    Lee, Y. H., Jung, J. W., & Lee, K. M. (2006). Vehicle routing scheduling for cross–docking in the supply chain, Computers and Industrial Engineering, 51(2), 247–256.
    Ley, S., & Elfayoumy, S. (2007). Cross dock scheduling using genetic algorithms, International Symposium on Computational Intelligence in Robotics and Automation, 416–420.
    Liu, P. (2009). Strategy of Green Logistics and Sustainable Development. International Conference on Information Management, Innovation Management and Industrial Engineering, 1, 339–342.
    Liu, R., Jiang, Z.,Yuan, B. (2015). A heuristic algorithm for the load–dependent capacitated vehicle routing problem with time windows. Industrial Engineering and Engineering Management, 843–847.
    MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.
    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 and Operations Research, 40(8), 2145–2160.
    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 and Operations Research, 24(11), 1097–1100.
    Mosheiov, G. (1998). Vehicle routing with pick–up and delivery: Tour partitioning heuristics. Computers and 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, 421–451.
    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.
    Purnomo, H. D., Wee, H. M., & Praharsi, Y. (2012). Two inventory review policies on supply chain configuration problem. Computers and Industrial Engineering, 63(2), 448–455.
    Reimann, M., Doerner, K., & Hartl, R. F. (2004). D–Ants: Savings based ants divide and conquer the vehicle routing problem. Computers and Operations Research, 31(4), 563–591.
    Rohrer, M. (1995). Simulation and cross docking. Proceeding of the 1995 Winter Simulation Conference, 846–849.
    Salhi, S., & Nagy, G. (1999). A cluster insertion heuristic for the single and multiple depot vehicle routing 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. International Journal of Production Economics, 141(1), 146–166.
    Sung, C. S., & Song, S. H. (2003). Integrated service network design for a cross–docking supply chain network. Journal of the Operational Research Society, 54(12), 1283–1295.
    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.
    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.
    Tiwari, A., Chang, P. C., Elangovan, G., & Annadurai, S. P. (2015). A hybrid edge recombination approach to solve price collecting vehicle routing problem. International Conference on Automation and Robotics, 200–203.
    Toth, P., & Vigo, D. (2001). The Vehicle Routing Problem (Monographs on Discrete Mathematics and Applications). Philadelphia, PA: SIAM.
    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, J., Zhou, Y., Wang, Y., Zhang, J., Chen, L. P., & Zheng, Z. (2015). Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: formulation, instances, and algorithms. IEEE Transactions on Cybernetics, 46(43), 582–594.
    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, Z., Li, H., & Wang, Y. (2011) An improved genetic algorithm for vehicle routing problem. Computational and Information Sciences. 1132–1135.
    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.
    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. (2009). An adaptive memory methodology for the vehicle routing problem with simultaneous pick–ups and deliveries. European Journal of Operational Research, 202, 401–411.
    Zhang, G., Gu, N., Lv, X., & Wang, X. (2010). The study of operation mode of green logistics. The 2nd International Conference on Intelligent Human–Machine Systems and Cybernetics, 40, 65–68.
    Zhang, S. Z., & Lee, C. K. M. (2015), An improved artificial bee colony algorithm for the capacitated vehicle routing problem. The 2015 IEEE International Conference on Systems, Man, and Cybernetics, 2124–2128.
    Zheng, Y., & Zhang, G. (2008). A genetic algorithm for vehicle routing problem with forward and reverse logistics. International Conference on Wireless Communications, Networking and Mobile Computing, 1–4.
    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 and Operations Research, 39(9), 2178–2195.

    QR CODE