473,325 Members | 2,308 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,325 software developers and data experts.

Measuring Similarity for Assignment Problems

179 100+
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...
Jul 29 '08 #1
7 1993
JosAH
11,448 Expert 8TB
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
Jul 29 '08 #2
IanWright
179 100+
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.
Jul 30 '08 #3
JosAH
11,448 Expert 8TB
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
Jul 30 '08 #4
IanWright
179 100+
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.
Jul 30 '08 #5
JosAH
11,448 Expert 8TB
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.
Jul 30 '08 #6
IanWright
179 100+
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]
Jul 31 '08 #7
JosAH
11,448 Expert 8TB
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
Jul 31 '08 #8

Sign in to post your reply or Sign up for a free account.

Similar topics

23
by: Paul Rubin | last post by:
OK, I want to scan a file for lines matching a certain regexp. I'd like to use an assignment expression, like for line in file: if (g := re.match(pat, line)): croggle(g.group(1)) Since...
5
by: Charles Law | last post by:
Hi folks Not really a .NET question, but I always think this is a good place to ask. Does anyone have a favourite algorithm for determining the similarity of, or difference between two...
8
by: ben | last post by:
hello, i'm trying to answer a "prove an upper bound on the number of machine instructions required to process M connections on N objects" exercise from an algorithms book. i don't understand a...
0
by: Anibal Acosta | last post by:
Somebody know an algorithm for determine the similarity between two string for example: string 1: "Hello what is your name?, where are you from?" string 2: "Hello man, where are you from?" ...
0
by: himoundary | last post by:
hi all i am using microsoft speech sdk (sapi 5.1). i have the following requirements: 1) i need to compare current input sound (through mic) with recorded sound file (say .wav). based of...
34
by: Chris | last post by:
Is there ever a reason to declare this as if(*this == rhs) as opposed to what I normally see if(this == &rhs) ?
5
by: subramanian | last post by:
Consdier the following program: #include <stdio.h> struct typeRecord { int id; char str; } records = { {0, "zero"}, {1, "one"},
12
by: hweekuan | last post by:
hi, it seems i can't assign the const variable u in class A, one way to solve the problem may be to build a copy constructor. however, why does C++ or vector class not like this code? my g++ is:...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.