This page is for an old version of Hexaly Optimizer. We recommend that you update your version and read the documentation for the latest stable release.

Order Picking

Principles learned

  • Add a list decision variable

  • Access the list elements with an “at” operator

  • Constrain the number of elements in the list with operator “count”

  • Access a multi-dimensional array with an “at” operator

  • Get the value of a list variable

  • Use indexOf to retrieve the index of a specific element in a list

Problem

../_images/order-picking.svg

The order picking problem consists in finding the picking order which minimizes the distance (or the time) needed to pick all of the orders in a given warehouse and to go back to the initial position. In this case, we consider an ordinary rectangular warehouse with a single depot used for order drop-off. The depot also acts as the initial position of the picker. The Products (or orders) to pick are located on either side of vertical aisles, both accessible. The vertical aisles are surrounded by horizontal cross aisles which allow the picker to navigate through the warehouse. The picker can move vertically and horizontally, and so the distances between every orders are computed using a Manhattan distance (in the data provided the distance between every pair of orders is computed and accessible in a matrix).

Download the example


Data

The instances provided come from a benchmark proposed by Cristophe Theys, Wout Dullaert and Willy Herroelen (Routing order pickers in multiple block warehouses. In Proceedings of the BIVEC-GIBET Transport Research Day, 2007/Hilferink, Pieter [edit.], pages 10–30, 2007.). The proposed format is composed of the number of orders to pick, followed by the distance matrix between all pairs of orders including the initial position (at index 0). The file names describe the configuration of the contained instance.

Program

We use a list to represent the picking order, considering the initial point as an order to pick. The constraint ensures that all of the orders are picked and the objective is to minimize the distance required to pick all the orders. To compute this distance, we use a lambda function which returns, for a given order, the distance to the next one. The objective value is then computed using the sum over the orders starting from the initial point, which corresponds to order 0 in our model. Because we have to bring back all the orders picked to the initial point, we then add to this sum the distance from the last order visited to the initial point.

The picking order is then saved in a file starting from the initial point. To do so, we use the indexOf operator (allowing us to access the index of the specified element inside the list) in the model declaration to recover the position of element 0 in the list.

Execution:
localsolver order_picking.lsp inFileName=instances/Instance_5_11_240_Random_Central_2.txt [solFileName=] [lsTimeLimit=]
use io;

function input() {
    local usage = "Usage: localsolver order_picking.lsp inFileName=instanceFile"
            + " [outFileName=outputFile] [lsTimeLimit=timeLimit]";
    if (inFileName == nil) throw usage;
    local inFile = io.openRead(inFileName);
    nbOrders = inFile.readInt() + 1;
    for [i in 0...nbOrders][j in 0...nbOrders]
        distances[i][j] = inFile.readInt();
    inFile.close();
}

function model() {
    // Declare the list containing the picking order
    pickingList <- list(nbOrders);

    // All orders must be picked
    constraint count(pickingList) == nbOrders;

    // The objective is to minimize the total distance required to pick 
    // all the orders and to go back to the initial position
    objective <- sum(0...nbOrders - 1, i => distances[pickingList[i]][pickingList[i + 1]]) 
        + distances[pickingList[nbOrders - 1]][pickingList[0]];
    
    // Store the index of the initial position in the list.
    // It will be used at the end to write the solution starting from the initial point.
    indexInitialPosition <- indexOf(pickingList, 0);

    minimize objective;
}

function param() {
    if (lsTimeLimit == nil) lsTimeLimit = 10;
}

function output() {
    if (outFileName != nil) {
        outFile = io.openWrite(outFileName);
        outFile.println(objective.value);
        println("Solution written in file ", outFileName);
        for [i in 0...nbOrders] {
            local index = (indexInitialPosition.value + i) % nbOrders;
            outFile.print(pickingList.value[index], " ");
        }
    }
}
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python order_picking.py instances\Instance_5_11_240_Random_Central_2.txt
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_0/bin/python
python order_picking.py instances/Instance_5_11_240_Random_Central_2.txt
import localsolver
import sys

def read_elem(filename) :
    with open(filename) as f :
        return [str(elem) for elem in f.read().split()]

def read_instance(filename) :
    file_iterator = iter(read_elem(filename))
    nb_orders = int(next(file_iterator)) + 1
    distances_data = [None] * nb_orders
    for i in range(nb_orders) :
        distances_data[i] = [None] * nb_orders
        for j in range(nb_orders) :
            distances_data[i][j] = int(next(file_iterator))
    return nb_orders, distances_data

def main(input_file, output_file, time_limit) :
    # Read the instance from input_file
    nb_orders, distances_data = read_instance(input_file)
    
    with localsolver.LocalSolver() as ls :
        # Declare the model
        model = ls.model

        # Declare the list containing the picking order
        picking_list = model.list(nb_orders)

        # All orders must be picked
        model.constraint(model.count(picking_list) == nb_orders)

        # Create a LocalSolver array for the distance matrix in order to access it using the "at" operator
        distances_matrix = model.array(distances_data)

        # Lambda expression to compute the distance to the next order
        distance_to_next_order_lambda = model.lambda_function( 
            lambda i : model.at(distances_matrix, picking_list[i], picking_list[i + 1]))

        # The objective is to minimize the total distance required to pick 
        # all the orders and to go back to the initial position
        objective = model.sum(model.range(0, nb_orders - 1), distance_to_next_order_lambda) \
            + model.at(distances_matrix, picking_list[nb_orders - 1], picking_list[0])

        # Store the index of the initial position in the list.
        # It will be used at the end to write the solution starting from the initial point.
        index_initial_position = model.index(picking_list, 0)

        model.minimize(objective)

        # End of the model declaration
        model.close()

        ls.param.time_limit = time_limit

        ls.solve()

        if output_file != None :
            with open(output_file, 'w') as f:
                f.write("%i\n" % objective.value)
                for i in range(nb_orders):
                    index = (index_initial_position.get_value() + i) % nb_orders
                    f.write("%i " % picking_list.value[index])


if __name__ == '__main__' :
    if len(sys.argv) < 2:
        print("Usage: python order_picking.py input_file [output_file] [time_limit]")
        sys.exit(1)
    input_file = sys.argv[1]
    output_file = sys.argv[2] if len(sys.argv) >= 3 else None
    time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 10
    main(input_file, output_file, time_limit)
Compilation / Execution (Windows)
cl /EHsc order_picking.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver120.lib
order_picking instances\Instance_5_11_240_Random_Central_2.txt
Compilation / Execution (Linux)
g++ order_picking.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -lpthread -o order_picking
./order_picking instances/Instance_5_11_240_Random_Central_2.txt
#include "localsolver.h"
#include <fstream>
#include <iostream>
#include <vector>

using namespace localsolver;
using namespace std;

class OrderPicking {
public:
    int nbOrders;
    vector<vector<int>> distancesData;
    LocalSolver localsolver;
    LSExpression pickingList;
    LSExpression objective;
    LSExpression indexInitialPosition;

    void readInstance(const string& inputFile) {
        ifstream infile(inputFile);
        if (!infile.is_open()) {
            throw std::runtime_error("Cannot open the file.");
        }
        infile >> nbOrders;
        ++nbOrders;
        distancesData.resize(nbOrders);
        for (int i = 0; i < nbOrders; ++i) {
            distancesData[i].resize(nbOrders);
            for (int j = 0; j < nbOrders; ++j) {
                infile >> distancesData[i][j];
            }
        }
    }

    void solve(int timeLimit) {
        // Declare the model
        LSModel model = localsolver.getModel();

        // Declare the list containing the picking order
        pickingList = model.listVar(nbOrders);

        // All orders must be picked
        model.constraint(model.count(pickingList) == nbOrders);

        // Create a LocalSolver array for the distance matrix in order to access it using the "at" operator
        LSExpression distancesMatrix = model.array();
        for (int i = 0; i < nbOrders; ++i) {
            distancesMatrix.addOperand(model.array(distancesData[i].begin(), distancesData[i].end()));
        }

        // Lambda expression to compute the distance to the next order
        LSExpression distanceToNextOrderLambda = model.createLambdaFunction([&](LSExpression i) {
            return model.at(distancesMatrix,  pickingList[i], pickingList[i + 1]);
        });

        // The objective is to minimize the total distance required to pick 
        // all the orders and to go back to the initial position
        objective = model.sum(model.range(0, nbOrders - 1), distanceToNextOrderLambda) 
            + model.at(distancesMatrix, pickingList[nbOrders - 1], pickingList[0]);

        // Store the index of the initial position in the list.
        // It will be used at the end to write the solution starting from the initial point.
        indexInitialPosition = model.indexOf(pickingList, 0);

        model.minimize(objective);

        // End of the model declaration
        model.close();

        localsolver.getParam().setTimeLimit(timeLimit);

        localsolver.solve();
    }

    void writeSolution(const string& outputFile) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(outputFile.c_str());
        outfile << objective.getValue() << endl;
        LSCollection pickingListCollection = pickingList.getCollectionValue();
        for (int i = 0; i < nbOrders; ++i) {
            int index = ((int)indexInitialPosition.getValue() + i) % nbOrders;
            outfile << pickingListCollection[index] << " ";
        }
        outfile << endl;
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "order_picking inputFile [outputFile] [timeLimit]" << endl;
        return 1;
    }
    const char* inputFile = argv[1];
    const char* outputFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "10";
    OrderPicking model;
    model.readInstance(inputFile);
    model.solve(atoi(strTimeLimit));
    if (outputFile != NULL)
        model.writeSolution(outputFile);
    return 0;
}
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc OrderPicking.cs /reference:localsolvernet.dll
OrderPicking instances\Instance_5_11_240_Random_Central_2.txt
using System;
using System.IO;
using System.Globalization;
using localsolver;

public class OrderPicking : IDisposable
{
    int nbOrders;
    int[][] distancesData;

    LocalSolver localsolver;

    LSExpression pickingList;

    LSExpression objective;

    LSExpression indexInitialPosition;

    public OrderPicking() 
    {
        localsolver = new LocalSolver();
    }

    public void ReadInstance(string filename) 
    {
        using(StreamReader input = new StreamReader(filename)) 
        {
            string[] splittedLine = input.ReadLine().Split();
            nbOrders = int.Parse(splittedLine[0]) + 1;
            distancesData = new int[nbOrders][];
            for (int i = 0; i < nbOrders; ++i) 
            {
                splittedLine = input.ReadLine().Split();
                distancesData[i] = new int[nbOrders];
                for (int j = 0; j < nbOrders; ++j) 
                {
                    distancesData[i][j] = int.Parse(splittedLine[j]);
                }
            }
        }
    }

    public void Dispose() 
    {
        if (localsolver != null)
            localsolver.Dispose();
    } 

    public void Solve(int timeLimit) 
    {
        // Declare the model
        LSModel model = localsolver.GetModel();

        // Declare the list containing the picking order
        pickingList = model.List(nbOrders);

        // All orders must be picked
        model.Constraint(model.Count(pickingList) == nbOrders);

        // Create a LocalSolver array for the distance matrix in order to access it using the "at" operator
        LSExpression distancesMatrix = model.Array(distancesData);

        // Lambda expression to compute the distance to the next order
        LSExpression distanceToNextOrderLambda = model.LambdaFunction( 
            i => distancesMatrix[pickingList[i]][pickingList[i + 1]]);

        // The objective is to minimize the total distance required to pick 
        // all the orders and to go back to the initial position
        objective = model.Sum(model.Range(0, nbOrders - 1), distanceToNextOrderLambda) 
            + distancesMatrix[pickingList[nbOrders - 1]][pickingList[0]];

        // Store the index of the initial position in the list.
        // It will be used at the end to write the solution starting from the initial point.
        indexInitialPosition = model.IndexOf(pickingList, 0);

        model.Minimize(objective);

        // End of the model declaration
        model.Close();

        localsolver.GetParam().SetTimeLimit(timeLimit);

        localsolver.Solve();
    }

    public void WriteSolution(string filename) 
    {
        using (StreamWriter output = new StreamWriter(filename)) 
        {
            output.WriteLine(objective.GetIntValue());
            LSCollection solutionCollection = pickingList.GetCollectionValue();
            for (int i = 0; i < nbOrders; ++i) 
            {
                int index = ((int)indexInitialPosition.GetValue() + i) % nbOrders;
                output.Write(solutionCollection[index] + " ");
            }
            output.Close();
        } 
    }


    public static void Main(string[] args) 
    {
        if (args.Length < 1) 
        {
            Console.WriteLine("Usage: OrderPicking inputFile [outputFile] [timeLimit]");
            Environment.Exit(1);
        }
        string inputFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        int timeLimit = args.Length > 2 ? int.Parse(args[2]) : 10;
        using (OrderPicking model = new OrderPicking()) 
        {
            model.ReadInstance(inputFile);
            model.Solve(timeLimit);
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }

}
Compilation / Execution (Windows)
javac OrderPicking.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. OrderPicking instances\Instance_5_11_240_Random_Central_2.txt
Compilation / Execution (Linux)
javac OrderPicking.java -cp /opt/localsolver_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/bin/localsolver.jar:. OrderPicking instances/Instance_5_11_240_Random_Central_2.txt
import java.util.*;
import java.io.*;
import localsolver.*;

public class OrderPicking {
    private int nbOrders;
    private int[][] distancesData;

    final LocalSolver localsolver;
    private LSExpression pickingList;
    private LSExpression objective; 

    private LSExpression indexInitialPosition;

    private OrderPicking(LocalSolver localsolver) {
        this.localsolver = localsolver;
    }

    private void readInstance(String inputFile) throws IOException {
        try (Scanner input = new Scanner(new File(inputFile))) {
            nbOrders = input.nextInt() + 1;
            distancesData = new int[nbOrders][nbOrders];
            for (int i = 0; i < nbOrders; ++i) {
                for (int j = 0; j < nbOrders; ++j) {
                    distancesData[i][j] = input.nextInt();
                }
            }
        }
    }

    public void solve(int timeLimit) {
        // Declare the model
        LSModel model = localsolver.getModel();

        // Declare the list containing the picking order
        pickingList = model.listVar(nbOrders);

        // All orders must be picked
        model.constraint(model.eq(model.count(pickingList), nbOrders));

        // Create a LocalSolver array for the distance matrix in order to access it using the "at" operator
        LSExpression distancesMatrix = model.array(distancesData);

        // Lambda expression to compute the distance to the next order
        LSExpression distanceToNextOrderLambda = model.lambdaFunction( i -> 
            model.at(distancesMatrix, model.at(pickingList, i), model.at(pickingList, model.sum(i, 1))));

        // The objective is to minimize the total distance required to pick 
        // all the orders and to go back to the initial position
        objective = model.sum(model.sum(model.range(0, nbOrders - 1), distanceToNextOrderLambda),
            model.at(distancesMatrix, model.at(pickingList, nbOrders - 1), model.at(pickingList, 0)));

        // Store the index of the initial position in the list.
        // It will be used at the end to write the solution starting from the initial point.
        indexInitialPosition = model.indexOf(pickingList, 0);

        model.minimize(objective);

        // End of the model declaration
        model.close();

        localsolver.getParam().setTimeLimit(timeLimit);

        localsolver.solve();
    }

    public void writeSolution(String inputFile) throws IOException {
        try (PrintWriter output = new PrintWriter(inputFile)) {
            output.println(objective.getValue());
            LSCollection pickingListCollection = pickingList.getCollectionValue();
            for (int i = 0; i < nbOrders; ++i) {
                int index = ((int)indexInitialPosition.getValue() + i) % nbOrders;
                output.print(pickingListCollection.get(index) + " ");
            }
            output.println();
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("Usage: java OrderPicking inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String inputFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "10";

        try (LocalSolver localsolver = new LocalSolver()) {
            OrderPicking model = new OrderPicking(localsolver);
            model.readInstance(inputFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch(Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}