OptaPlanner logo
  • Download
  • Learn
    • Documentation
    • Videos

    • Use cases
    • Compatibility
    • Testimonials and case studies
  • Get help
  • Blog
  • Source
  • Team
  • Services
  • Star
  • T
  • L
  • F
  • YT
Fork me on GitHub

Order picking optimization in warehouses and supermarkets with OptaPlanner

Thu 14 October 2021
Avatar Walter Medvedeo
Walter Medvedeo

GitHub

Senior Software Engineer

During the pandemic year, we saw many stores and supermarkets adapt their business in several ways. Sometimes these changes occurred from day to day. For example, as a consequence of the sharp decrease in customer physical visits, online orders increased exponentially.

How many of them were prepared to deal optimally with this increase…​?

In this blog post, we present the new OptaPlanner order-picking quickstart that shows how to complete online orders in an optimized way!

The order picking problem

The order picking problem consists of a set of orders that need to be prepared for delivery to various customers. Each order is composed of a set of order items (the requested products). These products are located on shelves in the warehouse or in the supermarket and occupy a specific volume of space.

To complete the orders, there is a set of available trolleys that follow a calculated path in the supermarket and pick the order items. One order item is picked on each step of this path. The location of the products within the warehouse determine the path of the trolley, and the space in each trolley is divided into a number of buckets with a specified capacity.

The goal of the order picking problem is to calculate a picking plan that provides the path for each trolley and considers the following constraints:

  • The distance to travel by the trolleys is minimized.

  • All the order items must be picked.

  • Items from different orders mustn’t be mixed in the same bucket, so enough buckets must be reserved for each of the orders that will be prepared on the same trolley.

  • The bucket’s capacity is not exceeded by the total volume of the items on it.

  • The splitting of an order into different trolleys should be minimized.

The following image shows a simplified view of the order picking problem input data and calculated picking plan:

orderPickingProblem

Warehouse structure

To formulate the problem, the warehouse is defined as a set of shelves organized into columns and rows. Products are located on the left or right side of a specific shelf, on a specific row. The shelf, side, and row determine the product location.

orderPickingSimplifiedWarehouseStructure

The new quickstart

Project structure

The following image shows the maven project that comprises the quickstart:

orderPickingProjectStructure

The server side code is in the src/main/java directory and is organized in four packages:

bootstrap

Helper classes for generating the randomized (but reproducible) data set used by the quickstart on application startup.

domain

Contains the domain model for representing the problem, and the planning classes used by OptaPlanner, for example the @PlanningSolution and the @PlanningEntity.

solver

Contains the ConstraintProvider implementation.

rest

Contains the REST API used by the client-side code to start and stop solving, and to retrieve the best solution to display.

The client code is in the src/main/resources/META-INF/resources/ directory. This directory has an index.html file that contains the basic HTML structure and loads the app.js file that calls the server’s REST API and makes the web page dynamic.

Planning domain model

orderPickingClassDiagram

Order picking constraints

The order picking constraints are implemented using the Constraint Streams API, and they can be found in the org.acme.orderpicking.solver.OrderPickingConstraintProvider class.

The following constraints are provided:

requiredNumberOfBuckets

Hard constraint to enforce the requirement that a trolley has a sufficient number of buckets for holding all of the elements picked along the path for each order, while at the same time the bucket’s capacity is not exceeded, and items from different orders are not mixed in the same bucket.

minimizeDistanceFromPreviousTrolleyStep

Soft constraint to enforce the requirement that the distance between the current trolley step, and the previous step in the calculated path is minimized.

minimizeDistanceFromLastTrolleyStepToPathOrigin

Soft constraint to enforce the requirement that the distance between the first trolley stop (the path origin), and the last trolley stop in the calculated path is minimized.

The conjunction of the minimizeDistanceFromPreviousTrolleyStep constraint applied to every step on the path, and the minimizeDistanceFromLastTrolleyStepToPathOrigin constraint, enforces the entire path minimization.

minimizeOrderSplitByTrolley

Soft constraint to minimize the orders splitting into different trolleys.

Execution explained

When you first start the order picker, you will see that no picking plan or paths are calculated. No worries, it’s perfectly fine because the solver isn’t executed yet.

Let’s take a moment to take a look at the initial data set before starting the solver. You use the Unassigned tab to do this.

Unassigned entities

The information about the unassigned trolleys and orders is shown on the different sub-tabs.

Before starting the solver, you can view all of the elements in the initial data set on this tab. However, as soon the solver starts solving, you will see that elements start disappearing from this tab. Good news, they’re becoming part of the picking plan!.

Unassigned trolleys

orderPickingUnassignedTrolleys

Unassigned Order_1

orderPickingUnassignedOrders

Solver execution

Click the Start button to start the solver. When the solver is started, you’ll see that the Picking plan tab will start showing the information about the calculated plan.

orderPickingPlan
Note
While the solver is running, the calculated plan is refreshed every 2 seconds, causing a screen refresh effect. You can use the stop solving button to mitigate this effect.

Trolley navigation

Use the Map tab to view a representation of how the different trolleys navigate the warehouse according to the calculated paths.

orderPickingTrolleyPaths

Running the quickstart

To run the quickstart, follow these steps:

  1. Clone the optaplanner-quickstarts repository:

$ git clone https://github.com/kiegroup/optaplanner-quickstarts
  1. Switch to the development branch with the following commands:

$ cd optaplanner-quickstarts
$ git checkout development
  1. Navigate to the use-cases/order-picking directory.

$ cd use-cases/order-picking
  1. Start the Order Picking quick start in Quarkus development mode:

$ mvn quarkus:dev
  1. Open http://localhost:8080 in your browser and click on the Solve button.


Permalink
 tagged as use case order picking quarkus

Comments

Visit our forum to comment
AtomNews feed
Don’t want to miss a single blog post?
Follow us on
  • T
  • L
  • F
Blog archive
Latest release
  • 8.35.0.Final released
    Fri 3 March 2023
Upcoming events
    Add event / Archive
Latest blog posts
  • OptaPlanner 9 is coming
    Tue 21 February 2023
    Lukáš Petrovický
  • Farewell - a new lead
    Tue 15 November 2022
    Geoffrey De Smet
  • Run OptaPlanner workloads on OpenShift, part II
    Wed 9 November 2022
    Radovan Synek
  • Bavet - A faster score engine for OptaPlanner
    Tue 6 September 2022
    Geoffrey De Smet
  • Run OptaPlanner workloads on OpenShift, part I.
    Thu 9 June 2022
    Radovan Synek
  • OptaPlanner deprecates score DRL
    Thu 26 May 2022
    Lukáš Petrovický
  • Real-time planning meets SolverManager
    Mon 7 March 2022
    Radovan Synek
  • Blog archive
Latest videos
  • The Vehicle Routing Problem
    Fri 23 September 2022
    Geoffrey De Smet
  • Introduction to OptaPlanner AI constraint solver
    Thu 25 August 2022
    Anna Dupliak
  • On schedule: Artificial Intelligence plans that meet expectations
    Sat 23 July 2022
    Geoffrey De Smet
  • Host your OptaPlanner app on OpenShift (Kubernetes)
    Mon 7 February 2022
    Geoffrey De Smet
  • OptaPlanner - A fast, easy-to-use, open source AI constraint solver for software developers
    Mon 31 January 2022
  • Order picking planning with OptaPlanner
    Fri 31 December 2021
    Anna Dupliak
  • AI lesson scheduling on Quarkus with OptaPlanner
    Thu 18 November 2021
    Geoffrey De Smet
  • Video archive

OptaPlanner is open. All dependencies of this project are available under the Apache Software License 2.0 or a compatible license. OptaPlanner is trademarked.

This website was built with JBake and is open source.

Community

  • Blog
  • Get Help
  • Team
  • Governance
  • Academic research

Code

  • Build from source
  • Issue tracker
  • Release notes
  • Upgrade recipes
  • Logo and branding
CC by 3.0 | Privacy Policy
Sponsored by Red Hat