Measuring Similarity for Assignment Problems

[IanWright]

I'm trying to come up with an effective assignment algorithm to allocate nodes to a nearest outlet, where each node should be have a time slot checked against the already allocated nodes for similarity (or even sequentiality to allow effective journey planning throughout a day).

I've currently looked at something called SPA - Simple Parallel Assigning which works out the cost of assigning each node to its nearest and next nearest outlet, and then assigns the one with the greatest cost saving.

The way the similarity would be calculated is

TimeDiff = difference between start/end or end/start time slots between existing node and 'to be assigned' node.
Time = Distance between existing node and 'to be assigned' node

The cost is then:
e^(-TimeDiff + Time) summed for each Node already assigned.

This value is compared to the second nearest outlet to determine the overall cost saving in assigning it.

Unfortunately the algorithm seems fairly slow, and seems to assign nodes in a very unusual way and I'm wondering if anyone can suggest a better way of doing something like this is they know about assignment problems?

Thanks...

[JosAH]

Are those demand nodes D independent in their demand except for their time slots?
Even if only, say sum(D) == Dtotal you can solve your problem using an MCNF
(Minimal Cost Network Flow) solver (which can easily be modelled as an ordinary LP).

kind regards,

Jos

[IanWright]

Are those demand nodes D independent in their demand except for their time slots?
Even if only, say sum(D) == Dtotal you can solve your problem using an MCNF
(Minimal Cost Network Flow) solver (which can easily be modelled as an ordinary LP).

kind regards,

Jos

Jos, yeah the demand of each node is independent, the time slots want to be loosely grouped to minimise the time you must wait at a node you visit if you're early. I'm basically trying to break a multiple depot problem down into single depot problems to then run a vehicle routing problem solver that I'm going to generate on them. I'm currently not sure whether or not my intended algorithm can cater for multiple depots (using Ant Colony Optimisation but don't have a great understanding of the maths) so thought it best to split it up into two problems.

So in the ideal word, the time slots actually want to be vaguely consecutive so an optimal tour between all the nodes can be generated.

I've not actually heard of a MCNF but it sounds like its actually very similar to my overall aim.

[JosAH]

VRP (Vehicle Routing Problems) are hell. What I once did was the following:

given an ordinary Transportation Problem with i producers Pi and j demands Dj
add more of each for each, say, hour of the day. Each artificial demand Dj has
the same demand as the original Dj; the same counts for the artificia producers
Pi. The artificial nodes represent the time (and cost) of the real node when its
closed. The added costs represent the waiting time. Also add an extra artificial
Producer Px if needed; make all the transportation costs originating in Px
extremely high.

Now you have an ordinary TP (Transportation Problem) again that can easily
be solved. Simply ignore all the activity from/to artificial nodes. Now you have
a nice crash basis solution for your original VRP.

Of course this trick doesn't work well for very narrow time slots.

kind regards,

Jos

[IanWright]

VRP (Vehicle Routing Problems) are hell. What I once did was the following:

given an ordinary Transportation Problem with i producers Pi and j demands Dj
add more of each for each, say, hour of the day. Each artificial demand Dj has
the same demand as the original Dj; the same counts for the artificia producers
Pi. The artificial nodes represent the time (and cost) of the real node when its
closed. The added costs represent the waiting time. Also add an extra artificial
Producer Px if needed; make all the transportation costs originating in Px
extremely high.

Now you have an ordinary TP (Transportation Problem) again that can easily
be solved. Simply ignore all the activity from/to artificial nodes. Now you have
a nice crash basis solution for your original VRP.

Of course this trick doesn't work well for very narrow time slots.

kind regards,

Jos

Hmm, I *think* I follow what you are saying, but I think I'll be all sorted for the VRP problem. I've worked on something recently for a company and am aiming to produce a slicker version myself so am just thinking about all the pitfalls from before and trying to figure out how to optimise them. Unfortunately I'm not a heavy algorithm person so following the principles of what is going on and what might cause it to break is kinda tricky.

At the moment my biggest hurdles are to improve the initial splitting of the problem so I can solve each outlet separately with a set of nodes to visit which is what I was asking about.

Once I've got that I need to consider if I can select vehicles to use in a more sensible way rather than sequentially (try to choose the best based on vehicle capacity etc.) and hope that pheremones save this data correctly.

Finally I need to turn a single day solver into a multi-day solver, carrying over an unvisited nodes to the next day to try to visit them then instead.

Manage to get all these sorted and I should be able to produce an MDCVRPTW (multi depot capacitated vehicle routing problem with time windows).. bit of a mouthful.

[JosAH]

At the moment my biggest hurdles are to improve the initial splitting of the problem so I can solve each outlet separately with a set of nodes to visit which is what I was asking about.

Don't go that way; it cripples the quality of your solution too much. You have
multiple outlets (P producers) and multiple stores (D demands). They can all
be served from several outlets serving multiple stores. If you chop up the problem
beforehand you severly reduce the quality of your solution.

Manage to get all these sorted and I should be able to produce an MDCVRPTW (multi depot capacitated vehicle routing problem with time windows).. bit of a mouthful.

Been there, done that; it is a mess. The best experience I had was using an
'incremental solver' i.e given a 'best' solution sofar, add another commodity such
that the total costs rise minimally. Afterwards a local search could optimize the
solution a bit further.

kind regards,

Jos

ps. it's a very interesting problem I admit.

[IanWright]

Don't go that way; it cripples the quality of your solution too much. You have
multiple outlets (P producers) and multiple stores (D demands). They can all
be served from several outlets serving multiple stores. If you chop up the problem
beforehand you severly reduce the quality of your solution.

It can do yes, but on the flip side it can save massively the amount of time you spend processing... Maybe you're right and I'll take a look at doing it without and see if the algorithm I'm using can handle it.

Maybe I'll send it your way sometime for you to take a look at! :D
[/quote]

[JosAH]

It can do yes, but on the flip side it can save massively the amount of time you spend processing... Maybe you're right and I'll take a look at doing it without and see if the algorithm I'm using can handle it.

About the additional processing: all true but dividing your problem up in several
single depot problems might, mathematically speaking generate deep 'cuts' in
your problem space and exclude (near) optimal solutions because they were
cut away from your problem space.

I once solved this 'multi depot capacitated vehicle routing with time slots problem'
once for an animal fodder production and transportation facility; before they did
it as you suggested. Regularly they found they had the fodder at one of their
factories, they had empty trucks, large enough, waiting at the gate, but the
order bill wanted the order to be handled by another outlet that used to be totally
empty at that time. Effectively spreading those orders over several outlets
really pays back although it is a terrible problem to solve even half decently ;-)

kind regards,

Jos