Question

Background

A delivery company has a service network of 100 customer sites. On any single day, not every site has some demand, i.e., the company only needs to serve a subset of the 100sites. As a result, the vehicle routing would be different from day to day.

The company takes a zoning approach in which the 100 sites are partitioned into 4 fixed zones. Each zone is served by one delivery person who can decide the daily vehicle routing within the zone. However, the zones cannot change once they are fixed.

We need to help the company design the zones, aiming to minimizing the total delivery cost.

We have collected some basic information.

1) Each site j, i=1,…, 100, as well as the hub referred to as site 0, has known (x,y) coordinates. The cost between two sites can be measured by their Manhattan distance.

2) Each zone cannot have more than 30 sites.

3) Vehicle capacity is not an issue.  

Phase I

The project has two phases. In phase I, we face periodic demand that repeats week by week, as shown below.

Customer	Mon	Tue	Wed	Thu	Fri	Sat
1	Y		Y		Y
2		Y	Y			Y
3	Y	Y		Y	Y
4	Y		Y	Y
5	Y	Y		Y
…

We need to minimize the total weekly cost.

Answer 1

I assume the objective is to come up with an optimised portion of the customer sites. Note we need to optimise for a single week only as the entire pattern repeats after a week (at least in phase1).

Realize that the total number of partitions without the upper bound of 30 per head is 4^100 (Each site can go to any of the 4), now this is a huge number.

We assume the aim is to minimise intra cluster distance and maximise inter cluster distance. We use Aglmoretive clustering to find the mean of each cluster and build bottom up from there. Refer to the following link to follow a bottom-up approach of clustering - https://en.wikipedia.org/wiki/Hierarchical_clustering