Identifying the most distinctive characteristics of a good solution for non-Euclidean CVRP using statistical learning model

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

Name: Piyabut Inbunsong

LCSH: Vehicle routing problem

LCSH: Euclidean algorithm

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.

Abstract: ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดหรือ CVRP เป็นปัญหาเอ็นพีแบบยากของการหาค่าเหมาะที่สุดเชิงการจัด ดังนั้นฮิวริสติกจึงเป็นวิธีการที่นิยมใช้ในการหาคำตอบที่ดี อัลกอริทึมดังกล่าวจะทำงานได้ดีขึ้นถ้ารู้จักลักษณะเฉพาะของคำตอบที่ดีของปัญหา ทั้งนี้มีงานวิจัยที่ศึกษาลักษณะเฉพาะของคำตอบของปัญหา CVRP แบบยูคลิด และภายหลังได้นำความรู้ที่ได้ไปประยุกต์ใช้กับเมธาฮิวริสติก งานวิจัยดังกล่าวได้กลายเป็นแรงบัลดาลใจของเราในการศึกษาลักษณะเฉพาะของคำตอบของปัญหา CVRP แบบไม่ยูคลิด ดังนั้นเพื่อให้บรรลุเป้าหมายดังกล่าว เราพิจารณาคำตอบของปัญหา CVRP แบบไม่ยูคลิดในปริภูมิใหม่แบบยูคลิดที่มีมิติเดียวกันหรือสูงกว่า โดยใช้ multi-dimensional scaling ที่ซึ่งลักษณะเฉพาะของคำตอบสามารถถูกนิยามภายใต้คุณสมบัติของยูคลิด นอกจากนี้ตัวแบบการเรียนรู้เชิงสถิติได้ถูกใช้เพื่อระบุลักษณะเฉพาะที่โดดเด่นที่สุด ที่ให้ความแม่นยำสูงสุดจากการทำนายการเป็นคำตอบที่ดีในปริภูมิใหม่นี้ ยิ่งไปกว่านั้นยังมีการระบุกฎการตัดสินใจสำหรับใช้ตีความลักษณะเฉพาะของคำตอบที่ดีและไม่ดีสำหรับปัญหา CVRP แบบไม่ยูคลิด

Chulalongkorn University. Office of Academic Resources

Address: BANGKOK

Email: cuir@car.chula.ac.th

Name: Boonyar ItIntiyot

Role: advisor

Created: 2022

Modified: 2024-11-17

Issued: 2024-11-17

วิทยานิพนธ์/Thesis

application/pdf

eng

DegreeName: Master of Science

Level: Master's Degree

Descipline: Applied Mathematics and Computational Science

Grantor: Chulalongkorn University

©copyrights Chulalongkorn University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	6270066923[1].pdf	3.84 MB

ใช้เวลา

0.027914 วินาที