Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
การระบุลักษณะเฉพาะที่เด่นที่สุดของคำตอบที่ดีสำหรับปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบไม่ยูคลิดโดยใช้ตัวแบบการเรียนรู้เชิงสถิติ
Year (A.D.)
2022
Document Type
Thesis
First Advisor
Boonyar ItIntiyot
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Applied Mathematics and Computational Science
DOI
10.58837/CHULA.THE.2022.9
Abstract
A capacitated vehicle routing problem (CVRP) is a well-known NP-hard combinatorial optimization. Therefore, heuristics are the common methods used to search for a good solution. The algorithms will perform better if characteristics of good solutions of the problem are known. There was a research study in the characteristics of Euclidean CVRP solutions and the knowledge was later applied in a metaheuristic. That study becomes our motivation to study the characteristics of non-Euclidean CVRP solutions. To that end, we considered the solutions of non-Euclidean CVRP in the new Euclidean space with the same or higher dimensions using multi-dimensional scaling in which the characteristics of the solutions can be defined under Euclidean properties. In addition, the statistical learning models were employed to identify the most distinctive characteristic which yields the highest accuracy of prediction of a good solution in the new space. Moreover, decision rules were also determined for interpreting characteristics of good and bad solutions of non-Euclidean CVRP.
Other Abstract (Other language abstract of ETD)
ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดหรือ CVRP เป็นปัญหาเอ็นพีแบบยากของการหาค่าเหมาะที่สุดเชิงการจัด ดังนั้นฮิวริสติกจึงเป็นวิธีการที่นิยมใช้ในการหาคำตอบที่ดี อัลกอริทึมดังกล่าวจะทำงานได้ดีขึ้นถ้ารู้จักลักษณะเฉพาะของคำตอบที่ดีของปัญหา ทั้งนี้มีงานวิจัยที่ศึกษาลักษณะเฉพาะของคำตอบของปัญหา CVRP แบบยูคลิด และภายหลังได้นำความรู้ที่ได้ไปประยุกต์ใช้กับเมธาฮิวริสติก งานวิจัยดังกล่าวได้กลายเป็นแรงบัลดาลใจของเราในการศึกษาลักษณะเฉพาะของคำตอบของปัญหา CVRP แบบไม่ยูคลิด ดังนั้นเพื่อให้บรรลุเป้าหมายดังกล่าว เราพิจารณาคำตอบของปัญหา CVRP แบบไม่ยูคลิดในปริภูมิใหม่แบบยูคลิดที่มีมิติเดียวกันหรือสูงกว่า โดยใช้ multi-dimensional scaling ที่ซึ่งลักษณะเฉพาะของคำตอบสามารถถูกนิยามภายใต้คุณสมบัติของยูคลิด นอกจากนี้ตัวแบบการเรียนรู้เชิงสถิติได้ถูกใช้เพื่อระบุลักษณะเฉพาะที่โดดเด่นที่สุด ที่ให้ความแม่นยำสูงสุดจากการทำนายการเป็นคำตอบที่ดีในปริภูมิใหม่นี้ ยิ่งไปกว่านั้นยังมีการระบุกฎการตัดสินใจสำหรับใช้ตีความลักษณะเฉพาะของคำตอบที่ดีและไม่ดีสำหรับปัญหา CVRP แบบไม่ยูคลิด
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Inbunsong, Piyabut, "Identifying the most distinctive characteristics of a good solution for non-Euclidean CVRP using statistical learning model" (2022). Chulalongkorn University Theses and Dissertations (Chula ETD). 5720.
https://digital.car.chula.ac.th/chulaetd/5720