# Clustered Vehicle Routing (cluVRP)¶

## Principles learned¶

• Add multiple list decision variables

• 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

## Problem¶

In the clustered vehicle routing problem (cluVRP), a fleet of delivery vehicles with uniform capacity must service clusters of customers with known demand for a single cluster. Clusters are composed of customers close to each other, and are known. All customers must be visited exactly once. The vehicles start and end their routes at a common depot. Each cluster, and therefore each customer can only be served by one vehicle, and a vehicle visiting one customer in a cluster must visit all the remaining customers therein before leaving it. The objective is to assign a sequence of clusters 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.

## Data¶

The instances provided come from the paper Exact Algorithms for the Clustered Vehicle Routing Problem. 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 number of trucks follows the keyword `VEHICLES`.

• The number of clusters follows the keyword `GVRP_CAPACITY`.

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

• After the keyword `GVRP_SET_SECTION`, for each cluster is listed its id and the nodes that are part of it (ending with value -1).

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

## Program¶

This LocalSolver model defines a route for each truck k as a list variable (`customersSequences[k]`). It corresponds to the sequence of clusters visited. To ensure that all clusters must be served, all the list variables are constrained to form a partition, thanks to the “partition” operator. A second set of lists (`clustersSequences[k]`) is needed to define the sequence within the clusters. Each of these lists is constrained to the size of its corresponding cluster

The quantity delivered on each cluster is the demand on this cluster. 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 clusters 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 cluster, 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. Two arrays (known as `initialNodes` and `endNodes`) are filled respectively with the first node and the last node visited in each clusters.

For each truck, the distance traveled from the cluster k-1 to the cluster k is accessed with an “at” operator to the multi-dimensional array `distanceMatrix`, with index `endNodes[k-1]` and `initialNodes[k]`. Here again we use a function to sum distances along each route. Total distance traveled by a truck is obtained by summing the distance traveled within each cluster, the distance between consecutive clusters in the sequence, and the distance to the depot of the first and last node of the route.

The objective is as follow : minimize the total distance traveled by all the trucks.

If you are interested in the classical variant without cluster, you can now study our CVRP model.

Execution:
localsolver clustered-vehicle-routing.lsp inFileName=instances/A-n32-k5-C11-V2.gvrp [lsTimeLimit=] [solFileName=]
```use io;

function input(){
local usage = "Usage: localsolver clustered-vehicle-routing.lsp "
+ "inFileName=inputFile [lsTimeLimit=timeLimit]";

if (inFileName == nil) throw usage;

computeDistanceMatrix();
computeDistanceCustomerDepot();
}

/* Declare the optimization model */
function model() {
// Sequences of clusters visited by each truck
truckSequences[k in 0...nbTrucks] <- list(nbClusters);

// A list is created for each cluster, to determine the order within the cluster
for[k in 0...nbClusters] {
// All customers in the cluster must be visited
}

// All clusters must be visited by the trucks
constraint partition[k in 0...nbTrucks](truckSequences[k]);

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

// Distance traveled within cluster k
clustersDistances[k] <- sum(1...c, i=>
distanceMatrix[clusters[k][sequence[i-1]]][clusters[k][sequence[i]]]
);

// first and last point visited when travelling into cluster k
initialNodes[k] <- clusters[k][sequence];
endNodes[k] <- clusters[k][sequence[c-1]];
}

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

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

// Distance traveled by truck k
// = distance in each cluster + distance between cluster + distance with depot at
// the beginning end at the end of a route
routeDistances[k] <- sum(1...c, i => clustersDistances[sequence[i]]
+ distanceMatrix[endNodes[sequence[i - 1]]][initialNodes[sequence[i]]] )
+ (c > 0 ? clustersDistances[sequence]
+ distanceDepot[initialNodes[sequence]]
+ distanceDepot[endNodes[sequence[c-1]]] : 0) ;

}
// Objective:  minimize the distance traveled
totalDistance <- sum[k in 0...nbTrucks](routeDistances[k]);
minimize totalDistance;
}

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

/* Write the solution in a file with the following format:
* - 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(totalDistance.value);
for [k in 0...nbTrucks] {
for [cluster in truckSequences[k].value]{
outfile.print(clusters[cluster][customer] + 2, " ");
}
outfile.println();
}
outfile.close();
}

local nbNodes = 0;
while (true) {
if (str.startsWith("DIMENSION")) {
nbCustomers = nbNodes - 1;
} else if ((str.startsWith("VEHICLES"))) {
} else if ((str.startsWith("GVRP_SETS"))) {
} else if ((str.startsWith("CAPACITY"))) {
} else if (str.startsWith("NODE_COORD_SECTION")) {
break;
} else {
}
}
for [n in 1..nbNodes] {
if (n != inFile.readInt()) throw "Unexpected index";
if(n==1){
}else{
// -2 because original customer indices are in 2..nbNodes
}
}

if (!dump.startsWith("GVRP_SET_SECTION")) throw "Expected keyword GVRP_SET_SECTION";
for [n in 1..nbClusters] {
if (n != inFile.readInt()) throw "Unexpected index";
i = 0;
while(value != -1){
// -2 because original customer indices are in 2..nbNodes
clusters[n-1][i] = value - 2;
i += 1;
}
}

if (!dump.startsWith("DEMAND_SECTION")) throw "Expected keyword DEMAND_SECTION";
for [n in 1..nbClusters] {
if (n != inFile.readInt()) throw "Unexpected index";
}
}

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

/* Compute the distance between customers and depot */
function computeDistanceCustomerDepot() {
for [i in 0...nbCustomers] {
distanceDepot[i] =  round(sqrt(pow((depotX - customersX[i]), 2)
+ pow((depotY - customersY[i]), 2)));
}
}

function computeDist(i, j) {
local exactDist = sqrt(pow((customersX[i] - customersX[j]), 2)
+ pow((customersY[i] - customersY[j]), 2));
return round(exactDist);
}
```
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python clustered-vehicle-routing.py instances\A-n32-k5-C11-V2.gvrp
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_0/bin/python
python clustered-vehicle-routing.py instances/A-n32-k5-C11-V2.gvrp
```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, nb_clusters, truck_capacity, dist_matrix_data, dist_depot_data, \

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

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

# A list is created for each cluster, to determine the order within the cluster
clusters_sequences = []
for k in range(nb_clusters):
clusters_sequences.append(model.list(len(clusters_data[k])))
# All customers in the cluster must be visited
model.constraint(model.count(clusters_sequences[k]) == len(clusters_data[k]))

clustersDistances = model.array()
initialNodes = model.array()
endNodes = model.array()
for k in range(nb_clusters):
sequence = clusters_sequences[k]
c = model.count(sequence)
# Distance traveled within cluster k
clustersDistances_lambda = model.lambda_function(lambda i:
model.at(dist_matrix, clusters[k][sequence[i - 1]],
clusters[k][sequence[i]]))
clustersDistances_lambda))

# First and last point when visiting cluster k

# Sequences of clusters visited by each truck
truckSequences = [model.list(nb_clusters) for _ in range(nb_trucks)]

# Each cluster must be visited by exactly one truck
model.constraint(model.partition(truckSequences))

routeDistances = [None] * nb_trucks
for k in range(nb_trucks):
sequence = truckSequences[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
# = distance in each cluster + distance between clusters + distance with depot at
# the beginning end at the end of a route
routeDistances_lambda = model.lambda_function(lambda i:
model.at(clustersDistances, sequence[i]) + model.at(dist_matrix,
endNodes[sequence[i - 1]], initialNodes[sequence[i]]))
routeDistances[k] = model.sum(model.range(1, c), routeDistances_lambda) \
+ model.iif(c > 0, model.at(clustersDistances, sequence)
+ dist_depot[initialNodes[sequence]]
+ dist_depot[endNodes[sequence[c - 1]]], 0)

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

# 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 the solution in a file with the following format:
# - 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\n" % (total_distance.value))
for k in range(nb_trucks):
# Values in sequence are in [0..nbCustomers - 1]. +2 is to put it back
# in [2..nbCustomers+1] as in the data files (1 being the depot)
for cluster in truckSequences[k].value:
for customer in clusters_sequences[cluster].value:
f.write("%d " % (clusters_data[cluster][customer] + 2))
f.write("\n")

# The input files follow the "Augerat" format

nb_nodes = 0
while True:
token = next(file_it)
if token == "DIMENSION:":
nb_nodes = int(next(file_it))
nb_customers = nb_nodes - 1
if token == "VEHICLES:":
nb_trucks = int(next(file_it))
elif token == "GVRP_SETS:":
nb_clusters = int(next(file_it))
elif token == "CAPACITY:":
truck_capacity = int(next(file_it))
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(float(next(file_it)))
depot_y = int(float(next(file_it)))
else:
# -2 because original customer indices are in 2..nbNodes
customers_x[node_id - 2] = int(float(next(file_it)))
customers_y[node_id - 2] = int(float(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 != "GVRP_SET_SECTION":
print("Expected token GVRP_SET_SECTION")
sys.exit(1)
clusters_data = [None]*nb_clusters
for n in range(nb_clusters):
node_id = int(next(file_it))
if node_id != n + 1:
print("Unexpected index")
sys.exit(1)
cluster = []
value = int(next(file_it))
while value != -1:
# -2 because original customer indices are in 2..nbNodes
cluster.append(value-2)
value = int(next(file_it))
clusters_data[n] = cluster
token = next(file_it)
if token != "DEMAND_SECTION":
print("Expected token DEMAND_SECTION")
sys.exit(1)

demands = [None] * nb_clusters
for n in range(nb_clusters):
node_id = int(next(file_it))
if node_id != n + 1:
print("Unexpected index")
sys.exit(1)
demands[n] = int(next(file_it))
return nb_customers, nb_trucks, nb_clusters, truck_capacity, distance_matrix, \
distance_depots, demands, clusters_data

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

if __name__ == '__main__':
if len(sys.argv) < 2:
print("Usage: python clustered-vehicle-routing.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 clustered-vehicle-routing.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver120.lib
clustered-vehicle-routing instances\A-n32-k5-C11-V2.gvrp
Compilation / Execution (Linux)
g++ clustered-vehicle-routing.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -lpthread -o clustered-vehicle-routing
./clustered-vehicle-routing instances/A-n32-k5-C11-V2.gvrp
```#include "localsolver.h"
#include <cmath>
#include <cstring>
#include <fstream>
#include <iostream>
#include <vector>

using namespace localsolver;
using namespace std;

class ClusteredCvrp {
public:
// LocalSolver
LocalSolver localsolver;

// Number of customers
int nbCustomers;

// Capacity of the trucks
int truckCapacity;

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

// Customers in each cluster;
vector<vector<int>> clustersData;

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

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

// Number of trucks
int nbTrucks;

// Number of clusters
int nbClusters;

// Decision variables
vector<LSExpression> truckSequences;

// 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;

}

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

// 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) {
distMatrixData[n].end()));
}
LSExpression clusters = model.array();
for (int n = 0; n < clustersData.size(); ++n) {
}
LSExpression distDepot = model.array(distDepotData.begin(), distDepotData.end());

// A list is created for each cluster, to determine the order within the cluster
for (int k = 0; k < nbClusters; ++k) {
int c = (int) clustersData[k].size();
// All customers in the cluster must be visited
}

LSExpression clustersDistances =  model.array();
LSExpression initialNodes = model.array();
LSExpression endNodes = model.array();
for (int k = 0; k < nbClusters; ++k) {
LSExpression c = model.count(sequence);

// Distance traveled within clsuter k
LSExpression clustersDistances_lambda = model.createLambdaFunction(
[&](LSExpression i) { return model.at(distMatrix,
clusters[k][sequence[i - 1]], clusters[k][sequence[i]]); });

// First and last point when visiting cluster k
}

// Sequence of clusters visited by each truck
truckSequences.resize(nbTrucks);
for (int k = 0; k < nbTrucks; ++k) {
truckSequences[k] = model.listVar(nbClusters);
}
// All clusters must be visited by the trucks
model.constraint(model.partition(truckSequences.begin(), truckSequences.end()));

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

// 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
// = distance in each cluster + distance between clusters + distance with depot
// at the beginning end at the end of a route
LSExpression routeDistances_lambda = model.createLambdaFunction(
[&](LSExpression i) { return model.at(clustersDistances, sequence[i])
+ model.at(distMatrix, endNodes[sequence[i - 1]], initialNodes[sequence[i]]);}
);

routeDistances[k] = model.sum(model.range(1, c), routeDistances_lambda)
+ model.iif(c > 0, model.at(clustersDistances, sequence)
+ distDepot[initialNodes[sequence]]
+ distDepot[endNodes[sequence[c - 1]]], 0);
}

// Total distance traveled
totalDistance = model.sum(routeDistances.begin(), routeDistances.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 with the following format:
* - total distance
* - for each truck the customers visited (omitting the start/end at the depot) */
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.open(fileName.c_str());

outfile << totalDistance.getValue() << endl;
for (int k = 0; k < nbTrucks; ++k) {
// Values in sequence are in [0..nbCustomers-1]. +2 is to put it back in
// [2..nbCustomers+1] as in the data files (1 being the depot)
LSCollection customersCollection = truckSequences[k].getCollectionValue();
for (int i = 0; i < customersCollection.count(); ++i) {
int cluster = customersCollection[i];
LSCollection clustersCollection =
for (int j = 0; j < clustersCollection.count(); ++j)
outfile << clustersData[cluster][clustersCollection[j]] + 2 << " ";
}
outfile << endl;
}
}

private:
// The input files follow the "Augerat" format
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, "VEHICLES:") == 0) {
pch = strtok(NULL, " ");
nbTrucks = atoi(pch);
} else if (strcmp(pch, "GVRP_SETS:") == 0) {
pch = strtok(NULL, " ");
nbClusters = atoi(pch);
} else if (strcmp(pch, "CAPACITY:") == 0) {
pch = strtok(NULL, "");
truckCapacity = atoi(pch);
} 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 >> pch;
infile >> depotY;
infile >> pch;
} else {
// -2 because original customer indices are in 2..nbNodes
infile >> customersX[n - 2];
infile >> pch;
infile >> customersY[n - 2];
infile >> pch;
}
}

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, "GVRP_SET_SECTION") != 0) {
throw std::runtime_error("Expected keyword GVRP_SET_SECTION");
}
for (int n = 1; n <= nbClusters; ++n) {
vector<int> cluster;
int id;
infile >> id;
if (id != n) {
throw std::runtime_error("Unexpected index");
}
int data;
infile >> data;
while (data != -1) {
// -2 because original customer indices are in 2..nbNodes
cluster.push_back(data - 2);
infile >> data;
}
clustersData.push_back(cluster);

};

getline(infile, str); // End the last line
getline(infile, str);
line = strdup(str.c_str());
pch = strtok(line, " ");
cout << pch;
cout << "test" << endl;
if (strcmp(pch, "DEMAND_SECTION") != 0) {
throw std::runtime_error("Expected keyword DEMAND_SECTION");
}
demandsData.resize(nbClusters);
for (int n = 1; n <= nbClusters; ++n) {
int id;
infile >> id;
if (id != n) {
throw std::runtime_error("Unexpected index");
}
int demand;
infile >> demand;
demandsData[n - 1] = demand;
}
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 main(int argc, char** argv) {
if (argc < 1) {
cerr << "Usage: clustered-vehicle-routing inputFile [outputFile] [timeLimit] " << endl;
return 1;
}
const char* instanceFile = argc > 1 ? argv : "instances/A-n32-k5-C11-V2.gvrp";
const char* solFile = argc > 2 ? argv : NULL;
const char* strTimeLimit = argc > 3 ? argv : "5";
try {
ClusteredCvrp model;
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 clustered-vehicle-routing.cs /reference:localsolvernet.dll
clustered-vehicle-routing instances\A-n32-k5-C11-V2.gvrp
```using System;
using System.IO;
using System.Collections.Generic;
using localsolver;

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

// Number of customers
int nbCustomers;

// Capacity of the trucks
int truckCapacity;

// Demand on each customer
long[] demandsData;

// Customers in each cluster
long[][] clustersData;

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

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

// Number of trucks
int nbTrucks;

// Number of Clusters
int nbClusters;

// Decision variables
LSExpression[] truckSequences;

// Distance traveled by all the trucks
LSExpression totalDistance;

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

{
}

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

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

LSExpression[] clustersDistances = new LSExpression[nbClusters];
LSExpression[] routeDistances = new LSExpression[nbTrucks];
LSExpression[] initialNodes = new LSExpression[nbClusters];
LSExpression[] endNodes = new LSExpression[nbClusters];

// A list is created for each cluster, to determine the order within the cluster
for ( int k = 0; k < nbClusters; ++k)
{
int c = (int) clustersData[k].Length;
// All customers in the cluster must be visited
}

// 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);
LSExpression clusters = model.Array(clustersData);

for (int k = 0; k < nbClusters; ++k)
{
LSExpression c = model.Count(sequence);

LSExpression routeDistances_lambda = model.LambdaFunction(
i => model.At(distMatrix,
clusters[k][sequence[i - 1]], clusters[k][sequence[i]]) );

// Distance traveled within cluster k
clustersDistances[k] = model.Sum(model.Range(1,c), routeDistances_lambda);

// first and last point visited when traveled into cluster k
initialNodes[k] = clusters[k][sequence];
endNodes[k] = clusters[k][sequence[c - 1]];
}

truckSequences = new LSExpression[nbTrucks];
// Sequence of clusters visited by each truck
for (int k = 0; k < nbTrucks; ++k)
truckSequences[k] = model.List(nbClusters);

// All customers must be visited by the trucks
model.Constraint(model.Partition(truckSequences));

LSExpression valueDistClusters = model.Array(clustersDistances);
LSExpression initials = model.Array(initialNodes);
LSExpression ends = model.Array(endNodes);
for (int k = 0; k < nbTrucks; ++k)
{
LSExpression sequence = truckSequences[k];
LSExpression c = model.Count(sequence);

// 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
// = distance in each cluster + distance between clusters + distance with depot
// at the beginning end at the end of a route
LSExpression routeDistances_lambda = model.LambdaFunction(
i => model.Sum( model.At(valueDistClusters, sequence[i]),
model.At(distMatrix, ends[sequence[i - 1]], initials[sequence[i]])));
routeDistances[k] = model.Sum(model.Range(1, c), routeDistances_lambda)
+ model.If(c > 0, valueDistClusters[ model.At(sequence,0)]
+ distDepot[initials[sequence]] + distDepot[ends[sequence[c - 1]]], 0);
}

totalDistance = model.Sum(routeDistances);

// 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 with the following format:
* -  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(totalDistance.GetValue());
for (int k = 0; k < nbTrucks; ++k)
{
// Values in sequence are in [0..nbCustomers-1]. +2 is to put it back in
// [2..nbCustomers+1] as in the data files (1 being the depot)
LSCollection customersCollection = truckSequences[k].GetCollectionValue();
for (int i = 0; i < customersCollection.Count(); ++i)
{
long cluster = customersCollection[i];
LSCollection clustersCollection =
for (int j = 0; j < clustersCollection.Count(); ++j)
output.Write((clustersData[cluster][clustersCollection[j]] + 2) + " ");
}
output.WriteLine();
}
}
}

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

using (cluCvrp model = new cluCvrp())
{
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}

// The input files follow the "Augerat" format
{
{
int nbNodes = 0;
string[] splitted;
while (true)
{
if (splitted.Contains("DIMENSION"))
{
nbNodes = int.Parse(splitted);
nbCustomers = nbNodes - 1;
}
else if (splitted.Contains("VEHICLES"))
nbTrucks = int.Parse(splitted);
else if (splitted.Contains("GVRP_SETS"))
nbClusters = int.Parse(splitted);
else if (splitted.Contains("CAPACITY"))
truckCapacity = int.Parse(splitted);
else if (splitted.Contains("NODE_COORD_SECTION"))
break;
}
int[] customersX = new int[nbCustomers];
int[] customersY = new int[nbCustomers];
int depotX = 0,
depotY = 0;
char[] delimiterChars = { ' ', '.' };
for (int n = 1; n <= nbNodes; ++n)
{
int id = int.Parse(splitted);
if ( id != n)
throw new Exception("Unexpected index");
if (n == 1)
{
depotX = int.Parse(splitted);
depotY = int.Parse(splitted);
}
else
{
// -2 because original customer indices are in 2..nbNodes
customersX[n - 2] = int.Parse(splitted);
customersY[n - 2] = int.Parse(splitted);
}
}

ComputeDistanceMatrix(depotX, depotY, customersX, customersY);

if (!splitted.Contains("GVRP_SET_SECTION"))
throw new Exception("Expected keyword GVRP_SET_SECTION");

clustersData = new long[nbClusters][];
for (int n = 1; n <= nbClusters; ++n)
{
splitted = input
.Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
if (int.Parse(splitted) != n)
throw new Exception("Unexpected index");
List<long> cluster = new List<long>();
int i = 1;
var customer = int.Parse(splitted);
while (customer != -1)
{
// -2 because original customer indices are in 2..nbNodes
i++;
customer = int.Parse(splitted[i]);
}
clustersData[n - 1] = cluster.ToArray();
}

if (!splitted.Contains("DEMAND_SECTION"))
throw new Exception("Expected keyword DEMAND_SECTION");

demandsData = new long[nbCustomers];
for (int n = 1; n <= nbClusters; ++n)
{
splitted = input
.Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
if (int.Parse(splitted) != n)
throw new Exception("Unexpected index");
var demand = int.Parse(splitted);
demandsData[n - 1] = demand;
}

}
}

// 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));
}
}
```
Compilation / Execution (Windows)
javac clustered_vehicle_routing.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. clustered_vehicle_routing instances\A-n32-k5-C11-V2.gvrp
Compilation / Execution (Linux)
javac clustered_vehicle_routing.java -cp /opt/localsolver_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/bin/localsolver.jar:. clustered_vehicle_routing instances/A-n32-k5-C11-V2.gvrp
```import java.util.*;
import java.io.*;
import localsolver.*;

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

// Number of customers
int nbCustomers;

// Capacity of the trucks
private int truckCapacity;

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

// Customers in each cluster
private long[][] clustersData;

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

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

// Number of trucks
private int nbTrucks;

// Number of clusters
private int nbClusters;

// Decision variables
private LSExpression[] truckSequences;

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

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

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

// 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);
LSExpression[] distClusters = new LSExpression[nbClusters];
LSExpression[] distRoutes = new LSExpression[nbTrucks];
LSExpression[] initialNodes = new LSExpression[nbClusters];
LSExpression[] endNodes = new LSExpression[nbClusters];

// A list is created for each cluster, to determine the order within the cluster
for (int k = 0; k < nbClusters; ++k) {
// All customers in the cluster must be visited
clustersData[k].length));
}

for (int k = 0; k < nbClusters; ++k) {
LSExpression sequenceCluster = model.array(clustersData[k]);
LSExpression c = model.count(sequence);

// Distance traveled within cluster k
LSExpression distLambda = model
.lambdaFunction(i -> model.at(distMatrix,
model.at(sequenceCluster, model.at(sequence, model.sub(i, 1))),
model.at(sequenceCluster, model.at(sequence, i) ))
);
distClusters[k] = model.sum(model.range(1,c), distLambda);

// First and last point when visiting cluster k
initialNodes[k] = model.at(sequenceCluster, model.at(sequence, 0));
endNodes[k]     = model.at(sequenceCluster, model.at(sequence, model.sub(c,1)));
}

truckSequences = new LSExpression[nbTrucks];
// Sequence of clusters visited by each truck.
for (int k = 0; k < nbTrucks; ++k)
truckSequences[k] = model.listVar(nbClusters);
// Each cluster must be visited by exactly one truck
model.constraint(model.partition(truckSequences));

LSExpression valueDistCluster = model.array(distClusters);
LSExpression initials         = model.array(initialNodes);
LSExpression ends             = model.array(endNodes);

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

// 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
// = distance in each cluster + distance between clusters + distance with depot
// at the beginning end at the end of a route
LSExpression distLambda = model.lambdaFunction(i -> model.sum(
model.at(valueDistCluster, model.at(sequence,i)),
model.at(distMatrix, model.at(ends, model.at(sequence, model.sub(i, 1))),
model.at(initials, 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(valueDistCluster, model.at(sequence,0)),
model.at(distDepot, model.at(initials, model.at(sequence, 0))),
model.at(distDepot, model.at(ends, model.at(sequence, model.sub(c, 1))))),
0) );
}

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 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( totalDistance.getValue());
for (int k = 0; k < nbTrucks; ++k) {

// Values in sequence are in [0..nbCustomers-1]. +2 is to put it back in
// [2..nbCustomers+1] as in the data files (1 being the depot)
LSCollection customersCollection = truckSequences[k].getCollectionValue();
for (int i = 0; i < customersCollection.count(); ++i) {
int cluster = (int) customersCollection.get(i);
LSCollection clustersCollection =
for (int j = 0; j < clustersCollection.count(); ++j)
output.print((clustersData[cluster][(int) clustersCollection.get(j)] + 2)
+ " ");
}
output.println();
}
}
}

// The input files follow the "Augerat" format
private void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
int nbNodes = 0;
String[] splitted;
while (true) {
splitted = input.nextLine().split(":");
if (splitted.contains("DIMENSION")) {
nbNodes = Integer.parseInt(splitted.trim());
nbCustomers = nbNodes - 1;
} else if (splitted.contains("VEHICLES")) {
nbTrucks = Integer.parseInt(splitted.trim());
} else if (splitted.contains("GVRP_SETS")) {
nbClusters = Integer.parseInt(splitted.trim());
} else if (splitted.contains("CAPACITY")) {
truckCapacity = Integer.parseInt(splitted.trim());
} else if (splitted.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 = (int) input.nextFloat();
depotY = (int) input.nextFloat();
} else {
// -2 because original customer indices are in 2..nbNodes
customersX[n - 2] = (int) input.nextFloat();
customersY[n - 2] = (int) input.nextFloat();
}
}
computeDistanceMatrix(depotX, depotY, customersX, customersY);

input.nextLine().split(""); // End the last line
String name = input.nextLine();
if (!name.contains("GVRP_SET_SECTION")) {
throw new RuntimeException("Expected keyword GVRP_SET_SECTION");
}
clustersData = new long[nbClusters][];
for (int n = 1; n <= nbClusters; ++n) {
List<Long> cluster = new ArrayList<>();
int id = input.nextInt();
if (id != n)
throw new IOException("Unexpected index");
long customer = input.nextInt();
while (customer != -1) {
// -2 because original customer indices are in 2..nbNodes
customer = input.nextInt();
}
long[] clusterArray = cluster.stream()
.mapToLong(Long::intValue).toArray();
clustersData[n - 1] = clusterArray;
}

input.nextLine().split("");
name = input.nextLine();
if (!name.contains("DEMAND_SECTION")) {
throw new RuntimeException("Expected keyword DEMAND_SECTION");
}
demandsData = new long[nbCustomers];
for (int n = 1; n <= nbClusters; ++n) {
int id = input.nextInt();
if (id != n) throw new IOException("Unexpected index");
int demand = input.nextInt();
demandsData[n - 1] = demand;
}
}
}

// 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);
}

public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Usage: java clustered-vehicle-routing inputFile [outputFile] [timeLimit]");
System.exit(1);
}
try (LocalSolver localsolver = new LocalSolver()) {
String instanceFile = args;
String outputFile = args.length > 1 ? args : null;
String strTimeLimit = args.length > 2 ? args : "20";

clustered_vehicle_routing model = new clustered_vehicle_routing(localsolver);