Using K-Means-TSP for Solving the Capacitated Vehicle Routing Problem : a Case Study of Sangchai Rungruang Company Limited
Keywords:
Two-Phase Heuristic, Vehicle Routing Problem, K-means, Travelling Salesman ProblemAbstract
This paper was to present a heuristic for solving the capacitated vehicle routing problem using K-means-TSP to tackle in a case study of snack wholesale in Kalasin Province. The proposed consists of two phase. The first phase was to cluster a group of customers using K-means algorithm. For second phase, each group of customers was generated transport routes using Travelling Salesman Problem model (TSP model). The computational results showed that the proposed heuristic provides good efficiency. The comparisons with VRP model and driver's experience shown that deviation of proposed method are +19.00% and -20.49% respectively.
References
เมธาพร คงทอง. (2556). การจัดกลุ่มลูกค้าค้างชำระของสินเชื่อที่อยู่อาศัยของธนาคารพาณิชย์แห่งหนึ่ง. วิทยานิพนธ์บริหารธุรกิจมหาบัณฑิต. มหาวิทยาลัยเทคโนโลยีราชมงคลธัญบุรี.
นรงค์ วิชาผา, ไทยทัศน์ สุดสวนสี, พรเทพ ขอขจายเกียรติ. (2562). การแก้ปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลาโดยใช้วิธีเชิงพันธุกรรมแบบผสมผสานด้วยฮิวริสติกส์แบบแทรกไปข้างหน้าและวิธีการค้นหาคำตอบเฉพาะที่. วารสารวิชาการพระจอมเกล้าพระนครเหนือ, 29(1), 4 - 13.
พัชณี มีบัว และจิราวัลย์ จิตรถเวช. (2558). การจัดกลุ่มลูกค้าของบริษัทโลจิสติกส์ที่ให้บริการขนส่งตู้คอนเทนเนอร์ทางทะเลระหว่างประเทศ. วารสารวิทยาศาสตร์ มข., 43(2), 297 - 308.
วันดี สุฉันทบุตร, สรวิชญ์ เยาวสุวรรณไชย, วัชรพจน์ ทรัพย์สงวนบุญ. (2556). การจัดกลุ่มผู้ส่งมอบด้วย Cluster Analysis เพื่อพัฒนาผู้ส่งมอบในธุรกิจค้าปลีก. วารสารวิจัย มข. (ฉบับบัณฑิตศึกษา) สาขามนุษยศาสตร์และสังคมศาสตร์, 1(3), 72 - 85.
สำนักงานสภาพัฒนาการเศรษฐกิจและสังคมแห่งชาติ. (2561). รายงานโลจิสติกส์ของประเทศไทย ประจำปี 2561 [ออนไลน์]. ค้นเมื่อ 20 มิถุนายน 2563, จาก : https://www.nesdc.go.th/ewt_dl_link.php?nid=9359.
อรนุช ชัยหมื่น. (2548). การศึกษาเปรียบเทียบแบ่งกลุ่มข้อมูลลูกค้าสินค้าหัตถกรรมไทยโดยวิธีขั้นตอนของ SOM กับ K-Means Algorithm และ Hierarchical Clustering and K-Means Algorithm. วิทยานิพนธ์วิทยาศาสตรมหาบัณฑิต. มหาวิทยาลัยเกษตรศาตร์.
Kuo, R. J., Ho, L. M., Hu, C. M. (2002). Integration of Self-Organizing Feature Map and K-Means Algorithm for Market Segmentation. Computers & Operations Research, 29(11), 1475 - 1493.
Laporte, G. (1992). The Vehicle Routing Problem : An Overview of Exact and Approximate Algorithms. European Journal of Operational Research, 59(3), 345 - 358.
Wichapa, N. and Khokhajaikiat, P. (2018). Solving a Multi-Objective Location Routing Problem for Infectious Waste Disposal Using Hybrid Goal Programming and Hybrid Genetic Algorithm. International Journal of Industrial Engineering Computations, 9(1), 75 - 98.
