• Docs »
  • Example tour »
  • Multi Trip Capacitated Vehicle Routing Problem (MTCVRP)

Multi Trip Capacitated Vehicle Routing Problem (MTCVRP)

Principles learned

  • Use a “unassigned visits” list

  • Use a lambda expression to define a recursive array

  • Use ternary expression

Problem

In the Multi Trip Capacitated Vehicle Routing Problem, 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. Trucks can reset their stock by going through any depot. Moreover, they can only travel a limited distance. The objective is to minimize the total distance traveled by all trucks such that all the customers are served and each truck does not exceed its capacity at any point in time.

Download the example


Data

The instance used in this example comes from the S. Barreto instances. This instance is originally for the LRP, but has been adapted to this problem.

The format of the data files is as follows:

  • The number of customers

  • The number of depots

  • The x and y coordinates of the depots and the customers

  • The capacity of the delivery vehicles

  • The capacity of each depot (ignored here)

  • The demand for every customer

  • The opening cost of each depot (ignored here)

  • The opening cost of a route (ignored here)

  • The areCostDouble boolean value indicating if costs should be rounded (ignored here)

In addition to that, the capacity has been divided by 2 and the number of trucks and their maximal travel distance have been set manually for this example.

Program

The principal difficulty in this Localsolver model is to allow a depot to be visited multiple times. To do so, we introduce a constant nbDepotCopies which represents the maximal number of time a depot can be visited. Here it is set to 20. Locations are ordered in the following way:

  • Customers locations correspond to the indices 0 to nbCustomers-1

  • The depot d and its copies correspond to the indices nbCustomers + d*nbDepotCopies to nbCustomers + (d+1)*nbDepotCopies-1

This Hexaly model defines a sequence for nbTrucks+1 list variable (visitOrder[k]). The first nbTrucks lists correspond to the sequences of locations visited by each truck (customers, depots or depots copies). The last list is the “unassigned visits list”, every non-visited depot (or depot copy) will end up in this one. It allows depots to be visited less than exactly nbDepotCopies times. To ensure that the “unassigned visits list” contains no customer location, we add a constraint by using the “contains” operator. To ensure that every customer is served, all the list are constrained to form a partition by using the “partition” operator.

The quantities carried by a truck after each stop is either 0 if it is a Depot, or the sum of the quantity it had the stop before and the customer demand if it is a customer. Such a recursive definition is introduced with the function (i, prev) =>. It allows computing the ith element of an array given i and the (i-1)th element of the array. See the documentation on this topic for details.

We define the distance traveled by each truck and the total distance traveled as in the CVRP model. We just add a simple constraint on the distance traveled by each truck wich should not exceed the limit maxDist.

Execution:
localsolver multi_trip_vrp.lsp inFileName=instances/coordChrist100.dat [lsTimeLimit=] [solFileName=]
use io;

/* Read instance data */
function input() {

    local usage = "Usage : localsolver location_routing_problem.lsp "
            + "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]";
    if (inFileName == nil) throw usage;

    if (lsTimeLimit == nil) lsTimeLimit=20;

    nbDepotCopies = 20;

    readInputMultiTripVrp();
    
    nbTotalLocations = nbCustomers + nbDepots*nbDepotCopies;
    
    computeDistances();

    maxDist = 400;

    truckCapacity = truckCapacity/2;

    nbTrucks = 3;

}

function model(){

    // add an extra fictive truck
    visitOrder[0...nbTrucks+1] <- list(nbTotalLocations);

    // Constraint on the fictive truck (can only "visit" depots)
    for[i in 0...nbCustomers] constraint !contains(visitOrder[nbTrucks],i);

    // All clients are visited
    constraint partition(visitOrder);

    // Capacity constraints
    for[k in 0...nbTrucks]{
        local sequence <- visitOrder[k];
        local c <- count(sequence);

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

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

        // The quantity needed in each route must not exceed the truck capacity
        // at any point in the sequence
        routeQuantity[k] <- array( 
            0...c, 
            (i,prev) => (sequence[i] < nbCustomers) ? prev+demands[sequence[i]]:0,
            0);
        constraint and(0...c, i => routeQuantity[k][i]<=truckCapacity);

        constraint routeDistances[k] <= maxDist;
    }

    totalDistance <- sum[k in 0...nbTrucks](routeDistances[k]);

    minimize totalDistance;
}

function readInputMultiTripVrp() {
    if (inFileName.endsWith(".dat")) readInputDat();
    else throw "Unknown file format";
}

function readInputDat() {
    local inFile = io.openRead(inFileName);

    nbCustomers = inFile.readInt();
    nbDepots = inFile.readInt();

    coordinatesDepots[d in 0...nbDepots][l in 0...2] = inFile.readDouble();
    coordinatesCustomers[c in 0...nbCustomers][l in 0...2] = inFile.readDouble();

    truckCapacity = inFile.readInt();

    // Ignore information on depot capacity on this problem
    depotsCapacity[d in 0...nbDepots] = inFile.readInt(); 

    demands[c in 0...nbCustomers] = inFile.readInt();
}

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

function computeDistances() {
    for [i in 0...nbCustomers] {
        distanceMatrix[i][i] = 0;
        for [j in i+1...nbCustomers] {
            local localDistance = computeDist(coordinatesCustomers[i][0], coordinatesCustomers[j][0], coordinatesCustomers[i][1], coordinatesCustomers[j][1]);
            distanceMatrix[j][i] = localDistance;
            distanceMatrix[i][j] = localDistance;
        }
    }

    for [i in 0...nbCustomers] {
        for [d in 0...nbDepots]{
            local localDistance = computeDist(coordinatesDepots[d][0], coordinatesCustomers[i][0], coordinatesDepots[d][1], coordinatesCustomers[i][1]);
            for [c in 0...nbDepotCopies] {
                j = nbCustomers + d*nbDepotCopies + c;
                distanceMatrix[i][j] = localDistance;
                distanceMatrix[j][i] = localDistance;
            }
        }
    }

    for [i in nbCustomers...nbTotalLocations] {
        for [j in nbCustomers...nbTotalLocations] {
            distanceMatrix[i][j] = 100000;
        }
    }
}

function output() {
    if (solFileName == nil) return;
    local outfile = io.openWrite(solFileName);
    outfile.println("File name: " + inFileName +"; totalDistance = " + totalDistance.value);
    for [k in 0...nbTrucks] {
        if(truckUsed[k].value){
            outfile.print("Truck " + k + " : ");
            for [customer in visitOrder[k].value]{
                outfile.print(customer<nbCustomers ? customer:-(floor((customer-nbCustomers)/nbDepotCopies) + 1), " ");
            }
            outfile.println();
        }
    }
}
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python multi_trip_vrp.py instances\coordChrist100.dat
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_5/bin/python
python multi_trip_vrp.py instances/coordChrist100.dat
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):
    nb_customers, nb_trucks, truck_capacity, dist_matrix_data, nb_depots, \
    nb_depot_copies, nb_total_locations, demands_data, max_dist = read_input_multi_trip_vrp(instance_file)
    
    with localsolver.LocalSolver() as ls:

        #
        # Declare the optimization model
        #
        model = ls.model

        # Locations visited by each truck (customer or depot)
        # Add copies of the depots (so that they can be visited multiple times)
        # Add an extra fictive truck (who will visit every depot that will not be visited by real trucks)
        visit_orders = [model.list(nb_total_locations) for k in range(nb_trucks+1)]

        # The fictive truck cannot visit customers
        for i in range(nb_customers):
            model.constraint((model.contains(visit_orders[nb_trucks],i)) == False)

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

        # 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_total_locations):
            dist_matrix.add_operand(model.array(dist_matrix_data[n]))
        
         # A truck is used if it visits at least one customer
        trucks_used = [(model.count(visit_orders[k]) > 0) for k in range(nb_trucks)]

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

            # Compute the quantity in the truck at each step
            route_quantity_lambda = model.lambda_function(lambda i,prev: \
                model.iif(sequence[i] < nb_customers, prev+demands[sequence[i]],0))
            route_quantity = model.array(model.range(0, c), route_quantity_lambda, 0)

            # Trucks cannot carry more than their capacity
            quantity_lambda = model.lambda_function(
                lambda i: route_quantity[i] <= truck_capacity)
            model.constraint(model.and_(model.range(0, c), quantity_lambda))

            # 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,
                            model.at(dist_matrix,nb_customers,sequence[0]) +\
                            model.at(dist_matrix,sequence[c-1],nb_customers),\
                            0)
            
            # Limit distance traveled
            model.constraint( dist_routes[k] <= max_dist)

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

        # Objective: minimize the distance traveled
        model.minimize(total_distance)

        model.close()

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

        ls.solve()

        # Write solution output
        if output_file != None:
            with open(output_file, 'w') as file:
                file.write("File name: %s; totalDistance = %d \n" % (instance_file,total_distance.value))
                for k in range(nb_trucks):
                    if trucks_used[k].value:
                        file.write("Truck %d : " % (k))
                        for customer in visit_orders[k].value:
                            file.write( "%d" % (customer) if customer<nb_customers else "%d" % (-(math.floor((customer-nb_customers)/nb_depot_copies) + 1)))
                            file.write(" ")
                        file.write("\n")


def read_input_multi_trip_vrp(filename):
    if filename.endswith(".dat"):
        return read_input_multi_trip_vrp_dat(filename)
    else:
        raise Exception("Unknown file format")

def read_input_multi_trip_vrp_dat(filename):
    file_it = iter(read_elem(filename))

    nb_customers = int(next(file_it))
    nb_depots = int(next(file_it))

    depots_x = [None] * nb_depots
    depots_y = [None] * nb_depots
    for i in range(nb_depots):
        depots_x[i] = int(next(file_it))
        depots_y[i] = int(next(file_it))

    customers_x = [None] * nb_customers
    customers_y = [None] * nb_customers
    for i in range(nb_customers):
        customers_x[i] = int(next(file_it))
        customers_y[i] = int(next(file_it))

    truck_capacity = int(next(file_it))//2

    # Skip depots capacity infos (not related to the problem)
    for i in range(nb_depots):
        next(file_it)

    demands_data = [None] * nb_customers
    for i in range(nb_customers):
        demands_data[i] = int(next(file_it))

    nb_depot_copies = 20

    nb_total_locations  = nb_customers + nb_depots*nb_depot_copies

    max_dist = 400

    nb_trucks = 3

    dist_matrix_data = compute_distance_matrix(depots_x, depots_y, customers_x, customers_y, nb_depot_copies)

    return  nb_customers, nb_trucks, truck_capacity, dist_matrix_data, nb_depots, \
        nb_depot_copies, nb_total_locations, demands_data, max_dist


# Compute the distance matrix
def compute_distance_matrix(depots_x, depots_y, customers_x, customers_y, nb_depot_copies):
    nb_customers = len(customers_x)
    nb_depots = len(depots_x)
    nb_total_locations = nb_customers + nb_depots*nb_depot_copies
    dist_matrix = [[0 for _ in range(nb_total_locations)] for _ in range(nb_total_locations)]
    for i in range(nb_customers):
        dist_matrix[i][i] = 0
        for j in range(i,nb_customers):
            dist = compute_dist(customers_x[i], customers_x[j], customers_y[i], customers_y[j])
            dist_matrix[i][j] = dist
            dist_matrix[j][i] = dist
        for d in range(nb_depots):
            dist = compute_dist(customers_x[i], depots_x[d], customers_y[i], depots_y[d])
            for c in range(nb_depot_copies):
                j = nb_customers+d*nb_depot_copies + c
                dist_matrix[i][j] = dist
                dist_matrix[j][i] = dist
    
    for i in range(nb_customers, nb_total_locations):
        for j in range(nb_customers, nb_total_locations):
            # Going from one depot to an other is never worth it
            dist_matrix[i][j] = 100000

    return dist_matrix


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))


if __name__ == '__main__':
    if len(sys.argv) < 2:
        print("Usage: python cvrp.py input_file [output_file] [time_limit]")
        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"

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

using namespace localsolver;
using namespace std;

class MultiTripVRP {
public:
    // LocalSolver
    LocalSolver localsolver;

    // Number of customers
    int nbCustomers;

    // Number of depots
    int nbDepots;

    // Number of depot copies
    int nbDepotCopies;

    // Total number of locations (customers, depots, depots copies)
    int nbTotalLocations;

    // Capacity of the trucks
    int truckCapacity;

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

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

    // Number of trucks
    int nbTrucks;

    // Maximum distance traveled by a truck
    int maxDist;

    // Decision variables
    vector<LSExpression> visitOrders;

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

    // Distance traveled by all the trucks
    LSExpression totalDistance;

    void readInstance(const char* fileName) { readInputMultiTripVRP(fileName); }

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

        // Locations visited by each truck (Customers and Depots)
        // Add copies of the depots (so that they can be visited multiple times)
        // Add an extra fictive truck (who will visit every depot that will not be visited by real trucks)
        visitOrders.resize(nbTrucks + 1);
        for (int k = 0; k < nbTrucks + 1; ++k) {
            visitOrders[k] = model.listVar(nbTotalLocations);
        }

        // The fictive truck cannot visit customers
        for(int i=0; i < nbCustomers; i++){
            model.constraint(!(model.contains(visitOrders[nbTrucks],i)));
        }

        // All customers must be visited by exactly one truck
        model.constraint(model.partition(visitOrders.begin(), visitOrders.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 + nbDepots * nbDepotCopies; ++n) {
            distMatrix.addOperand(model.array(distMatrixData[n].begin(), distMatrixData[n].end()));
        }

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

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

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

            // Compute the quantity in the truck at each step
            LSExpression routeQuantityLambda =
                model.createLambdaFunction([&](LSExpression i, LSExpression prev) { return model.iif(sequence[i] < nbCustomers, prev+demands[sequence[i]],0); });
            LSExpression routeQuantity = model.array(model.range(0, c), routeQuantityLambda, 0);
            // Trucks cannot carry more than their capacity
            LSExpression quantityLambda = model.createLambdaFunction([&](LSExpression i){ return routeQuantity[i]<=truckCapacity; });
            model.constraint(model.and_(model.range(0,c), quantityLambda));

            // 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,
                                model.at(distMatrix,nbCustomers,sequence[0]) +
                                model.at(distMatrix,sequence[c-1],nbCustomers),
                                0);
            
            // Limit distance traveled
            model.constraint(distRoutes[k] <= maxDist);
        }

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

        // Objective: minimize the distance traveled
        model.minimize(totalDistance);

        model.close();

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

        localsolver.solve();
    }

    /* Write the solution in a file */
    void writeSolution(const char* inFile, const string& solFile) {
        ofstream file;
        file.exceptions(ofstream::failbit | ofstream::badbit);
        file.open(solFile.c_str());
        file << "File name: " << inFile << "; total distance = " << totalDistance.getValue() << endl;
        for (int r = 0; r < nbTrucks; ++r) {
            if (trucksUsed[r].getValue()) {
                LSCollection visitCollection = visitOrders[r].getCollectionValue();
                    file << "Truck " << r << " : " ;
                for (lsint i = 0; i < visitCollection.count(); ++i) {
                    file << (visitCollection[i]<nbCustomers ? visitCollection[i] : -(floor((visitCollection[i]-nbCustomers)/nbDepotCopies) + 1)) << " ";
                }
                file << endl;
            }
        }
    }

private:

    void readInputMultiTripVRP(const char* fileName) {
        vector<int> customersX, customersY, depotsX, depotsY;
        string file = fileName;
        ifstream infile(file.c_str());
        if (!infile.is_open()) {
            throw std::runtime_error("File cannot be opened.");
        }
        infile >> nbCustomers;
        customersX.resize(nbCustomers);
        customersY.resize(nbCustomers);
        demandsData.resize(nbCustomers);
        distMatrixData.resize(nbTotalLocations);
        infile >> nbDepots;
        depotsX.resize(nbDepots);
        depotsY.resize(nbDepots);
        for (int i = 0; i < nbDepots; ++i) {
            infile >> depotsX[i];
            infile >> depotsY[i];
        }
        for (int i = 0; i < nbCustomers; ++i) {
            infile >> customersX[i];
            infile >> customersY[i];
        }
        infile >> truckCapacity;
        truckCapacity /= 2;
        // Ignore depot infos
        int temp;
        for (int i = 0; i < nbDepots; ++i) {
            infile>>temp;
        }
        for (int i = 0; i < nbCustomers; ++i) {
            infile >> demandsData[i];
        }

        nbDepotCopies = 20;

        nbTotalLocations = nbCustomers + nbDepots*nbDepotCopies;

        maxDist = 400;
            
        nbTrucks = 3;

        computeDistanceMatrix(depotsX, depotsY, customersX, customersY);
    }

    // Compute the distance matrix
    void computeDistanceMatrix(const vector<int>& depotsX, const vector<int>& depotsY, const vector<int>& customersX, const vector<int>& customersY) {
        distMatrixData.resize(nbTotalLocations);
        for (int i = 0; i < nbTotalLocations; ++i) {
            distMatrixData[i].resize(nbTotalLocations);
        }
        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;
            }

            for (int d=0; d<nbDepots; ++d){
                int distance = computeDist(customersX[i], depotsX[d], customersY[i], depotsY[d]);
                for (int c=0; c<nbDepotCopies; ++c){
                    int j = nbCustomers + d*nbDepotCopies + c;
                    distMatrixData[i][j] = distance;
                    distMatrixData[j][i] = distance;
                }
            }
        }

        for(int i=nbCustomers; i<nbTotalLocations; i++){
            for(int j=nbCustomers; j<nbTotalLocations;j++){
                // Going from one depot to an other is never worth it
                distMatrixData[i][j] = 100000;
            }
        }
    }

    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 main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: ./lrp inputFile [outputFile] [timeLimit]" << endl;
        return 1;
    }
    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "20";

    try {
        MultiTripVRP model;
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
        if (solFile != NULL)
            model.writeSolution(instanceFile, solFile);
    } catch (const std::exception& e) {
        std::cerr << "An error occured: " << e.what() << endl;
    }

    return 0;
}
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc MultiTripVrp.cs /reference:localsolvernet.dll
MultiTripVrp instances\coordChrist100.dat
using System;
using System.IO;
using localsolver;

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

    // Number of customers
    int nbCustomers;

    // Number of depots
    int nbDepots;

    // Number of depot copies
    int nbDepotCopies;

    // Total number of locations (customers, depots, depots copies)
    int nbTotalLocations;

    // Capacity of the trucks
    int truckCapacity;

    // Demand on each customer
    int[] demandsData;

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

    // Number of trucks
    int nbTrucks;

    // Maximum distance traveled by a truck
    int maxDist;

    // Decision variables
    LSExpression[] visitOrders;

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

    // Distance traveled by all the trucks
    LSExpression totalDistance;

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

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

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            nbDepotCopies = 20;
            maxDist = 400;
            string[] line;
            line = ReadNextLine(input);
            nbCustomers = int.Parse(line[0]);
            int[] customersX = new int[nbCustomers];
            int[] customersY = new int[nbCustomers];
            demandsData = new int[nbCustomers];

            line = ReadNextLine(input);
            nbDepots = int.Parse(line[0]);
            int[] depotsX = new int[nbDepots];
            int[] depotsY = new int[nbDepots];

            line = ReadNextLine(input);
            for (int i = 0; i < nbDepots; ++i)
            {
                line = ReadNextLine(input);
                depotsX[i] = int.Parse(line[0]);
                depotsY[i] = int.Parse(line[1]);
            }
            line = ReadNextLine(input);

            for (int i = 0; i < nbCustomers; ++i)
            {
                line = ReadNextLine(input);
                customersX[i] = int.Parse(line[0]);
                customersY[i] = int.Parse(line[1]);
            }
            line = ReadNextLine(input);
            line = ReadNextLine(input);
            truckCapacity = int.Parse(line[0]) / 2;
            line = ReadNextLine(input);

            // Ignore depot infos
            for (int i = 0; i < nbDepots; ++i)
            {
                ReadNextLine(input);
            }
            line = ReadNextLine(input);
            for (int i = 0; i < nbCustomers; ++i)
            {
                line = ReadNextLine(input);
                demandsData[i] = int.Parse(line[0]);
            }
            line = ReadNextLine(input);

            nbTotalLocations = nbCustomers + nbDepots * nbDepotCopies;

            nbTrucks = 3;

            ComputeDistanceMatrix(depotsX, depotsY, customersX, customersY);
        }
    }

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

        trucksUsed = new LSExpression[nbTrucks];
        visitOrders = new LSExpression[nbTrucks + 1];
        LSExpression[] distRoutes = new LSExpression[nbTrucks];

        // Locations visited by each truck (Customers and Depots)
        // Add copies of the depots (so that they can be visited multiple times)
        // Add an extra fictive truck (who will visit every depot that will not be visited by real trucks)
        for (int k = 0; k < nbTrucks + 1; ++k)
            visitOrders[k] = model.List(nbTotalLocations);

        // The fictive truck cannot visit customers
        for (int i = 0; i < nbCustomers; i++)
            model.Constraint(!(model.Contains(visitOrders[nbTrucks], i)));

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

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

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

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

            // Compute the quantity in the truck at each step
            LSExpression routeQuantityLambda = model.LambdaFunction((i, prev) =>
                model.If(sequence[i] < nbCustomers, prev + demands[sequence[i]], 0));
            LSExpression routeQuantity = model.Array(model.Range(0, c), routeQuantityLambda, 0);
            // Trucks cannot carry more than their capacity
            LSExpression quantityLambda = model.LambdaFunction(i => routeQuantity[i] <= truckCapacity);
            model.Constraint(model.And(model.Range(0, c), quantityLambda));

            // 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, distMatrix[nbCustomers, sequence[0]] + distMatrix[sequence[c - 1], nbCustomers], 0);

            model.Constraint(distRoutes[k] <= maxDist);
        }

        // Total distance traveled
        totalDistance = model.Sum(distRoutes);

        // Objective: minimize the distance traveled
        model.Minimize(totalDistance);

        model.Close();

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

        localsolver.Solve();
    }

    /* Write the solution in a file */
    void WriteSolution(string infile, string outfile)
    {
        using (StreamWriter output = new StreamWriter(outfile))
        {
            output.WriteLine(
                "File name: " + infile + "; total distance = " + totalDistance.GetValue()
            );
            for (int r = 0; r < nbTrucks; ++r)
            {
                if (trucksUsed[r].GetValue() == 1)
                {
                    output.Write(
                        "Truck " + r + ": "
                    );
                    LSCollection visitCollection = visitOrders[r].GetCollectionValue();
                    for (int i = 0; i < visitCollection.Count(); ++i)
                        output.Write(
                            (visitCollection[i] < nbCustomers ? visitCollection[i] : -(Math.Floor(Convert.ToDouble((visitCollection[i] - nbCustomers) / nbDepotCopies) + 1)))
                            + " ");
                    output.WriteLine();
                }
            }
        }
    }

    String[] ReadNextLine(StreamReader input)
    {
        return input.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
    }


    private int 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.ToInt32(Math.Round(exactDist));
    }

    // Compute the distance matrix
    private void ComputeDistanceMatrix(int[] depotsX, int[] depotsY, int[] customersX, int[] customersY)
    {
        distMatrixData = new int[nbTotalLocations][];
        for (int i = 0; i < nbCustomers + nbDepots * nbDepotCopies; ++i)
            distMatrixData[i] = new int[nbTotalLocations];
        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;
            }

            for (int d = 0; d < nbDepots; d++)
            {
                int distance = computeDist(customersX[i], depotsX[d], customersY[i], depotsY[d]);
                for (int c = 0; c < nbDepotCopies; c++)
                {
                    int j = nbCustomers + d * nbDepotCopies + c;
                    distMatrixData[i][j] = distance;
                    distMatrixData[j][i] = distance;
                }
            }
        }

        for (int i = nbCustomers; i < nbTotalLocations; i++)
        {
            // Going from one depot to an other is never worth it
            for (int j = nbCustomers; j < nbTotalLocations; j++)
                distMatrixData[i][j] = 100000;
        }
    }

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

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

};
Compilation / Execution (Windows)
javac MultiTripVrp.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. MultiTripVrp instances\coordChrist100.dat
Compilation / Execution (Linux)
javac MultiTripVrp.java -cp /opt/localsolver_12_5/bin/localsolver.jar
java -cp /opt/localsolver_12_5/bin/localsolver.jar:. MultiTripVrp instances/coordChrist100.dat
import java.util.*;
import java.io.*;
import localsolver.*;
import java.lang.Math;

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

    // Number of customers
    private int nbCustomers;

    // Number of depots
    private int nbDepots;

    // Number of depot copies
    private int nbDepotCopies;

    // Total number of locations (customers, depots, depots copies)
    private int nbTotalLocations;

    // Capacity of the trucks
    private int truckCapacity;

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

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

    // Number of trucks
    private int nbTrucks;

    // Maximum distance traveled by a truck
    private int maxDist;

    // Decision variables
    private LSExpression[] visitOrders;

    // 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 MultiTripVrp(LocalSolver localsolver) {
        this.localsolver = localsolver;
    }

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

        trucksUsed = new LSExpression[nbTrucks];
        visitOrders = new LSExpression[nbTrucks + 1];
        LSExpression[] distRoutes = new LSExpression[nbTrucks];

        // Locations visited by each truck (Customers and Depots)
        // Add copies of the depots (so that they can be visited multiple times)
        // Add an extra fictive truck (who will visit every depot/ depot copy that will
        // not be visited by real trucks)
        for (int k = 0; k < nbTrucks + 1; ++k)
            visitOrders[k] = m.listVar(nbTotalLocations);

        // The fictive truck cannot visit customers
        for (int k = 0; k < nbCustomers; ++k)
            m.constraint(m.not((m.contains(visitOrders[nbTrucks], k))));

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

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

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

            // A truck is used if it visits at least one customer
            trucksUsed[k] = m.gt(c, 0);
            // The quantity needed in each route must not exceed the truck capacity
            LSExpression routeQuantityLambda = m.lambdaFunction((i, prev) -> m
                    .iif(m.leq(m.at(sequence, i), nbCustomers - 1), m.sum(prev, m.at(demands, m.at(sequence, i))), 0));
            LSExpression routeQuantity = m.array(m.range(0, c), routeQuantityLambda, 0);
            // Trucks cannot carry more than their capacity
            LSExpression quantityLambda = m.lambdaFunction(i -> m.leq(m.at(routeQuantity, i), truckCapacity));
            m.constraint(m.and(m.range(0, c), quantityLambda));

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

            m.constraint(m.leq(distRoutes[k], maxDist));
        }

        totalDistance = m.sum(distRoutes);

        // Objective: minimize the distance traveled
        m.minimize(totalDistance);

        m.close();

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

        localsolver.solve();
    }

    /* Write the solution in a file */
    private void writeSolution(String infile, String outfile) throws IOException {
        try (PrintWriter output = new PrintWriter(outfile)) {
            output.println("File name: " + infile + "; total distance = " + totalDistance.getValue());
            for (int r = 0; r < nbTrucks; ++r) {
                if (trucksUsed[r].getValue() != 0) {
                    output.print("Truck " + r + " : ");
                    LSCollection visitCollection = visitOrders[r].getCollectionValue();
                    for (int i = 0; i < visitCollection.count(); ++i) {
                        output.print(
                                (visitCollection.get(i) < nbCustomers ? visitCollection.get(i)
                                        : -((int) (Math.floor((visitCollection.get(i) - nbCustomers) / nbDepotCopies)
                                                + 1)))
                                        + " ");
                    }
                    output.println();
                }
            }
        } catch (FileNotFoundException e) {
            System.out.println("An error occurred.");
            e.printStackTrace();
        }
    }

    private void readInstanceMultiTripVrp(String fileName) throws IOException {
        try (Scanner infile = new Scanner(new File(fileName))) {
            nbDepotCopies = 20;
            nbCustomers = infile.nextInt();
            long[] customersX = new long[nbCustomers];
            long[] customersY = new long[nbCustomers];
            demandsData = new long[nbCustomers];
            nbDepots = infile.nextInt();
            long[] depotsX = new long[nbDepots];
            long[] depotsY = new long[nbDepots];

            for (int i = 0; i < nbDepots; ++i) {
                depotsX[i] = infile.nextInt();
                depotsY[i] = infile.nextInt();
            }
            for (int i = 0; i < nbCustomers; ++i) {
                customersX[i] = infile.nextInt();
                customersY[i] = infile.nextInt();
            }
            truckCapacity = infile.nextInt() / 2;
            for (int i = 0; i < nbDepots; ++i) {
                infile.next();
            }
            for (int i = 0; i < nbCustomers; ++i) {
                demandsData[i] = infile.nextInt();
            }

            nbTotalLocations = nbCustomers + nbDepots * nbDepotCopies;

            nbTrucks = 3;

            maxDist = 400;

            computeDistanceMatrix(depotsX, depotsY, customersX, customersY);

        } catch (FileNotFoundException e) {
            System.out.println("An error occurred.");
            e.printStackTrace();
        }
    }

    // Compute the distance matrix
    private void computeDistanceMatrix(long[] depotsX, long[] depotsY, long[] customersX, long[] customersY) {
        distMatrixData = new long[nbTotalLocations][nbTotalLocations];

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

            for (int d = 0; d < nbDepots; d++) {
                long distance = computeDist(customersX[i], depotsX[d], customersY[i], depotsY[d]);
                for (int c = 0; c < nbDepotCopies; c++) {
                    int j = nbCustomers + d * nbDepotCopies + c;
                    distMatrixData[i][j] = distance;
                    distMatrixData[j][i] = distance;
                }
            }
        }

        for (int i = nbCustomers; i < nbTotalLocations; i++) {
            for (int j = nbCustomers; j < nbTotalLocations; j++) {
                // Going from one depot to an other is never worth it
                distMatrixData[i][j] = 100000;
            }
        }
    }

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

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

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

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