There are two main ways to decompose a problem: geographical and temporal. An example of a geographical decomposition is to preallocate to depots and to create subproblems for each depot. An example of a temporal decomposition is a problem where technicians return to their base every night. You create subproblems for each day.

Why decompose a problem? The complexity of Dispatcher is O(n2). This empirical complexity varies, at the very least, with the square of the number of visits. If you have n visits and k subproblems, you have n/k visits per problem. Therefore, if you decompose the problem the complexity is reduced to

k(n/k)2 = n2/k

You do pay a price by decomposing the problem. The solution will not be as good as one found for the whole problem. However, you can overcome this limitation by using an iterative solution process. Each subproblem is improved and then the whole problem is improved. This gives you the performance advantages of problem decomposition, while still allowing you to find a good overall solution.

Into how many subproblems should you decompose your problem? It is most useful to decompose your problem into logical subproblems based on your problem: number of depots, number of days, number of weeks, and so on. Even if you decompose into only 2-5 subproblems, you will already see substantial performance advantages.