การแก้ปัญหาการหาตำแหน่งที่ตั้งของสถานีให้บริการแบบไม่มีความจุโดยใช้ขั้นตอน วิธีเชิงพันธุกรรมและการค้นหาเฉพาะที่ (To Solve Uncapacitaed Facility Location Problem using Genetic Algorithms and Local Search)

Abstract

                    งานวิจัยนี้มีเป้าหมายคือการศึกษาแบบจำลองทางคณิตศาสตร์ของการแก้ปัญหาการหาตำแหน่งที่ตั้งของสถานีให้บริการแบบไม่มีความจุ ปัญหานี้เป็นปัญหาเกี่ยวกับการเลือกที่ตั้งของสถานีจากสถานที่ที่สามารถตั้งเป็นสถานีที่กำหนดให้ โดยมีกำหนดให้สถานีที่เปิดให้กับลูกค้า เป้าหมายของคือการลดมูลค่าของผลรวมของค่าของการเปิดสถานีและค่าใช้จ่ายของลูกค้า หากเปิดสถานีด้วยจำนวนและสถานที่ที่เหมาะสมจะทำให้ลดค่าใช้จ่ายทั้งผู้ให้บริการและลูกค้า งานวิจัยนี้ทำการสร้างขั้นตอนวิธีเชิงพันธุกรรมสำหรับการแก้ปัญหาการหาตำแหน่งที่ตั้งของสถานีให้บริการแบบไม่มีความจุ การทดลองเปรียบเทียบการทำงานของการคัดเลือกและการไขว้เปลี่ยนของขั้นตอนวิธีเชิงพันธุกรรมเพื่อหาวิธีการที่เหมาะสม นำขั้นตอนวิธีเชิงพันธุกรรมที่ทดสอบว่ามีประสิทธิภาพเพิ่มขึ้นมาใช้ร่วมกับการค้นหาเฉพาะที่

                    The objective of this research is to study a mathematical model and to solve the Uncapacitated Facility Location Problem. The problem focuses on selecting of station locations form a set of given locations. Customers will be assigned to a selected station. The objective is to minimize the sum of the cost for establishing the station and the cost of transportation for all customers. The suitable set of stations reduces the cost of both a station owner and customers. This paper implements the genetic algorithm for solving Uncapacitated Facility Location Problem. The experiment compares the genetic algorithm in terms of finding a suitable set of selection and crossover operators. Using local search with genetic algorithm improves a performance in this problem.