What do designing an aircraft wing, packing boxes into a container, and making timetables have in common? They’re all optimization problems, according to Picnic blogger Geert Konijnendijk: “there’s an objective to be maximized or minimized (least air resistance, most boxes packed or least man-hours spent). Each individual solution to these problems will have a score for the objective and the goal is to find the best possible one”.
In a previous Picnic blog post Geert discussed how the world of logistics is fundamentally one of algorithms and optimization. In a new blog post he zooms into one specific case. Each day tens of thousands of orders for Picnic’s customers are packed at their fulfillment centers. These orders are loaded into trucks and shipped to our hubs, from which they are delivered to the customer’s doorstep. How do they create an optimal schedule for these trucks driving between fulfillment centers and hubs?
Picnic uses a Genetic Algorithm (GA) to solve this truck scheduling problem. Geert: “GAs are a great tool to solve problems when it is impossible to consider every possible solution because there are simply too many. Instead GAs consider only a fraction of the solutions. This is achieved by taking inspiration from Darwin’s evolutionary theory: letting a population of individual solutions reproduce while subjecting them to natural selection gradually improves the whole population. This is done until the population contains a solution that is deemed good enough”. Genetic Algorithms are a great way to approximate solutions to optimization problems in a reasonable time.
Before making the truck schedule, our algorithms have already determined which groceries should be packed together in a shipment (a truck trailer full of groceries). The input to the GA are these shipments, which need to go from a warehouse to a hub before a certain time. Additionally, Picnic has estimated the number of trucks they require and input that to the GA too. The GA will then calculate which truck takes which shipment at what time. As the number of shipments and trucks grows, the number of possible shipment-to-truck mappings explodes. A GA is a good fit for this problem since Picnic cannot try out every possible option.