π #16 OR in action: Local Search to enhance solutions, and Mercadona facing optimization
And in between, more about warehouses...
Today, I'm getting straight to the point. I'm going to tell you 2 βπ» things in today's edition of Feasible:
How to improve an initial solution with local search methods
The market share of Mercadona and the problems that arise around its warehouses, the famous beehives
Ready, set...
I recently created a database with over 70 Operational Research resources.
FREE.
And it includes things like:
π¨βπ©βπ§βπ§ Top communities
π The best courses
ποΈ Podcasts where you learn a lot
βοΈ Useful software for Operational Research
β And much more...
I would infinitely appreciate it if you could give it 5 stars βββββ if you find it useful.
You can get it here.
β¬οΈ We already have an initial solution, shall we improve it?
In case you don't remember, a couple of weeks ago, we saw how to build an initial solution. In fact, we explored 5 different methods:
All of them are quite fast, and they all have the same problem: the solution you'll find for your problem is... well, I don't like to say these things, but yes, it's not good.
But it's a starting point.
Let's say it's like when you go for a hike in the mountains, and your goal is to reach the summit of a mountain. So, with this, what we've done is parked the car right where the trail begins. You still have a way to go, but you're in a better position than when you left home. And what do you do to start the journey?
Get moving.
In optimization, a move is a change in the solution that you determine. This move defines a specific neighborhood; and it's called a neighborhood because the solutions found from a solution and a type of move are close to that solution. Moving through the solution space, finding better solutions (in one or several neighborhoods) until you can't find a better solution anymore is what's known as local search.
This local search evaluates each solution it finds, and if it's better than the current one, it keeps it. When no better solutions are found, it reaches what we know as a local optimum.
If you notice, this concept of local search is based on what is probably the oldest procedure in optimization: trial and error. You try a new solution with a given move, and if it's better, you stick with it, but if not, you keep looking.
For example, it's very typical in vehicle routing problems to make moves like this:
In which initially we have the connection b-e and c-f, and we end up linking b-c and e-f to improve the solution. In fact, this specific move has its own name and is called 2-opt, although I repeat: you can define the types of moves you want.
Let's continue.
When exploring the neighborhood defined by a move, there are two classical strategies:
Best improvement: the entire neighborhood is explored with a deterministic process, meaning nothing is left to chance. Once explored, the move that improves the solution the most is chosen, and the neighborhood of this new solution is explored again. This continues until no better solution is found.
First improvement: only a part of the neighborhood is explored, randomly or not, because as soon as a better solution is found, the current solution is updated to that one, and the search continues from there. Again, the process is repeated until no better solution is found.
If you had to choose a strategy, which one would you choose?
With best improvement, at each step, you ensure that the solution you are heading towards is the best possible, but it takes a lot of time, and it's not guaranteed to find a better solution than with first improvement at the end of the process.
So... I'm clear on this, I'll go with first improvement.
In summary: a local search makes moves in one or several defined neighborhoods until it finds a local optimal (or suboptimal) solution:
πΆ MercadoOOona, Mercadona
The other day I was telling you about the importance of warehouses in modern logistics:
And one of the most interesting problems to solve is that of order picking, which is usually done in batches.
I'm not saying it; Mercadona, the leading Spanish supermarket with over a 25% market share, is saying it:
And it turns out that during my doctoral thesis, I dedicated my time to proposing solutions to different order picking problems. So don't be surprised if I tell you how even better solutions to optimization problems can be found than those obtained with a local search π Consider yourself warned!
But before that, and considering eeeeverything I tell you in the tweet above ππ», I would like to ask you:
Today we'll leave it here, but...
I couldn't say goodbye without playing the Mercadona song:
And yes, thatβs the song that sounds in each Mercadona supermarket every single day.
Talk soon,
Borja.
Interesting article. I also wrote one about optimization in the warehouse industry recently. It is about the Storage Location Assignment Problem solved with MILP. In the future I want to go deeper into metaheuristic solutions. Maybe this is interesting for other readers. Keep up the great work!
https://medium.com/@beware-sim/optimizing-warehouse-efficiency-the-storage-location-assignment-problem-47ac683a7f56