This thesis presents a heuristic algorithm for the vehicle routing problem with fixed costs. In this algorithm, the generalized assignment heuristic developed by Fisher and Jaikumar is extended, which solves the vehicle routing problem only without fixed costs. A realistic variation of the problem in which there are limits on the number of vehicles of each type can be considered in this heuristic. And the microcomputer application of the heuristic algorithm described in this thesis is also considered.
Finally, meaningful computational results and suggestions for further study are presented.
본 논문은 고정비용을 고려한 차량운행문제(Vehicle Routing Problem) 의 근사적 해법(Heuristic Algorithm) 에 관한 연구이다.
Fisher와 Jaikumar 는 고정비용을 고려하지 않는 차량운행문제를 풀기 위한 근사적 해법으로 일반화된 할당방법 (Generalized Assignment Heuristic) 을 제시했는데, 이 해법은 최적성과 계산속도 면에서 우수한 것으로 인정받고 있다. 본 논문에서는 이 해법을 고정비용이 있는 경우에 적용될 수 있도록 수정했다. 이렇게 수정된 해법에서는 이용할 수 있는 각 차량의 수에 대한 제한이 있는 경우에도 그 해를 구할 수 있다. 이 외에도 본 논문에서는 이러한 해법을 microcomputer 에 적용시키는 점도 고려하였다.
끝으로 의미있는 계산결과와 앞으로의 연구방향도 아울러 이 논문에서 제시하고 있다.
