The vehicle routing problem with time constraints

This paper deals with a vehicle routing problem of finding the minimum number of capacitated vehicles (AGVs) used for delivery from a central depot to demand points while meeting the delivery times requirements. Recently, with a ongoing progress in CIM, a production system which can efficiently control and utilize automated facilities is strongly required. As part of this system, AGV scheduling that can timely supply these these automated facilities with parts, tools, and other things have become more and more important. In order to meet the demands with only a few available AGVs efficiently, a method to clarify of the minimum number of AGVs required for a given production planning is useful (to check the feasibility of the production planning). First, the authors formulate the present vehicle routing problem with time constraints. After that, they introduce a heuristic algorithm for this problem. the heuristic algorithm first transforms the problem to the one with no capacity constraints. By the out-of-kilter method, the relaxed problem is solved. Using the resulting ‘optimum’ but infeasible set of tours, the algorithm then cuts off each of tours which exceed capacity constraints into smaller segments in such a manner that the segmented tours satisfy the constraints. Given a set of tours satisfying the capacity constraints, the problem which assigns those tours to AGVs is also solved by the out-of-kilter method. The results of an evaluation of this method indicate that the proposed heuristic is useful and promising. It is also shown that the size of the vehicle capacity and/or the location of depot have significant effects on the result obtained through this heuristic process. The larger the capacity becomes, the smaller the influence of relaxing capacity constraints becomes and the more useful this heuristic becomes. When the depot is not centrally located, the larger the distances from demand points to the depot become, the less useful the heuristic becomes. [In Japanese.]