Liên quan đến khoảng cách: Một quy trình áp dụng trực tiếp thuật toán Tổ Ong Nhân Tạo trong các bài toán định tuyến

Soft Computing - Tập 24 - Trang 9071-9089 - 2019
Dimitra Trachanatzi1, Manousos Rigakis1, Magdalene Marinaki1, Yannis Marinakis1, Nikolaos Matsatsinis1
1School of Production Engineering and Management, Technical University of Crete, Chania, Greece

Tóm tắt

Mục tiêu của bài viết này là giới thiệu một phương pháp thuật toán sáng tạo, Thuật toán Tổ Ong Nhân Tạo Liên quan đến Khoảng cách (DRABC), như một biến thể của thuật toán Tổ Ong Nhân Tạo (ABC) gốc. Phương pháp nói trên đã được sử dụng để giải quyết bài toán điều hướng đội nhóm (TOP). TOP thuộc loại bài toán định tuyến phương tiện có lợi nhuận, và vì vậy, mỗi nút được liên kết với một giá trị điểm. Mục tiêu của TOP là hình thành các lộ trình khả thi với giới hạn tổng thời gian di chuyển tương ứng với việc tối đa hóa tổng giá trị điểm. Tóm tắt phương pháp đã đề xuất, thuật toán này áp dụng các phương trình gốc của ABC trên các vectơ giải được mã hóa phù hợp, cụ thể là trên các vectơ thể hiện khoảng cách Euclide giữa các nút liên tiếp trong một lộ trình. Quy trình này được kết hợp với một phương pháp giải mã để biểu diễn vectơ giải dưới dạng một chuỗi có thứ tự các nút. Phương pháp mã hóa/giải mã này được gọi là quy trình “Liên quan đến Khoảng cách”. Phương pháp đã đề xuất đạt được hầu hết các giải pháp tốt nhất đã biết của các phiên bản tham chiếu có trong tài liệu, và hiệu suất của thuật toán DRABC được so sánh với các thuật toán khác liên quan đến việc giải quyết TOP.

Từ khóa

#Thuật toán Tổ Ong Nhân Tạo #Bài toán điều hướng đội nhóm #Định tuyến phương tiện có lợi nhuận #Khoảng cách Euclide #Mã hóa giải mã.

Tài liệu tham khảo

Alzaqebah M, Abdullah S, Jawarneh S (2016) Modified artificial bee colony for the vehicle routing problems with time windows. SpringerPlus 5(1):1298 Archetti C, Hertz A, Speranza M (2007) Metaheuristics for the team orienteering problem. J Heuristics 13:49–76 Archetti C, Speranza MG, Vigo D (2014) Vehicle routing problems with profits. In: Toth P, Vigo D (eds) Vehicle routing: problems, methods, and applications. MOS-SIAM series on optimization. SIAM, Philadelphia, pp 273–298 Bouly H, Dang DC, Moukrim A (2010) A memetic algorithm for the team orienteering problem. 4OR 8(1):49–70 Brajevic I (2011) Artificial bee colony algorithm for the capacitated vehicle routing problem. In: Proceedings of the European computing conference, pp 239–244 Butt S, Cavalier T (1994) A heuristic for the multiple tour maximum collection problem. Comput Oper Res 21:101–111 Cao E, Lai M, Yang H (2014) Open vehicle routing problem with demand uncertainty and its robust strategies. Expert Syst Appl 41(7):3569–3575 Chao IM, Golden BL, Wasil EA (1996a) The team orienteering problem. Eur J Oper Res 88(3):464–474 Chao IM, Golden BL, Wasil EA (1996b) A fast and effective heuristic for the orienteering problem. Eur J Oper Res 88(3):475–489 Cura T (2014) An artificial bee colony algorithm approach for the team orienteering problem with time windows. Comput Ind Eng 74:270–290 Dang DC, Guibadj RN, Moukrim A (2011) A PSO-based memetic algorithm for the team orienteering problem. In: European conference on the applications of evolutionary computation. Springer, Berlin, pp 471–480 Dang DC, Guibadj RN, Moukrim A (2013) An effective PSO-inspired algorithm for the team orienteering problem. Eur J Oper Res 229(2):332–344 Ferreira J, Quintas A, Oliveira JA (2014) Solving the team orienteering problem: developing a solution tool using a genetic algorithm approach. In: Kromer P, Koppen M, Schaefer G (eds) Soft computing in industrial applications. Advances in intelligent systems and computing, vol 223. Springer, Berlin, pp 365–375 Gavalas D, Konstantopoulos C, Mastakas K, Pantziou G (2014) A survey on algorithmic approaches for solving tourist trip design problems. J Heuristics 20(3):291–328 Golden BL, Levy L, Vohra R (1987) The orienteering problem. Naval Res Logist 34(3):307–318 Gomez A, Salhi S (2014) Solving capacitated vehicle routing problem by artificial bee colony algorithm. In: IEEE symposium on computational intelligence in production and logistics systems (CIPLS). IEEE, pp 48–52 Gunawan A, Lau HC, Vansteenwegen P (2016) Orienteering problem: a survey of recent variants, solution approaches and applications. Eur J Oper Res 255(2):315–332 Iqbal S, Kaykobad M, Rahman MS (2015) Solving the multi-objective vehicle routing problem with soft time windows with the help of bees. Swarm Evolut Comput 24:50–64 Ji P, Wu Y (2011) An improved artificial bee colony algorithm for the capacitated vehicle routing problem with time-dependent travel times. In: Tenth international symposium on operations research and its applications, pp 75–82 Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Technical report-tr06, Erciyes University, Engineering Faculty. Computer Engineering Department 200 Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (abc) algorithm. J Global Optim 39:459–471 Karaboga D, Basturk B (2008) On the performance of artificial bee colony (abc) algorithm. Appl Soft Comput 8:687–697 Ke L, Archetti C, Feng Z (2008) Ants can solve the team orienteering problem. Comput Ind Eng 54:648–665 Ke L, Zhai L, Li J, Chan FT (2016) Pareto mimic algorithm: an approach to the team orienteering problem. Omega 61:155–166 Kim BI, Li H, Johnson AL (2013) An augmented large neighbourhood search method for solving the team orienteering problem. Expert Syst Appl 40(8):3065–3072 Lin SW (2013) Solving the team orienteering problem using effective multi-start simulated annealing. Appl Soft Comput 13(2):1064–1073 Mao S, Zheng M, Zhao X, Xie W, Wang Z (2016) The uncertain time dependent vehicle routing problem with soft time windows. In: IEEE International conference on fuzzy systems (FUZZ-IEEE). IEEE, pp 38–45 Marinakis Y, Marinaki M, Migdalas A (2017) Particle swarm optimization for the vehicle routing problem: a survey and a comparative analysis. In: Martí Rafael, Panos Pardalos, Resende Mauricio (eds) Handbook of heuristics. Springer, Berlin, pp 1–34 Muthuswamy S, Lam SS (2011) Discrete particle swarm optimization for the team orienteering problem. Memet Comput 3(4):287–303 Nahum OE, Hadas Y, Spiegel U (2014) Multi-objective vehicle routing problems with time windows: a vector evaluated artificial bee colony approach. Int J Comput Inf Technol 3(1):41–47 Rosenkrantz DJ, Stearns RE, Lewis PM II (1977) An analysis of several heuristics for the travelling salesman problem. SIAM J Comput 6(3):563–581 Seidgar H, Kiani M, Fazlollahtabar H (2016) Genetic and artificial bee colony algorithms for scheduling of multi-skilled manpower in combined manpower-vehicle routing problem. Prod Manuf Res 4(1):133–151 Shi YJ, Meng FW, Shen GJ (2012) A modified artificial bee colony algorithm for vehicle routing problems with time windows. Inf Technol J 11(10):1490 Souffriau W, Vansteenwegen P, Berghe GV, Van Oudheusden D (2010) A path relinking approach for the team orienteering problem. Comput Oper Res 37(11):1853–1859 Szeto WY, Ho SC (2011) An artificial bee colony algorithm for the capacitated vehicle routing problem. Eur J Oper Res 215(1):126–135 Tang H, Miller-Hooks E (2005) A tabu search heuristic for the team orienteering problem. Comput Oper Res 32:1379–1407 Tuntitippawan N, Asawarungsaengkul K (2016) An artificial bee colony algorithm with local search for vehicle routing problem with backhauls and time windows. KKU Eng J 43:404–408 Vansteenwegen P, Souffriau W, Van Berghe G, Van den Oudheusden D (2009) A guided local search metaheuristic for the team orienteering problem. Eur J Oper Res 196(1):118–127 Vansteenwegen P, Souffriau P, Vanden Berghe G, Van Oudheusden D (2009) Metaheuristics for tourist trip planning. In: Geiger M, Habenicht W, Sevaux M, Sörensen K (eds) Metaheuristics in the service industry. Lecture notes in economics and mathematical systems, vol 624. Springer, Berlin, pp 15–31 Vansteenwegen P, Souffriau W, Van Oudheusden D (2011) The orienteering problem: a survey. Eur J Oper Res 209(1):1–10 Wu B, Lin JG, Dong M (2013a) Artificial bee colony algorithm for three-dimensional loading capacitated vehicle routing problem, in Proceedings of 20th International Conference on Industrial Engineering and Engineering Management. Springer, Berlin, pp 815–825 Wu B, Cai H, Cui Z (2013b) Artificial bee colony algorithm for two-dimensional loading capacitated vehicle routing problem. In: International conference on management science and engineering (ICMSE). IEEE, pp 406–412 Yao B, Hu P, Zhang M, Wang S (2013) Artificial bee colony algorithm with scanning strategy for the periodic vehicle routing problem. Simulation 89(6):762–770 Yin PY, Chuang YL (2016) Adaptive memory artificial bee colony algorithm for green vehicle routing with cross-docking. Appl Math Model 40(21):9302–9315 Yu S, Tai C, Liu Y, Gao L (2016) An improved artificial bee colony algorithm for vehicle routing problem with time windows: a real case in Dalian. Adv Mech Eng 8(8):1–9 Zettam M, Elbenani B (2016) A novel randomized heuristic for the team orienteering problem. In: 3rd International conferenceon logistics operations management (GOL). IEEE Zhang SZ, Lee CKM (2015) An improved artificial bee colony algorithm for the capacitated vehicle routing problem. In: 2015 IEEE international conference on systems, man, and cybernetics (SMC). IEEE, pp 2124–2128 Zhang S, Lee CKM, Choy KL, Ho W, Ip WH (2014) Design and development of a hybrid artificial bee colony algorithm for the environmental vehicle routing problem. Transp Res D Transp Environ 31:85–99