CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    May 2013
    Posts
    4

    Question 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 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 )

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Help with algorithm - Delivery problem with LIFO loading

    Quote Originally Posted by logicsheep View Post
    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?
    Last edited by nuzzle; June 1st, 2013 at 06:14 AM.

  3. #3
    Join Date
    May 2013
    Posts
    4

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

    And again, thanks for your time

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: Help with algorithm - Delivery problem with LIFO loading

    Quote Originally Posted by logicsheep View Post
    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
    Last edited by nuzzle; June 4th, 2013 at 01:21 AM.

  5. #5
    Join Date
    May 2013
    Posts
    4

    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!

  6. #6
    Join Date
    Oct 2008
    Posts
    1,456

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

  7. #7
    Join Date
    May 2013
    Posts
    4

    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
  •  





Click Here to Expand Forum to Full Width

Featured