CUCKOO SEARCH ALGORITHM FOR THE VEHICLE ROUTING PROBLEM WITH BACKHAULS AND TIME WINDOWS
Article Sidebar
Main Article Content
บทคัดย่อ
A Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW) involves two different subsets of customers known as linehauls and backhauls. The demands of the linehauls must be delivered before the backhaul pickups. The total demands of customers must not exceed a vehicle’s capacity, and the time that a vehicle arrives at every customer must be within the required time windows. In this study, we present a cuckoo search (CS) algorithm, which is inspired from aggressive breeding behavior of cuckoo birds to solve this problem. Moreover, we proposed the nearest neighbor with roulette wheel selection method (NNRW) as an initial solution algorithm. The proposed method was tested on a set of benchmark instances. The results indicated that NNRW gave equal or better solutions than the improved nearest neighbor algorithm (INN). Furthermore, CS algorithm was compared with other methods from existing studies. Computational results show that our algorithm gave equivalent solutions to or better solutions than the best known solutions for the majority of small and medium-size instances. Hence, it is a competitive method for solving small and medium size VRPBTW problems.
ปัญหาการจัดการเส้นทางเดินรถโดยมีข้อจำกัดด้านรถเที่ยวกลับและตารางเวลานั้นเกี่ยวข้องกับกลุ่มลูกค้าสองประเภท ได้แก่ ลูกค้าเที่ยวไป และลูกค้าเที่ยวกลับ โดยเราจะต้องนำสินค้าไปส่งให้กับลูกค้าเที่ยวไปก่อนที่จะรับสินค้าจากลูกค้าเที่ยวกลับเสมอ ทั้งนี้ปริมาณสินค้าที่บรรทุกไปนั้นจะต้องไม่เกินความจุของรถ และส่งสินค้าภายในกรอบเวลาที่ลูกค้าสะดวกอีกด้วย ในการศึกษานี้เราได้นำเสนอขั้นตอนวิธีการค้นหาคำตอบเลียนแบบพฤติกรรมของนกกาเหว่า ซึ่งได้รับแรงบันดาลใจมาจากพฤติกรรมการสืบพันธุ์ที่ก้าวร้าวของนกกาเหว่าเพื่อแก้ปัญหานี้ โดยเราได้นำเสนอขั้นตอนวิธีการเลือกคำตอบที่ใกล้ที่สุดด้วยวงล้อรูเล็ตต์ (roulette wheel) สำหรับการสร้างคำตอบเริ่มต้น และได้ทดสอบขั้นตอนวิธีดังกล่าวกับตัวอย่างที่ใช้เปรียบเทียบประสิทธิภาพ ผลการศึกษาพบว่า ขั้นตอนวิธีการเลือกคำตอบที่ใกล้ที่สุดด้วยวงล้อรูเล็ตต์ได้คำตอบเทียบเท่าหรือดีกว่าการค้นหาคำตอบด้วยวิธีการเลือกคำตอบที่ใกล้ที่สุดที่ปรับปรุงแล้ว นอกจากนี้เรายังได้ทำการเปรียบเทียบขั้นตอนวิธีการค้นหาคำตอบเลียนแบบพฤติกรรมของนกกาเหว่ากับวิธีอื่นๆ ที่รวบรวมมาจากงานวิจัยต่างๆ จนถึงปัจจุบัน พบว่าในส่วนใหญ่ของปัญหาที่มีขนาดเล็กและขนาดกลางขั้นตอนวิธีการค้นหาคำตอบเลียนแบบพฤติกรรมของนกกาเหว่าสามารถพบคำตอบที่เทียบเท่าหรือดีกว่าคำตอบที่ดีที่สุดเท่าที่เคยพบมา ดังนั้นขั้นตอนวิธีนี้จึงเป็นอีกทางเลือกหนึ่งที่ดีในการหาคำตอบของปัญหานี้ที่มีขนาดเล็กและขนาดกลาง
Article Details
“ข้าพเจ้าและผู้เขียนร่วม (ถ้ามี) ขอรับรองว่า บทความที่เสนอมานี้ยังไม่เคยได้รับการตีพิมพ์และไม่ได้อยู่ระหว่างกระบวนการพิจารณาลงตีพิมพ์ในวารสารหรือแหล่งเผยแพร่อื่นใด ข้าพเจ้าและผู้เขียนร่วมยอมรับหลักเกณฑ์การพิจารณาต้นฉบับ ทั้งยินยอมให้กองบรรณาธิการมีสิทธิ์พิจารณาและตรวจแก้ต้นฉบับได้ตามที่เห็นสมควร พร้อมนี้ขอมอบลิขสิทธิ์บทความที่ได้รับการตีพิมพ์ให้แก่สถาบันการจัดการปัญญาภิวัฒน์หากมีการฟ้องร้องเรื่องการละเมิดลิขสิทธิ์เกี่ยวกับภาพ กราฟ ข้อความส่วนใดส่วนหนึ่งและ/หรือข้อคิดเห็นที่ปรากฏในบทความข้าพเจ้าและผู้เขียนร่วมยินยอมรับผิดชอบแต่เพียงฝ่ายเดียว”
References
Berger, J. & Barkaoui, M. (2002). A memetic algorithm for the vehicle routing problem with time windows. In The 7th International Command and Control Research and Technology Symposium.
Berger, J. & Barkaoui, M. (2004). A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers & operations research, 31(12), 2037-2053.
Brandao, J. (2006). A new tabu search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research, 173(2), 540-555.
Bräysy, O. & Gendreau, M. (2002). Tabu search heuristics for the vehicle routing problem with time windows. Top, 10(2), 211-237.
Casco, D., Golden, B. & Wasil, E. (1988). Vehicle routing with backhauls: Models, algorithms and case studies. Vehicle Routing: Methods and Studies. Studies in management science and systems-Volume 16. Publication of Dalctraf.
Chiang, W. C. & Russell, R. A. (1997). A reactive tabu search metaheuristic for the vehicle routing problem with time windows. INFORMS Journal on computing, 9(4), 417-430.
Emeç, U., Çatay, B. & Bozkaya, B. (2016). An adaptive large neighborhood search for an e-grocery delivery routing problem. Computers & Operations Research, 69, 109-125.
Gajpal, Y. & Abad, P. L. (2009). Multi-ant colony system (MACS) for a vehicle routing problem with backhauls. European Journal of Operational Research, 196(1), 102-117.
Gelinas, S., Desrochers, M., Desrosiers, J. & Solomon, M. M. (1995). A new branching strategy for time constrained routing problems with application to backhauling. Annals of Operations Research, 61(1), 91-109.
Holland, J. H. (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press.
Küçükoğlu, İ. & Öztürk, N. (2015). An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows. Computers & Industrial Engineering,86, 60-68.
Osman, I. H. & Wassan, N. A. (2002). A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls. Journal of Scheduling, 5(4), 263-285.
Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of operations research, 41(4), 421-451.
Ouaarab, A., Ahiod, B. & Yang, X. S. (2014). Discrete cuckoo search algorithm for the travelling salesman problem. Neural Computing and Applications, 24(7-8), 1659-1669.
Potvin, J. Y., Duhamel, C. & Guertin, F. (1996). A genetic algorithm for vehicle routing with backhauling. Applied Intelligence, 6(4), 345-355.
Pradhananga, R., Taniguchi, E., Yamada, T. & Qureshi, A. G. (2014). Environmental Analysis of Pareto Optimal Routes in Hazardous Material Transportation. Procedia-Social and Behavioral Sciences, 125, 506-517.
Reimann, M., Doerner, K. & Hartl, R. F. (2002). Insertion based ants for vehicle routing problems with backhauls and time windows. In International Workshop on Ant Algorithms (pp. 135-148). Springer Berlin Heidelberg.
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.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
Tavakkoli-Moghaddam, R., Saremi, A. R. & Ziaee, M. S. (2006). A memetic algorithm for a vehicle routing problem with backhauls. Applied Mathematics and Computation, 181(2), 1049-1060.
Thangiah, S. R., Potvin, J. Y. & Sun, T. (1996). Heuristic approaches to vehicle routing with backhauls and time windows. Computers & Operations Research, 23(11), 1043-1057.
Wang, X., Wang, M., Ruan, J. & Zhan, H. (2016). The Multi-objective Optimization for Perishable Food Distribution Route Considering Temporal-spatial Distance. Procedia Computer Science, 96, 1211-1220.
Yang, X. S. & Deb, S. (2009). Cuckoo search via Lévy flights. In Nature & Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on (pp. 210-214). IEEE.
Yu, B., Yang, Z. Z. & Yao, B. Z. (2011). A hybrid algorithm for vehicle routing problem with time windows. Expert Systems with Applications, 38(1), 435-441.
Zheng, H., Zhou, Y., Xie, J. & Luo, Q. (2013). A hybrid Cuckoo Search Algorithm-GRASP for Vehicle Routing Problem. Journal of Convergence Information Technology, 8(3), 821-828.
Zhong, Y. & Cole, M. H. (2005). A vehicle routing problem with backhauls and time windows: a guided local search solution. Transportation Research Part E: Logistics and Transportation Review, 41(2), 131-144.