Re: GAs and TSP-Type Problems

"JJ Lay" <[EMAIL PROTECTED]> wrote:

> Hi,

> 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.

Probably to keep your salespersons happy, you'd better add
at least two more criteria, which will vastly increase the
computational difficulty of your optimization:

1) A salesperson's set of counties should be contiguous
(easier)

2) A salesperson's set of counties should be compact
(harder)

Both are in interest of cutting down the driving
requirements to service a single territory, of course,
which gives the sales force as a whole better efficiency.

Up to there, a GA or a Pareto optimization could have done
the job fairly easily, given an intelligent fitness measure,
and I cannot guess whether either would have an advantage
with the added constraints.

Knocking out a GA to do your original stuff is probably a
week's work via cut and paste from a working GA software,
once you select the fitness function. Adding the geometric
constraints to the purely numerical ones adds quite a bit of
complexity to the software chore.

As a horrible example set from which to cut and paste, I of
course volunteer my own freeware muddles:

http://www.well.com/user/xanthian/java/TravellerDoc.html

http://www.anycities.com/user/xanthian/MovieScheduler/MovieScheduler.html

What, except flogging my trash, would ever prompt me to
respond in the first place, after all?

I haven't done the Pareto stuff, I just know from earlier
messages here that it is quite competitive with GAs,
especially for the fairly tiny datasets you are handling
compared to some tractible engineering problems.

You didn't mention whether personal income tax constraints
make it better to keep territories limited to one state, so
I don't know if that would be another issue.

Despite the similarity of names, until you add a real
metric space geometrical issue, you really don't have
a traveling salesman problem yet, so the MovieScheduler is
probably closer to what you need, though not of course very
close either.

xanthian.






-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG