Re: GAs and TSP-Type Problems

Hi,

I was wondering if you had much success with your problem as posted almost
two months ago.  I am in the process of building an application similar. 
Our organization has a finite territory across two states broken down by
"county".  We have a set of salesmen living in various counties.  The
problem we are trying to solve is balancing three factors: (1) territory
size in square miles, (2) number of customers in each salesman's
territory, and (3) opportunity in sales based on historical sales.  As you
can imagine, we want the territory size to be roughly equal for each
salesman, approximately the same number of customers per salesman, and the
opportunity per salesman to be the same.  Each county can be assigned to
one salesman and preference for assignment is given to a salesman living
in the county.  The problem is complex given the large number of
customers, a large number of counties and the large number of salesmen.

Thank you for any input.
JJ Lay
Six Sigma Black Belt
Thompson Machinery Commerce Corporation

On Mon, 22 Sep 2003 12:45:02 +0000, Costas Vlachos wrote:

> Hi all,
> 
> I'm involved in a project where we need to solve a TSP-type problem. The
> problem is as follows: There is a set of n sites in a 2-D grid, at known
> locations, and there are m salesmen (m < n). The m salesmen are located at
> an originating point in the grid. Each salesman can visit any number of
> sites - from 0 up to all n of them, and must then return to the originating
> point. Every grid point must be visited, but only once and by only one
> salesman. So, there will be as many routes as there are salesmen (some of
> which may be zero-length), and the routes must be disjoint (i.e., no common
> nodes, except the originating point of course). The goal is to minimise the
> total distance (which is the sum of the distances of all m routes). m will
> be around 30 and n will be around 500. There are other constraints involved
> in the problem, but let's ignore them for now.
> 
> We are thinking of using GAs for this problem. I have used GAs extensively
> for function optimisation problems, but not for this kind of TSP-type tasks.
> The main concern is the choice of an efficient chromosome representation
> that can generate valid offspring after a crossover operation, and does not
> contain a lot of redundancy. I have tried to use an order-based chromosome
> structure which basically includes all combinations of salesmen and sites,
> like this (for m = 2 and n = 3):