Solving the vehicle routing problem with time windows by using the adaptive local search in artificial bee colony optimization
Article Sidebar
Published:
Dec 27, 2021
Keywords:
vehicle routing problem time windows artificial bee colony optimization adaptive local search
Main Article Content
Abstract
Vehicle Routing Problem (VRP) is one of the popular problems in the transportation and logistics industry. With various types of constraints being difficult to solve, VRP with time windows (VRPTW) has received a large amount of attention from researchers. Usually, the objective of VRPTW is to specify the routes for the vehicles such that the total transportation distance is minimized. This study proposes an Artificial Bee Colony Optimization with Adaptive Local Search (ALABCO) for VRPTW. In this method, the local search method is adapted to improve the quality solution that adapted for escaping the local optima. The repair procedure is used for changing infeasible solutions that exceed capacity and violate time windows to feasible solutions. The proposed method has been tested in Solomon instances in different problems and compared to other existing algorithms. The results show that the proposed method is effective in solving problem.
Article Details
Section
บทความวิจัย (Research Article)
References
[1] Dantzig GB, Ramser JH. The truck dispatching problem. Management science. 1959;6(1):80-91.
[2] Taillard É, Badeau P, Gendreau M, Guertin F, Potvin JY. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation science. 1997;31(2):170-86.
[3] Toth P, Vigo D, editors. The vehicle routing problem. Society for Industrial and Applied Mathematics; 2002 Jan 1.
[4] คลอเคลีย วจนะวิชากร, กนกกาญจน์ ศรีสุรินทร์. วิธีการหาคำตอบสำหรับปัญหาการจัดเส้นทางรถเก็บขยะมูลฝอย กรณีศึกษา เทศบาลตำบลอุบล จังหวัดอุบลราชธานี. ว. วิศวกรรมศาสตร์ ม.อบ. 2561;11: 41-52.
[5] Clarke G, Wright JW. Scheduling of vehicles from a central depot to a number of delivery points. Operations research. 1964 Aug;12(4):568-81.
[6] Solomon MM. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research. 1987 Apr;35(2):254-65.
[7] ณัฐพล ธิมา, ณัฐพนธ์ ลาละคร, ชยานนท์ สุริวงษ์, นวพรรษ ทอนสระน้อย, ปรัชญ์ บุญแซม, วรุทัย เดชตานนท์. การเปรียบเทียบประสิทธิภาพการหาคำตอบด้วยวิธีฮิวริสติกส์เพื่อใช้แก้ปัญหาการจัดเส้นทางเดินรถขนส่งแบบมีกรอบเวลาในการจัดส่ง. ใน: การประชุมวิชาการระดับชาติ ครั้งที่ 13 มหาวิทยาลัยเกษตรศาสตร์ วิทยาเขตกำแพงแสน. นครปฐม: มหาวิทยาลัย;2559. หน้า 632-641.
[8] นรงค์ วิชาผา, ไทยทัศน์ สุดสวนสี, พรเทพ ขอขจายเกียรติ. การแก้ปัญหาการจัดเส้นทางขนส่งแบบมีกรอบเวลาโดยใช้วิธีเชิงพันธุกรรมแบบผสมผสานด้วยวิธีฮิวริสติกแบบแทรกไปข้างหน้าและวิธีการค้นหาคำตอบเฉพาะที่. ว. วิชาการพระจอมเกล้าพระนครเหนือ 2562; 29(1):4-13.
[9] วรรณวรา เนืองนิตย์นราพร, อำพล การุณสุนทวงษ์. วิธีฮิวริสติกการสร้างสำหรับการจัดเส้นทางการขนส่งสินค้าที่ระยะเวลาเดินทางขึ้นกับเวลาภายใต้ข้อจำกัดกรอบเวลาในการรับส่งสินค้าแบบไม่เคร่งครัดและการใช้พาหนะหลายเที่ยว. ว. วิจัยและพัฒนา มจธ. 2561;41(1): 63-81.
[10] Talbi EG. Metaheuristics: from design to implementation. John Wiley & Sons; 2009 May 27.
[11] สุพรรณ สุดสนธิ์, สรายุทธ กรวิรัตน์, นคร สุดสนธิ์. วิธีซิมมูเลเตด แอลเนลลิ่ง สำหรับการจัดเส้นทางขนส่งภายใต้กรอบเวลาที่ยืดหยุ่น. วิศวกรรมสาร มข. 2557;41(4):449-461.
[12] Razavi M, Eshlaghy AT. A two Phase Approach for solving Dynamic Capacitated Vehicle Routing Problem with Time Windows. Research Journal of Recent Sciences. 2015;4:34-40.
[13] Yu B, Yang ZZ, Yao BZ. A hybrid algorithm for vehicle routing problem with time windows. Expert Systems with Applications. 2011 Jan 1;38(1):435-41.
[14] Ombuki B, Ross BJ, Hanshar F. Multi-objective genetic algorithms for vehicle routing problem with time windows. Applied Intelligence. 2006 Feb 1;24(1):17-30.
[15] Gong YJ, Zhang J, Liu O, Huang RZ, Chung HS, Shi YH. Optimizing the vehicle routing problem with time windows: A discrete particle swarm optimization approach. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews). 2011 May 27;42(2):254-67.
[16] Nagata Y, Bräysy O, Dullaert W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Computers & operations research. 2010 Apr 1;37(4):724-37.
[17] Bezerra SN, Souza MJ, de Souza SR, Coelho VN. A VNS-based algorithm with adaptive local search for solving the multi-depot vehicle routing problem. InInternational Conference on Variable Neighborhood Search 2018 Oct 4 (pp. 167-181). Springer, Cham.
[18] Avci M, Topaloglu S. An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries. Computers & Industrial Engineering. 2015 May 1;83:15-29.
[19] Wassan NA, Osman IH. Tabu search variants for the mix fleet vehicle routing problem. Journal of the Operational Research Society. 2002 Jul 1;53(7):768-82.
[20] Jawarneh S, Abdullah S. Sequential insertion heuristic with adaptive bee colony optimisation algorithm for vehicle routing problem with time windows. PloS one. 2015 Jul 1;10(7):e0130224.
[21] Batsyn M, Bychkov I, Komosko L, Nikolaev A. Tabu search for fleet size and mix vehicle routing problem with hard and soft time windows. InInternational Conference on Network Analysis 2016 May 26 (pp. 3-18). Springer, Cham.
[22] Desrochers M, Desrosiers J, Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Operations research. 1992 Apr;40(2):342-54.
[23] Lau HC, Lim YF, Liu Q. Diversification of neighborhood via constraint-based local search and its application to VRPTW. InProc. CP-AI-OR 2001 Workshop 2001.
[24] Tan KC, Chew YH, Lee LH. A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Computational Optimization and Applications. 2006 May;34(1):115-51.
[25] Kallehauge B, Larsen J, Madsen OB. Lagrangian duality applied to the vehicle routing problem with time windows. Computers & Operations Research. 2006 May 1;33(5):1464-87.
[26] Cook W, Rich JL. A parallel cutting-plane algorithm for the vehicle routing problem with time windows. 1999.
[27] Chiang WC, Russell RA. A reactive tabu search metaheuristic for the vehicle routing problem with time windows. INFORMS Journal on computing. 1997 Nov;9(4):417-30.
[28] Rochat Y, Taillard ÉD. Probabilistic diversification and intensification in local search for vehicle routing. Journal of heuristics. 1995 Sep;1(1):147-67.
[29] Tan KC, Lee LH, Ou K. Artificial intelligence heuristics in solving vehicle routing problems with time window constraints. Engineering Applications of Artificial Intelligence. 2001 Dec 1;14(6):825-37.
[30] Rousseau LM, Gendreau M, Pesant G. Using constraint-based operators to solve the vehicle routing problem with time windows. Journal of heuristics. 2002 Jan;8(1):43-58.
[31] Thangiah SR, Osman IH, Sun T. Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows. Computer Science Department, Slippery Rock University, Technical Report SRU CpSc-TR-94-27. 1994;69.
[32] Homberger J, Gehring H. Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR: Information Systems and Operational Research. 1999 Aug 1;37(3):297-318.
[33] Berger J, Barkaoui M. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers & operations research. 2004 Oct 1;31(12):2037-53.
[34] Bent R, Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science. 2004 Nov;38(4):515-30.
[35] Ransikarbum K, Pitakaso R, Kim N. A decision-support model for additive manufacturing scheduling using an integrative analytic hierarchy process and multi-objective optimization. Applied Sciences. 2020 Jan;10(15):5159.
[36] Ransikarbum K, Ha S, Ma J, Kim N. Multi-objective optimization analysis for part-to-Printer assignment in a network of 3D fused deposition modeling. Journal of Manufacturing Systems. 2017 Apr 1;43:35-46.
[2] Taillard É, Badeau P, Gendreau M, Guertin F, Potvin JY. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation science. 1997;31(2):170-86.
[3] Toth P, Vigo D, editors. The vehicle routing problem. Society for Industrial and Applied Mathematics; 2002 Jan 1.
[4] คลอเคลีย วจนะวิชากร, กนกกาญจน์ ศรีสุรินทร์. วิธีการหาคำตอบสำหรับปัญหาการจัดเส้นทางรถเก็บขยะมูลฝอย กรณีศึกษา เทศบาลตำบลอุบล จังหวัดอุบลราชธานี. ว. วิศวกรรมศาสตร์ ม.อบ. 2561;11: 41-52.
[5] Clarke G, Wright JW. Scheduling of vehicles from a central depot to a number of delivery points. Operations research. 1964 Aug;12(4):568-81.
[6] Solomon MM. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research. 1987 Apr;35(2):254-65.
[7] ณัฐพล ธิมา, ณัฐพนธ์ ลาละคร, ชยานนท์ สุริวงษ์, นวพรรษ ทอนสระน้อย, ปรัชญ์ บุญแซม, วรุทัย เดชตานนท์. การเปรียบเทียบประสิทธิภาพการหาคำตอบด้วยวิธีฮิวริสติกส์เพื่อใช้แก้ปัญหาการจัดเส้นทางเดินรถขนส่งแบบมีกรอบเวลาในการจัดส่ง. ใน: การประชุมวิชาการระดับชาติ ครั้งที่ 13 มหาวิทยาลัยเกษตรศาสตร์ วิทยาเขตกำแพงแสน. นครปฐม: มหาวิทยาลัย;2559. หน้า 632-641.
[8] นรงค์ วิชาผา, ไทยทัศน์ สุดสวนสี, พรเทพ ขอขจายเกียรติ. การแก้ปัญหาการจัดเส้นทางขนส่งแบบมีกรอบเวลาโดยใช้วิธีเชิงพันธุกรรมแบบผสมผสานด้วยวิธีฮิวริสติกแบบแทรกไปข้างหน้าและวิธีการค้นหาคำตอบเฉพาะที่. ว. วิชาการพระจอมเกล้าพระนครเหนือ 2562; 29(1):4-13.
[9] วรรณวรา เนืองนิตย์นราพร, อำพล การุณสุนทวงษ์. วิธีฮิวริสติกการสร้างสำหรับการจัดเส้นทางการขนส่งสินค้าที่ระยะเวลาเดินทางขึ้นกับเวลาภายใต้ข้อจำกัดกรอบเวลาในการรับส่งสินค้าแบบไม่เคร่งครัดและการใช้พาหนะหลายเที่ยว. ว. วิจัยและพัฒนา มจธ. 2561;41(1): 63-81.
[10] Talbi EG. Metaheuristics: from design to implementation. John Wiley & Sons; 2009 May 27.
[11] สุพรรณ สุดสนธิ์, สรายุทธ กรวิรัตน์, นคร สุดสนธิ์. วิธีซิมมูเลเตด แอลเนลลิ่ง สำหรับการจัดเส้นทางขนส่งภายใต้กรอบเวลาที่ยืดหยุ่น. วิศวกรรมสาร มข. 2557;41(4):449-461.
[12] Razavi M, Eshlaghy AT. A two Phase Approach for solving Dynamic Capacitated Vehicle Routing Problem with Time Windows. Research Journal of Recent Sciences. 2015;4:34-40.
[13] Yu B, Yang ZZ, Yao BZ. A hybrid algorithm for vehicle routing problem with time windows. Expert Systems with Applications. 2011 Jan 1;38(1):435-41.
[14] Ombuki B, Ross BJ, Hanshar F. Multi-objective genetic algorithms for vehicle routing problem with time windows. Applied Intelligence. 2006 Feb 1;24(1):17-30.
[15] Gong YJ, Zhang J, Liu O, Huang RZ, Chung HS, Shi YH. Optimizing the vehicle routing problem with time windows: A discrete particle swarm optimization approach. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews). 2011 May 27;42(2):254-67.
[16] Nagata Y, Bräysy O, Dullaert W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Computers & operations research. 2010 Apr 1;37(4):724-37.
[17] Bezerra SN, Souza MJ, de Souza SR, Coelho VN. A VNS-based algorithm with adaptive local search for solving the multi-depot vehicle routing problem. InInternational Conference on Variable Neighborhood Search 2018 Oct 4 (pp. 167-181). Springer, Cham.
[18] Avci M, Topaloglu S. An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries. Computers & Industrial Engineering. 2015 May 1;83:15-29.
[19] Wassan NA, Osman IH. Tabu search variants for the mix fleet vehicle routing problem. Journal of the Operational Research Society. 2002 Jul 1;53(7):768-82.
[20] Jawarneh S, Abdullah S. Sequential insertion heuristic with adaptive bee colony optimisation algorithm for vehicle routing problem with time windows. PloS one. 2015 Jul 1;10(7):e0130224.
[21] Batsyn M, Bychkov I, Komosko L, Nikolaev A. Tabu search for fleet size and mix vehicle routing problem with hard and soft time windows. InInternational Conference on Network Analysis 2016 May 26 (pp. 3-18). Springer, Cham.
[22] Desrochers M, Desrosiers J, Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Operations research. 1992 Apr;40(2):342-54.
[23] Lau HC, Lim YF, Liu Q. Diversification of neighborhood via constraint-based local search and its application to VRPTW. InProc. CP-AI-OR 2001 Workshop 2001.
[24] Tan KC, Chew YH, Lee LH. A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Computational Optimization and Applications. 2006 May;34(1):115-51.
[25] Kallehauge B, Larsen J, Madsen OB. Lagrangian duality applied to the vehicle routing problem with time windows. Computers & Operations Research. 2006 May 1;33(5):1464-87.
[26] Cook W, Rich JL. A parallel cutting-plane algorithm for the vehicle routing problem with time windows. 1999.
[27] Chiang WC, Russell RA. A reactive tabu search metaheuristic for the vehicle routing problem with time windows. INFORMS Journal on computing. 1997 Nov;9(4):417-30.
[28] Rochat Y, Taillard ÉD. Probabilistic diversification and intensification in local search for vehicle routing. Journal of heuristics. 1995 Sep;1(1):147-67.
[29] Tan KC, Lee LH, Ou K. Artificial intelligence heuristics in solving vehicle routing problems with time window constraints. Engineering Applications of Artificial Intelligence. 2001 Dec 1;14(6):825-37.
[30] Rousseau LM, Gendreau M, Pesant G. Using constraint-based operators to solve the vehicle routing problem with time windows. Journal of heuristics. 2002 Jan;8(1):43-58.
[31] Thangiah SR, Osman IH, Sun T. Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows. Computer Science Department, Slippery Rock University, Technical Report SRU CpSc-TR-94-27. 1994;69.
[32] Homberger J, Gehring H. Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR: Information Systems and Operational Research. 1999 Aug 1;37(3):297-318.
[33] Berger J, Barkaoui M. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers & operations research. 2004 Oct 1;31(12):2037-53.
[34] Bent R, Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science. 2004 Nov;38(4):515-30.
[35] Ransikarbum K, Pitakaso R, Kim N. A decision-support model for additive manufacturing scheduling using an integrative analytic hierarchy process and multi-objective optimization. Applied Sciences. 2020 Jan;10(15):5159.
[36] Ransikarbum K, Ha S, Ma J, Kim N. Multi-objective optimization analysis for part-to-Printer assignment in a network of 3D fused deposition modeling. Journal of Manufacturing Systems. 2017 Apr 1;43:35-46.