Help with algorithm - Delivery problem with LIFO loading

Hello everyone! :wave: I've been trying to tackle a problem but I 've reached a roadblock in my train of thought and would appreciate some help... :D

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 in-bound items and load all
out-bound 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 help-ideas you have... and thanks for your time (pre-emptively :p ) :D

Quote:

---

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 in-bound items and load all
out-bound 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 re-ordering 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 re-ordering 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?

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 load-unload items in order to unload a specific item:
If it is above most, the cost (1 point per load-unload) will be smaller...

Sorry if I am a bit confusing, I'm trying my best to explain a not-so-well stated problem :p

And again, thanks for your time :o

Quote:

---

Originally Posted by logicsheep

not-so-well stated problem

---

I made a net search and found this link I think applies to your problem,

http://www.computational-logistics.o...per/TSPPDL.pdf

But the "two-roundtrips" 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 "on-the-fly" 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 on-the-fly 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

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! :thumb:

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 re-loaded later with the same or some other item ?

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