Dividing Consignments: An Exploration of Different Methods

Abstract

I denne masteren blir ulike metoder for å dele opp større, sammensatte ordre til mindre ordre som har plass på en enkelt pall undersøkt. Motivasjonen bak detter er å gi det norske logistikk- og robotikkselskapet Solwr mer kunnskap om hva som gir gode resultater for deres automatiserte pakkingsrobot, Grab. Per dags dato søker de etter en egnet fremgang for å dele ordre som tar hensyn til Grab, og dens svakheter.

De ulike metode for å dele en større ordre som ble undersøkt, var hvordan en baseline heuristikk brukt til å løse pakkings problemet, kalt Next Fit, gjør det i forhold til metoder med mål om å minimere antall paller som trengs for å tildele alle varene til en bestilling. Spesifikt ble en Mixed-Integer Programming (MIP)-metode og heuristikken simulated annealing brukt. Utvidelse av kostnadsfunksjonen for simulated annealing ble testet for å se om en multiobjektiv kostnadsfunksjon ville være mer egnet enn en enkeltobjektiv kostnadsfunksjon. Muligheten for å bruke maskinlæring for å inkludere en modell for å forutsi hvilken kvalitet Grab hadde gitt ordren, og bruke det som en kostnadsfunksjon i simulated annealing, ble undersøkt.

Resultatene indikerer at metoden som virket mest lovene av de metodene som er testet og som kan være aktuell å utforske nærmere, var å bruke en maskinlæringsmodell i kostnadsfunksjonen. Dette var den eneste metoden som viste en økning i gjennomsnittlig stabilitet sammenlignet med grunnleggende metoden.

In this thesis, different methods of dividing consignments are investigated. The motivation is to provide the Norwegian logistics and robotics company, Solwr, with more knowledge on what gives suitable results for their automated packing robot Grab. As of writing this thesis, they are searching for a suitable approach which takes Grabs performance into account.

The different approaches investigated were how a baseline heuristic used to solve the bin packing problem, Next Fit, performs compared to methods with the goal of minimizing the number of pallets needed to assign all the items to an order. Specifically, a MIP and the heuristic simulated annealing. Expanding the cost function for simulated annealing was tested to see if a multi-objective cost function would be more suitable than the single-objective cost function. The possibility of using machine learning to incorporate a model to predict the quality of an order according to Grab and use it as a cost function in simulated annealing was investigated.

The results indicate that the method of dividing a consignment which was the most promising to explore further was using a machine learning model in the cost function. This was the only method showing an increase in the average stability compared to the baseline method.