다특성 차량경로문제에 대한 휴리스틱 알고리즘 : 국내 복합사료 업체 사례
Heuristics for Rich Vehicle Routing Problem :A Case of a Korean Mixed Feed Company
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
The vehicle routing problem is one of the vibrant research problems for half a century. Many studies have extensively studied the vehicle routing problem in order to deal with practical decision-making issues in logistics. However, developments of new logistics strategies have inevitably required investigations on solution methods for solving the problem because of computational complexity and inherent constraints in the problem. For this reason, this paper suggests a simulated annealing (SA) algorithm for a variant of vehicle routing problem introduced by a previous study. The vehicle routing problem is a multi-depot and multi-trip vehicle routing problem with multiple heterogeneous vehicles restricted by the maximum permitted weight and the number of compartments. The SA algorithm generates an initial solution through a greedy-type algorithm and improves it using an enhanced SA procedure with three local search methods. A series of computational experiments are performed to evaluate the performance of the heuristic and several managerial findings are further discussed through scenario analyses. Experiment results show that the proposed SA algorithm can obtain good solutions within a reasonable computation time and scenario analyses show that a transportation system visiting non-dedicated factories shows better performance in truck management in terms of the numbers of vehicles used and trips for serving customer orders than another system visiting only dedicated factories.
Abstract
The vehicle routing problem is one of the vibrant research problems for half a century. Many studies have extensively studied the vehicle routing problem in order to deal with practical decision-making issues in logistics. However, developments of new logistics strategies have inevitably required investigations on solution methods for solving the problem because of computational complexity and inherent constraints in the problem. For this reason, this paper suggests a simulated annealing (SA) algorithm for a variant of vehicle routing problem introduced by a previous study. The vehicle routing problem is a multi-depot and multi-trip vehicle routing problem with multiple heterogeneous vehicles restricted by the maximum permitted weight and the number of compartments. The SA algorithm generates an initial solution through a greedy-type algorithm and improves it using an enhanced SA procedure with three local search methods. A series of computational experiments are performed to evaluate the performance of the heuristic and several managerial findings are further discussed through scenario analyses. Experiment results show that the proposed SA algorithm can obtain good solutions within a reasonable computation time and scenario analyses show that a transportation system visiting non-dedicated factories shows better performance in truck management in terms of the numbers of vehicles used and trips for serving customer orders than another system visiting only dedicated factories.
참고문헌 (25)
- Baldacci, R., "An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts", Mathematical Programming, 115(2), pp.351~385 (2008)
- Baldacci, R., "Recent advances in vehicle oruting exact algorithms", 4OR : A Quarterly Journal of Operations Research, 5(4), pp.269~298 (2007)
- 조병민, "소요차량을 최소화하는 기간차량경로 문제에 관한 2단계 발견적 기법", 한국산업경영시스템학회지, 31(3), pp.90~100 (2008), 한국산업경영시스템학회
- Dantzig, G. B., "The Truck Dispatching Problem", Management Science, 6(1), pp.80~91 (1959)
- Fukasawa, R., "Robust branchand-cut-and-price for the capacitated vehicle routing problem", Mathematical Programming, 106(3), pp.491~511 (2006)
- Goel, A.Gruhn, V., "Large neighborhood search for rich VRP with multiple pickup and delivery locations", Operations Research Proceedings, pp.367~372 (2005)
- Hartl, R. F., "Special issue on rich vehicle routing problems", Central European Journal of Operations Research, 14(2), pp.103~104 (2006)
- 김화중, "Effects of Truck-shared Delivery: A Case of a Korean Mixed Feed Company", Journal of International Logistics and Trade, 14(2), pp.165~173 (2016), 정석물류통상연구원[DOI]
- Kirkpatrick, S., "Optimization by simulated annealing", Science, 220, pp.671~680 (1983)
- Lahyani, R., "Rich Vehicle Routing Problems : From a Taxonomy to Definition", European Journal of Operational Research, 241(1), pp.1~14 (2015)
- Laporte, G., "Fifty years of vehicle routing", Transportation Science, 43(4), pp.408~416 (2009)
- 이상철, "복수물류센터에 대한 VRP 및 GA-TSP의 개선모델개발", 한국산학기술학회논문지, 8(5), pp.1279~1288 (2007), 한국산학기술학회
- Application of Two Nearest Neighbor Approaches to a Rich Vehicle Routing Problem, "Pellegrini, P.", ~ (2005)
- Rieck, J., "A new mixed integer linear model for a rich vehicle routing problem with docking constraints", Annuals of Operations Research, 181(1), pp.337~358 (2010)
- Ropke, S., "A unified heuristic for a large class of vehicle routing problems with backhauls", European Journal of Operational Research, 171(3), pp.750~775 (2006)
- Ropke, S., "An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows", Transportation Science, 40(4), pp.455~472 (2006)
- Santillan, C.G, "Logistics Management and Optimization through Hybrid Artificial Intelligence Systems", pp.207~237 (2012)
- Shaw, P, "Using constraint programming and local search methods to solve vehicle routing problems", Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming (CP-98)(Lecture Notes in Computer Science), pp.417~431 (1998)
- Solomon, M. M., "Algorithms for the vehicle routing and scheduling problems with time window constraints", Operations Research, 35(2), pp.166~324 (1987)
- Suman, B., "A survey of simulated annealing as a tool for single and multiobjective optimization", Journal of the Operational Research Society, 57(10), pp.1143~1160 (2006)
- Vidal, T., "Heuristics for multi-attribute vehicle routing problems : A survey and synthesis", European Journal of Operational Research, 231(1), pp.1~21 (2013)
- Wen, M., "Rich Vehicle Routing Problems and Applications", Ph.D, pp.2010
- Wen, M., "A multilevel variable neighborhood search heuristic for a practical vehicle routing and driver scheduling problem", Networks, 58(4), pp.311~322 (2011)
- Wen, M., "Vehicle routing with cross-docking", Journal of the Operational Research Society, 60(12), pp.1708~1718 (2008)
- Zeng, L., "A generalized crossing local search method for solving vehicle routing problems", Journal of the Operational Research Society, 58(4), pp.528~532 (2007)