Loading ...
Sorry, an error occurred while loading the content.

Cargo/Load-optimizer algorithm

Expand Messages
  • zappbrann
    Hello, I m trying to build an application that optimizes the way packages (cargo) are loaded into a 3D space (truck). The goal is to fit as many packages as
    Message 1 of 5 , Jun 14, 2006
    View Source
    • 0 Attachment
      Hello,

      I'm trying to build an application that optimizes the way packages
      (cargo) are loaded into a 3D space (truck). The goal is to fit as many
      packages as possible.

      I've looked at using a standard search algorithm (from chapter 3)
      However, the branching factor is definitely too big to make it
      feasible. I also thought about using a planning algorithm (from
      chapter 11) but I don't know if that is the right approach.

      Does anybody have any ideas on what types of algorithms I should look
      at?

      Regards,

      John.
    • Robin
      This is a classic Operations Research problem that I d think would be straightforward to solve by linear programming. Have you looked into using an LP solver?
      Message 2 of 5 , Jun 14, 2006
      View Source
      • 0 Attachment
        This is a classic Operations Research problem that
        I'd think would be straightforward to solve by linear
        programming. Have you looked into using an LP solver?

        -- Robin

        --- In aima-talk@yahoogroups.com, "zappbrann" <john@...> wrote:
        >
        > Hello,
        >
        > I'm trying to build an application that optimizes the way packages
        > (cargo) are loaded into a 3D space (truck). The goal is to fit as many
        > packages as possible.
        >
        > I've looked at using a standard search algorithm (from chapter 3)
        > However, the branching factor is definitely too big to make it
        > feasible. I also thought about using a planning algorithm (from
        > chapter 11) but I don't know if that is the right approach.
        >
        > Does anybody have any ideas on what types of algorithms I should look
        > at?
        >
        > Regards,
        >
        > John.
        >
      • zappbrann
        I looked up linear programming in AIMA and found very little contents. I m not familiar with the LP solvers, however I looked it up on wikipedia and found the
        Message 3 of 5 , Jun 14, 2006
        View Source
        • 0 Attachment
          I looked up linear programming in AIMA and found very little contents.
          I'm not familiar with the LP solvers, however I looked it up on
          wikipedia and found the "Simplex" algorithm... but I was unable to see
          the connection with load-optimization. Perhaps you could shed some
          more light on this?

          Thanks for the reply.

          Regards,
          John.

          --- In aima-talk@yahoogroups.com, "Robin" <rhewitt@...> wrote:
          >
          > This is a classic Operations Research problem that
          > I'd think would be straightforward to solve by linear
          > programming. Have you looked into using an LP solver?
          >
          > -- Robin
          >
          > --- In aima-talk@yahoogroups.com, "zappbrann" <john@> wrote:
          > >
          > > Hello,
          > >
          > > I'm trying to build an application that optimizes the way packages
          > > (cargo) are loaded into a 3D space (truck). The goal is to fit as
          many
          > > packages as possible.
          > >
          > > I've looked at using a standard search algorithm (from chapter 3)
          > > However, the branching factor is definitely too big to make it
          > > feasible. I also thought about using a planning algorithm (from
          > > chapter 11) but I don't know if that is the right approach.
          > >
          > > Does anybody have any ideas on what types of algorithms I should
          look
          > > at?
          > >
          > > Regards,
          > >
          > > John.
          > >
          >
        • Robin
          Hello John, It might have helped had I mentioned the problem name. It s bin packing. You might try searching for that directly, or for that and
          Message 4 of 5 , Jun 15, 2006
          View Source
          • 0 Attachment
            Hello John,

            It might have helped had I mentioned the problem name. It's "bin
            packing." You might try searching for that directly, or for that and
            "programming."

            Bin packing would actually be an integer programming problem, but one
            method for tackling these is to solve first by linear programming,
            ignoring the integer constraint, then find the integer solution that's
            closest and is within the constraints. Better integer-programming
            methods you might consider for this are Branch and Bound and Cutting
            Plane:
            http://mat.gsia.cmu.edu/orclass/integer/integer.html

            Bin packing is NP hard, but it sounds like your particular problem
            might be small. That's why I thought it would make sense to at least
            look at using a direct method from OR.

            There are also special-purpose methods for bin packing, however, since
            it's such a classic problem and an NP-hard one. Here are some links:
            http://mathworld.wolfram.com/Bin-PackingProblem.html
            http://en.wikipedia.org/wiki/Bin_packing_problem

            A 1D bin-packing solver:
            http://www.cs.arizona.edu/icon/oddsends/bpack/bpack.htm

            I did a quick search and find that people have used genetic algorithms
            to solve, and to optimize solutions for, bin packing problems. That
            might be more along the lines of what you were originally looking for.
            The idea would be to use a heuristic (such as sorting by size) with a
            greedy algorithm to solve non-optimally, then use a GA to optimize
            the solution.

            Finally, the resource I've found most helpful for understanding the
            principles of LP is the classic text by George Dantzig: Linear
            Programming and Extensions:
            http://www.amazon.com/gp/product/0691059136/102-0117124-8181715?v=glance&n=283155

            -- Robin

            --- In aima-talk@yahoogroups.com, "zappbrann" <john@...> wrote:
            >
            > I looked up linear programming in AIMA and found very little contents.
            > I'm not familiar with the LP solvers, however I looked it up on
            > wikipedia and found the "Simplex" algorithm... but I was unable to see
            > the connection with load-optimization. Perhaps you could shed some
            > more light on this?
            >
            > Thanks for the reply.
            >
            > Regards,
            > John.
            >
            > --- In aima-talk@yahoogroups.com, "Robin" <rhewitt@> wrote:
            > >
            > > This is a classic Operations Research problem that
            > > I'd think would be straightforward to solve by linear
            > > programming. Have you looked into using an LP solver?
            > >
            > > -- Robin
            > >
            > > --- In aima-talk@yahoogroups.com, "zappbrann" <john@> wrote:
            > > >
            > > > Hello,
            > > >
            > > > I'm trying to build an application that optimizes the way packages
            > > > (cargo) are loaded into a 3D space (truck). The goal is to fit as
            > many
            > > > packages as possible.
            > > >
            > > > I've looked at using a standard search algorithm (from chapter 3)
            > > > However, the branching factor is definitely too big to make it
            > > > feasible. I also thought about using a planning algorithm (from
            > > > chapter 11) but I don't know if that is the right approach.
            > > >
            > > > Does anybody have any ideas on what types of algorithms I should
            > look
            > > > at?
            > > >
            > > > Regards,
            > > >
            > > > John.
            > > >
            > >
            >
          • Ivan F. Villanueva B.
            ... It is a very interesting problem. Please post the solutions, links, etc you find to solve it. -- Ivan F. Villanueva B. A.I. library:
            Message 5 of 5 , Jun 15, 2006
            View Source
            • 0 Attachment
              On Wed, Jun 14, 2006 12:22:56PM -0000, zappbrann wrote:
              > Hello,
              >
              > I'm trying to build an application that optimizes the way packages
              > (cargo) are loaded into a 3D space (truck). The goal is to fit as many
              > packages as possible.

              It is a very interesting problem. Please post the solutions, links, etc you find
              to solve it.

              --
              Ivan F. Villanueva B.
              A.I. library: http://www.artificialidea.com
              <<< The European Patent Litigation Agreement (EPLA) >>>
              <<< will bring Software patents by the backdoor >>>
              <<< http://www.no-lobbyists-as-such.com/florian-mueller-blog/epla/ >>>
              <<< http://wiki.ffii.de/EplaEn >>>
            Your message has been successfully submitted and would be delivered to recipients shortly.