비대칭차량경로문제의 휴리스틱해법
A Heuristic Algorithm for the Asymmetric Vehicle Routing Problem
1
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
본 연구에서는 비대칭차량경로문제에 관한 새로운 휴리스틱 hRS를 제시하고 실험한다. 휴리스틱 hRS는 경로분할모형의 선형완화 최적해로부터 초기해를 구하고, 삽입의 절차를 통해 실행가능해를 확보하고, 경로교환의 반복적 절차를 통해 해의 개선을 모색하는 삼단계로 구성되어 있으며, 매번 휴리스틱해의 개선시 각 경로를 최적화기법을 통해 최적화한다. 무작위 문제를 통한 실험연산에서 hRS는 타 휴리스틱 해에 대해 뚜렷한 우위를 보인다.
Abstract
This study develops and experiments a heuristic about the asymmetric vehicle routing problem. Heuristic hRS obtains a first solution from the optimal solution of the LP relaxation of the route-splitting model, and secures a feasible solution through the Insert procedure. Then hRS tries to improve the incumbent heuristic solution through a series of iterative diverse Exchange procedures. Finally, hRS tries to update the solution through a TSP routine applied to each route. Computational experiments on the number of randomly generated problems show that hRS is superior to existing heuristic algorithms in terms of solution quality.
참고문헌 (18)
- 강성민, "비대칭차량경로문제의 경로분할모형에 관한 연구", 한국생산관리학회지, 18(4), pp.3~31 (2007), 한국생산관리학회
- Christofides N, "An algorithm for the vehicle dispatching problem", Operations Research Quarterly, 20, pp.309~318 (1969)
- Christofides N, "The vehicle routing problem, in Combinatorial Optimization" (1979), Wiley
- Fischetti M, "A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs", Operations Research, 42(5), pp.846~859 (1994)
- Fukasawa R, "Robust branch-and-cut-and-price for the capacitated vehicle routing problem", Math. Program Ser A, 106, pp.491~511 (2006)
- Golden B, "The vehicle routing problem: latest advances and new challenges", pp.2008, Operations Research
- Kang S, "A route-splitting approach to the vehicle routing problem and a lotsizing and scheduling problem with sequence-dependent setup costs", 박사, pp.1994
- Kang S, "An exact algorithm for the asymmetric vehicle routing problem by a route-splitting approach, in preparation", ~ (2009)
- Laporte G, "The vehicle routing problem: an overview of exact and approximate algorithms", European Journal of Operational Research, 59, pp.345~358 (1992)
- Laporte G, "An exact algorithm for the asymmetric capacitated vehicle routing problem", Networks, 16, pp.33~46 (1986)
- Laporte G, "A branch and bound algorithm for a class of asymmetrical vehicle routeing problems", Journal of Operations Research Society, 43(5), pp.469~481 (1992)
- Lin S, "Computer solutions to the travelling salesman problem", Bell System Technical Journal, 44, pp.2245~2269 (1965)
- Lin S, "An effective heuristic algorithm for the Travelling Salesman Problem", Operations Research, 21, pp.498~516 (1973)
- Pessoa A, "Robust branch-cut-and-price algorithms for vehicle routing problems. in The Vehicle Routing Problem", pp.297~325 (2008), springer
- Savelsbergh MWP, "Computer aided routing", 박사, pp.1988
- Toth P, "Models, relaxations and exact approaches for the capacitated vehicle routing problem", Discrete Applied Mathematics, 123, pp.487~512 (2002)
- Toth P, "The Vehicle Routing Problem" (2002), SIAM Monographs on Discrete Mathematics and Applications
- Vigo D, "A heuristic algorithm for the asymmetric capacitated vehicle routing problem", European Journal of Operational Research, 89, pp.108~126 (1996)