
May 31st, 2013, 11:50 AM
#1
Help with algorithm  Delivery problem with LIFO loading
Hello everyone! I've been trying to tackle a problem but I 've reached a roadblock in my train of thought and would appreciate some help...
The description of the problem is the following:
You are given a delivery list of items that have to be moved from one location to another. The number of "locations" is known, and each action you
perform has a "cost":
moving from one location to another costs 3 points
loading or unloading an item costs 1 point
The catch is that the items you carry are loaded in a LIFO format, meaning that when you can only load to or unload from the "top" of your currently carried items.
You start from "Home" and have to end there, having satisfied the delivery list with the least possible cost.
For simplicity, the only desired output is the least possible cost.
So, while trying to figure out the problem I 've become stumped, since I cannot prove any possible "simplifications" of the delivery route.
For example, you could say that a smart move is to first completely satisfy a specific location: that is, deliver all its inbound items and load all
outbound items, so you don't have to visit this location again. But, I can't be sure that this will always be the least costly decision.
Then again, you can always try to exhaustively search all possible moves and compare costs, but these are too many (what location will you go to? what will
the order of your carried items be?)
So, I would appreciate any helpideas you have... and thanks for your time (preemptively )

June 1st, 2013, 06:20 AM
#2
Re: Help with algorithm  Delivery problem with LIFO loading
Originally Posted by logicsheep
For example, you could say that a smart move is to first completely satisfy a specific location: that is, deliver all its inbound items and load all
outbound items, so you don't have to visit this location again. But, I can't be sure that this will always be the least costly decision.
Or you could make two roundtrips to all locations. During the first roundtrip you push all items on the LIFO as you find them. Afterwards you pop all items and immediately push them back on again in visiting order so the appropriate items become available for delivery at each location during the second roundtrip.
The roundtrips are linear in the number of locations and the LIFO handling including the reordering is linear in the number of items so all in all this is an O(N) algorithm. I cannot say if it gives the lowest cost but at least it's an upper bound (if the reordering which requires an additional data structure is legal),
Cost = 2 roundtrips * N locations * 3 points + (4 push/pop + 1 ordering) * M items * 1 point = 6*N + 5*M;
If you want help to improve on this you need to be more specific about the nature of the items and the delivety list. At least I don't fully get it. I guess initially there are items at each location. Is each item labelled with the target location as if it were a post parcel?
Last edited by nuzzle; June 1st, 2013 at 07:14 AM.

June 1st, 2013, 06:51 AM
#3
Re: Help with algorithm  Delivery problem with LIFO loading
First of all, I would like to thank you for your help and time!
Now, regarding the items...
The items are (as you correctly stated) situated in the various locations in the beginning.
We should also treat the items as "unique" post parcels. Allow me to explain:
If you have an order (in the input delivery list) stating "An item has to be moved from location #2 to location #3" then,
once you push this item in your LIFO list it should be treated like a "unique" parcel that has to be delivered to location #3.
Other items may be pushed on top of it, but ultimately this specific parcel will have to be delivered to its target location.
I assume that this constriction will influence the cost we pay to loadunload items in order to unload a specific item:
If it is above most, the cost (1 point per loadunload) will be smaller...
Sorry if I am a bit confusing, I'm trying my best to explain a notsowell stated problem
And again, thanks for your time

June 3rd, 2013, 05:08 AM
#4
Re: Help with algorithm  Delivery problem with LIFO loading
Originally Posted by logicsheep
notsowell stated problem
I made a net search and found this link I think applies to your problem,
http://www.computationallogistics.o...per/TSPPDL.pdf
But the "tworoundtrips" heuristics (*) I suggested and the "satisfy" heuristics you suggested are still relevant. I notice that your approach can be done in two equivalent ways. You can satisfy a location by picking up all items adressed to it, or you can satisfy the location by delivering all items from it. Doing either of these for every location will solve the problem.
A somewhat obvious additional heuristics is that when you go from one location to the next you should always take with you all items destined for the next location. This "onthefly" rule takes full advantage of the LIFO style loading and it can be used to improve on other strategies by taking items out of circulation for free. The more onthefly deliveries the better.
All in all I found the problem quite hard. For an exact algorithm I have to refer to the literature. Good luck.
(*) In fact this represents a common way to reduce the complexity of a situation where N nodes interact with each other. Instead of all N interacting with all N, an intermediate is introduced so N interacts with 1 and 1 interacts with N. The complexity drops from (N^2) to O(N). This is the basis of the Mediator design pattern. It's also the basis of the Fast Multipole Algorithm which has been named one of the top 10 algorithms of the 20th century,
http://www.siam.org/pdf/news/637.pdf
Last edited by nuzzle; June 4th, 2013 at 02:21 AM.

June 5th, 2013, 04:37 PM
#5
Re: Help with algorithm  Delivery problem with LIFO loading
Well, thank you for your help  and time!
I' m going to study the TSPPDL, though I might try my luck with an exhaustive approach (maybe with some optimizations) just to see the results...
Again, thanks!

June 6th, 2013, 03:38 AM
#6
Re: Help with algorithm  Delivery problem with LIFO loading
just to better specify the problem statement,
are all locations occupied by an item in the beginning ? can a location "store" more than one item at a time ? if yes, can be loaded in any order ? can a location from which an item has been loaded be reloaded later with the same or some other item ?

June 10th, 2013, 08:34 AM
#7
Re: Help with algorithm  Delivery problem with LIFO loading
Hello! Apologies for the late reply.
You can store as many items as you like at one location, and you can load them in any order.
Now, each location can have from none to as many as are required items.
The items required to be "exported" from one location can be counted from the input "delivery list", which states orders like
"move an item from location 1 to location 2
move an item from location 1 to location 4"
...and so on
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
