A Two-Phase Heuristic for Solving Vehicle Routing Problem: a Case Study of Snack Wholesale in Kalasin Province
Keywords:
Fisher and Jaikumar algorithm, Vehicle routing problem, General Assignment Problem, Heuristic, Travelling Salesman ProblemAbstract
This paper is to present a heuristic for solving the capacitated vehicle routing problem. We apply a two-phase heuristic, Fisher and Jaikumar Algorithm (FJA), to solve for solutions with the objective of minimizing the total distance traveled. A variant FJA consists of three steps. The first step is to generate the seed vehicles. The second step is to formulate the General Assignment Problem (GAP) to allocate customers into each group. The Final step is to generate the transport route using Travelling Salesman Problem Model (TSP Model). The computational results showed that the proposed algorithm provided effective solutions. The total distance is decreased from 1,093.4 kilometers to 766.15 kilometers can be reduced to 29.93%.
References
รายงานโลจิสติกส์ของประเทศไทยประจำปี 2562, “สำนักงานคณะกรรมการพัฒนาการเศรษฐกิจและสังคมแห่งชาติ,” [ออนไลน์]. ที่มา: https://www.nesdc.go.th/more_news.php?cid=717&filename=. ¬[วันที่ 16 กรกฎาคม 2564].
G. B. Dantzig and J.H.Ramser, “The truck dispatching problem,” Management Science., vol. 6, no. 1, pp. 80–91, 1959.
ณัฏฐ์ดนัย สุพัฒน์ธนานนท์. ปณัทพร เรืองเชิงชุม.
“การเลือกรูปแบบการกระจายสินค้าที่เหมาะสมด้วยตัวแบบกำหนดการเชิงเส้นผสมจำนวนเต็ม: กรณีศึกษาธุรกิจกระจายสินค้าเครื่องดื่ม,” วารสารศรีปทุมปริทัศน์ ฉบับวิทยาศาสตร์และเทคโนโลยี., ปีที่ 12, ฉบับที่ -, น. 37-50, 2563.
สุวิมล คำแสน. อธิวัฒน์ บุญมี. อัมภิกา บุญมี,
“การวางแผนเส้นทางการเยี่ยมชมจุดท่องเที่ยวภายใต้เงื่อนไขด้านกรอบเวลาโดยประยุกต์ใช้วิธีเชิงพันธุกรรม: กรณีศึกษาเมืองจำลอง จังหวัดชลบุรี,” วารสารไทยการวิจัยดำเนินงาน., ปีที่ 6, ฉบับที่ 1, น. 1-12, 2561.
นรงค์ วิชาผา. ไทยทัศน์ สุดสวนสี. พรเทพ ขอขจายเกียรติ, “การแก้ปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลาโดยใช้วิธีเชิงพันธุกรรมแบบผสมผสานด้วยฮิวริสติกแบบแทรกไปข้างหน้าและวิธีการค้นหาคำตอบเฉพาะ,” วารสารวิชาการพระจอมเกล้าพระนครเหนือ., ปีที่ 29, ฉบับที่ 1, น. 4-13, 2562.
T.Sultana, M. A. H. Akhand and M. M. Hafizur Rahman, “A variant fisher and Jaikuamr algorithm to solve capacitated vehicle routing problem,” in 8th International Conference on Information Technology (ICIT), Jordan, 2017.
P. Hokama, F. K. Miyazawa and E. C. Xavier, “A branch – and – cut approach for the vehicle routing problem with loading constraints,” Expert Systems With Applications., vol. 47, pp. 1-13, 2016.
J. Oppen, A. løkketangen and J. Desrosiers, “Solving a rich vehicle routing and inventory problem using column generation,” Computer & Operations Research., vol. 37, no. 7, pp. 1308 -1317, 2010.
Y. Yu and et al, “A branch -and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows,” Transportation Research Part B., vol. 122, pp. 511-527, 2019.
Marshall L. Fisher and Ramchandran Jaikumar, “A generalized assignment heuristic for vehicle routing,” Networks An International journal., vol. 11, no. 2, pp. 109–124, 1981.
N.Wichapa, P.Khokhajaikiat, “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., vol. 9, no. 1, pp. 75–98, 2018.
W.Chowmalia and S.Suktoa, “A novel two-phase approach for solving the multi-compartment vehicle routing problem with a heterogeneous fleet of vehicles: a case study on fuel delivery,” Decision Science Letters., vol. 9, no. 1, pp. 70–90, 2020.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
