In Network Flow Planning and Servic

In Network Flow Planning and Service Network Design problems, arc-based variables are mostly used (Fig. 3), while path-based and cycle-based formulations, particularly in dynamic Service Network Designs where physical network is multiplied by the number of time periods, are computationally interesting to study . A cycle-based formulation as soon as the cycles are enumerated, outperforms the arc-based formulation in both time and solution quality (Andersen, Crainic, & Christiansen, 2009a). Andersen et al. (2009a) show that compared to the arc-based formulation which yield 5% to 20% gap, the cycle-based formulation exhibit gaps from 1% to 5%. However, the drawback is that by increasing the number of periods in the planning horizon, the number of cycles to be generated grows exponentially and generating them needs smart enumeration algorithms. To cope with this problem, Andersen, Christiansen, Crainic, and Gronhaug (2011) design a customized Branch-and-Price (B&P) algorithm for the problem presented Andersen et al. (2009a) and show its superiority to the other common exact algorithms. In their proposed algorithm, they integrate two column generation subproblems for integer cycle design and continuous flow-path variables. They also use a combination of branching strategies, a mechanism to dynamically add violated strong linear relaxation cut, and an acceleration teachnique based on depth-first search to speed up finding integer solutions.

ผลลัพธ์ (ไทย) 1:

ในเครือข่ายของการวางแผนการไหลและการบริการที่ปัญหาการออกแบบเครือข่ายโค้งตัวแปรที่ใช้ส่วนใหญ่จะใช้ (รูปที่ 3) ในขณะที่เส้นทางที่ใช้และสูตรวงจรที่ใช้โดยเฉพาะอย่างยิ่งในการให้บริการการออกแบบเครือข่ายแบบไดนามิกที่เครือข่ายทางกายภาพจะถูกคูณด้วยจำนวนของช่วงเวลา เป็นคอมพิวเตอร์ที่น่าสนใจในการศึกษา สูตรวงจรตามทันทีที่รอบจะแจกแจงมีประสิทธิภาพดีกว่าการกำหนดส่วนโค้งที่ใช้ทั้งในเวลาและวิธีการแก้ปัญหาที่มีคุณภาพ (เซน crainic, & Ch​​ristiansen, 2009a) เซนและอัล (2009a) แสดงให้เห็นว่าเมื่อเทียบกับสูตรโค้งตามที่ผลผลิต 5% ถึงช่องว่าง 20% วงจรตามช่องว่างที่กำหนดจัดแสดงตั้งแต่วันที่ 1% เป็น 5% แต่ข้อเสียเปรียบก็คือว่าโดยการเพิ่มจำนวนของระยะเวลาในขอบฟ้าวางแผนจำนวนรอบที่จะสร้างเติบโตชี้แจงและสร้างพวกเขาต้องการขั้นตอนวิธีการระบุสมาร์ท เพื่อรับมือกับปัญหานี้เซนคริสเตียน crainic และ gronhaug (2011) สาขาการออกแบบและราคา (ข&พี) ขั้นตอนวิธีการที่กำหนดเองสำหรับปัญหาที่นำเสนอเซนตอัล (2009a) และแสดงความเหนือกว่าของตนกับคนอื่น ๆ ขั้นตอนวิธีการที่ถูกต้องร่วมกัน ในขั้นตอนวิธีการที่นำเสนอของพวกเขาพวกเขารวมทั้งสองรุ่นปัญาคอลัมน์สำหรับการออกแบบวงจรจำนวนเต็มและตัวแปรการไหลของเส้นทางอย่างต่อเนื่อง พวกเขายังใช้การรวมกันของกลยุทธ์แยก​​กลไกที่จะเพิ่มแบบไดนามิกละเมิดแข็งแกร่งตัดผ่อนคลายเชิงเส้นและ teachnique เร่งความเร็วขึ้นอยู่กับความลึกการค้นหาครั้งแรกเพื่อเพิ่มความเร็วในการหาโซลูชั่นจำนวนเต็ม

ผลลัพธ์ (ไทย) 2:

ปัญหาเครือข่ายขั้นตอนการวางแผนและออกแบบเครือข่ายบริการ ตัวแปรตามส่วนโค้งเป็นส่วนใหญ่ใช้ (Fig. 3) , ขณะที่ ตามรอบ และเส้นทางตามสูตร โดยเฉพาะอย่างยิ่งในการออกแบบเครือข่ายบริการแบบไดนามิกที่ที่คูณ ด้วยจำนวนของรอบระยะเวลา เครือข่ายทางกายภาพ computationally น่าสนใจศึกษา การใช้วงจรกำหนดเป็นรอบการนำ outperforms แบ่งตามส่วนโค้งในเวลาและแก้ปัญหา (แอนเดอร์ Crainic & Christiansen, 2009a) แอนเดอร์ et al. (2009a) แสดงว่าเมื่อเทียบกับการแบ่งตามส่วนโค้งที่ช่องว่างซึ่งผลตอบแทน 5% ถึง 20% ของ ช่องแสดงรอบตามกำหนดจาก 1% เป็น 5% อย่างไรก็ตาม ข้อเสียเปรียบคือ โดยการเพิ่มจำนวนของระดับการวางแผน ขยายจำนวนรอบจะสร้างสร้าง และสร้างพวกเขาจำเป็นต้องระบุสมาร์ทอัลกอริทึม เพื่อรับมือกับปัญหานี้ แอนเดอร์ Christiansen, Crainic และ Gronhaug แอนเดอร์ et al. (2009a) แสดงขั้นตอนวิธีสาขา และราคา (B&P) การกำหนดปัญหาการออกแบบ (2011) และแสดงของปมไปอื่น ๆ ทั่วไปตรงกระบวน ในขั้นตอนวิธีการนำเสนอ พวกเขารวมสองคอลัมน์รุ่น subproblems ออกแบบเต็มรอบและตัวแปรเส้นทางขั้นตอนการต่อเนื่อง พวกเขายังใช้การรวมของกลยุทธ์การโยงหัวข้อ กลไกการเพิ่มแบบไดนามิกละเมิดตัดเป็นเส้นตรงแข็งแรง และ teachnique การเร่งความเร็วตามความลึกของการค้นหาเร็วหาจำนวนเต็ม

ผลลัพธ์ (ไทย) 3:

ในเครือข่ายการไหลของการวางแผนการออกแบบเครือข่ายบริการปัญหาและตัวแปร ARC - ใช้มีการใช้(รูปส่วนใหญ่จะเป็น 3 )หลักในขณะที่เส้นทางและการใช้โดยเฉพาะในผู้ให้บริการเครือข่ายการออกแบบแบบไดนามิกที่เครือข่ายทาง กายภาพ จะคูณด้วยจำนวนของช่วงเวลาจะต้องน่าสนใจที่จะศึกษา สูตรหนึ่งรอบ - ใช้เป็นรอบที่มีระบุไว้มีสูตร ARC - ใช้ได้ทั้งในเวลาและโซลูชัน คุณภาพ (แอนเดอร์เซ่น crainic & christiansen 2009 ) แอนเดอร์เซ่น et al . ( 2009 )แสดงให้เห็นว่าเมื่อเทียบกับสถาบัน ARC - ใช้ซึ่งให้ผลตอบแทน 5% ถึง 20% ลดช่องว่างระหว่างการใช้ช่องว่างที่จัดแสดงจาก 1% เป็น 5% แต่ถึงอย่างไรก็ตามยังมีข้อเสียเปรียบที่ว่าด้วยการเพิ่มจำนวนเส้นขอบฟ้าในช่วงเวลาในการวางแผนจำนวนรอบของการสร้างและเพิ่มขึ้นอย่างรวดเร็วซึ่งการสร้างความต้องการให้ระบุสมาร์ทอัลกอริธึม ในการรับมือกับปัญหานี้แอนเดอร์เซ่น christiansen crainic และ gronhaug ( 2011 )สาขาการออกแบบที่ปรับให้เหมาะกับความต้องการและราคา( b&p )อัลกอริทึมสำหรับปัญหาที่นำเสนอแอนเดอร์เซ่น et al . ( 2009 )และการแสดงโชว์ความเหนือกว่าของมันที่แท้จริงทั่วไปอัลกอริธึม ในอัลกอริธึมที่เสนอของพวกเขารวมระบบสอง subproblems รุ่นคอลัมน์สำหรับตัวแปรการพาธอย่างต่อเนื่องและการออกแบบการคำนวณเลขจำนวนเต็ม นอกจากนี้ยังใช้กลยุทธ์ให้เห็นโครงข่ายกลไกในการเพิ่มลดการผ่อนคลายแบบ linear Strong ละเมิด teachnique แบบไดนามิกและการเร่งความเร็วที่ใช้ในการค้นหาความลึก - ครั้งแรกในการเพิ่มความเร็วการค้นหาโซลูชันจำนวนเต็ม