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

# Multi Trip Capacitated Vehicule 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 Vehicule 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.

## 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 LocalSolver 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;

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;

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][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;
}

else throw "Unknown file format";
}

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

// Ignore information on depot capacity on this problem

}

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], coordinatesCustomers[j], coordinatesCustomers[i], coordinatesCustomers[j]);
distanceMatrix[j][i] = localDistance;
distanceMatrix[i][j] = localDistance;
}
}

for [i in 0...nbCustomers] {
for [d in 0...nbDepots]{
local localDistance = computeDist(coordinatesDepots[d], coordinatesCustomers[i], coordinatesDepots[d], coordinatesCustomers[i]);
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_0/bin/python
python multi_trip_vrp.py instances/coordChrist100.dat
```import localsolver
import sys
import math

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

# 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) +\
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")

if filename.endswith(".dat"):
else:
raise Exception("Unknown file format")

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
output_file = sys.argv if len(sys.argv) > 2 else None
str_time_limit = sys.argv 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\localsolver120.lib
multi_trip_vrp instances\coordChrist100.dat
Compilation / Execution (Linux)
g++ multi_trip_vrp.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -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 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) {
}

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) +
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.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:

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;
const char* solFile = argc > 2 ? argv : NULL;
const char* strTimeLimit = argc > 3 ? argv : "20";

try {
MultiTripVRP model;
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();
}

{
{
nbDepotCopies = 20;
maxDist = 400;
string[] line;
nbCustomers = int.Parse(line);
int[] customersX = new int[nbCustomers];
int[] customersY = new int[nbCustomers];
demandsData = new int[nbCustomers];

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

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

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

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

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] + 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();
}
}
}
}

{
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;
string outputFile = args.Length > 1 ? args : null;
string strTimeLimit = args.Length > 2 ? args : "20";

using (MultiTripVrp model = new MultiTripVrp())
{
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_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/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;
String strOutfile = args.length > 1 ? args : null;
String strTimeLimit = args.length > 2 ? args : "20";

MultiTripVrp model = new MultiTripVrp(localsolver);