A combinatorial optimization proble

A combinatorial optimization problem requires to take discrete decisions under constraints and optimizing a given objective function, such as planning, routing and scheduling problems. These problems arise in many industrial fields and are of economical significance. The general scope of this thesis is about Local Search (LS), that is an iterative methodology to solve combinatorial optimization problems. The principle is to generate a first solution, and to iteratively perform slight modifications to this solution in order to obtain a good score with respect to the objective function. Very Large-Scale Neighborhood (VLSN) is a sophisticated technique in Local Search to perform many modifications to the solutions at each
iteration. These techniques have a greater visibility at each iteration and choose the next solution more efficiently. Very Large-Scale Neighborhoods have been successfully applied on many complex real-life problems. However VLSN are very hard to implement. This prevents the applicability of these techniques to new problems. This thesis aims at remedying this limitation and presents a frame-work that expresses VLSN search algorithms in terms of high-level components. VLSN search algorithms expressed by mean of our framework exhibits several benefits compared to existing approaches: 1) a more natural design of VLSN search algorithm, 2) a better reusability of existing components, 3) a greater adaptability to modifications to the problem to solve, and 4) a faster development of complex VLSN approaches. As a proof of concept, we implemented this framework. Experimental results show that our approach is comparable in time with respect to existing approaches, and that it allows to obtain state-of-the-art solutions on two real-life problems exhibiting different structure (one timetabling and one routing application).This validates that our approach is a helpful and efficient support to develop VLSN search algorithms on new and complex problems.

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

ต้องเพิ่มประสิทธิภาพปัญหาปัญหาจะตัดสินใจแยกกันภายใต้ข้อจำกัดและการเพิ่มประสิทธิภาพฟังก์ชันวัตถุประสงค์กำหนด วางแผน สายงานการผลิต และปัญหาการจัดกำหนดการ ปัญหาเหล่านี้เกิดขึ้นในอุตสาหกรรมหลายสาขา และสำคัญประหยัด ขอบเขตทั่วไปของวิทยานิพนธ์นี้จะเกี่ยวกับเครื่องค้นหา (LS), ซึ่งเป็นวิธีการซ้ำเพื่อแก้ปัญหาปัญหาเพิ่มประสิทธิภาพ หลักการคือ การสร้างโซลูชันแรก และดำเนินการแก้ไขปัญหานี้การปรับเปลี่ยนเล็กน้อยเพื่อให้ได้คะแนนดีกับฟังก์ชันวัตถุประสงค์ซ้ำ ๆ ย่าน Large-Scale มาก (VLSN) เป็นเทคนิคที่ซับซ้อนในการค้นหาการปรับเปลี่ยนเพื่อแก้ปัญหาที่แต่ละท้องถิ่น เกิดซ้ำ เทคนิคเหล่านี้ได้เห็นมากกว่าที่เกิดซ้ำแต่ละ และเลือกแก้ปัญหาต่อไปมีประสิทธิภาพมากขึ้น ใช้ละแวกใกล้เคียง Large-Scale มากกับปัญหาชีวิตที่ซับซ้อนมากมายประสบความสำเร็จ อย่างไรก็ตาม VLSN ได้ยากมากที่จะใช้ ซึ่งป้องกันความเกี่ยวข้องของเทคนิคเหล่านี้จะมีปัญหา วิทยานิพนธ์นี้มีวัตถุประสงค์เพื่อ remedying ข้อจำกัดนี้ และแสดงเฟรมงานที่แสดง VLSN อัลกอริทึมค้นหาในคอมโพเนนต์ระดับสูง การจัดแสดงแสดง โดยของกรอบงานของอัลกอริทึมค้นหา VLSN ประโยชน์หลายประการเมื่อเทียบกับแนวทางที่มีอยู่: 1) การออกแบบธรรมชาติของอัลกอริทึมการค้นหา VLSN, reusability 2) ที่ดีกว่าของคอมโพเนนต์ที่มีอยู่ 3) ที่หลากหลายมากขึ้นเพื่อแก้ไขปัญหาการแก้ไข และ 4) การพัฒนาเร็วกว่าวิธี VLSN ที่ซับซ้อน เป็นหลักฐานของแนวคิด เราใช้กรอบนี้ ผลการทดลองแสดงว่า วิธีการของเราได้เปรียบเวลากับวิธีที่มีอยู่ และที่จะช่วยให้สามารถแก้ไขปัญหารัฐ-of-the-art ในปัญหาชีวิตสองอย่างมีระดับโครงสร้างแตกต่างกัน (timetabling หนึ่งและโปรแกรมประยุกต์สายหนึ่ง) ตรวจสอบว่าวิธีการของเรามีประโยชน์ และมีประสิทธิภาพสนับสนุนพัฒนาอัลกอริทึมค้นหา VLSN ในปัญหาใหม่ และซับซ้อน

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

ปัญหาการเพิ่มประสิทธิภาพ combinatorial ต้องใช้การตัดสินใจที่ไม่ต่อเนื่องภายใต้ข้อ จำกัด และเพิ่มประสิทธิภาพการทำงานของวัตถุประสงค์ที่กำหนดเช่นการวางแผนเส้นทางและปัญหาการตั้งเวลา ปัญหาเหล่านี้เกิดขึ้นในเขตอุตสาหกรรมจำนวนมากและมีความสำคัญทางเศรษฐกิจ ขอบเขตทั่วไปของวิทยานิพนธ์ฉบับนี้เป็นเรื่องเกี่ยวกับการค้นหาในท้องถิ่น (แอลเอส) ที่เป็นวิธีการที่กล่าวย้ำในการแก้ปัญหาการเพิ่มประสิทธิภาพ combinatorial หลักการคือการสร้างโซลูชั่นแรกและซ้ำดำเนินการปรับเปลี่ยนเล็กน้อยเพื่อแก้ปัญหานี้เพื่อให้ได้คะแนนดีเกี่ยวกับฟังก์ชันวัตถุประสงค์ พื้นที่ใกล้เคียงมากขนาดใหญ่ (VLSN) เป็นเทคนิคที่มีความซับซ้อนในการค้นหาในท้องถิ่นในการดำเนินการปรับเปลี่ยนจำนวนมากที่จะแก้ปัญหาในแต่ละ
ซ้ำ เทคนิคเหล่านี้มีการมองเห็นมากขึ้นที่ซ้ำกันและเลือกวิธีการแก้ปัญหาต่อไปได้อย่างมีประสิทธิภาพ มากย่านขนาดใหญ่ได้รับการใช้ประสบความสำเร็จในหลายปัญหาที่ซับซ้อนในชีวิตจริง อย่างไรก็ตาม VLSN จะยากมากที่จะใช้ นี้จะช่วยป้องกันการบังคับใช้เทคนิคเหล่านี้ไปสู่ปัญหาใหม่ วิทยานิพนธ์ฉบับนี้มีจุดมุ่งหมายในการรักษาข้อ จำกัด นี้และนำเสนอกรอบการทำงานที่แสดงออกถึงขั้นตอนวิธีการค้นหา VLSN ในแง่ขององค์ประกอบในระดับสูง VLSN ค้นหาขั้นตอนวิธีการแสดงโดยเฉลี่ยของการจัดแสดงนิทรรศการของเรากรอบประโยชน์หลายประการเมื่อเทียบกับวิธีการที่มีอยู่: 1) การออกแบบที่เป็นธรรมชาติมากขึ้นของวิธีการค้นหา VLSN 2) สามารถนำมาใช้ที่ดีขึ้นของส่วนประกอบที่มีอยู่ 3) การปรับตัวมากขึ้นเพื่อแก้ไขปัญหาที่จะแก้ปัญหา และ 4) การพัฒนาได้เร็วขึ้นของวิธีการที่ซับซ้อน VLSN เป็นหลักฐานของแนวคิดที่เรานำมาใช้กรอบนี้ ผลการทดลองแสดงให้เห็นว่าวิธีการของเราก็เปรียบได้ในเวลาที่มีความเคารพต่อวิธีการที่มีอยู่และที่จะช่วยให้การแก้ปัญหาที่จะได้รับรัฐของศิลปะบนสองปัญหาในชีวิตจริงแสดงโครงสร้างที่แตกต่างกัน (หนึ่ง timetabling และการประยุกต์ใช้เส้นทางหนึ่ง) นี้จะตรวจสอบ ว่าวิธีการของเราคือการสนับสนุนที่เป็นประโยชน์และมีประสิทธิภาพในการพัฒนาอัลกอริทึมในการค้นหา VLSN ปัญหาใหม่และซับซ้อน

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

ปัญหาการเพิ่มประสิทธิภาพต้องใช้การตัดสินใจที่เหมาะสมและต่อเนื่อง ภายใต้เงื่อนไขที่กำหนดเป้าหมายการทำงาน เช่น การวางแผน การจัดเส้นทางและตารางมีปัญหา ปัญหาเหล่านี้เกิดขึ้นในเขตอุตสาหกรรมมาก และมีความสำคัญทางเศรษฐกิจ . ขอบเขตทั่วไปของวิทยานิพนธ์ฉบับนี้คือการค้นหาในท้องถิ่น ( LS )นั่นเป็นวิธีการของการแก้ปัญหาการเพิ่มประสิทธิภาพการ . หลักการคือการสร้างโซลูชั่นแรก และซ้ำแสดงการปรับเปลี่ยนเล็กน้อยในโซลูชั่นนี้เพื่อให้ได้คะแนนที่ดีเกี่ยวกับฟังก์ชั่นวัตถุประสงค์บ้านขนาดใหญ่มาก ( vlsn ) เป็นเทคนิคที่ซับซ้อนในการค้นหาในท้องถิ่นเพื่อดําเนินการแก้ไขหลายปัญหาที่ซ้ำกัน
. เทคนิคเหล่านี้มีมากขึ้นมองเห็นได้ในแต่ละ iteration และเลือกโซลูชั่นต่อไปได้อย่างมีประสิทธิภาพ ย่านมากขนาดใหญ่ได้รับการสมัครเรียบร้อยแล้ว ในชีวิตจริง ปัญหาที่ซับซ้อนมาก อย่างไรก็ตาม vlsn ยากมากที่จะใช้ .นี้จะช่วยป้องกันการประยุกต์ใช้เทคนิคเหล่านี้กับปัญหาใหม่ วิทยานิพนธ์ฉบับนี้มีจุดมุ่งหมายเพื่อการแก้ปัญหาข้อจำกัดนี้ และเสนอกรอบการทำงานที่แสดงขั้นตอนวิธีการค้นหา vlsn ในแง่ของชิ้นส่วนพื้นฐาน vlsn ขั้นตอนวิธีการค้นหาที่แสดงออกโดยหมายถึงกรอบของเราจัดแสดงหลายประการเมื่อเทียบกับวิธีการที่มีอยู่ : 1 ) แบบธรรมชาติมากกว่า vlsn ค้นหาอัลกอริทึม2 ) ใช้ดีกว่าขององค์ประกอบที่มีอยู่ 3 ) การปรับตัวมากขึ้นเพื่อแก้ไขปัญหา เพื่อแก้ปัญหา และ 4 ) การพัฒนาอย่างรวดเร็วของวิธีการ vlsn ซับซ้อน เป็นหลักฐานของแนวคิดที่เราใช้กรอบนี้ ผลการทดลองแสดงให้เห็นว่าวิธีการของเราเทียบได้ในเวลาเกี่ยวกับวิธีการที่มีอยู่และมันสามารถได้รับโซลูชั่นที่ทันสมัยในชีวิตจริงปัญหา exhibiting สองโครงสร้างที่แตกต่างกัน ( และการบริหารจัดการใช้ห้องประชุม 1 เส้นทาง ) นี้ตรวจสอบว่า แนวทางของเราคือการสนับสนุนที่เป็นประโยชน์และมีประสิทธิภาพเพื่อพัฒนา vlsn ขั้นตอนวิธีการค้นหาปัญหาใหม่และซับซ้อน