3.1.2. Customer grouping
After the step of customer assignment, when a proportion of
the deliveries to customers have been assigned to the same depot,
the corresponding orders of those customers will be delivered from
the same depot. However, the orders of those customers may not
be transported by a single vehicle on its delivery route, because
vehicles have fixed capacities that must not be exceeded. Therefore,
the operation of each depot can be view as a capacity-limited
vehicle routing problem (CVRP) (Chen et al., 2010). The CVRP is
similar to the VRP, but all vehicles have a capacity restriction.
In the present research, a clockwise search (CS) method proposed
by Kuo et al. (2009) is adopted for customers grouping.
The CS selects a customer at random and then searches for other
customers in the group in a clockwise direction until the capacity
of a vehicle will be exceeded by adding the order of the next customer,
or until all the customers have been selected. In Fig. 2, for
example, there are 8 customers assigned to Depot 1. The orders
for each customer are shown in the right hand side of the circle.
If the capacity of vehicle is 20 units, and Customer 3 is selected
firstly by a random method, then following in the clockwise direction,
Customers 3 to 7 will form one group.