A study of the development of algorithms for optimal route design of the vehicle routing problems

This paper is concerned with the development of a tree-search algorithm for the exact solution to the vehicle routing problem (VRP), where a set of vehicles of known capacity based at depots, have to be routed in order to supply customers with known requirements. What is required is to design routes, so that the total cost (i.e. total route length or time duration, etc.) is minimized. For obtaining the exact solution, the most important factors are the value of bound and branching strategy. Using the bound based on with bound ascent procedures from subgradient and state-space ascents, the incorporation of bounds into tree search algorithm to solve the problem is shown. Computational results of the corresponding algorithm show that VRPs with up to 40 customers can be solved optimally with this algorithm. [In Korean.]