  VRP (Vehicle Routing Problem) is an NP hard problem, and it has attracted a
lot of research interest. In contexts where vehicles have limited carrying
capacity, such as volume and weight but needed to deliver items at various
locations. Initially before creating a route, each vehicle needs a group of
delivery points that are not exceeding their maximum capacity. Drivers tend to
deliver only to certain areas. Cluster-based is one of the approaches to give a
basis for generating tighter routes. In this paper we propose new algorithms
for producing such clusters/groups that do not exceed vehicles maximum
capacity. Our basic assumptions are each vehicle originates from a depot,
delivers the items to the customers and returns to the depot, also the vehicles
are homogeneous. This methods are able to compact sub-areas in each cluster.
Computational results demonstrate the effectiveness of our new procedures,
which are able to assist users to plan service territories and vehicle routes
more efficiently.
