Capacitated Vehicle Routing (CVRP)

Principles learned

  • Add multiple list decision variables

  • Add a partition constraint

  • Use a lambda expression to compute a sum with a variable number of terms

  • Define a sequence of expressions

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

  • Add multiple objectives

Problem

../_images/vrp.svg

In the capacitated vehicle routing problem (CVRP), a fleet of delivery vehicles with uniform capacity must service customers with known demand for a single commodity. The vehicles start and end their routes at a common depot. Each customer can only be served by one vehicle. The objectives are to minimize the fleet size and assign a sequence of customers to each truck of the fleet minimizing the total distance traveled such that all customers are served and the total demand served by each truck does not exceed its capacity.

Download the example


Data

The instances provided come from the Augerat et al. Set A instances. They follow the TSPLib format.

The format of the data files is as follows:

  • The number of nodes follows the keyword DIMENSION (there is one warehouse so the number of customers is the number of nodes minus 1).

  • The truck capacity follows the keyword CAPACITY.

  • The edge type follows EDGE_WEIGHT_TYPE. Note that in our model the only edge type accepted is EUC_2D.

  • After the keyword NODE_COORD_SECTION, for each node is listed its id and the corresponding x and y coordinates.

  • After the keyword DEMAND_SECTION, for each node is listed its id and the corresponding demand.

  • Warehouses are listed after the keyword DEPOT_SECTION. Note that in our model only one warehouse is accepted.

The number of available trucks can be defined through the command line. If not, it is deduced from the instance file name that follow this pattern: A-nXX- kNBTRUCKS.vrp.

Program

This Hexaly model defines a route for each truck k as a list variable (customersSequences[k]). It corresponds to the sequence of customers visited. To ensure that all customers must be served, all the list variables are constrained to form a partition, thanks to the “partition” operator.

The number of trucks used for the fleet is defined by the number of trucks that serve at least one customer (if their list variable has at least one element). The definition of these expressions is really straightforward thanks to the “count” and the “greater than” operators.

The quantity delivered on each visit is the demand on the node of this visit. This expression is just defined with an “at” operator to access the array demands. The total quantity delivered by each truck is computed with a function to apply the sum operator over all customers visited by a truck. Note that the number of terms in this sum varies automatically with the size of the list. This quantity is constrained to be lower than the truck capacity.

For each truck, the distance traveled from the visit n-1 to the visit n is accessed with an “at” operator to the multi-dimensional array distanceMatrix, with the first index. Here again we use a function to sum distances along each route.

The two objectives are defined in lexicographical order: we first minimize the number of trucks used, and then we minimize the total distance traveled by all the trucks.

If you are interested in the classical variant where time-windows are defined for each customer, you can now study our CVRPTW model.

Execution:
localsolver cvrp.lsp inFileName=instances/A-n32-k5.vrp [lsTimeLimit=] [solFileName=]
use io;

/* Read instance data. The input files follow the "Augerat" format */
function input() {
    usage = "Usage: localsolver cvrp.lsp inFileName=inputFile "
        + "[solFileName=outputFile] [lsTimeLimit=timeLimit] [nbTrucks=value]";

    if (inFileName == nil) throw usage;
    
    readInputCvrp();
    
    // The number of trucks is usually given in the name of the file
    // nbTrucks can also be given in command line
    if (nbTrucks == nil) nbTrucks = getNbTrucks();

    computeDistanceMatrix();
}
 
/* Declare the optimization model */
function model() {
    // Sequence of customers visited by each truck
    customersSequences[k in 0...nbTrucks] <- list(nbCustomers);

    // All customers must be visited by exactly one truck
    constraint partition[k in 0...nbTrucks](customersSequences[k]);

    for [k in 0...nbTrucks] {
        local sequence <- customersSequences[k];
        local c <- count(sequence);

        // A truck is used if it visits at least one customer
        trucksUsed[k] <- c > 0;

        // The quantity needed in each route must not exceed the truck capacity
        routeQuantity <- sum(sequence, j => demands[j]);
        constraint routeQuantity <= truckCapacity;

        // Distance traveled by truck k
        routeDistances[k] <- sum(1...c, i => distanceMatrix[sequence[i - 1]][sequence[i]])
                + (c > 0 ? (distanceDepot[sequence[0]] + distanceDepot[sequence[c - 1]]) : 0);
    }

    // Total number of trucks used
    nbTrucksUsed <- sum[k in 0...nbTrucks](trucksUsed[k]);

    // Total distance traveled
    totalDistance <- sum[k in 0...nbTrucks](routeDistances[k]);

    // Objective: minimize the number of trucks used, then minimize the distance traveled
    minimize nbTrucksUsed;
    minimize totalDistance;
}

/* Parametrize the solver */
function param() { 
    if (lsTimeLimit == nil) lsTimeLimit = 20;
}

/* Write the solution in a file with the following format:
 * - number of trucks used and total distance
 * - for each truck the customers visited (omitting the start/end at the depot) */
function output() {
    if (solFileName == nil) return;
    local outfile = io.openWrite(solFileName);

    outfile.println(nbTrucksUsed.value, " ", totalDistance.value);
    for [k in 0...nbTrucks] {
        if (trucksUsed[k].value != 1) continue;
        // Values in sequence are in 0...nbCustomers.
        // +2 is to put it back in 2...nbCustomers+2
        // as in the data files (1 being the depot)
        for [customer in customersSequences[k].value]
            outfile.print(customer + 2, " ");
        outfile.println();
    }
}


function readInputCvrp() {
    local inFile = io.openRead(inFileName);
    local nbNodes = 0;
    while (true) {
        local str = inFile.readString();
        if (str.startsWith("DIMENSION")) {
            if (!str.endsWith(":")) str = inFile.readString();
            nbNodes = inFile.readInt();
            nbCustomers = nbNodes - 1;
        } else if ((str.startsWith("CAPACITY"))) {
            if (!str.endsWith(":")) str = inFile.readString();
            truckCapacity = inFile.readInt();
        } else if ((str.startsWith("EDGE_WEIGHT_TYPE"))) {
            if (!str.endsWith(":")) str = inFile.readString();
            local weightType = inFile.readString();
            if (weightType != "EUC_2D")
                throw "Edge Weight Type " + weightType + " is not supported (only EUC_2D)";
        } else if (str.startsWith("NODE_COORD_SECTION")) {
            break;
        } else {
            local dump = inFile.readln();
        }
    }

    // -2 because original customer indices are in 2..nbNodes
    for [n in 0...nbNodes] {
        local node_id = inFile.readInt();
        if (n + 1 != node_id) throw "Unexpected index";
        if (node_id == 1) {
            depotX = round(inFile.readDouble());
            depotY = round(inFile.readDouble());
        } else {
            customersX[node_id - 2] = round(inFile.readDouble());
            customersY[node_id - 2] = round(inFile.readDouble());
        }
    }

    dump = inFile.readln();
    if (!dump.startsWith("DEMAND_SECTION")) throw "Expected keyword DEMAND_SECTION";
    for [n in 1..nbNodes] {
        if (n != inFile.readInt()) throw "Unexpected index";
        local demand = inFile.readInt();
        if (n == 1) {
            if (demand != 0) throw "Demand for depot should be O";
        } else {
            demands[n - 2] = demand; // -2 because original customer indices are in 2..nbNodes
        }
    }

    dump = inFile.readln();
    if (!dump.startsWith("DEPOT_SECTION")) throw "Expected keyword DEPOT_SECTION";
    local depotId = inFile.readInt();
    if (depotId != 1) throw "Depot id is supposed to be 1";
    local endOfDepotSection = inFile.readInt();
    if (endOfDepotSection != -1) throw "Expecting only one depot, more than one found";
}

/* Compute the distance matrix */
function computeDistanceMatrix() {
    for [i in 0...nbCustomers] {
        distanceMatrix[i][i] = 0;
        for [j in i+1...nbCustomers] {
            local localDistance = computeDist(customersX[i], customersX[j], customersY[i], customersY[j]);
            distanceMatrix[j][i] = localDistance;
            distanceMatrix[i][j] = localDistance;
        }
    }

    for [i in 0...nbCustomers] {
        local localDistance = computeDist(depotX, customersX[i], depotY, customersY[i]);
        distanceDepot[i] = localDistance;
    }
}

function computeDist(xi, xj, yi, yj) {
    local exactDist = sqrt(pow((xi - xj), 2) + pow((yi - yj), 2));
    return round(exactDist);
}

function getNbTrucks() {
    local splitted = inFileName.split("-k");
    if (count(splitted) >= 2) {
        local numvrp = splitted[count(splitted) - 1];
        splitted = numvrp.split(".");
        if (count(splitted) == 2) return splitted[0].toInt();
    } else {
        println("Error: nbTrucks could not be read from the file name.
                Enter it from the command line");
        throw usage;
    }
}
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python cvrp.py instances\A-n32-k5.vrp
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_5/bin/python
python cvrp.py instances/A-n32-k5.vrp
import localsolver
import sys
import math


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


def main(instance_file, str_time_limit, output_file, str_nb_trucks):
    nb_trucks = int(str_nb_trucks)

    #
    # Read instance data
    #
    nb_customers, truck_capacity, dist_matrix_data, dist_depot_data, \
        demands_data = read_input_cvrp(instance_file)

    # The number of trucks is usually given in the name of the file
    # nb_trucks can also be given in command line
    if nb_trucks == 0:
        nb_trucks = get_nb_trucks(instance_file)

    with localsolver.LocalSolver() as ls:
        #
        # Declare the optimization model
        #
        model = ls.model

        # Sequence of customers visited by each truck
        customers_sequences = [model.list(nb_customers) for _ in range(nb_trucks)]

        # All customers must be visited by exactly one truck
        model.constraint(model.partition(customers_sequences))

        # Create LocalSolver arrays to be able to access them with an "at" operator
        demands = model.array(demands_data)
        dist_matrix = model.array()
        for n in range(nb_customers):
            dist_matrix.add_operand(model.array(dist_matrix_data[n]))
        dist_depot = model.array(dist_depot_data)

        # A truck is used if it visits at least one customer
        trucks_used = [(model.count(customers_sequences[k]) > 0) for k in range(nb_trucks)]

        dist_routes = [None] * nb_trucks
        for k in range(nb_trucks):
            sequence = customers_sequences[k]
            c = model.count(sequence)

            # The quantity needed in each route must not exceed the truck capacity
            demand_lambda = model.lambda_function(lambda j: demands[j])
            route_quantity = model.sum(sequence, demand_lambda)
            model.constraint(route_quantity <= truck_capacity)

            # Distance traveled by each truck
            dist_lambda = model.lambda_function(lambda i:
                                                model.at(dist_matrix,
                                                         sequence[i - 1],
                                                         sequence[i]))
            dist_routes[k] = model.sum(model.range(1, c), dist_lambda) \
                + model.iif(c > 0,
                            dist_depot[sequence[0]] + dist_depot[sequence[c - 1]],
                            0)

        # Total number of trucks used
        nb_trucks_used = model.sum(trucks_used)

        # Total distance traveled
        total_distance = model.sum(dist_routes)

        # Objective: minimize the number of trucks used, then minimize the distance traveled
        model.minimize(nb_trucks_used)
        model.minimize(total_distance)

        model.close()

        # Parameterize the solver
        ls.param.time_limit = int(str_time_limit)

        ls.solve()

        #
        # Write the solution in a file with the following format:
        #  - number of trucks used and total distance
        #  - for each truck the customers visited (omitting the start/end at the depot)
        #
        if output_file is not None:
            with open(output_file, 'w') as f:
                f.write("%d %d\n" % (nb_trucks_used.value, total_distance.value))
                for k in range(nb_trucks):
                    if trucks_used[k].value != 1:
                        continue
                    # Values in sequence are in 0...nbCustomers. +2 is to put it back
                    # in 2...nbCustomers+2 as in the data files (1 being the depot)
                    for customer in customers_sequences[k].value:
                        f.write("%d " % (customer + 2))
                    f.write("\n")


# The input files follow the "Augerat" format
def read_input_cvrp(filename):
    file_it = iter(read_elem(filename))

    nb_nodes = 0
    while True:
        token = next(file_it)
        if token == "DIMENSION":
            next(file_it)  # Removes the ":"
            nb_nodes = int(next(file_it))
            nb_customers = nb_nodes - 1
        elif token == "CAPACITY":
            next(file_it)  # Removes the ":"
            truck_capacity = int(next(file_it))
        elif token == "EDGE_WEIGHT_TYPE":
            next(file_it)  # Removes the ":"
            token = next(file_it)
            if token != "EUC_2D":
                print("Edge Weight Type " + token + " is not supported (only EUD_2D)")
                sys.exit(1)
        elif token == "NODE_COORD_SECTION":
            break

    customers_x = [None] * nb_customers
    customers_y = [None] * nb_customers
    depot_x = 0
    depot_y = 0
    for n in range(nb_nodes):
        node_id = int(next(file_it))
        if node_id != n + 1:
            print("Unexpected index")
            sys.exit(1)
        if node_id == 1:
            depot_x = int(next(file_it))
            depot_y = int(next(file_it))
        else:
            # -2 because original customer indices are in 2..nbNodes
            customers_x[node_id - 2] = int(next(file_it))
            customers_y[node_id - 2] = int(next(file_it))

    distance_matrix = compute_distance_matrix(customers_x, customers_y)
    distance_depots = compute_distance_depots(depot_x, depot_y, customers_x, customers_y)

    token = next(file_it)
    if token != "DEMAND_SECTION":
        print("Expected token DEMAND_SECTION")
        sys.exit(1)

    demands = [None] * nb_customers
    for n in range(nb_nodes):
        node_id = int(next(file_it))
        if node_id != n + 1:
            print("Unexpected index")
            sys.exit(1)
        if node_id == 1:
            if int(next(file_it)) != 0:
                print("Demand for depot should be 0")
                sys.exit(1)
        else:
            # -2 because original customer indices are in 2..nbNodes
            demands[node_id - 2] = int(next(file_it))

    token = next(file_it)
    if token != "DEPOT_SECTION":
        print("Expected token DEPOT_SECTION")
        sys.exit(1)

    depot_id = int(next(file_it))
    if depot_id != 1:
        print("Depot id is supposed to be 1")
        sys.exit(1)

    end_of_depot_section = int(next(file_it))
    if end_of_depot_section != -1:
        print("Expecting only one depot, more than one found")
        sys.exit(1)

    return nb_customers, truck_capacity, distance_matrix, distance_depots, demands


# Compute the distance matrix
def compute_distance_matrix(customers_x, customers_y):
    nb_customers = len(customers_x)
    distance_matrix = [[None for i in range(nb_customers)] for j in range(nb_customers)]
    for i in range(nb_customers):
        distance_matrix[i][i] = 0
        for j in range(nb_customers):
            dist = compute_dist(customers_x[i], customers_x[j], customers_y[i], customers_y[j])
            distance_matrix[i][j] = dist
            distance_matrix[j][i] = dist
    return distance_matrix


# Compute the distances to depot
def compute_distance_depots(depot_x, depot_y, customers_x, customers_y):
    nb_customers = len(customers_x)
    distance_depots = [None] * nb_customers
    for i in range(nb_customers):
        dist = compute_dist(depot_x, customers_x[i], depot_y, customers_y[i])
        distance_depots[i] = dist
    return distance_depots


def compute_dist(xi, xj, yi, yj):
    exact_dist = math.sqrt(math.pow(xi - xj, 2) + math.pow(yi - yj, 2))
    return int(math.floor(exact_dist + 0.5))


def get_nb_trucks(filename):
    begin = filename.rfind("-k")
    if begin != -1:
        begin += 2
        end = filename.find(".", begin)
        return int(filename[begin:end])
    print("Error: nb_trucks could not be read from the file name. Enter it from the command line")
    sys.exit(1)


if __name__ == '__main__':
    if len(sys.argv) < 2:
        print("Usage: python cvrp.py input_file [output_file] [time_limit] [nb_trucks]")
        sys.exit(1)

    instance_file = sys.argv[1]
    output_file = sys.argv[2] if len(sys.argv) > 2 else None
    str_time_limit = sys.argv[3] if len(sys.argv) > 3 else "20"
    str_nb_trucks = sys.argv[4] if len(sys.argv) > 4 else "0"

    main(instance_file, str_time_limit, output_file, str_nb_trucks)
Compilation / Execution (Windows)
cl /EHsc cvrp.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver125.lib
cvrp instances\A-n32-k5.vrp
Compilation / Execution (Linux)
g++ cvrp.cpp -I/opt/localsolver_12_5/include -llocalsolver125 -lpthread -o cvrp
./cvrp instances/A-n32-k5.vrp
#include "localsolver.h"
#include <cmath>
#include <cstring>
#include <fstream>
#include <iostream>
#include <vector>

using namespace localsolver;
using namespace std;

class Cvrp {
public:
    // LocalSolver
    LocalSolver localsolver;

    // Number of customers
    int nbCustomers;

    // Capacity of the trucks
    int truckCapacity;

    // Demand on each customer
    vector<int> demandsData;

    // Distance matrix between customers
    vector<vector<int>> distMatrixData;

    // Distances between customers and depot
    vector<int> distDepotData;

    // Number of trucks
    int nbTrucks;

    // Decision variables
    vector<LSExpression> customersSequences;

    // Are the trucks actually used
    vector<LSExpression> trucksUsed;

    // Number of trucks used in the solution
    LSExpression nbTrucksUsed;

    // Distance traveled by all the trucks
    LSExpression totalDistance;

    Cvrp(const char* strNbTrucks) { nbTrucks = atoi(strNbTrucks); }

    /* Read instance data */
    void readInstance(const string& fileName) {
        readInputCvrp(fileName);

        // The number of trucks is usually given in the name of the file
        // nbTrucks can also be given in command line
        if (nbTrucks == 0)
            nbTrucks = getNbTrucks(fileName);
    }

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

        // Sequence of customers visited by each truck
        customersSequences.resize(nbTrucks);
        for (int k = 0; k < nbTrucks; ++k) {
            customersSequences[k] = model.listVar(nbCustomers);
        }

        // All customers must be visited by exactly one truck
        model.constraint(model.partition(customersSequences.begin(), customersSequences.end()));

        // Create LocalSolver arrays to be able to access them with an "at" operator
        LSExpression demands = model.array(demandsData.begin(), demandsData.end());
        LSExpression distMatrix = model.array();
        for (int n = 0; n < nbCustomers; ++n) {
            distMatrix.addOperand(model.array(distMatrixData[n].begin(), distMatrixData[n].end()));
        }
        LSExpression distDepot = model.array(distDepotData.begin(), distDepotData.end());

        trucksUsed.resize(nbTrucks);
        vector<LSExpression> distRoutes(nbTrucks);

        for (int k = 0; k < nbTrucks; ++k) {
            LSExpression sequence = customersSequences[k];
            LSExpression c = model.count(sequence);

            // A truck is used if it visits at least one customer
            trucksUsed[k] = c > 0;

            // The quantity needed in each route must not exceed the truck capacity
            LSExpression demandLambda =
                model.createLambdaFunction([&](LSExpression j) { return demands[j]; });
            LSExpression routeQuantity = model.sum(sequence, demandLambda);
            model.constraint(routeQuantity <= truckCapacity);

            // Distance traveled by truck k
            LSExpression distLambda = model.createLambdaFunction(
                [&](LSExpression i) { return model.at(distMatrix, sequence[i - 1], sequence[i]); });
            distRoutes[k] = model.sum(model.range(1, c), distLambda) +
                            model.iif(c > 0, distDepot[sequence[0]] + distDepot[sequence[c - 1]], 0);
        }

        // Total number of trucks used
        nbTrucksUsed = model.sum(trucksUsed.begin(), trucksUsed.end());

        // Total distance traveled
        totalDistance = model.sum(distRoutes.begin(), distRoutes.end());

        // Objective: minimize the number of trucks used, then minimize the distance traveled
        model.minimize(nbTrucksUsed);
        model.minimize(totalDistance);

        model.close();

        // Parametrize the solver
        localsolver.getParam().setTimeLimit(limit);

        localsolver.solve();
    }

    /* Write the solution in a file with the following format:
     *  - number of trucks used and total distance
     *  - for each truck the customers visited (omitting the start/end at the depot) */
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());

        outfile << nbTrucksUsed.getValue() << " " << totalDistance.getValue() << endl;
        for (int k = 0; k < nbTrucks; ++k) {
            if (trucksUsed[k].getValue() != 1)
                continue;
            // Values in sequence are in 0...nbCustomers. +2 is to put it back in 2...nbCustomers+2
            // as in the data files (1 being the depot)
            LSCollection customersCollection = customersSequences[k].getCollectionValue();
            for (int i = 0; i < customersCollection.count(); ++i) {
                outfile << customersCollection[i] + 2 << " ";
            }
            outfile << endl;
        }
    }

private:
    // The input files follow the "Augerat" format
    void readInputCvrp(const string& fileName) {
        ifstream infile(fileName.c_str());
        if (!infile.is_open()) {
            throw std::runtime_error("File cannot be opened.");
        }

        string str;
        char* pch;
        char* line;
        int nbNodes;
        while (true) {
            getline(infile, str);
            line = strdup(str.c_str());
            pch = strtok(line, " :");
            if (strcmp(pch, "DIMENSION") == 0) {
                pch = strtok(NULL, " :");
                nbNodes = atoi(pch);
                nbCustomers = nbNodes - 1;
            } else if (strcmp(pch, "CAPACITY") == 0) {
                pch = strtok(NULL, " :");
                truckCapacity = atoi(pch);
            } else if (strcmp(pch, "EDGE_WEIGHT_TYPE") == 0) {
                pch = strtok(NULL, " :");
                if (strcmp(pch, "EUC_2D") != 0) {
                    throw std::runtime_error("Only Edge Weight Type EUC_2D is supported");
                }
            } else if (strcmp(pch, "NODE_COORD_SECTION") == 0) {
                break;
            }
        }

        vector<int> customersX(nbCustomers);
        vector<int> customersY(nbCustomers);
        int depotX, depotY;
        for (int n = 1; n <= nbNodes; ++n) {
            int id;
            infile >> id;
            if (id != n) {
                throw std::runtime_error("Unexpected index");
            }
            if (n == 1) {
                infile >> depotX;
                infile >> depotY;
            } else {
                // -2 because original customer indices are in 2..nbNodes
                infile >> customersX[n - 2];
                infile >> customersY[n - 2];
            }
        }

        computeDistanceMatrix(depotX, depotY, customersX, customersY);

        getline(infile, str); // End the last line
        getline(infile, str);
        line = strdup(str.c_str());
        pch = strtok(line, " :");
        if (strcmp(pch, "DEMAND_SECTION") != 0) {
            throw std::runtime_error("Expected keyword DEMAND_SECTION");
        }

        demandsData.resize(nbCustomers);
        for (int n = 1; n <= nbNodes; ++n) {
            int id;
            infile >> id;
            if (id != n) {
                throw std::runtime_error("Unexpected index");
            }
            int demand;
            infile >> demand;
            if (n == 1) {
                if (demand != 0) {
                    throw std::runtime_error("Demand for depot should be O");
                }
            } else {
                // -2 because original customer indices are in 2..nbNodes
                demandsData[n - 2] = demand;
            }
        }

        getline(infile, str); // End the last line
        getline(infile, str);
        line = strdup(str.c_str());
        pch = strtok(line, " :");
        if (strcmp(pch, "DEPOT_SECTION") != 0) {
            throw std::runtime_error("Expected keyword DEPOT_SECTION");
        }

        int depotId;
        infile >> depotId;
        if (depotId != 1) {
            throw std::runtime_error("Depot id is supposed to be 1");
        }

        int endOfDepotSection;
        infile >> endOfDepotSection;
        if (endOfDepotSection != -1) {
            throw std::runtime_error("Expecting only one depot, more than one found");
        }

        infile.close();
    }

    // Compute the distance matrix
    void computeDistanceMatrix(int depotX, int depotY, const vector<int>& customersX, const vector<int>& customersY) {
        distMatrixData.resize(nbCustomers);
        for (int i = 0; i < nbCustomers; ++i) {
            distMatrixData[i].resize(nbCustomers);
        }
        for (int i = 0; i < nbCustomers; ++i) {
            distMatrixData[i][i] = 0;
            for (int j = i + 1; j < nbCustomers; ++j) {
                int distance = computeDist(customersX[i], customersX[j], customersY[i], customersY[j]);
                distMatrixData[i][j] = distance;
                distMatrixData[j][i] = distance;
            }
        }

        distDepotData.resize(nbCustomers);
        for (int i = 0; i < nbCustomers; ++i) {
            distDepotData[i] = computeDist(depotX, customersX[i], depotY, customersY[i]);
        }
    }

    int computeDist(int xi, int xj, int yi, int yj) {
        double exactDist = sqrt(pow((double)xi - xj, 2) + pow((double)yi - yj, 2));
        return floor(exactDist + 0.5);
    }

    int getNbTrucks(const string& fileName) {
        size_t pos = fileName.rfind("-k");
        if (pos != string::npos) {
            string nbTrucksStr = fileName.substr(pos + 2);
            pos = nbTrucksStr.find(".");
            if (pos != string::npos) {
                return atoi(nbTrucksStr.substr(0, pos).c_str());
            }
        }
        throw std::runtime_error(
            "Error: nbTrucks could not be read from the file name. Enter it from the command line");
        return -1;
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: cvrp inputFile [outputFile] [timeLimit] [nbTrucks]" << endl;
        return 1;
    }

    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "20";
    const char* strNbTrucks = argc > 4 ? argv[4] : "0";

    try {
        Cvrp model(strNbTrucks);
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
        if (solFile != NULL)
            model.writeSolution(solFile);
        return 0;
    } catch (const exception& e) {
        cerr << "An error occurred: " << e.what() << endl;
        return 1;
    }
}
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc Cvrp.cs /reference:localsolvernet.dll
Cvrp instances\A-n32-k5.vrp
using System;
using System.IO;
using localsolver;

public class Cvrp : IDisposable
{
    // LocalSolver
    LocalSolver localsolver;

    // Number of customers
    int nbCustomers;

    // Capacity of the trucks
    int truckCapacity;

    // Demand on each customer
    long[] demandsData;

    // Distance matrix between customers
    long[][] distMatrixData;

    // Distances between customers and depot
    long[] distDepotData;

    // Number of trucks
    int nbTrucks;

    // Decision variables
    LSExpression[] customersSequences;

    // Are the trucks actually used
    LSExpression[] trucksUsed;

    // Number of trucks used in the solution
    LSExpression nbTrucksUsed;

    // Distance traveled by all the trucks
    LSExpression totalDistance;

    public Cvrp(string strNbTrucks)
    {
        localsolver = new LocalSolver();
        nbTrucks = int.Parse(strNbTrucks);
    }

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        ReadInputCvrp(fileName);

        // The number of trucks is usually given in the name of the file
        // nbTrucks can also be given in command line
        if (nbTrucks == 0)
            nbTrucks = GetNbTrucks(fileName);
    }

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

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

        trucksUsed = new LSExpression[nbTrucks];
        customersSequences = new LSExpression[nbTrucks];
        LSExpression[] distRoutes = new LSExpression[nbTrucks];

        // Sequence of customers visited by each truck
        for (int k = 0; k < nbTrucks; ++k)
            customersSequences[k] = model.List(nbCustomers);

        // All customers must be visited by exactly one truck
        model.Constraint(model.Partition(customersSequences));

        // Create LocalSolver arrays to be able to access them with an "at" operator
        LSExpression demands = model.Array(demandsData);
        LSExpression distDepot = model.Array(distDepotData);
        LSExpression distMatrix = model.Array(distMatrixData);

        for (int k = 0; k < nbTrucks; ++k)
        {
            LSExpression sequence = customersSequences[k];
            LSExpression c = model.Count(sequence);

            // A truck is used if it visits at least one customer
            trucksUsed[k] = c > 0;

            // The quantity needed in each route must not exceed the truck capacity
            LSExpression demandLambda = model.LambdaFunction(j => demands[j]);
            LSExpression routeQuantity = model.Sum(sequence, demandLambda);
            model.Constraint(routeQuantity <= truckCapacity);

            // Distance traveled by truck k
            LSExpression distLambda = model.LambdaFunction(
                i => distMatrix[sequence[i - 1], sequence[i]]
            );
            distRoutes[k] =
                model.Sum(model.Range(1, c), distLambda)
                + model.If(c > 0, distDepot[sequence[0]] + distDepot[sequence[c - 1]], 0);
        }

        nbTrucksUsed = model.Sum(trucksUsed);
        totalDistance = model.Sum(distRoutes);

        // Objective: minimize the number of trucks used, then minimize the distance traveled
        model.Minimize(nbTrucksUsed);
        model.Minimize(totalDistance);

        model.Close();

        // Parametrize the solver
        localsolver.GetParam().SetTimeLimit(limit);

        localsolver.Solve();
    }

    /* Write the solution in a file with the following format:
     *  - number of trucks used and total distance
     *  - for each truck the customers visited (omitting the start/end at the depot) */
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(nbTrucksUsed.GetValue() + " " + totalDistance.GetValue());
            for (int k = 0; k < nbTrucks; ++k)
            {
                if (trucksUsed[k].GetValue() != 1)
                    continue;
                // Values in sequence are in 0...nbCustomers. +2 is to put it back in 2...nbCustomers+2
                // as in the data files (1 being the depot)
                LSCollection customersCollection = customersSequences[k].GetCollectionValue();
                for (int i = 0; i < customersCollection.Count(); ++i)
                    output.Write((customersCollection[i] + 2) + " ");
                output.WriteLine();
            }
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Cvrp inputFile [solFile] [timeLimit] [nbTrucks]");
            Environment.Exit(1);
        }
        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "20";
        string strNbTrucks = args.Length > 3 ? args[3] : "0";

        using (Cvrp model = new Cvrp(strNbTrucks))
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }

    // The input files follow the "Augerat" format
    private void ReadInputCvrp(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            int nbNodes = 0;
            string[] splitted;
            while (true)
            {
                splitted = input.ReadLine().Split(':');
                if (splitted[0].Contains("DIMENSION"))
                {
                    nbNodes = int.Parse(splitted[1]);
                    nbCustomers = nbNodes - 1;
                }
                else if (splitted[0].Contains("CAPACITY"))
                    truckCapacity = int.Parse(splitted[1]);
                else if (splitted[0].Contains("EDGE_WEIGHT_TYPE"))
                {
                    if (!splitted[1].Trim().Equals("EUC_2D"))
                        throw new Exception(
                            "Edge Weight Type " + splitted[1] + " is not supported (only EUC_2D)"
                        );
                }
                else if (splitted[0].Contains("NODE_COORD_SECTION"))
                    break;
            }
            int[] customersX = new int[nbCustomers];
            int[] customersY = new int[nbCustomers];
            int depotX = 0,
                depotY = 0;
            for (int n = 1; n <= nbNodes; ++n)
            {
                splitted = input
                    .ReadLine()
                    .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
                if (int.Parse(splitted[0]) != n)
                    throw new Exception("Unexpected index");
                if (n == 1)
                {
                    depotX = int.Parse(splitted[1]);
                    depotY = int.Parse(splitted[2]);
                }
                else
                {
                    // -2 because original customer indices are in 2..nbNodes
                    customersX[n - 2] = int.Parse(splitted[1]);
                    customersY[n - 2] = int.Parse(splitted[2]);
                }
            }

            ComputeDistanceMatrix(depotX, depotY, customersX, customersY);

            splitted = input.ReadLine().Split(':');
            if (!splitted[0].Contains("DEMAND_SECTION"))
                throw new Exception("Expected keyword DEMAND_SECTION");

            demandsData = new long[nbCustomers];
            for (int n = 1; n <= nbNodes; ++n)
            {
                splitted = input
                    .ReadLine()
                    .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
                if (int.Parse(splitted[0]) != n)
                    throw new Exception("Unexpected index");
                var demand = int.Parse(splitted[1]);
                if (n == 1)
                {
                    if (demand != 0)
                        throw new Exception("Depot demand is supposed to be 0");
                }
                else
                {
                    // -2 because original customer indices are in 2..nbNodes
                    demandsData[n - 2] = demand;
                }
            }

            splitted = input.ReadLine().Split(':');
            if (!splitted[0].Contains("DEPOT_SECTION"))
                throw new Exception("Expected keyword DEPOT_SECTION");

            int depotId = int.Parse(input.ReadLine());
            if (depotId != 1)
                throw new Exception("Depot id is supposed to be 1");

            int endOfDepotSection = int.Parse(input.ReadLine());
            if (endOfDepotSection != -1)
                throw new Exception("Expecting only one depot, more than one found");
        }
    }

    // Compute the distance matrix
    private void ComputeDistanceMatrix(int depotX, int depotY, int[] customersX, int[] customersY)
    {
        distMatrixData = new long[nbCustomers][];
        for (int i = 0; i < nbCustomers; ++i)
            distMatrixData[i] = new long[nbCustomers];

        for (int i = 0; i < nbCustomers; ++i)
        {
            distMatrixData[i][i] = 0;
            for (int j = i + 1; j < nbCustomers; ++j)
            {
                long dist = ComputeDist(customersX[i], customersX[j], customersY[i], customersY[j]);
                distMatrixData[i][j] = dist;
                distMatrixData[j][i] = dist;
            }
        }

        distDepotData = new long[nbCustomers];
        for (int i = 0; i < nbCustomers; ++i)
            distDepotData[i] = ComputeDist(depotX, customersX[i], depotY, customersY[i]);
    }

    private long ComputeDist(int xi, int xj, int yi, int yj)
    {
        double exactDist = Math.Sqrt(Math.Pow(xi - xj, 2) + Math.Pow(yi - yj, 2));
        return Convert.ToInt64(Math.Round(exactDist));
    }

    private int GetNbTrucks(string fileName)
    {
        string[] splitted = fileName.Split(
            new[] { '-', 'k' },
            StringSplitOptions.RemoveEmptyEntries
        );
        if (splitted.Length >= 2) {
            string toSplit = splitted[splitted.Length - 1];
            splitted = toSplit.Split(new[] { '.' }, StringSplitOptions.RemoveEmptyEntries);
            return int.Parse(splitted[0]);
        }

        throw new Exception(
            "Error: nbTrucks could not be read from the file name. Enter it from the command line"
        );
    }
}
Compilation / Execution (Windows)
javac Cvrp.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Cvrp instances\A-n32-k5.vrp
Compilation / Execution (Linux)
javac Cvrp.java -cp /opt/localsolver_12_5/bin/localsolver.jar
java -cp /opt/localsolver_12_5/bin/localsolver.jar:. Cvrp instances/A-n32-k5.vrp
import java.util.*;
import java.io.*;
import localsolver.*;

public class Cvrp {
    // LocalSolver
    private final LocalSolver localsolver;

    // Number of customers
    int nbCustomers;

    // Capacity of the trucks
    private int truckCapacity;

    // Demand on each customer
    private long[] demandsData;

    // Distance matrix between customers
    private long[][] distMatrixData;

    // Distances between customers and depot
    private long[] distDepotData;

    // Number of trucks
    private int nbTrucks;

    // Decision variables
    private LSExpression[] customersSequences;

    // Are the trucks actually used
    private LSExpression[] trucksUsed;

    // Number of trucks used in the solution
    private LSExpression nbTrucksUsed;

    // Distance traveled by all the trucks
    private LSExpression totalDistance;

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

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

        trucksUsed = new LSExpression[nbTrucks];
        customersSequences = new LSExpression[nbTrucks];
        LSExpression[] distRoutes = new LSExpression[nbTrucks];

        // Sequence of customers visited by each truck.
        for (int k = 0; k < nbTrucks; ++k)
            customersSequences[k] = model.listVar(nbCustomers);

        // All customers must be visited by exactly one truck
        model.constraint(model.partition(customersSequences));

        // Create LocalSolver arrays to be able to access them with an "at" operator
        LSExpression demands = model.array(demandsData);
        LSExpression distDepot = model.array(distDepotData);
        LSExpression distMatrix = model.array(distMatrixData);

        for (int k = 0; k < nbTrucks; ++k) {
            LSExpression sequence = customersSequences[k];
            LSExpression c = model.count(sequence);

            // A truck is used if it visits at least one customer
            trucksUsed[k] = model.gt(c, 0);

            // The quantity needed in each route must not exceed the truck capacity
            LSExpression demandLambda = model.lambdaFunction(j -> model.at(demands, j));
            LSExpression routeQuantity = model.sum(sequence, demandLambda);
            model.constraint(model.leq(routeQuantity, truckCapacity));

            // Distance traveled by truck k
            LSExpression distLambda = model
                .lambdaFunction(i -> model.at(distMatrix, model.at(sequence, model.sub(i, 1)), model.at(sequence, i)));
            distRoutes[k] = model.sum(model.sum(model.range(1, c), distLambda),
                model.iif(model.gt(c, 0), model.sum(model.at(distDepot, model.at(sequence, 0)),
                    model.at(distDepot, model.at(sequence, model.sub(c, 1)))), 0));
        }

        nbTrucksUsed = model.sum(trucksUsed);
        totalDistance = model.sum(distRoutes);

        // Objective: minimize the number of trucks used, then minimize the distance traveled
        model.minimize(nbTrucksUsed);
        model.minimize(totalDistance);

        model.close();

        // Parametrize the solver
        localsolver.getParam().setTimeLimit(limit);

        localsolver.solve();
    }

    /*
     * Write the solution in a file with the following format:
     * - number of trucks used and total distance
     * - for each truck the customers visited (omitting the start/end at the depot)
     */
    private void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(fileName)) {
            output.println(nbTrucksUsed.getValue() + " " + totalDistance.getValue());
            for (int k = 0; k < nbTrucks; ++k) {
                if (trucksUsed[k].getValue() != 1)
                    continue;
                // Values in sequence are in 0...nbCustomers. +2 is to put it back in
                // 2...nbCustomers as in the data files (1 being the depot)
                LSCollection customersCollection = customersSequences[k].getCollectionValue();
                for (int i = 0; i < customersCollection.count(); ++i) {
                    output.print((customersCollection.get(i) + 2) + " ");
                }
                output.println();
            }
        }
    }

    // The input files follow the "Augerat" format
    private void readInstance(int customNbTrucks, String fileName) throws IOException {
        // The number of trucks is usually given in the name of the file
        // nbTrucks can also be given in command line
        nbTrucks = customNbTrucks <= 0 ? extractNbTrucksFromFileName(fileName) : customNbTrucks;

        if (nbTrucks <= 0) {
            throw new RuntimeException(
                    "Error: nbTrucks could not be read from the file name. Enter it from the command line");
        }

        try (Scanner input = new Scanner(new File(fileName))) {
            int nbNodes = 0;
            String[] splitted;
            while (true) {
                splitted = input.nextLine().split(":");
                if (splitted[0].contains("DIMENSION")) {
                    nbNodes = Integer.parseInt(splitted[1].trim());
                    nbCustomers = nbNodes - 1;
                } else if (splitted[0].contains("CAPACITY")) {
                    truckCapacity = Integer.parseInt(splitted[1].trim());
                } else if (splitted[0].contains("EDGE_WEIGHT_TYPE")) {
                    if (splitted[1].trim().compareTo("EUC_2D") != 0) {
                        throw new RuntimeException(
                            "Edge Weight Type " + splitted[1] + " is not supported (only EUC_2D)");
                    }
                } else if (splitted[0].contains("NODE_COORD_SECTION")) {
                    break;
                }
            }

            int[] customersX = new int[nbCustomers];
            int[] customersY = new int[nbCustomers];
            int depotX = 0, depotY = 0;
            for (int n = 1; n <= nbNodes; ++n) {
                int id = input.nextInt();
                if (id != n)
                    throw new IOException("Unexpected index");
                if (n == 1) {
                    depotX = input.nextInt();
                    depotY = input.nextInt();
                } else {
                    // -2 because original customer indices are in 2..nbNodes
                    customersX[n - 2] = input.nextInt();
                    customersY[n - 2] = input.nextInt();
                }
            }

            computeDistanceMatrix(depotX, depotY, customersX, customersY);

            input.nextLine().split(":"); // End the last line
            splitted = input.nextLine().split(":");
            if (!splitted[0].contains("DEMAND_SECTION")) {
                throw new RuntimeException("Expected keyword DEMAND_SECTION");
            }

            demandsData = new long[nbCustomers];
            for (int n = 1; n <= nbNodes; ++n) {
                int id = input.nextInt();
                if (id != n)
                    throw new IOException("Unexpected index");
                int demand = input.nextInt();
                if (n == 1) {
                    if (demand != 0)
                        throw new IOException("Depot demand is supposed to be 0");
                } else {
                    // -2 because original customer indices are in 2..nbNodes
                    demandsData[n - 2] = demand;
                }
            }

            input.nextLine().split(":"); // End the last line
            splitted = input.nextLine().split(":");
            if (!splitted[0].contains("DEPOT_SECTION")) {
                throw new RuntimeException("Expected keyword DEPOT_SECTION");
            }

            int depotId = input.nextInt();
            if (depotId != 1)
                throw new IOException("Depot id is supposed to be 1");

            int endOfDepotSection = input.nextInt();
            if (endOfDepotSection != -1) {
                throw new RuntimeException("Expecting only one depot, more than one found");
            }
        }
    }

    // Compute the distance matrix
    private void computeDistanceMatrix(int depotX, int depotY, int[] customersX, int[] customersY) {
        distMatrixData = new long[nbCustomers][nbCustomers];
        for (int i = 0; i < nbCustomers; ++i) {
            distMatrixData[i][i] = 0;
            for (int j = i + 1; j < nbCustomers; ++j) {
                long dist = computeDist(customersX[i], customersX[j], customersY[i], customersY[j]);
                distMatrixData[i][j] = dist;
                distMatrixData[j][i] = dist;
            }
        }

        distDepotData = new long[nbCustomers];
        for (int i = 0; i < nbCustomers; ++i) {
            distDepotData[i] = computeDist(depotX, customersX[i], depotY, customersY[i]);
        }
    }

    private long computeDist(int xi, int xj, int yi, int yj) {
        double exactDist = Math.sqrt(Math.pow(xi - xj, 2) + Math.pow(yi - yj, 2));
        return Math.round(exactDist);
    }

    private int extractNbTrucksFromFileName(String fileName) {
        int begin = fileName.lastIndexOf("-k");
        if (begin != -1) {
            int end = fileName.indexOf(".", begin + 2);
            return Integer.parseInt(fileName.substring(begin + 2, end));
        } else {
            return -1;
        }
    }

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

        try (LocalSolver localsolver = new LocalSolver()) {
            String instanceFile = args[0];
            String outputFile = args.length > 1 ? args[1] : null;
            String strTimeLimit = args.length > 2 ? args[2] : "20";
            String strNbTrucks = args.length > 3 ? args[3] : "0";

            Cvrp model = new Cvrp(localsolver);
            model.readInstance(Integer.parseInt(strNbTrucks), instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}