본문 바로가기
KERD
논문KCI 등재

클러스터링 기반의 최적 차량 운행 계획 수립을 위한 비교연구

Comparative Analysis for Clustering Based Optimal Vehicle Routes Planning

신광섭|김재원
사)한국빅데이터학회 (KOREA BIGDATA SOCIETY)|2020.08|한국빅데이터학회 학회지 (The Korea Journal of BigData)|제5권 제1호|pp. 155-180|DOI 10.36498/kbigdt.2020.5.1.155

0

조회

0

다운로드

3

인용

0

참고문헌

키워드

빅데이터Big DataClustering클러스터링VRP차량경로 계획CFRS

초록

화물의 수배송을 위한 차량의 배차 및 최적 경로 설계는 물류 서비스의 효율성 향상을 위한 가장 핵심적인 역할을 담당한다. 이 문제는 차량의 대수, 차량별 적재 용량, 차량의 총 이동거리와 같이 다양한 비용 요소를 동시에 고려해야 하기 때문이다. 최근 비용 최소화 및 운영 효율성 향상을 위해 TMS를 도입하는 사례가 증가하고 있으나, 현장에서 필요한 모든 요소를 고려하지 못한다는 한계가 존재한다. 이를 해결하기 위해 현장 전문가가 TMS의 결과를 경험과 직관에 기반하여 수정하는 과정이 필요하다. 본 연구에서는 지금까지 총 비용의 최소화에 집중하고 있는 기존 연구들과 달리 서비스에 투입되는 자원 활용의 효율성과 형평성을 동시에 높일 수 있는 방법을 제안한다. 이를 위해 Cluster-First Route-Second (CFRS)기법을 활용한다. 고객의 위치를 기준으로 네 가지 클러스터링 알고리즘(K-Means, K-Medoids, DBSCAN, Model-based)과 Fisher & Jaikumar 알고리즘을 적용하여 고객들을 군집화하였다. 이 후, 군집별 최적의 차량 경로 계획을 수립하였다. 수치 실험을 통해 본 연구에서 제안하는 CFRS 기법을 적용한 방안이 상대적으로 차량의 전체 이동거리와 평균 이동거리 및 이동시간이 더 절감될 수 있다는 사실을 확인하였다. 또한, 차량별 방문하는 고객의 수에 대한 편차가 더 낮다는 사실로부터 기본적인 차량 경로 배정 유형에 비해본 연구에서 제안하는 방안이 상대적으로 형평성 있게 업무가 할당되었음을 확인할 수 있었다.

Abstract

It takes the most important role the problem of assigining vehicles and desigining optimal routes for each vehicle in order to enhance the logistics service level. While solving the problem, various cost factors such as number of vehicles, the capacity of vehicles, total travelling distance, should be considered at the same time. Although most of logistics service providers introduced the Transportation Management System (TMS), the system has the limitation which can not consider the practical constraints. In order to make the solution of TMS applicable, it is required experts revised the solution of TMS based on their own experience and intuition. In this research, different from previous research which have focused on minimizing the total cost, it has been proposed the methodology which can enhance the efficiency and fairness of asset utilization, simultaneously. First of all, it has been adopted the Cluster-First Route-Second (CFRS) approach. Based on the location of customers, we have grouped customers as clusters by using four different clustering algorithm such as K-Means, K-Medoids, DBSCAN, Model-based clustering and a procedural approach, Fisher & Jaikumar algorithm. After getting the result of clustering, it has been developed the optiamal vehicle routes within clusters. Based on the result of numerical experiments, it can be said that the propsed approach based on CFRS may guarantee the better performance in terms of total travelling time and distance. At the same time, the variance of travelling distance and number of visiting customers among vehicles, it can be concluded that the proposed approach can guarantee the better performance of assigning tasks in terms of fairness

참고문헌 (68)

  1. 김지수, "Refuse collection network design and vehicle routing in reverse logistics", 박사, 산업공학과, pp.2014
  2. 나유진, "시간대별 도로교통 상황을 고려한 도심 식자재 배송서비스 개선방안에 관한 연구", 로지스틱스연구, 24(4), pp.79~96 (2016), 한국로지스틱스학회[DOI]
  3. Ai, T. J., "A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery", Computers & Operations Research, 36(5), pp.1693~1702 (2009)
  4. Big data analytics architecture for real-time traffic control, "Amini, S.", 710~715 (2017)
  5. Badeau, P., "A parallel tabu search heuristic for the vehicle routing problem with time windows", Transportation Research Part C : Emerging Technologies, 5(2), pp.109~122 (1997)
  6. Baker, B. M., "A genetic algorithm for the vehicle routing problem", Computers & Operations Research, 30(5), pp.787~800 (2003)
  7. Baldacci, R., "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints", European Journal of Operational Research, 218(1), pp.1~6 (2012)
  8. Bast, H., "Route planning in transportation networks", 19~80 (2016)
  9. Beasley, J. E., "Route first—cluster second methods for vehicle routing", Omega, 11(4), pp.403~408 (1983)
  10. Calvete, H. I., "A goal programming approach to vehicle routing problems with soft time windows", European Journal of Operational Research, 177(3), pp.1720~1733 (2007)
  11. Charrad, M., "Package ‘NbClust’", J.Stat.Soft, 61, pp.1~36 (2014)
  12. Chen, J., "Vehicle routing problem with simultaneous deliveries and pickups", Journal of the Operational Research Society, 57(5), pp.579~587 (2006)
  13. Chun-Hua, L., "Vehicle routing problem with time windows and simultaneous pickups and deliveries", pp.685~689 (2009)
  14. Cordeau, J., "A tabu search heuristic for periodic and multi-depot vehicle routing problems", Networks, 30(2), pp.105~119 (1997)
  15. Cordeau, J., "A guide to vehicle routing heuristics", Journal of the Operational Research society, pp.512~522 (2002)
  16. Dantzig, G., "Solution of a large-scale traveling-salesman problem", Journal of the operations research society of America, 2(4), pp.393~410 (1954)
  17. Davies, D. L., "A cluster separation measure", IEEE Transactions on Pattern Analysis and Machine Intelligence, (2), pp.224~227 (1979)
  18. De Jaegere, N., "The vehicle routing problem:state of the art classification and review", ~ (2014)
  19. Dempster, A. P., "Maximum likelihood from incomplete data via the EM algorithm", Journal of the royal statistical society.Series B (methodological), pp.1~38 (1977)
  20. Dondo, R., "A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows", European Journal of Operational Research, 176(3), pp.1478~1507 (2007)
  21. Ester, M., "A density-based algorithm for discovering clusters in large spatial databases with noise", 96(34), pp.226~231 (1996)
  22. Feng, L., "Conceptual modeling of evolvable local searches in memetic algorithms using linear genetic programming : a case study on capacitated vehicle routing problem", Soft Computing, 20(9), pp.3745~3769 (2016)
  23. Fisher, M. L., "A generalized assignment heuristic for vehicle routing", Networks, 11(2), pp.109~124 (1981)
  24. Fraley, C., "How many clusters? Which clustering method? Answers via model-based cluster analysis", The computer journal, 41(8), pp.578~588 (1998)
  25. Fraley, C., "Model-based clustering, discriminant analysis, and density estimation", Journal of the American statistical Association, 97(458), pp.611~631 (2002)
  26. Gendreau, M., "A tabu search heuristic for the vehicle routing problem", Management science, 40(10), pp.1276~1290 (1994)
  27. Gendreau, M., "A tabu search heuristic for the heterogeneous fleet vehicle routing problem", Computers & Operations Research, 26(12), pp.1153~1173 (1999)
  28. Gillett, B. E., "A heuristic algorithm for the vehicle-dispatch problem", Operations research, 22(2), pp.340~349 (1974)
  29. Goetschalckx, M., "The vehicle routing problem with backhauls", European Journal of Operational Research, 42(1), pp.39~51 (1989)
  30. Gounaris, C. E., "The robust capacitated vehicle routing problem under demand uncertainty", Operations research, 61(3), pp.677~693 (2013)
  31. Grangier, P., "An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization", European Journal of Operational Research, 254(1), pp.80~91 (2016)
  32. "Gurobi Optimizer Reference Manual" (2016)[URL]
  33. Han, J., "Data mining:concepts and techniques" (2011), Elsevier
  34. Hernandez, F., "Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows", European Journal of Operational Research, 249(2), pp.551~559 (2016)
  35. Iassinovskaia, G., "The inventory-routing problem of returnable transport items with time windows and simultaneous pickup and delivery in closed-loop supply chains", International Journal of Production Economics, 183, pp.570~582 (2017)
  36. Imran, A., "A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem", European Journal of Operational Research, 197(2), pp.509~518 (2009)
  37. Irnich, S., "A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles", European Journal of Operational Research, 122(2), pp.310~328 (2000)
  38. Jepsen, M., "A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem", Transportation Science, 47(1), pp.23~37 (2013)
  39. Jin, J., "A cooperative parallel metaheuristic for the capacitated vehicle routing problem", Computers &Operations Research, 44, pp.33~41 (2014)
  40. Karadimas, N. V., "Routing optimization heuristics algorithms for urban solid waste transportation management", WSEAS Transaction on Computers, 7(12), pp.2022~2031 (2008)
  41. Kaufman, L., "Clustering by means of medoids" (1987), North-Holland
  42. Ko, H. J., "A genetic algorithm-based heuristic for the dynamic integrated forward", reverse logistics network for 3PLs, 2007, pp.34(2), 346~366
  43. Koç, Ç., "The green vehicle routing problem : A heuristic based exact solution approach", Applied Soft Computing, 39, pp.154~164 (2016)
  44. Land, A. H., "50 Years of Integer Programming 1958-2008", pp.105~132 (2010)
  45. Li, F., "A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem", Computers & Operations Research, 34(9), pp.2734~2742 (2007)
  46. Lim, A., "Multi-depot vehicle routing problem : A one-stage approach", IEEE transactions on Automation Science and Engineering, 2(4), pp.397~402 (2005)
  47. Lysgaard, J., "A branchand-cut-and-price algorithm for the cumulative capacitated vehicle routing problem", European Journal of Operational Research, 236(3), pp.800~810 (2014)
  48. Michael, R. G., "Computers and intractability: a guide to the theory of NP-completeness", pp.90~91 (1979), WH Free.Co
  49. Mittal, P., "Development of intelligent transportation system for improving average moving and waiting time with artificial intelligence", Indian Journal of Science and Technology, 9(3) (2016)
  50. Nagy, G., "Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries", European Journal of Operational Research, 162(1), pp.126~141 (2005)
  51. Ombuki, B., "Multi-objective genetic algorithms for vehicle routing problem with time windows", Applied Intelligence, 24(1), pp.17~30 (2006)
  52. Penna, P. H. V., "An iterated local search heuristic for the heterogeneous fleet vehicle routing problem", Journal of Heuristics, pp.1~32 (2013)
  53. Potvin, J., "A genetic algorithm for vehicle routing with backhauling", Applied Intelligence, 6(4), pp.345~355 (1996)
  54. Reed, M., "An ant colony algorithm for the multi-compartment vehicle routing problem", Applied Soft Computing, 15, pp.169~176 (2014)
  55. Renaud, J., "A tabu search heuristic for the multi-depot vehicle routing problem", Computers & Operations Research, 23(3), pp.229~235 (1996)
  56. Rivera, J. C., "Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem", European Journal of Operational Research, 249(1), pp.93~104 (2016)
  57. Roodbergen, K. J., "Routing order pickers in a warehouse with a middle aisle", European Journal of Operational Research, 133(1), pp.32~43 (2001)
  58. Rousseeuw, P. J., "Silhouettes : a graphical aid to the interpretation and validation of cluster analysis", Journal of Computational and Applied Mathematics, 20, pp.53~65 (1987)
  59. Ryan, D. M., "Extensions of the petal method for vehicle routeing", Journal of the Operational Research Society, pp.289~296 (1993)
  60. Savelsbergh, M. W., "The vehicle routing problem with time windows : Minimizing route duration", ORSA journal on computing, 4(2), pp.146~154 (1992)
  61. Scott, A. J., "Clustering methods based on likelihood ratio criteria", Biometrics, pp.387~397 (1971)
  62. Subramanian, A., "A hybrid algorithm for the heterogeneous fleet vehicle routing problem", European Journal of Operational Research, 221(2), pp.285~295 (2012)
  63. Taillard, É., "A tabu search heuristic for the vehicle routing problem with soft time windows", Transportation science, 31(2), pp.170~186 (1997)
  64. Taş, D., "Vehicle routing with soft time windows and stochastic travel times : A column generation and branch-and-price solution approach", European Journal of Operational Research, 236(3), pp.789~799 (2014)
  65. Tibshirani, R., "Estimating the number of clusters in a data set via the gap statistic", Journal of the Royal Statistical Society : Series B(Statistical Methodology), 63(2), pp.411~423 (2001)
  66. Wei, L., "A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints", European Journal of Operational Research (2017)
  67. Yao, B., "An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot", Annals of Operations Research, 242(2), pp.303~320 (2016)
  68. Yu, B., "An improved ant colony optimization for vehicle routing problem", European Journal of Operational Research, 196(1), pp.171~176 (2009)

관련 논문AI추천

K-Means Clustering의 차량경로문제 적용연구문기주, 하제민한국산업경영시스템학회 · 한국산업경영시스템학회지2015 · 제38권 제3호수요응답형 대중교통체계를 위한 클러스터링 기반의 다중차량 경로탐색 방법론 연구김정윤, 김지후, 여화수한국ITS학회 · 한국ITS학회 논문지2020 · 제19권 제5호왕복비대칭 차량이동속도 하에서의 복수차량 배송경로 최적화문기주, 박성미한국산업경영시스템학회 · 한국산업경영시스템학회지2013 · 제36권 제4호편의점 물류 효율화를 위한 집하 시간 간격 최적 운영 방안강명구, 김용재, 남대식, 임현우한국교통연구원 · 교통연구2025 · 제32권 제2호유연 회차와 플렉스를 이용한 빠른 배송 서비스박태준, 정예림한국컴퓨터정보학회 · 한국컴퓨터정보학회논문지2021 · 제26권 제9호Sweep해법 및 공동구역 2차 재할당에 의한 복수차량 배송 최적화 연구문기주, 박성미한국산업경영시스템학회 · 한국산업경영시스템학회지2014 · 제37권 제1호

이 간행물의 다른 논문 (18건)

LSTM을 활용한 고위험성 조류인플루엔자(HPAI) 확산 경로 예측강태훈, 이원빈, 한예지, 최대우, 송유한pp. 1-9교육종단연구 분석을 위한 빅데이터 플랫폼 개발 및 적용박정, 조완섭pp. 11-27맞춤형 여행 콘텐츠 개발을 위한 OCR 기법을 활용한 영화 속 촬영지 정보 추출 방안 제시강주영, 박은비, 신유빈pp. 29-39탐색적 자료 분석(EDA) 기법을 활용한 온라인 해외직접구매에 대한 소비자 불만족 및 제도 개선 방안 연구박성우, 강주영pp. 41-54포스퀘어 사용자의 집단적 활동 군집화: 서울시 사례조재희, 서일정pp. 55-63
원문 보기