# Prize-Collecting Vehicle Routing (PCVRP)¶

## 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 prize-collecting vehicle routing problem (PCVRP), a fleet of vehicles with uniform capacity can deliver customers with known demand and prize for a single commodity. The vehicles start and end their routes at a common depot. Each customer might be served by at most one vehicle. The objectives are to minimize the fleet size, maximize the total prize and assign a sequence of customers to each truck of the fleet minimizing the total distance traveled such that a predefined amount of demands are satisfied and the total demand served by each truck does not exceed its capacity.

## Data¶

The instances provided come from the Long et al. Set A instances. They added a prize and a minimum quantity of demands to satisfy to the Augerat et al. Set A instances.

The format of the data files is as follows:

• The first line: the number of vehicles, vehicle capacity, the predetermined amount needed to be satisfied

• The second line (depot): node ID, abscissa value, ordinate value

• The third line to the last line (customers): node ID, abscissa value, ordinate value, demand, prize

## Program¶

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

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

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

The prize earned on each visit is the prize on the node of this visit. We also use a function to sum prizes along each route. The total prize is the sum of the prizes of each route.

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

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

If you are interested in the more classical variant CVRP (without prize), you can now study our CVRP model.

Execution:
localsolver pcvrp.lsp inFileName=instances/A-n32-k5_1.txt [lsTimeLimit=] [solFileName=]
```use io;

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

if (inFileName == nil) throw usage;

computeDistanceMatrix();
}

/* Declare the optimization model */
function model() {
// Sequence of customers visited by each truck

// A customer might be visited by only one truck

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

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

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

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

// Route prize of truck k
routePrizes[k] <- sum(sequence, j => prizes[j]);
}

// Total nb demands satisfied
totalQuantity <- sum[k in 0...nbTrucks](routeQuantities[k]);

// Minimal number of demands to satisfy
constraint totalQuantity >= demandsToSatisfy;

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

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

// Total prize
totalPrize <- sum[k in 0...nbTrucks](routePrizes[k]);

// Objective: minimize the number of trucks used, then maximize the total prize and minimize the distance traveled
minimize nbTrucksUsed;
maximize totalPrize;
minimize totalDistance;
}

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

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

outfile.println(totalPrize.value, " ", nbTrucksUsed.value, " ", totalDistance.value);
nbUnvisitedCustomers = nbCustomers;

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

outfile.println(nbUnvisitedCustomers, " ", totalQuantity.value);

outfile.close();
}

n = 0;
while (!inFile.eof()) {
if (n != inFile.readInt()) throw "Unexpected index";
if (n == 0) {
depotId = n;
} else {
// -1 because depot has no demand neither prize
}
n += 1;
}

nbCustomers = n - 1;

inFile.close();
}

/* 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 + 1, j + 1);
distanceMatrix[j][i] = localDistance;
distanceMatrix[i][j] = localDistance;
}
}

for [i in 0...nbCustomers] {
local localDistance = computeDist(0, i + 1);
distanceDepot[i] = localDistance;
}
}

/* Compute the euclidean distance */
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 pcvrp.py instances\A-n32-k5_1.txt
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_0/bin/python
python pcvrp.py instances/A-n32-k5_1.txt
```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, dist_depot_data, \

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

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

# A customer might be visited by only one truck
model.constraint(model.disjoint(customers_sequences))

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

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

dist_routes = [None] * nb_trucks
route_prizes = [None] * nb_trucks
route_quantities = [None] * nb_trucks

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

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

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

# Route prize of truck k
prize_lambda = model.lambda_function(lambda j: prizes[j])
route_prizes[k] = model.sum(sequence, prize_lambda)

# Total nb demands satisfied
total_quantity = model.sum(route_quantities)

# Minimal number of demands to satisfy
model.constraint(total_quantity >= demands_to_satisfy)

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

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

# Total prize
total_prize = model.sum(route_prizes)

# Objective: minimize the number of trucks used, then maximize the total prize and minimize the distance traveled
model.minimize(nb_trucks_used)
model.maximize(total_prize)
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 prize, number of trucks used and total distance
#  - for each truck the customers visited (omitting the start/end at the depot)
#  - number of unvisited customers, demands satisfied
if output_file is not None:
with open(output_file, 'w') as f:
f.write("%d %d %d\n" % (total_prize.value, nb_trucks_used.value, total_distance.value))
nb_unvisited_customers = nb_customers
for k in range(nb_trucks):
if trucks_used[k].value != 1:
continue
# Values in sequence are in 0...nbCustomers. +1 is to put it back in 1...nbCustomers+1
# as in the data files (0 being the depot)
for customer in customers_sequences[k].value:
f.write("%d " % (customer + 1))
nb_unvisited_customers -= 1
f.write("\n")
f.write("%d %d\n" % (nb_unvisited_customers, total_quantity.value))

# The input files follow the "longjianyu" format

nb_trucks = int(next(file_it))
truck_capacity = int(next(file_it))
demands_to_satisfy = int(next(file_it))

n = 0
customers_x = []
customers_y = []
depot_x = 0
depot_y = 0
demands = []
prizes = []

it = next(file_it, None)
while (it != None):
node_id = int(it)
if node_id != n:
print("Unexpected index")
sys.exit(1)

if n == 0:
depot_x = int(next(file_it))
depot_y = int(next(file_it))
else:
customers_x.append(int(next(file_it)))
customers_y.append(int(next(file_it)))
demands.append(int(next(file_it)))
prizes.append(int(next(file_it)))
it = next(file_it, None)
n += 1

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

nb_customers = n - 1

return nb_customers, nb_trucks, truck_capacity, distance_matrix, distance_depots, \
demands, demands_to_satisfy, prizes

# Compute the distance matrix
def compute_distance_matrix(customers_x, customers_y):
nb_customers = len(customers_x)
distance_matrix = [[None for _ in range(nb_customers)] for _ 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 pcvrp.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 pcvrp.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver120.lib
pcvrp instances\A-n32-k5_1.txt
Compilation / Execution (Linux)
g++ pcvrp.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -lpthread -o pcvrp
./pcvrp instances/A-n32-k5_1.txt
```#include "localsolver.h"
#include <cmath>
#include <cstring>
#include <fstream>
#include <iostream>
#include <vector>

using namespace localsolver;
using namespace std;

class Pcvrp {
public:
// LocalSolver
LocalSolver localsolver;

// Number of customers
int nbCustomers;

// Capacity of the trucks
int truckCapacity;

// Minimum number of demands to satisfy
int demandsToSatisfy;

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

// Prize on each customer
vector<int> prizesData;

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

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

// Number of trucks
int nbTrucks;

// Decision variables

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

// Total prize of the solution
LSExpression totalPrize;

// Total nb demands satisfied in the solution
LSExpression totalQuantity;

}

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

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

// Sequence of customers visited by each truck
for (int k = 0; k < nbTrucks; ++k) {
}

// A customer might be visited by only one truck

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

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

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

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

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

// Route prize of truck k
LSExpression prizeLambda =
model.createLambdaFunction([&](LSExpression j) { return prizes[j]; });
routePrizes[k] = model.sum(sequence, prizeLambda);
}

// Total nb demands satisfied
totalQuantity = model.sum(routeQuantities.begin(), routeQuantities.end());

model.constraint(totalQuantity >= demandsToSatisfy);

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

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

// Total prize
totalPrize = model.sum(routePrizes.begin(), routePrizes.end());

// Objective: minimize the number of trucks used, then maximize the total prize and minimize the distance traveled
model.minimize(nbTrucksUsed);
model.maximize(totalPrize);
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 prize, number of trucks used and total distance
* - for each truck the customers visited (omitting the start/end at the depot)
* - number of unvisited customers, demands satisfied */
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.open(fileName.c_str());

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

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

infile >> nbTrucks;
infile >> truckCapacity;
infile >> demandsToSatisfy;

int n = 0;
vector<int> customersX, customersY;
int depotX, depotY;
int x, y, demand, prize;
int id;
while (infile >> id) {
if (id != n) {
throw std::runtime_error("Unexpected index");
}
if (n == 0) {
infile >> depotX;
infile >> depotY;
} else {
infile >> x;
infile >> y;
customersX.push_back(x);
customersY.push_back(y);
infile >> demand;
infile >> prize;
demandsData.push_back(demand);
prizesData.push_back(prize);
}
++n;
}

nbCustomers = n - 1;

computeDistanceMatrix(depotX, depotY, customersX, customersY);

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 < 2) {
cerr << "Usage: pcvrp 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 {
Pcvrp 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 Pcvrp.cs /reference:localsolvernet.dll
Pcvrp instances\A-n32-k5_1.txt
```using System;
using System.IO;
using localsolver;
using System.Collections.Generic;

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

// Number of customers
int nbCustomers;

// Capacity of the trucks
int truckCapacity;

// Minimum number of demands to satisfy
long demandsToSatisfy;

// Demand on each customer
long[] demandsData;

// Prize on each customer
long[] prizesData;

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

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

// Number of trucks
int nbTrucks;

// Decision variables

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

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

// Distance traveled by all the trucks
LSExpression totalDistance;

// Total prize of the solution
LSExpression totalPrize;

// Total nb demands satisfied in the solution
LSExpression totalQuantity;

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

{
}

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

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

trucksUsed = new LSExpression[nbTrucks];
LSExpression[] distRoutes = new LSExpression[nbTrucks];
LSExpression[] routeQuantities = new LSExpression[nbTrucks];
LSExpression[] routePrizes = new LSExpression[nbTrucks];

// Sequence of customers visited by each truck
for (int k = 0; k < nbTrucks; ++k)

// A customer might be visited by only one truck

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

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

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

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

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

// Route prize of truck k
LSExpression prizeLambda = model.LambdaFunction(j => prizes[j]);
routePrizes[k] = model.Sum(sequence, prizeLambda);
}

// Minimal number of demands to satisfy
totalQuantity = model.Sum(routeQuantities);
model.Constraint(totalQuantity >= demandsToSatisfy);

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

// Objective: minimize the number of trucks used, then maximize the total prize and minimize the distance traveled
model.Minimize(nbTrucksUsed);
model.Maximize(totalPrize);
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 prize, number of trucks used and total distance
* - for each truck the customers visited (omitting the start/end at the depot)
* - number of unvisited customers, demands satisfied */
void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine(totalPrize.GetValue() + " " + nbTrucksUsed.GetValue() + " " + totalDistance.GetValue());
int nbUnvisitedCustomers = nbCustomers;
for (int k = 0; k < nbTrucks; ++k)
{
if (trucksUsed[k].GetValue() != 1)
continue;
// Values in sequence are in 0...nbCustomers. +1 is to put it back in 1...nbCustomers+1
// as in the data files (0 being the depot)
for (int i = 0; i < customersCollection.Count(); ++i)
output.Write((customersCollection[i] + 1) + " ");
--nbUnvisitedCustomers;
output.WriteLine();
}
output.WriteLine(nbUnvisitedCustomers + " " + totalQuantity.GetValue());
}
}

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

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

// The input files follow the "longjianyu" format
{
{
string[] splitted;
splitted = input
.Split((char[])null, StringSplitOptions.RemoveEmptyEntries);

nbTrucks = int.Parse(splitted);
truckCapacity = int.Parse(splitted);
demandsToSatisfy = int.Parse(splitted);

int n = 0;
List<int> customersXList = new List<int>(), customersYList = new List<int>();
List<long> demandsDataList = new List<long>(), prizesDataList = new List<long>();
int depotX = 0, depotY = 0;
string line;

while ((line = input.ReadLine()) != null)
{
splitted = line.Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
if (int.Parse(splitted) != n)
throw new Exception("Unexpected index");
if (n == 0)
{
depotX = int.Parse(splitted);
depotY = int.Parse(splitted);
}
else
{
}
++n;
}

nbCustomers = n - 1;

int[] customersX = customersXList.ToArray();
int[] customersY = customersYList.ToArray();

demandsData = demandsDataList.ToArray();
prizesData = prizesDataList.ToArray();

ComputeDistanceMatrix(depotX, depotY, customersX, customersY);
}
}

// 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 Pcvrp.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Pcvrp instances\A-n32-k5_1.txt
Compilation / Execution (Linux)
javac Pcvrp.java -cp /opt/localsolver_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/bin/localsolver.jar:. Pcvrp instances/A-n32-k5_1.txt
```import java.util.*;
import java.io.*;
import localsolver.*;

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

// Number of customers
int nbCustomers;

// Capacity of the trucks
private int truckCapacity;

// Minimum number of demands to satisfy
private long demandsToSatisfy;

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

// Prize on each customer
private long[] prizesData;

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

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

// Number of trucks
private int nbTrucks;

// Decision variables

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

// Total prize of the solution
private LSExpression totalPrize;

// Total nb demands satisfied in the solution
private LSExpression totalQuantity;

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

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

trucksUsed = new LSExpression[nbTrucks];
LSExpression[] distRoutes = new LSExpression[nbTrucks];
LSExpression[] routeQuantities = new LSExpression[nbTrucks];
LSExpression[] routePrizes = new LSExpression[nbTrucks];

// Sequence of customers visited by each truck.
for (int k = 0; k < nbTrucks; ++k)

// A customer might be visited by only one truck

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

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

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

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

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

// Route prize of truck k
LSExpression prizeLambda = model.lambdaFunction(j -> model.at(prizes, j));
routePrizes[k] = model.sum(sequence, prizeLambda);
}

// Minimal number of demands to satisfy
totalQuantity = model.sum(routeQuantities);
model.constraint(model.geq(totalQuantity, demandsToSatisfy));

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

// Objective: minimize the number of trucks used, then maximize the total prize and minimize the distance traveled
model.minimize(nbTrucksUsed);
model.maximize(totalPrize);
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 prize, number of trucks used and total distance
* - for each truck the customers visited (omitting the start/end at the depot)
* - number of unvisited customers, demands satisfied */
private void writeSolution(String fileName) throws IOException {
try (PrintWriter output = new PrintWriter(fileName)) {
output.println(totalPrize.getValue() + " " + nbTrucksUsed.getValue() + " " + totalDistance.getValue());
int nbUnvisitedCustomers = nbCustomers;
for (int k = 0; k < nbTrucks; ++k) {
if (trucksUsed[k].getValue() != 1)
continue;
// Values in sequence are in 0...nbCustomers. +1 is to put it back in 1...nbCustomers+1
// as in the data files (0 being the depot)
for (int i = 0; i < customersCollection.count(); ++i) {
output.print((customersCollection.get(i) + 1) + " ");
--nbUnvisitedCustomers;
}
output.println();
}
output.println(nbUnvisitedCustomers + " " + totalQuantity.getValue());
}
}

// The input files follow the "longjianyu" format
private void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
nbTrucks = input.nextInt();
truckCapacity = input.nextInt();
demandsToSatisfy = input.nextInt();

int n = 0;
ArrayList<Integer> customersXList = new ArrayList<>(), customersYList = new ArrayList<>();
ArrayList<Long> demandsDataList = new ArrayList<>(), prizesDataList = new ArrayList<>();
int depotX = 0, depotY = 0;
while (input.hasNext()) {
int id = input.nextInt();
if (id != n)
throw new IOException("Unexpected index");
if (n == 0) {
depotX = input.nextInt();
depotY = input.nextInt();
} else {
}
++n;
}
nbCustomers = n - 1;

int[] customersX = customersXList.stream().mapToInt(i -> i).toArray();
int[] customersY = customersYList.stream().mapToInt(i -> i).toArray();

demandsData = demandsDataList.stream().mapToLong(i -> i).toArray();
prizesData = prizesDataList.stream().mapToLong(i -> i).toArray();

computeDistanceMatrix(depotX, depotY, customersX, customersY);
}
}

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

Pcvrp model = new Pcvrp(localsolver);