BasketSplitter

What Is BasketSplitter?

Say goodbye to receiving multiple small packages for individual items! BasketSplitter is an intelligent delivery management library designed to minimize the number of deliveries while ensuring that your purchases reach your doorstep swiftly and efficiently. Whether you’re a seasoned bargain hunter or a time-strapped executive, this algorithm ensures that your items are bundled together in the most optimal way.

Using BasketSplitter: A Step-by-Step Guide

Warning

• Make sure you have Java 17 or higher version to avoid "Major-Minor Version" issue.

Method 1: Building from Source

Clone the Repository:

• First, navigate to the BasketSplitter repository on GitHub.

• Click the <> Code button to copy the repository URL.

• Open your terminal or command prompt and run:

  git clone <repository_url>

Replace <repository_url> with the actual URL you copied.

Build the Project:

• Change into the cloned repository directory:

  cd BasketSplitter/basket-splitter

• Run the following Maven command to build the project:

  mvn clean package

• This will generate a basket_splitter.jar file in the target directory.

Usage:

• You now have the basket_splitter.jar file.
• Incorporate it into your projects by adding it to your classpath.
• Use the BasketSplitter objects in your code.

Method 2: Direct Download

Download the JAR File:

• If you prefer not to build from source, you can directly download the basket_splitter.jar file from the repository.
• Look for the file in the repository’s code section.

Integration into Maven Project:

If you’re working with a Maven project:

• Open your terminal or command prompt.

• Run the following command, replacing <path_to_jar> with the actual path to the downloaded JAR file:

  mvn install:install-file -Dfile=<path_to_jar> -DgroupId=com.ocado.basket -DartifactId=basket_splitter -Dversion=1.0.0 -Dpackaging=jar

• Add the following dependency to your project’s pom.xml:

  <dependency>
    <groupId>com.ocado.basket</groupId>
    <artifactId>basket_splitter</artifactId>
    <version>1.0.0</version>
  </dependency>

Basic Java App:

If you’re working with a basic Java application:

• Compile your Java code along with the basket_splitter.jar:

  javac -cp <path_to_jar> Your_App.java

• Run your application:

  java -cp <path_to_jar> Your_App.java

And that’s it! You’re all set to use BasketSplitter in your projects. If you’d like to see an example app, it’s available in the examples directory.

Set Cover Problem for Intelligent Delivery Distribution

Problem Context

In our project, we’ve developed an algorithm that optimizes the delivery process for online stores. The goal is to efficiently distribute products from a customer’s shopping basket while minimizing the number of deliveries. Imagine a scenario where a customer orders multiple items, and our system needs to decide how to pack and deliver those items in the most effective way.

The Set Cover Problem

The Set Cover Problem serves as the backbone of our intelligent delivery distribution algorithm. Here’s why we’ve chosen this problem:

• Coverage Efficiency: Just like covering all elements in a universe, our application aims to cover all the products in a customer’s order. Each product corresponds to an element, and the sets represent products that can be delivered via the same method.
• Minimizing Deliveries: By selecting the smallest sub-collection of sets (i.e., delivery options), we ensure that the customer receives all their items in as few deliveries as possible. This directly aligns with our project’s objective of optimizing the delivery process.

Problem Statement

Given:

• A universe of elements (often denoted as ${1, 2, \ldots, n}$).
• A collection of subsets (sets) whose union covers the entire universe.

The task is to identify the smallest sub-collection of sets whose union equals the universe. In other words, we want to find the most efficient way to cover all elements while minimizing the number of selected sets.

Example:

Let’s illustrate the problem with a simple example:

Universe:

$$U = \{1, 2, 3, 4, 5, 6\}$$

Collection of sets:

$$S = \{ \{1,2,3,6\}, \{1,2,4\}, \{3,4,5\} \}$$

Clearly, the union of all sets in S covers the entire universe U. However, we can achieve the same coverage using only two sets:

$$\{ \{1,2,3,6\}, \{3,4,5\} \}$$
Therefore, the solution to the set cover problem in this case has a size of 2.
In our algorithm, we’ve made a small modification to ensure that elements do not repeat, such as 3 in this example. An online shop would not be pleased if items were sent more times than they were ordered. 😉

Features

1. Config File Loading

• The configuration file (in JSON format) should contain a list of items that can be delivered.

• Next to each item, the configuration file should list the available delivery options. These options define how the item can be delivered. For example:

  {
   "Strawberries": [
      "Pick-up Point",
      "Courier"
    ],
   "Dining table": ["Courier"]
  }

  In this configuration:

  • Strawberries can be delivered either via a Pick-up Point or by Courier.
  • The Dining table is exclusively available for delivery through the Courier service.

• Warning: you can add up to 1000 items and 10 different deliveries to your config file

2. Basket Optimization

• Load a shopping basket from a separate JSON file. The basket includes the items selected by the user. For example:

  [
    "Strawberries",
    "Dining Table"
  ]

• Warning you can add up to 100 items to your basket

• BasketSplitter will intelligently group items from the basket to minimize the number of deliveries.

3. Output File Saving

• After optimization, BasketSplitter saves the optimized basket to an output JSON file. This file contains the grouped items and their delivery details. For example:

  {
   "Courier": [
     "Strawberries",
     "Dinning table"
   ]
  }

4. Format

• JSON Compatibility: All input and output files (config, basket, and output) must be in JSON format, using pattern specified earlier.

Ready to optimize your shopping experience? Let’s make deliveries smarter 📦