0

I have an optimization problem and I'm thinking about employing machine learning methods to resolve it.

The goal is to find optimal luggage load in the plane. The luggage has size, weight and some other attributes restricting the place where it can be put. There's some strict rules (e.g. some kind of baggage needs to be in front of the luggage department, some cannot be placed near the other, heavy ones should be on the bottom etc.) and some conditions have to be met at the end - the weight should be evenly distributed, all luggage needs to fit inside.

There're also some undocumented ("common sense") rules that are applied by people responsible for loading the luggage. Those could be derived basing on available examples.

I was thinking about training Neural Network basing on the examples. I looked at http://neuroph.sourceforge.net/sample_projects.html but couldn’t find the sample that could be modified for my domain. Also, I’m not sure if this is the right method for this problem category.

Here's a simplified example. Let's say a piece of baggage is described by 3 attributes:

  • weight
  • stiffness
  • type

Sample data:

B1 (20kg, soft, normal)
B2 (20kg, hard, normal)
B3 (40kg, hard, normal)
B4 (50kg, hard, normal)
B5 (20kg, soft, special)

There's 6 slots in the luggage department (S1-S6, S1 - front, S6 - back). Example rules:

  • the heaviest load should be placed as close to the middle of department as possible.
  • the special ones should be at the back
  • common sense rule (not documented) - the soft baggage shouldn't be placed between hard ones

One of the correct outputs is:

S1->B1 (normal but soft, so it's not between B2 and B4) 
S2->B2 (normal) 
S3->B4 (heavy - in the middle), 
S4->B3 (heavy - in the middle), 
S5->B5 (special - at the back)

Representing the output in normalized form required by NN is tricky. I'm wondering if NN is a good method for this problem at all. Maybe some other should be used (e.g. Reinforcement Learning)

What machine learning method(s) could be used to find the optimal luggage load?

nico
  • 21
  • 2
  • 1
    I'm not sure that the problem is suitable for machine learning. You should post some example data and desired output. It seems like a search problem. Neural networks were used in some search problems such as for example in alpha go – Donbeo Feb 03 '17 at 12:34
  • 1
    3-dimensional-bin-packing-algorithms http://stackoverflow.com/questions/2192087/3-dimensional-bin-packing-algorithms – patrick Feb 03 '17 at 15:22
  • 1
    Rather than machine learning, you could try an approach like 'simulated annealing' which is also relatively easy to code. All you need is a function to calculate quality of the arrangement (weights on your rules) and code to do the shuffling. – Ian Mercer Feb 03 '17 at 16:06
  • @Ian Mercer The performance of such solution may be insufficient. The plane takes hundreds of passengers (most of them with at least one bag) so the number of combinations is huge. – nico Feb 03 '17 at 16:30
  • @nico Simulated annealing doesn't examine all combinations. Most of the time it's doing a move that heads towards a local minimum, sometimes (with decreasing frequency) it makes a move that increases the value. These 'jumps' increase the chance that it ends in the global minimum. Unlike other algorithms, you can decide how long you want to run it for to increase the chances of it hitting the global minimum. 100 bags is a small number for such an algorithm. – Ian Mercer Feb 03 '17 at 21:54
  • Thanks for your answers. I'll try suggested methods. – nico Feb 06 '17 at 07:31
  • Just to wider your search space; you need to look for metaheuristics for optimization. Simulated annealing is one of those. Apart from this you can look for genetic algorithms, tabu search, swarm optimization, ant colony optimization etc. I will be Simulated annealing first as it is easy to code and I am not aware of any established rule for sequencing of trials of these metaheuristics. – abhiieor Feb 06 '17 at 10:00

0 Answers0