ในการออกแบบอิเล็กทรอนิกส์การเดินสายไฟหรือที่เรียกกันง่ายๆ ว่าการเดินสายเป็นขั้นตอนหนึ่งในการออกแบบแผงวงจรพิมพ์ (PCB) และวงจรรวม (IC) ขั้นตอนนี้ต่อยอดจากขั้นตอนก่อนหน้า ที่เรียกว่าการจัดวางซึ่งเป็นการกำหนดตำแหน่งของแต่ละองค์ประกอบที่ใช้งานของ IC หรือส่วนประกอบบน PCB หลังจากขั้นตอนการจัดวาง การเดินสายจะเพิ่มสายไฟที่จำเป็นเพื่อเชื่อมต่อส่วนประกอบที่วางไว้อย่างถูกต้อง โดยต้องปฏิบัติตามกฎการออกแบบ ทั้งหมด สำหรับ IC โดยรวมแล้ว ขั้นตอนการจัดวางและการเดินสายในการออกแบบ IC เรียกว่าการจัดวางและการเดินสาย

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

ปัญหาเกือบทุกอย่างที่เกี่ยวข้องกับการกำหนดเส้นทางเป็นที่ทราบกันดีว่าไม่สามารถแก้ไขได้ ปัญหา การกำหนดเส้นทางที่ง่ายที่สุด เรียกว่าปัญหาต้นไม้สไตเนอร์ซึ่งเป็นการหาเส้นทางที่สั้นที่สุดสำหรับเน็ตหนึ่งตัวในชั้นเดียวโดยไม่มีสิ่งกีดขวางและไม่มีกฎการออกแบบ เป็นที่ทราบกันดีว่าเป็นปัญหาNP-completeทั้งในกรณีที่อนุญาตให้ใช้มุมทั้งหมดหรือในกรณีที่การกำหนดเส้นทางถูกจำกัดเฉพาะสายแนวนอนและแนวตั้งเท่านั้น^{[ 1 ]} รูปแบบต่างๆ ของการกำหนดเส้นทางช่องสัญญาณก็แสดงให้เห็นว่าเป็นปัญหา NP-complete เช่นกัน^{[ 2 ]}เช่นเดียวกับการกำหนดเส้นทางที่ลดการรบกวนจำนวนviasและอื่นๆ แม้ก่อนที่ปัญหาการกำหนดเส้นทางจะได้รับการพิสูจน์ว่าเป็นปัญหา NP-complete ความยากลำบากในการหาคำตอบที่เหมาะสมที่สุดก็ปรากฏชัด ดังนั้นอัลกอริทึมเกือบทั้งหมดจึงขึ้นอยู่กับฮิวริสติกซึ่งไม่ได้พยายามหาค่าที่เหมาะสมที่สุด แต่พยายามหาคำตอบที่ "ดีพอ" แทน^{[ 3 ]}

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

เครื่องมือกำหนดเส้นทาง EDA รุ่นแรกๆ นั้นเป็น "เครื่องมือกำหนดเส้นทางแบบแมนนวล" โดยผู้ออกแบบจะคลิกเมาส์ที่จุดปลายของแต่ละส่วนของเส้นลวดในแต่ละเน็ต ซอฟต์แวร์ออกแบบ PCB สมัยใหม่มักจะมี "เครื่องมือกำหนดเส้นทางแบบโต้ตอบ" โดยผู้ออกแบบจะเลือกแพดและคลิกสองสามตำแหน่งเพื่อให้เครื่องมือ EDA ทราบว่าจะไปที่ใด และเครื่องมือ EDA จะพยายามวางสายไฟให้ใกล้กับเส้นทางนั้นมากที่สุดเท่าที่จะเป็นไปได้โดยไม่ละเมิดกฎการตรวจสอบการออกแบบ (DRC) เครื่องมือกำหนดเส้นทางแบบโต้ตอบขั้นสูงบางตัวมีคุณสมบัติ "ผลักและดัน" (หรือที่เรียกว่า "ดันออกไป" หรือ "เคลื่อนย้ายอัตโนมัติ") ในเครื่องมือกำหนดเส้นทางแบบโต้ตอบ โดยเครื่องมือ EDA จะดันเน็ตอื่นๆ ออกไปหากเป็นไปได้ เพื่อวางสายไฟใหม่ในตำแหน่งที่ผู้ออกแบบต้องการและยังคงหลีกเลี่ยงการละเมิด DRC ซอฟต์แวร์ออกแบบ PCB สมัยใหม่มักจะมี "เครื่องมือกำหนดเส้นทางอัตโนมัติ" ที่กำหนดเส้นทางการเชื่อมต่อที่ยังไม่ได้กำหนดเส้นทางทั้งหมดโดยไม่ต้องมีการแทรกแซงจากมนุษย์

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

• เราเตอร์เขาวงกต^{[ 4 ] [ 5 ]}
  • เราเตอร์ลี^{[ 6 ] [ 4 ] [ 7 ]} อัลกอริทึมการค้นหา A*มักใช้ในเราเตอร์เขาวงกตและเราเตอร์ลี
  • เราเตอร์ Hadlock ^{[ 8 ]}
  • เราเตอร์น้ำท่วม^{[ 4 ]}
• เราเตอร์โพรบเส้น
  • เราเตอร์ Mikami–Tahuchi ^{[ 9 ]}
  • เราเตอร์ไฮทาวเวอร์^{[ 10 ] [ 7 ] [ 11 ] [ 4 ]}
• เราเตอร์รูปแบบ^{[ 7 ] [ 11 ]}
• เราเตอร์ช่องสัญญาณ^{[ 12 ] [ 11 ] [ 7 ] [ 13 ]}
  • เราเตอร์สวิตช์บ็อกซ์^{[ 13 ]}
  • เราเตอร์แม่น้ำ^{[ 13 ]}
  • เราเตอร์สันและตะเข็บ^{[ 14 ]}
• เราเตอร์แบบไร้กริด^{[ 15 ] [ 11 ] [ 7 ] [ 16 ]}
  • เราเตอร์พื้นที่
  • เราเตอร์ตามทฤษฎีกราฟ^{[ 17 ]}
    • เราเตอร์ Bloodhound ^{[ 18 ] [ 19 ] [ 20 ]} ( CADSTARโดยRacal-Redac / Zuken )
    • Specctra ^{[ 20 ]} (หรือที่รู้จักกันในชื่อAllegro PCB Router ) (ไม่มีตารางตั้งแต่เวอร์ชัน 10)
  • เราเตอร์เชิงโทโพโลยี
    • FreeStyle Router (หรือที่รู้จักกันในชื่อSpeedWayซึ่งเป็น โปรแกรมกำหนดเส้นทางอัตโนมัติบนระบบ MS-DOSสำหรับP-CAD )
    • TopoR ( โปรแกรมกำหนดเส้นทางอัตโนมัติสำหรับระบบปฏิบัติการ Windowsซึ่งใช้ในDelta Design ของEremex ด้วย)
    • Toporouter (เราเตอร์โอเพนซอร์สของ Anthony Blake ในPCBของชุดซอฟต์แวร์ gEDA )
    • TopRouter (โปรแกรมกำหนดเส้นทางเบื้องต้นเชิงโทโพโลยีในCadSoft / Autodesk EAGLE เวอร์ชัน7.0ขึ้นไป)
    • SimplifyPCB (เราเตอร์เชิงโทโพโลยีที่เน้นการกำหนดเส้นทางแบบกลุ่มด้วยผลลัพธ์การกำหนดเส้นทางด้วยมือ) ^{[ 21 ]}

เราเตอร์หลายตัวทำงานโดยใช้อัลกอริทึมโดยรวมดังต่อไปนี้:

• ขั้นแรก ให้กำหนดเส้นทางโดยประมาณสำหรับแต่ละเน็ต โดยมักจะกำหนดเส้นทางบนกริดหยาบ ขั้นตอนนี้เรียกว่า^การ กำหนด เส้นทางทั่วโลก [ ^{22 ]}และอาจรวมถึงการกำหนดเลเยอร์ด้วย การกำหนดเส้นทางทั่วโลกจะจำกัดขนาดและความซับซ้อนของขั้นตอนการกำหนดเส้นทางโดยละเอียดต่อไปนี้ ซึ่งสามารถทำได้ทีละช่องกริด

สำหรับการกำหนดเส้นทางโดยละเอียด เทคนิคที่พบบ่อยที่สุดคือการฉีกออกและกำหนดเส้นทางใหม่หรือที่เรียกว่าการฉีกออกและลองใหม่ : ^{[ 4 ]}

• เลือกลำดับการเดินสายสัญญาณที่ต้องการ
• วางโครงข่ายแต่ละอันตามลำดับ
• หากไม่สามารถวางเส้นทางให้กับเน็ตทั้งหมดได้สำเร็จ ให้ใช้วิธี "การทำความสะอาด" ต่างๆ โดยการลบเส้นทางที่เลือกออก เปลี่ยนลำดับของเน็ตที่เหลือที่จะวางเส้นทาง และลองวางเส้นทางที่เหลืออีกครั้ง

กระบวนการนี้จะทำซ้ำไปเรื่อยๆ จนกว่าจะมีการวางเส้นทางของเน็ตเวิร์กทั้งหมด หรือจนกว่าโปรแกรม (หรือผู้ใช้) จะยอมแพ้

แนวทางทางเลือกคือการจัดการกับการลัดวงจร การละเมิดกฎการออกแบบ สิ่งกีดขวาง ฯลฯ บนพื้นฐานที่คล้ายคลึงกันกับความยาวสายไฟที่มากเกินไป กล่าวคือ ถือเป็นต้นทุนที่จำกัดที่จะต้องลดลง (ในตอนแรก) แทนที่จะเป็นต้นทุนที่แน่นอนที่จะต้องหลีกเลี่ยง วิธีการกำหนดเส้นทางแบบ "ปรับปรุงซ้ำ" หลายรอบนี้^{[ 23 ]}อธิบายได้ด้วยอัลกอริทึมต่อไปนี้:

• สำหรับแต่ละรอบการวนซ้ำหลายรอบ:
• กำหนดหรือปรับค่าพารามิเตอร์น้ำหนักของ "ฟังก์ชันเป้าหมาย" (โดยมีค่าพารามิเตอร์น้ำหนักสำหรับแต่ละหน่วยของความยาวสายไฟที่เกิน และสำหรับแต่ละประเภทของการละเมิด) ตัวอย่างเช่น ในรอบแรก ความยาวสายไฟที่เกินอาจมีค่าใช้จ่ายสูง ในขณะที่การละเมิดการออกแบบ เช่น การลัดวงจร การอยู่ติดกัน ฯลฯ จะมีค่าใช้จ่ายต่ำ ในรอบต่อๆ ไป ลำดับความสำคัญของค่าใช้จ่ายจะเปลี่ยนไป เพื่อให้การละเมิดมีค่าใช้จ่ายสูง หรืออาจถูกห้ามโดยเด็ดขาด
• เลือก (หรือสุ่มเลือก) ลำดับการเดินสายเน็ตในรอบนี้
• "รื้อถอน" (หากมีการเดินสายไว้ก่อนหน้านี้) และเดินสายใหม่ให้กับแต่ละสายทีละสาย เพื่อลดค่าของฟังก์ชันเป้าหมายสำหรับสายนั้นๆ ให้เหลือน้อยที่สุด (โดยทั่วไปแล้ว การเดินสายบางเส้นอาจมีการลัดวงจรหรือข้อบกพร่องด้านการออกแบบอื่นๆ)
• ดำเนินการวนซ้ำในรอบถัดไปจนกว่าการกำหนดเส้นทางจะเสร็จสมบูรณ์และถูกต้อง ไม่สามารถปรับปรุงให้ดีขึ้นได้อีก หรือเป็นไปตามเกณฑ์การยุติอื่นๆ

เราเตอร์ส่วนใหญ่จะกำหนดเลเยอร์การเดินสายเพื่อรองรับการเดินสายในทิศทาง "x" หรือ "y" เป็นหลัก แม้ว่าจะมีเราเตอร์บางตัวที่หลีกเลี่ยงหรือลดความจำเป็นในการกำหนดดังกล่าว^{[ 24 ]}แต่ละแนวทางมีข้อดีและข้อเสีย การกำหนดทิศทางที่จำกัดทำให้การออกแบบแหล่งจ่ายไฟและการควบคุมการรบกวนระหว่างเลเยอร์ทำได้ง่ายขึ้น แต่การอนุญาตให้มีเส้นทางตามอำเภอใจสามารถลดความจำเป็นในการใช้ vias และลดจำนวนเลเยอร์การเดินสายที่จำเป็นลงได้

• ระบบอัตโนมัติการออกแบบอิเล็กทรอนิกส์
• ขั้นตอนการออกแบบ (EDA)
• การออกแบบวงจรรวม
• สถานที่และเส้นทาง
• ขั้วอัตโนมัติ (คู่สายต่างระดับ)
• การเปลี่ยนเส้นทางอัตโนมัติ (อีเธอร์เน็ต)