Network Flow Algorithm Implementation to Determine Maximum Water Flow of Bangkok

Abstract

Thailand flood crisis in 2011 has damaged in many areas of Thailand. Especially in Bangkok, water cannot drain into the Gulf of Thailand in time. This paper focuses on the applied two algorithms consist of Generic augmenting part algorithm and Labeling algorithm to determine the maximum flow of water from north of Bangkok to the Gulf of Thailand. The flow of water in Bangkok are represented by network flow, river and canals are represented by nodes and arcs, Labeling and Generic augmenting part algorithm are used to find the water route from sort to sink and maximum water flow respectively. The results showed that the maximum flow in Bangkok was 228,960,000 cubic meters per day.

วิกฤติน้ำท่วมที่เกิดขึ้นในประเทศไทยปี 2554 ทำให้เกิดความเสียหายในหลายพื้นที่ของประเทศไทย โดยเฉพาะกรุงเทพมหานคร เนื่องจากไม่สามารถระบายน้ำลงสู่อ่าวไทยได้ทันเวลา งานวิจัยนี้มุ่งเน้นการประยุกต์สองขั้นตอนวิธี (Algorithm) ได้แก่ ขั้นตอนวิธีเลเบล (Labeling algorithm) และขั้นตอนวิธีขยาย (Generic augmenting part algorithm) เพื่อใช้หาเส้นทางและปริมาณการไหลสูงสุดของน้ำจากทางตอนบนของกรุงเทพมหานครลงสู่อ่าวไทย การไหลสูงสุดของน้ำในกรุงเทพมหานครแทนการไหลในข่ายงาน (Network flow) แม่น้ำและคลองต่าง ๆ แทนด้วยโหนด (nodes) และเส้นเชื่อม (arcs) โดยขั้นตอนวิธีเลเบล (Labeling algorithm) ทำหน้าที่ค้นหาเส้นทางการไหลของน้ำจากโหนดต้นทาง (sort) ไปยังโหนดปลายทาง (sink) หลังจากนั้นขั้นตอนวิธีขยาย (Generic augmenting part algorithm) จึงทำหน้าที่หาปริมาณการไหลสูงสุดของน้ำ ผลการวิจัยพบว่าปริมาณการไหลสูงสุดของน้ำในกรุงเทพมหานครคือ 228,960,000 ลูกบาศก์เมตรต่อวัน