Batching orders in warehouses by minimizing travel distance with genetic algorithms / การลดระยะทางไปหยิบสินค้าด้วยการรวมกลุ่มคำสั่งสินค้า

มาตรฐาน

ศรินดา วงศ์โกศลสุข (แปลและเรียบเรียง)

Chih-Ming Hsu (รองศาสตราจารย์ มหาวิทยาลัยวิทยาศาสตร์และเทคโนโลยี Ming Hsin ประเทศไต้หวัน),

Kai-Ying Chen (ผู้ช่วยศาสตราจารย์ มหาวิทยาลัยเทคโนโลยีแห่งชาติไทเป ประเทศไต้หวัน),

Mu-Chen Chen (ศาสตราจารย์ มหาวิทยาลัยเทคโนโลยีแห่งชาติไทเป ประเทศไต้หวัน)

Introduction

  • กระบวนการภายในคลังสินค้าที่เกี่ยวข้องกับคำสั่งซื้อดำเนินไปอย่างรวดเร็วกว่าสมัยก่อน
  • เพื่อตอบสนองรอบการสั่งซื้อที่สั้นลงของลูกค้า สินค้าอาจจะอยู่ในคลังเพียงแค่ไม่กี่วันหรืออาจจะไม่กี่ชั่วโมง
  • การหยิบสินค้าเป็นขั้นตอนที่สินค้าถูกนำออกจากตำแหน่งจัดเก็บตามคำสั่งซื้อของลูกค้า
  • การหยิบสินค้าเป็นขั้นตอนที่ต้องใช้แรงงานคนเป็นส่วนใหญ่ การเพิ่มประสิทธิภาพการหยิบสินค้าจะสามารถลดต้นทุนคลังสินค้าได้เป็นอย่างมาก
  • ประสิทธิภาพการหยิบสินค้าขึ้นอยู่กับปัจจัย เช่น ชั้นจัดเก็บสินค้า, การวางผังคลังสินค้า, และกลไกควบคุมคลังสินค้า
  • การรวมกลุ่มคำสั่งสินค้าเป็นกลไกที่สำคัญในการลดระยะทางไปหยิบและลดต้นทุนคลังสินค้า
  • การหยิบสินค้าแบ่งออกเป็นสองแบบคือ
  1. หยิบทีละคำสั่งสินค้า (single order picking)
  2. รวมกลุ่มคำสั่งสินค้าเพื่อหยิบทีเดียว (batch picking)

Objective Function

  • วิธีการรวมกลุ่มคำสั่งสินค้าจะใช้เป้าหมายด้านระยะทางที่สั้นที่สุดหรือเวลาที่ใช้น้อยที่สุดเป็นเกณฑ์

สมการวัตถุประสงค์ของการรวมกลุ่มคำสั่งสินค้าที่มีเป้าหมายด้านระยะทางเป็นดังนี้

12or

โดย

(1) = ลดผลรวมของระยะทางทุกกลุ่มคำสั่งสินค้าตั้งกลุ่มคำสั่งที่ 1 เป็นต้นไป

(2) = จำกัดจำนวนสินค้าของทุกคำสั่งสินค้าในแต่ละกลุ่มคำสั่งว่าจะต้องไม่มากกว่าความสามารถในการหยิบ

(3) = จำนวนรวมของสินค้าในแต่ละคำสั่งสินค้าจะต้องไม่มากกว่าความสามารถในการหยิบแต่ละครั้ง

(4) = ทุกคำสั่งสินค้าจะต้องถูกหยิบ

(5) = ห้ามแตก 1 คำสั่งสินค้าออกไปในกลุ่มคำสั่งสินค้าอื่น

เมื่อ

Batchk = กลุ่มคำสั่งสินค้าใดๆ

CapPF = ความสามารถในการหยิบแต่ละครั้ง

Dk = ระยะทางไปหยิบสินค้าในกลุ่มคำสั่งสินค้าหนึ่งๆ โดยระยะทางจะต้องมากกว่าหรือเท่ากับ 0

NO_batch = จำนวนกลุ่มคำสั่งสินค้าที่เกิดขึ้น

NO_location = จำนวนชนิดสินค้าในคลังสินค้า

NO_order = จำนวนคำสั่งสินค้าที่จะถูกหยิบ

i = คำสั่งสินค้าใดๆ

S = กลุ่มคำสั่งสินค้าที่จะถูกหยิบ

Vij = จำนวนสินค้าชนิดใดชนิดหนึ่งที่จะถูกหยิบเพื่อให้ครบตามคำสั่งสินค้าหนึ่ง โดยจำนวนสินค้าจะต้องมากกว่าหรือเท่ากับ 0

Optimal or Heuristic Solution?

  • เป็นการยากที่จะหา Optimal Solution
    • ผลรวมระยะทางขึ้นอยู่กับการรวมกลุ่มคำสั่งสินค้าและการวางผังคลังสินค้า
    • การหาผลลัพธ์เป็นจำนวนเต็มส่วนมากจะใช้ได้กับปัญหาที่มีจำนวนตัวเลขไม่มาก
    • ใช้ระยะเวลาในการคำนวณนาน
  • Heuristic Solution
  1. เลือกใบสั่งสินค้าหลัก
  2. เลือกใบสั่งสินค้าอื่นๆ ที่คล้ายกับใบสั่งสินค้าหลัก จนกระทั่งเต็มความสามารถในการหยิบแต่ละครั้ง

Literature Review

  • งานวิจัยของ J.P. Van den Berg (1999) ใช้วิธีการวัดความใกล้กันของสินค้าที่จะไปหยิบและประมาณการระยะทางที่จะไปหยิบ
  • งานวิจัยของ Hwang et al. (1988) แบ่งชั้นจัดเก็บสินค้าเป็นกลุ่มและวัดความใกล้กันของแต่ละคำสั่งสินค้าด้วยกลุ่มชั้นจัดเก็บสินค้าที่จะไปหยิบ
  • งานวิจัยของ Gibson and Sharp (1992) ใช้วิธีประมาณการระยะทางด้วยผลรวมระยะทางของแต่ละชนิดสินค้าในใบสั่งสินค้าหลักกับชนิดสินค้าที่ใกล้ที่สุดในใบสั่งสินค้าอื่นๆ
  • งานวิจัยที่ผ่านๆ มา ส่วนใหญ่จะวิจัยโดยยึดผังคลังสินค้าที่วางสินค้าในแนวนอน (ไม่มีชั้นจัดเก็บสินค้าในแนวตั้ง)

Genetic Algorithms-Based Batching Method (GABM)

  • งานวิจัยนี้ใช้วิธีการลดระยะทางรวมที่จะเดินไปหยิบด้วย Genetic Algorithms
  • ข้อดีของ Genetic Algorithms
  1. มีข้อกำหนดทางคณิตศาสตร์น้อย, สามารถใช้ได้กับ objective function ทุกแบบ, constraint สามารถเป็นได้ทั้ง discrete, continuous, และ mixed
  2. สามารถหาความน่าจะเป็นและหาผลลัพธ์ที่ดีที่สุดได้
  3. มีความยืดหยุ่นในการผสมผสาน domain-dependent heuristics เพื่อให้สามารถนำผลลัพธ์ไปใช้ได้อย่างมีประสิทธิภาพ

Genetic Algorithms

  • ผลลัพธ์ (โครโมโซม) ถูกใส่รหัสเรียงกันเป็นแถวจากหลายๆ ส่วนประกอบ (ยีนส์)
  • ส่วนประกอบเริ่มแรกของโครโมโซมอาจถูกสร้างขึ้นจากหลักการหนึ่งๆ หรือการสุ่มก็ได้
  • ระบบกฎเกณฑ์ถูกสร้างขึ้นเพื่อวัดคุณภาพ (ความเหมาะสม) ของผลลัพธ์นั้นๆ
  • ผลลัพธ์ที่ดีที่สุดได้จาก
  1. การเลือกคู่โครโมโซมที่มีสัดส่วนความน่าจะเป็นที่เหมาะสม
  2. จับคู่โครโมโซมและสร้างโครโมโซมรุ่นถัดไปซึ่งได้มีการปรับปรุงเปลี่ยนแปลง (เจเนอเรชั่น)
  3. การประเมินผลและการเปลี่ยนแปลงถูกทำซ้ำจนกระทั่งได้ผลลัพธ์ในขอบเขตที่ต้องการ
  • กลไกหลัก
    • Crossover – สลับยีนส์ในโครโมโซมหนึ่งกับโครโมโซมอื่นๆ
    • Mutation – เปลี่ยนลำดับ / ตำแหน่งยีนส์ในโครโมโซมหนึ่งๆ
    • Selection – ตั้งกลุ่มที่จะนำไปจับคู่โครโมโซมโดยเลือกจากโครโมโซมก่อนๆ ที่มีความเป็นไปได้ โดยความน่าจะเป็นที่โครโมโซมใดๆ จะถูกเลือกเข้ากลุ่มขึ้นอยู่กับสัดส่วนความเหมาะสมต่อสมการวัตถุประสงค์และข้อจำกัด
    • Surviving – ความน่าจะเป็นที่โครโมโซมที่มีความเป็นไปได้จะยังใช้ได้อยู่ในรุ่นต่อไป

Performance Study

  • ใส่รหัสด้วยโปรแกรม Visual C++ 6.0
  • ประมวลผลด้วยเครื่อง IBM Pentium 4 Processor
  • สมมุติฐาน
  1. มีการทราบทุกคำสั่งสินค้าล่วงหน้า
  2. ไม่สามารถแบ่งคำสั่งสินค้าไปในกลุ่มอื่นได้
  3. จุดรวมสินค้าอยู่ที่มุมซ้ายของคลังสินค้า
  4. ผังคลังสินค้า 2 มิติ จะคิดระยะทางไปหยิบสินค้าตามแนวนอน และผังคลังสินค้า 3 มิติ จะคิดระยะทางไปหยิบสินค้าตามแนวนอนและแนวตั้ง
  5. ใช้วิธี S-Shape ในการไปหยิบสินค้า
  6. ผู้หยิบสินค้าสามารถหยิบสินค้าในตำแหน่งเดียวกันจากชั้นวางทางซ้ายและขวาโดยไม่คิดเป็นระยะที่เพิ่มขึ้น
  7. อุปกรณ์บรรจุสินค้าที่หยิบสามารถไปตามชั้นวางสินค้าได้ทั้งซ้ายขวาหน้าหลัง

ตารางที่ 1 – แผนผังคลังสินค้าจำลอง

3or

ตารางที่ 2 – ตัวอย่างที่นำมาใช้ในการทดสอบ

4or

ตารางที่ 3 – ตัวแปรที่ถูกกำหนดของ Genetic Algorithms

5or

Batching Method

  • First Come First Serve – คำสั่งสินค้าใบแรกถูกนำมาจัดกลุ่มกับคำสั่งสินค้าใบถัดๆ มา จนกระทั่งเต็มความสามารถในการหยิบแต่ละครั้ง
  • Gibson and Sharp – ใช้เมตริกซ์การประมาณระยะทาง
  • Genetic Algorithms

ตารางที่ 4 – เปรียบเทียบผลการทดสอบผังคลังสินค้า 2 มิติ ด้วย FCFS, GSBM, GABM

6or

ตารางที่ 5 – เปรียบเทียบผลการทดสอบผังคลังสินค้า 3 มิติ ด้วย FCFS, GABM

7or

Conclusion

ตารางที่ 6 – เปรียบเทียบระยะทางรวม

8or

  • ได้ near-optimal solution
  • สามารถใช้ได้กับทุกรูปแบบการรวมกลุ่มคำสั่งสินค้าและทุกรูปแบบการวางผังคลังสินค้า
  • ไม่ต้องคำนวณความใกล้ของแต่ละคำสั่งหรือกลุ่มคำสั่งสินค้า
  • ไม่ต้องประมาณการระยะทาง

เอกสารอ้างอิง

Hsu, C.M., Chen, K.Y., Chen, M.C., 2005. Batching orders in warehouses by minimizing travel distance with genetic algorithms. Computers in Industry 56 (2005), 169-178.

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s