ขั้นตอนวิธีการแก้ปัญหาพีเซนเตอร์โดยการพัฒนาขอบเขตบน

Abstract

ปัญหาการเลือกตำแหน่งที่ตั้งที่เหมาะสมแบบไม่มีข้อจำกัดด้านความสามารถในผลิตถูกศึกษาผ่านปัญหาพีเซนเตอร์ ในงานวิจัยชิ้นนี้ ซึ่งปัญหาดังกล่าวมีวัตถุประสงค์เพื่อให้ระยะทางระหว่างโรงงานที่เลือกเปิด p แห่งกับลูกค้าคนที่อยู่ไกลที่สุดของแต่ละโรงงานมีค่าน้อยที่สุด ในบทความนี้ได้นำเสนอข้อเสนอเพื่อลดขนาดของบริเวณคำตอบที่เป็นไปได้และช่วยปรับปรุงค่าขอบเขตบนของปัญหาให้มีค่าลดลงจากเดิม วิธีการหาคำตอบแบบฮิวริสติกส์ในงานวิจัยนี้ได้สร้างขึ้นโดยอาศัยข้อเสนอที่ได้กล่าวมาข้างต้นเพื่อช่วยในการปรับปรุงค่าขอบเขตบนของปัญหาให้มีค่าดีขึ้น อีกทั้งยังมีการนำเสนอตัวอย่างและจำลองสถานการณ์ทางคอมพิวเตอร์สำหรับปัญหาพีเซนเตอร์เพื่อแสดงวิธีการทำงานของขั้นตอนวิธีที่ได้นำเสนอในงานวิจัยชิ้นนี้  ซึ่งผลจากการจำลองสถานการณ์ทางคอมพิวเตอร์สำหรับปัญหาพีเซนเตอร์แสดงให้เห็นว่าขั้นตอนวิธีที่ได้นำเสนอในงานชิ้นนี้สามารถแก้ปัญหาที่มีจำนวนลูกค้าและสถานให้บริการได้มากที่สุดถึง 5000 x 1000 โดยใช้เวลาในการคำนวณไม่เกิน 22 นาที ในขณะที่ผลเฉลยที่ดีที่สุดสามารถหาค่าได้เมื่อปัญหามีจำนวนลูกค้าและสถานให้บริการมากที่สุดเพียง 300 x 30 เท่านั้น นอกจากนี้ผลจากการจำลองสถานการณ์ทางคอมพิวเตอร์ยังแสดงให้เห็นว่าระยะห่างระหว่างผลเฉลยที่ได้จากขั้นตอนวิธีที่ได้นำเสนอในงานวิจัยนี้กับผลเฉลยที่ดีที่สุดมีค่าไม่เกิน 1% สำหรับปัญหาที่มีจำนวนลูกค้าและสถานให้บริการน้อยกว่า 200 x 20 และไม่เกิน 17% สำหรับปัญหาที่มีขนาด 300 x 30