초록 close

본 연구에서는 비대칭차량경로문제에 관한 새로운 휴리스틱 hRS를 제시하고 실험한다. 휴리스틱 hRS는 경로분할모형의 선형완화 최적해로부터 초기해를 구하고, 삽입의 절차를 통해 실행가능해를 확보하고, 경로교환의 반복적 절차를 통해 해의 개선을 모색하는 삼단계로 구성되어 있으며, 매번 휴리스틱해의 개선시 각 경로를 최적화기법을 통해 최적화한다. 무작위 문제를 통한 실험연산에서 hRS는 타 휴리스틱 해에 대해 뚜렷한 우위를 보인다.


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.