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

김재원; 신광섭

doi:10.36498/kbigdt.2020.5.1.155

클러스터링 기반의 최적 차량 운행 계획 수립을 위한 비교연구
Comparative Analysis for Clustering Based Optimal Vehicle Routes Planning 원문보기

The journal of Bigdata = 한국빅데이터학회지, v.5 no.1, 2020년, pp.155 - 180

초록
AI-Helper

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

Abstract ▼ AI-Helper

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.

주제어

질의응답

핵심어	질문	논문에서 추출한 답변
	VRP 알고리즘은 어느 시스템에 탑재되는가?	이러한 VRP 알고리즘은 Transportation Management system (TMS)에 탑재된다(Ko & Evans, 2007; Karadimas, et al., 2008).
	TMS의 운영 목적은?	, 2008). TMS는 전체 시스템의 효율성 극대화 및 비용 최소화를 목적으로 운영되는데, 이를 위해 투입 차량 대수, 총 운행 및 시간으로 구성되는 비용함수를 최소화하기 위한 방안을 수립한다. 그러나 앞의 비용 항목 외에도 실제 현장에서는 정량적으로 측정하기 어려운 항목이 존재하여 수리 모형으로 인해 도출된 최적해가 반드시 실제 현장에 적용될 수 있다고 보장할 수는 없다.
	Cluster-First Route-Second 접근법이란 어떤 방법인가?	이를 위해 본 연구에서는 전통적인 VRP 를 해결하기 위한 방법 중 Cluster-First Route-Second (CFRS) 접근법을 활용한다. CFRS는 배송기사가 방문해야 할 위치를 다수의 군집으로 나눈 다음 군집 내에서의 최적의 배송 경로를 설계하는 방법이다. CFRS는 단순히 배송 거리 혹은 시간을 기준으로 개별 차량의 이동경로를 설정하는 기존의 방법과는 달리 방문지 사이의 특성을 고려하여 군집을 구성하게 되면 앞서 언급한 배송차량 혹은 기사들 사이의 불균형을 사전에 방지할 수 있다.

참고문헌 (68)

김지수(2014). Refuse collection network design and vehicle routing in reverse logistics, 박사학위논문. 한양대학교 대학원.
나유진, 임현우, 문정민(2016). 시간대별 도로교통 상황을 고려한 도심 식자재 배송서비스 개선 방안에 관한 연구. 로지스틱스연구, 24(4), 79-97.

상세보기
Ai, T. J. & Kachitvichyanukul, V. (2009). A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 36(5), 1693-1702.

상세보기
Amini, S., Gerostathopoulos, I. & Prehofer, C. (2017). Big data analytics architecture for real-time traffic control., 710-715.
Badeau, P., Guertin, F., Gendreau, M., Potvin, J. & Taillard, E. (1997). A parallel tabu search heuristic for the vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies, 5(2), 109-122.

상세보기
Baker, B. M. & Ayechew, M. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800.

상세보기
Baldacci, R., Mingozzi, A. & Roberti, R. (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1), 1-6.

상세보기
Bast, H., Delling, D., Goldberg, A., Muller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D. & Werneck, R. F. (2016). Route planning in transportation networks., 19-80.
Beasley, J. E. (1983). Route first-cluster second methods for vehicle routing. Omega, 11(4), 403-408.

상세보기
Calvete, H. I., Gale, C., Oliveros, M. & Sanchez-Valverde, B. (2007). A goal programming approach to vehicle routing problems with soft time windows. European Journal of Operational Research, 177(3), 1720-1733.

상세보기
Charrad, M., Ghazzali, N., Boiteau, V., Niknafs, A. & Charrad, M. M. (2014). Package 'NbClust'. J.Stat.Soft, 61, 1-36.
Chen, J. & Wu, T. (2006). Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, 57(5), 579-587.

상세보기
Chun-Hua, L., Hong, Z. & Jian, Z. (2009). Vehicle routing problem with time windows and simultaneous pickups and deliveries., 685-689.
Cordeau, J., Gendreau, M. & Laporte, G. (1997). A tabu search heuristic for periodic and multidepot vehicle routing problems. Networks, 30(2), 105-119.

상세보기
Cordeau, J., Gendreau, M., Laporte, G., Potvin, J. & Semet, F. (2002). A guide to vehicle routing heuristics. Journal of the Operational Research society, 512-522.
Dantzig, G., Fulkerson, R. & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, 2(4), 393-410.

상세보기
Davies, D. L. & Bouldin, D. W. (1979). A cluster separation measure. IEEE Transactions on Pattern Analysis and Machine Intelligence(2), 224-227.
De Jaegere, N., Defraeye, M. & Van Nieuwenhuyse, I. (2014). The vehicle routing problem: state of the art classification and review.
Dempster, A. P., Laird, N. M. & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the royal statistical society.Series B (methodological), 1-38.
Dondo, R. & Cerda, J. (2007). A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. European Journal of Operational Research, 176(3), 1478-1507.

상세보기
Ester, M., Kriegel, H., Sander, J. & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise., 96(34), 226-231.
Feng, L., Ong, Y., Chen, C. & Chen, X. (2016). 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), 3745- 3769.

상세보기
Fisher, M. L. & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.

상세보기
Fraley, C. & Raftery, A. E. (1998). How many clusters? Which clustering method? Answers via model-based cluster analysis. The computer journal, 41(8), 578-588.

상세보기
Fraley, C. & Raftery, A. E. (2002). Model-based clustering, discriminant analysis, and density estimation. Journal of the American statistical Association, 97(458), 611-631.

상세보기
Gendreau, M., Hertz, A. & Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management science, 40(10), 1276-1290.

상세보기
Gendreau, M., Laporte, G., Musaraganyi, C. & Taillard, .. D. (1999). A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & Operations Research, 26(12), 1153-1173.

상세보기
Gillett, B. E. & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations research, 22(2), 340-349.

상세보기
Goetschalckx, M. & Jacobs-Blecha, C. (1989). The vehicle routing problem with backhauls. European Journal of Operational Research, 42(1), 39-51.

상세보기
Gounaris, C. E., Wiesemann, W. & Floudas, C. A. (2013). The robust capacitated vehicle routing problem under demand uncertainty. Operations research, 61(3), 677-693.

상세보기
Grangier, P., Gendreau, M., Lehuede, F. & Rousseau, L. (2016). An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. European Journal of Operational Research, 254(1), 80-91.

상세보기
Gurobi Optimization, I. (2016). Gurobi Optimizer Reference Manual; 2015. URL http://www.gurobi.com.
Han, J., Pei, J. & Kamber, M. (2011). Data mining: concepts and techniques. Elsevier.
Hernandez, F., Feillet, D., Giroudeau, R. & Naud, O. (2016). Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows. European Journal of Operational Research, 249(2), 551-559.

상세보기
Iassinovskaia, G., Limbourg, S. & Riane, F. (2017). 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, 570-582.

상세보기
Imran, A., Salhi, S. & Wassan, N. A. (2009). A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem. European Journal of Operational Research, 197(2), 509-518.

상세보기
Irnich, S. (2000). A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles. European Journal of Operational Research, 122(2), 310-328.

상세보기
Jepsen, M., Spoorendonk, S. & Ropke, S. (2013). A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. Transportation Science, 47(1), 23-37.

상세보기
Jin, J., Crainic, T. G. & Lokketangen, A. (2014). A cooperative parallel metaheuristic for the capacitated vehicle routing problem. Computers & Operations Research, 44, 33-41.

상세보기
Karadimas, N. V., Doukas, N., Kolokathi, M. & Defteraiou, G. (2008). Routing optimization heuristics algorithms for urban solid waste transportation management. WSEAS Transaction on Computers, 7(12), 2022-2031.
Kaufman, L. & Rousseeuw, P. (1987). Clustering by means of medoids. North-Holland.
Ko, H. J. & Evans, G. W. (2007). A genetic algorithm-based heuristic for the dynamic integrated forward/reverse logistics network for 3PLs. Computers & Operations Research, 34(2), 346-366.

상세보기
Koc, C. & Karaoglan, I. (2016). The green vehicle routing problem: A heuristic based exact solution approach. Applied Soft Computing, 39, 154-164.

상세보기
Land, A. H. & Doig, A. G. (2010). An automatic method for solving discrete programming problems. 50 Years of Integer Programming 1958-2008, 105-132.
Li, F., Golden, B. & Wasil, E. (2007). A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem. Computers & Operations Research, 34(9), 2734-2742.

상세보기
Lim, A. & Wang, F. (2005). Multi-depot vehicle routing problem: A one-stage approach. IEEE transactions on Automation Science and Engineering, 2(4), 397-402.

상세보기
Lysgaard, J. & Wohlk, S. (2014). A branchand- cut-and-price algorithm for the cumulative capacitated vehicle routing problem. European Journal of Operational Research, 236(3), 800-810.

상세보기
Michael, R. G. & David, S. J. (1979). Computers and intractability: a guide to the theory of NP-completeness. WH Free.Co., San Fr, 90-91.
Mittal, P. & Singh, Y. (2016). Development of intelligent transportation system for improving average moving and waiting time with artificial intelligence. Indian Journal of Science and Technology, 9(3).

상세보기
Nagy, G. & Salhi, S. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research, 162(1), 126-141.

상세보기
Ombuki, B., Ross, B. J. & Hanshar, F. (2006). Multi-objective genetic algorithms for vehicle routing problem with time windows. Applied Intelligence, 24(1), 17-30.

상세보기
Penna, P. H. V., Subramanian, A. & Ochi, L. S. (2013). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 1-32.
Potvin, J., Duhamel, C. & Guertin, F. (1996). A genetic algorithm for vehicle routing with backhauling. Applied Intelligence, 6(4), 345-355.

상세보기
Reed, M., Yiannakou, A. & Evering, R. (2014). An ant colony algorithm for the multi-compartment vehicle routing problem. Applied Soft Computing, 15, 169-176.

상세보기
Renaud, J., Laporte, G. & Boctor, F. F. (1996). A tabu search heuristic for the multi-depot vehicle routing problem. Computers & Operations Research, 23(3), 229-235.

상세보기
Rivera, J. C., Afsar, H. M. & Prins, C. (2016). Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem. European Journal of Operational Research, 249(1), 93-104.

상세보기
Roodbergen, K. J. & De Koster, R. (2001). Routing order pickers in a warehouse with a middle aisle. European Journal of Operational Research, 133(1), 32-43.

상세보기
Rousseeuw, P. J. (1987). Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20, 53-65.

상세보기
Ryan, D. M., Hjorring, C. & Glover, F. (1993). Extensions of the petal method for vehicle routeing. Journal of the Operational Research Society, 289-296.
Savelsbergh, M. W. (1992). The vehicle routing problem with time windows: Minimizing route duration. ORSA journal on computing, 4(2), 146-154.

상세보기
Scott, A. J. & Symons, M. J. (1971). Clustering methods based on likelihood ratio criteria. Biometrics, 387-397.
Subramanian, A., Penna, P. H. V., Uchoa, E. & Ochi, L. S. (2012). A hybrid algorithm for the heterogeneous fleet vehicle routing problem. European Journal of Operational Research, 221(2), 285-295.

상세보기
Taillard, E., Badeau, P., Gendreau, M., Guertin, F. & Potvin, J. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation science, 31(2), 170-186.

상세보기
Ta？, D., Gendreau, M., Dellaert, N., Van Woensel, T. & De Kok, A. (2014). 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), 789-799.

상세보기
Tibshirani, R., Walther, G. & Hastie, T. (2001). 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), 411-423.
Wei, L., Zhang, Z., Zhang, D. & Leung, S. C. (2017). A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research.
Yao, B., Yu, B., Hu, P., Gao, J. & Zhang, M. (2016). An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot. Annals of Operations Research, 242(2), 303-320.

상세보기
Yu, B., Yang, Z. & Yao, B. (2009). An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 196(1), 171-176.

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증