# Routing with time windows¶

## Principles learned¶

• Add multiple list decision variables
• Use lambda expression to define a recursive array
• Define a sequence of expressions

## Problem¶

In the capacitated vehicle routing problem with time-windows (CVRPTW), a fleet of delivery vehicles with uniform capacity must service customers with known demand and opening hours for a single commodity. The vehicles start and end their routes at a common depot. Each customer can only be served by one vehicle. The objectives are to minimize the fleet size and assign a sequence of customers to each truck of the fleet minimizing the total distance travelled 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 Solomon instances..

The format of the data files is as follows:

• The first line gives the name of the instance

• The fifth line contains the number of vehicle and their common capacity

• From the 10th line, each line contains the integer data associated to each customer, starting with the depot.

• The index of the customer
• The x coordinate
• The y coordinate
• The demand
• The earliest arrival
• The latest arrival
• The service time.

## Program¶

The LocalSolver model is an extension of the CVRP model. We refer the reader to this model for the routing aspect of problem. The time-windows are handled as a prioritary objective. In case of early arrival, the truck has to wait for the opening hour of the customer. In case of late arrival, the lateness is measured and the total lateness has to be minimized. The solution is feasible when this cumulated lateness is zero.

In the model the ending times of each truck are defined as a recursive array. The arrivaltime is the maximum of:

• the end time of the previous visit plus the traveling time (equal to the distance in these instances). For the first visit it amounts to the traveling time from the depot (starting at t=0)
• the earliest allowed arrival at this customer

The ending time is merely this arrival time plus the service time for this customer. The arrival to the depot at the end of the tour occurs at the end time of the last visit plus the traveling time from this point to the depot.

Such a recursive definition is introduced with a function `(i, prev) => ...`. It allows defining the ith element of an array in function of i and of the (i-1)th element of the array. See our documentation on this topic for details.

The lateness at each visit is computed from the difference between the ending time of this visit and the latest allowed end for this customer. For the arrival at the depot, we compare the arrival time to the maximum horizon defined for the problem.

Finally we minimize in lexicographic order: the total lateness, the number of trucks used, and the total distance travelled by all the trucks.

Execution:
localsolver cvrptw.lsp inFileName=instances/R101.25.txt [lsTimeLimit=] [solFileName=]
```/********** cvrptw.lsp **********/

use io;

/* The input files follow the "Solomon" format.*/
function input() {
usage = "\nUsage: localsolver cvrptw.lsp "
+ "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]\n";

if (inFileName == nil) throw usage;

// Compute distance matrix
computeDistanceMatrix();

}

/* Declares the optimization model. */
function model() {

// All customers must be visited by  the trucks

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

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

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

endTime[k] <- array(0..c-1, (i, prev) => max(earliestStart[sequence[i]],
i == 0 ?
distanceWarehouse[sequence[0]] :
prev + distanceMatrix[sequence[i-1]][sequence[i]])
+ serviceTime[sequence[i]]);

homeLateness[k] <- truckUsed[k] ?
max(0, endTime[k][c - 1] + distanceWarehouse[sequence[c - 1]] - maxHorizon) :
0;

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

lateness[k] <- homeLateness[k] + sum(0..c-1,
i => max(0, endTime[k][i] - latestEnd[sequence[i]]));
}

// Total lateness, must be 0 for a solution to be valid
totalLateness <- sum[k in 1..nbTrucks](lateness[k]);

nbTrucksUsed <- sum[k in 1..nbTrucks](truckUsed[k]);

// Total distance travelled (convention in Solomon's instances is to round to 2 decimals)
totalDistance <- round(100*sum[k in 1..nbTrucks](routeDistances[k]))/100;

minimize totalLateness;
minimize nbTrucksUsed;
minimize totalDistance;
}

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

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

outfile.println(nbTrucksUsed.value, " ", totalDistance.value);
for [k in 1..nbTrucks] {
if (truckUsed[k].value != 1) continue;
outfile.print(customer + 1, " ");
}
outfile.println();
}
}

skipLines(inFile, 4);

//Truck related data

skipLines(inFile, 3);

//Warehouse data
warehouseIndex = line[0].toInt();
warehouseX = line[1].toInt();
warehouseY = line[2].toInt();
maxHorizon = line[5].toInt();

//Customers data
i = 0;
while (!inFile.eof()) {
line = inLine.split();
if(count(line) == 0) break;
if(count(line) != 7) throw "Wrong file format";
customerIndex[i] = line[0].toInt();
customerX[i] = line[1].toInt();
customerY[i] = line[2].toInt();
demands[i] = line[3].toInt();
serviceTime[i] = line[6].toInt();
earliestStart[i] = line[4].toInt();
latestEnd[i] = line[5].toInt() + serviceTime[i]; //in input files due date is meant as latest start time
i = i + 1;
}
nbCustomers = i;

inFile.close();
}

function skipLines(inFile, nbLines) {
if (nbLines < 1) return;
for[i in 2..nbLines] dump = inFile.readln();
}

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

for[i in 0..nbCustomers-1] {
local localDistance = computeDepotDist(i);
distanceWarehouse[i] = localDistance;
}
}

function computeDist(i, j) {
local x1 = customerX[i];
local x2 = customerX[j];
local y1 = customerY[i];
local y2 = customerY[j];
return computeDistance(x1, x2, y1, y2);
}

function computeDepotDist(i) {
local x1 = customerX[i];
local xd = warehouseX;
local y1 = customerY[i];
local yd = warehouseY;
return computeDistance(x1, xd, y1, yd);
}

function computeDistance(x1, x2, y1, y2) {
return sqrt(pow((x1 - x2), 2) + pow((y1 - y2), 2));
}
```
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python27\
python cvrptw.py instances\R101.25.txt
Execution (Linux)
export PYTHONPATH=/opt/localsolver_XXX/bin/python27/
python cvrptw.py instances/R101.25.txt
```########## cvrptw.py ##########

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

#
#
(nb_customers, nb_trucks, truck_capacity, distance_matrix, distance_warehouses, demands, service_time, earliest_start,latest_end, max_horizon) = read_input_cvrptw(instance_file)

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

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

# All customers must be visited by  the trucks
model.constraint(model.partition(customers_sequences))

# Create demands, earliest, latest and service as arrays to be able to access it with an "at" operator
demands_array = model.array(demands)
earliest_array = model.array(earliest_start)
latest_array = model.array(latest_end)
service_array = model.array(service_time)

# Create distance as an array to be able to acces it with an "at" operator
distance_array = model.array()
for n in range(nb_customers):
distance_warehouse_array = model.array(distance_warehouses)

route_distances = [None for n in range(nb_trucks)]
end_time = [None for n in range(nb_trucks)]
home_lateness = [None for n in range(nb_trucks)]
lateness = [None for n in range(nb_trucks)]

# 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)]
nb_trucks_used = model.sum(trucks_used)

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

# Quantity in each truck
demand_selector = model.function(lambda i: model.at(demands_array, sequence[i]))
route_quantity = model.sum(model.range(0, c), demand_selector)
model.constraint(route_quantity <= truck_capacity)

# Distance traveled by each truck
dist_selector = model.function(lambda i: model.at(distance_array, sequence[i-1], sequence[i]))
route_distances[k] = model.sum(model.range(1,c), dist_selector) + \
model.iif(c > 0, model.at(distance_warehouse_array, sequence[0]) + model.at(distance_warehouse_array, sequence[c-1]),0)

# End of each visit
end_selector = model.function(lambda i, prev: model.max(model.at(earliest_array, sequence[i]), \
model.iif(i == 0, \
model.at(distance_warehouse_array,sequence[0]), \
prev + model.at(distance_array,sequence[i-1],sequence[i]))) + \
model.at(service_array, sequence[i]))

end_time[k] = model.array(model.range(0,c), end_selector)

# Arriving home after max_horizon
home_lateness[k] = model.iif(trucks_used[k], \
model.max(0,model.at(end_time[k],c-1) + model.at(distance_warehouse_array,sequence[c-1])-max_horizon), \
0)

# completing visit after latest_end
late_selector = model.function(lambda i:  model.max(0,model.at(end_time[k],i) - model.at(latest_array, sequence[i])))
lateness[k] = home_lateness[k] + model.sum(model.range(0,c),late_selector)

# Total lateness
total_lateness = model.sum(lateness)

# Total distance travelled
total_distance = model.div(model.round(100 * model.sum(route_distances)),100);

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

model.close()

#
# Parameterizes the solver
#
ls.create_phase().time_limit = int(str_time_limit)

ls.solve()

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

# The input files follow the "Solomon" format.

for i in range(4): file_it.next()

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

for i in range(13): file_it.next()

warehouse_x = int(file_it.next())
warehouse_y = int(file_it.next())

for i in range(2): file_it.next()

max_horizon = int(file_it.next())

file_it.next()

customers_x = []
customers_y = []
demands = []
earliest_start = []
latest_end = []
service_time = []

while(1):
val = next(file_it,None)
if (val is None) : break
i = int(val) - 1
customers_x.append(int(file_it.next()))
customers_y.append(int(file_it.next()))
demands.append(int(file_it.next()))
due = int(file_it.next())
stime = int(file_it.next())
latest_end.append(due + stime) #in input files due date is meant as latest start time
service_time.append(stime)

nb_customers = i + 1

# Compute distance matrix
distance_matrix = compute_distance_matrix(customers_x, customers_y)
distance_warehouses = compute_distance_warehouses(warehouse_x, warehouse_y, customers_x, customers_y)

return (nb_customers, nb_trucks, truck_capacity, distance_matrix, distance_warehouses, demands, service_time, earliest_start,latest_end, max_horizon)

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

# Computes the distances to warehouse
def compute_distance_warehouses(depot_x, depot_y, customers_x, customers_y):
nb_customers = len(customers_x)
distance_warehouses = [None for i in range(nb_customers)]
for i in range(nb_customers):
dist = compute_dist(depot_x, customers_x[i], depot_y, customers_y[i])
distance_warehouses[i] = dist
return distance_warehouses

def compute_dist(xi, xj, yi, yj):
return math.sqrt(math.pow(xi - xj, 2) + math.pow(yi - yj, 2))

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

instance_file = sys.argv[1];
sol_file =  sys.argv[2] if len(sys.argv) > 2 else None;
str_time_limit = sys.argv[3] if len(sys.argv) > 3 else "20";

main(instance_file, str_time_limit, sol_file)
```
Compilation / Execution (Windows)
cl /EHsc cvrptw.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver.dll.lib
cvrp instances\R101.25.txt
Compilation / Execution (Linux)
g++ cvrptw.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o cvrp
./cvrp instances/R101.25.txt
```/********** cvrptw.cpp **********/

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <cmath>
#include "localsolver.h"

using namespace localsolver;
using namespace std;

class Cvrptw {
public:
// LocalSolver
LocalSolver localsolver;

// Number of customers
int nbCustomers;

// Capacity of the trucks
int truckCapacity;

// Latest allowed arrival to depot
int maxHorizon;

// Demand on each node
vector<lsint> demands;

// Earliest arrival on each node
vector<lsint> earliestStart;

// Latest departure from each node
vector<lsint> latestEnd;

// Service time on each node
vector<lsint> serviceTime;

// Distance matrix
vector<vector<lsdouble> > distanceMatrix;

// Distance to depot
vector<lsdouble> distanceWarehouses;

// Number of trucks
int nbTrucks;

// Decision variables

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

// Cumulated lateness in the solution (must be 0 for the solution to be valid)
LSExpression totalLateness;

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

// Distance travelled by all the trucks
LSExpression totalDistance;

// Constructor
Cvrptw() {
}

}

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

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

// All customers must be visited by  the trucks

// Create demands, earliest, latest and service as arrays to be able to access it with an "at" operator
LSExpression demandsArray = model.array(demands.begin(), demands.end());
LSExpression earliestArray = model.array(earliestStart.begin(), earliestStart.end());
LSExpression latestArray = model.array(latestEnd.begin(), latestEnd.end());
LSExpression serviceArray = model.array(serviceTime.begin(), serviceTime.end());

// Create distance as an array to be able to acces it with an "at" operator
LSExpression distanceArray = model.array();
for (int n = 0; n < nbCustomers; n++) {
}
LSExpression distanceWarehousesArray = model.array(distanceWarehouses.begin(), distanceWarehouses.end());

trucksUsed.resize(nbTrucks);
vector<LSExpression> routeDistances(nbTrucks), endTime(nbTrucks), homeLateness(nbTrucks), lateness(nbTrucks);

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 demandSelector = model.createFunction([&](LSExpression i) { return demandsArray[sequence[i]]; });
LSExpression routeQuantity = model.sum(model.range(0, c), demandSelector);
model.constraint(routeQuantity <= truckCapacity);

// Distance traveled by truck k
LSExpression distSelector = model.createFunction([&](LSExpression i) { return model.at(distanceArray, sequence[i - 1], sequence[i]); });
routeDistances[k] = model.sum(model.range(1, c), distSelector) +
model.iif(c > 0, distanceWarehousesArray[sequence[0]] + distanceWarehousesArray[sequence[c - 1]], 0);

//End of each visit
LSExpression endSelector = model.createFunction([&](LSExpression i, LSExpression prev) {
return model.max(model.at(earliestArray, sequence[i]),
model.iif(i == 0,
distanceWarehousesArray[sequence[0]],
prev + model.at(distanceArray,sequence[i-1],sequence[i]))
) +
model.at(serviceArray, sequence[i]); });

endTime[k] = model.array(model.range(0,c), endSelector);

// Arriving home after max_horizon
homeLateness[k] = model.iif(trucksUsed[k],
model.max(0,endTime[k][c-1] + distanceWarehousesArray[sequence[c-1]] - maxHorizon),
0);

//completing visit after latest_end
LSExpression lateSelector = model.createFunction([&](LSExpression i) { return model.max(0,endTime[k][i] - latestArray[sequence[i]]);});
lateness[k] = homeLateness[k] + model.sum(model.range(0,c),lateSelector);
}

// Total lateness
totalLateness = model.sum(lateness.begin(), lateness.end());

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

// Total distance travelled
totalDistance = model.round(100*model.sum(routeDistances.begin(), routeDistances.end()))/100;

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

model.close();

// Parameterizes the solver.
LSPhase phase = localsolver.createPhase();
phase.setTimeLimit(limit);
localsolver.solve();

}

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

outfile << nbTrucksUsed.getValue() << " " << totalDistance.getDoubleValue() << endl;
for (int k = 0; k < nbTrucks; k++) {
if (trucksUsed[k].getValue() != 1) continue;
// 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 (lsint i = 0; i < customersCollection.count(); i++) {
outfile << customersCollection[i] + 2 << " ";
}
outfile << endl;
}
}

private:

// The input files follow the "Solomon" 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;
long dump;

int depotX, depotY;
vector<int> customersX;
vector<int> customersY;

getline(infile, str);
getline(infile, str);
getline(infile, str);
getline(infile, str);

infile >> nbTrucks;
infile >> truckCapacity;

cout << nbTrucks << " " << truckCapacity <<endl;

getline(infile, str);
getline(infile, str);
getline(infile, str);
getline(infile, str);

infile >> dump;
infile >> depotX;
infile >> depotY;
infile >> dump;
infile >> dump;
infile >> maxHorizon;
infile >> dump;

int tt = 1;
while (!infile.eof()) {
infile >> dump;
infile >> cx;
infile >> cy;
infile >> demand;
infile >> due;
infile >> service;

customersX.push_back(cx);
customersY.push_back(cy);
demands.push_back(demand);
latestEnd.push_back(due+service);//in input files due date is meant as latest start time
serviceTime.push_back(service);
}

nbCustomers = customersX.size();

// Compute distance matrix
computeDistanceMatrix(depotX, depotY, customersX, customersY);

infile.close();
}

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

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

lsdouble computeDist(int xi, int xj, int yi, int yj) {
return sqrt(pow((double) xi - xj, 2) + pow((double) yi - yj, 2));
}

};

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

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

try {
Cvrptw model;
model.solve(atoi(strTimeLimit));
if(solFile != NULL) model.writeSolution(solFile);
return 0;
} catch (const exception& e){
cerr << "Error occurred: " << e.what() << endl;
return 1;
}
}
```
Compilation/Execution (Windows)
copy %LS_HOME%\bin\*net.dll .
csc Cvrptw.cs /reference:localsolvernet.dll
Cvrp instances\R101.25.txt
```/********** Cvrptw.cs **********/

using System;
using System.IO;
using System.Collections.Generic;
using localsolver;

public class Cvrptw : IDisposable
{
// Solver
LocalSolver localsolver;

// Number of customers (= number of nodes minus 1)
int nbCustomers;

// Capacity of the trucks
int truckCapacity;

// Latest allowed arrival to depot
int maxHorizon;

// Demand on each node
List<int> demands;

// Earliest arrival on each node
List<int> earliestStart;

// Latest departure from each node
List<int> latestEnd;

// Service time on each node
List<int> serviceTime;

// Distance matrix between customers
double[][] distanceMatrix;

// Distances between customers and warehouse
double[] distanceWarehouses;

// Number of trucks
int nbTrucks;

// Decision variables

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

// Distance travelled by each truck
LSExpression[] routeDistances;

// End time array for each truck
LSExpression[] endTime;

// Home lateness for each truck
LSExpression[] homeLateness;

// Cumulated Lateness for each truck
LSExpression[] lateness;

// Cumulated lateness in the solution (must be 0 for the solution to be valid)
LSExpression totalLateness;

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

// Distance travelled by all the trucks
LSExpression totalDistance;

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

{
}

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

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

trucksUsed = new LSExpression[nbTrucks];
routeDistances = new LSExpression[nbTrucks];
endTime = new LSExpression[nbTrucks];
homeLateness = new LSExpression[nbTrucks];
lateness = new LSExpression[nbTrucks];

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

// All customers must be visited by the trucks

// Create demands and distances as arrays to be able to access it with an "at" operator
LSExpression demandsArray = model.Array(demands);
LSExpression earliestArray = model.Array(earliestStart);
LSExpression latestArray = model.Array(latestEnd);
LSExpression serviceArray = model.Array(serviceTime);

LSExpression distanceWarehouseArray = model.Array(distanceWarehouses);
LSExpression distanceArray = model.Array(distanceMatrix);

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 demandSelector = model.Function(i => demandsArray[sequence[i]]);
LSExpression routeQuantity = model.Sum(model.Range(0, c), demandSelector);
model.Constraint(routeQuantity <= truckCapacity);

// Distance travelled by truck k
LSExpression distSelector = model.Function(i => distanceArray[sequence[i - 1], sequence[i]]);
routeDistances[k] = model.Sum(model.Range(1, c), distSelector)
+ model.If(c > 0, distanceWarehouseArray[sequence[0]] + distanceWarehouseArray[sequence[c - 1]], 0);

//End of each visit
LSExpression endSelector = model.Function( (i,prev) => model.Max(earliestArray[sequence[i]],
model.If(i == 0,
distanceWarehouseArray[sequence[0]],
prev + distanceArray[sequence[i-1],sequence[i]])) +
serviceArray[sequence[i]] );

endTime[k] = model.Array(model.Range(0,c), endSelector);

// Arriving home after max_horizon
homeLateness[k] = model.If(trucksUsed[k],
model.Max(0,endTime[k][c-1] + distanceWarehouseArray[sequence[c-1]] - maxHorizon),
0);

//completing visit after latest_end
LSExpression lateSelector = model.Function( i => model.Max(endTime[k][i] - latestArray[sequence[i]],0));
lateness[k] = homeLateness[k] + model.Sum(model.Range(0,c),lateSelector);
}

totalLateness = model.Sum(lateness);
nbTrucksUsed = model.Sum(trucksUsed);
totalDistance = model.Round(100*model.Sum(routeDistances))/100;

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

model.Close();

// Parameterizes the solver.
LSPhase phase = localsolver.CreatePhase();
phase.SetTimeLimit(limit);

localsolver.Solve();
}

// Writes the solution in a file with the following format :
//  - number of trucks used and total distance
//  - for each truck the nodes visited (omitting the start/end at the depot)
void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine(nbTrucksUsed.GetValue() + " " + totalDistance.GetDoubleValue());
for (int k = 0; k < nbTrucks; k++)
{
if (trucksUsed[k].GetValue() != 1) continue;
// 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 (int i = 0; i < customersCollection.Count(); i++)
{
output.Write((customersCollection[i] + 2) + " ");
}
output.WriteLine();
}
}
}

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

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

if (line == null) return new string[0];
return line.Split(new [] {' '}, StringSplitOptions.RemoveEmptyEntries);
}

// The input files follow the "Solomon" format.
{
{
string[] splitted;

splitted = SplitInput(input);
nbTrucks = int.Parse(splitted[0]);
truckCapacity = int.Parse(splitted[1]);

splitted = SplitInput(input);
int depotX = int.Parse(splitted[1]);
int depotY = int.Parse(splitted[2]);
maxHorizon = int.Parse(splitted[5]);

List<int> customersX = new List<int>();
List<int> customersY = new List<int>();
demands = new List<int>();
earliestStart = new List<int>();
latestEnd = new List<int>();
serviceTime = new List<int>();

while(!input.EndOfStream)
{
splitted = SplitInput(input);
if (splitted.Length < 7) break;
int due = int.Parse(splitted[5]);
int service = int.Parse(splitted[6]);

latestEnd.Add(due+service);//in input files due date is meant as latest start time
}

nbCustomers = customersX.Count;

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

// Computes the distance matrix
private void ComputeDistanceMatrix(int depotX, int depotY, List<int> customersX, List<int> customersY)
{
distanceMatrix = new double[nbCustomers][];
for (int i = 0; i < nbCustomers; i++)
distanceMatrix[i] = new double[nbCustomers];

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

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

private double ComputeDist(int xi, int xj, int yi, int yj)
{
return Math.Sqrt(Math.Pow(xi - xj, 2) + Math.Pow(yi - yj, 2));
}

}
```
Compilation / Execution (Windows)
javac Cvrptw.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Cvrptw instances\R101.25.txt
Compilation/Execution (Linux)
javac Cvrptw.java -cp /opt/localsolver_XXX/bin/localsolver.jar
java -cp /opt/localsolver_XXX/bin/localsolver.jar:. Cvrptw instances/R101.25.txt
```/********** Cvrptw.java **********/

import java.util.*;
import java.io.*;
import localsolver.*;

public class Cvrptw {
// Solver
private LocalSolver localsolver;

// Number of customers (= number of nodes minus 1)
int nbCustomers;

// Capacity of the trucks
private int truckCapacity;

// Latest allowed arrival to depot
int maxHorizon;

// Demand on each node
List<Integer> demands;

// Earliest arrival on each node
List<Integer> earliestStart;

// Latest departure from each node
List<Integer> latestEnd;

// Service time on each node
List<Integer> serviceTime;

// Distance matrix
private double[][] distanceMatrix;

// Distances between customers and warehouse
private double[] distanceWarehouses;

// Number of trucks
private int nbTrucks;

// Decision variables

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

// Distance travelled by each truck
private LSExpression[] routeDistances;

// End time array for each truck
private LSExpression[] endTime;

// Home lateness for each truck
private LSExpression[] homeLateness;

// Cumulated Lateness for each truck
private LSExpression[] lateness;

// Cumulated lateness in the solution (must be 0 for the solution to be valid)
private LSExpression totalLateness;

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

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

private Cvrptw() {
localsolver = new LocalSolver();
}

private void readInstance(String fileName) throws IOException {
}

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

trucksUsed = new LSExpression[nbTrucks];
routeDistances = new LSExpression[nbTrucks];
endTime = new LSExpression[nbTrucks];
homeLateness = new LSExpression[nbTrucks];
lateness = new LSExpression[nbTrucks];

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

// All customers must be visited by the trucks

// Create demands and distances as arrays to be able to access it with an "at" operator
LSExpression demandsArray = model.array(demands);
LSExpression earliestArray = model.array(earliestStart);
LSExpression latestArray = model.array(latestEnd);
LSExpression serviceArray = model.array(serviceTime);

LSExpression distanceWarehouseArray = model.array(distanceWarehouses);
LSExpression distanceArray = model.array(distanceMatrix);

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 demandSelector = model.function(i -> model.at(demandsArray, model.at(sequence, i)));
LSExpression routeQuantity = model.sum(model.range(0, c), demandSelector);
model.constraint(model.leq(routeQuantity, truckCapacity));

// Distance traveled by truck k
LSExpression distSelector = model.function(i -> model.at(
distanceArray,
model.at(sequence, model.sub(i, 1)),
model.at(sequence, i)));
routeDistances[k] = model.sum(model.sum(model.range(1, c), distSelector),
model.iif(model.gt(c, 0), model.sum(
model.at(distanceWarehouseArray, model.at(sequence, 0)),
model.at(distanceWarehouseArray, model.at(sequence, model.sub(c, 1)))),  0));

//End of each visit
LSExpression endSelector = model.function( (i,prev) -> model.sum(
model.max(model.at(earliestArray,model.at(sequence,i)),
model.sum(model.iif(model.eq(i,0),
model.at(distanceWarehouseArray,model.at(sequence,0)),
model.sum(prev, model.at(distanceArray, model.at(sequence,model.sub(i,1)),model.at(sequence,i)))))),
model.at(serviceArray,model.at(sequence,i)) ));

endTime[k] = model.array(model.range(0,c), endSelector);

LSExpression theEnd = endTime[k];

// Arriving home after max_horizon
homeLateness[k] = model.iif(trucksUsed[k],
model.max(0,model.sum(model.at(theEnd,model.sub(c,1)),
model.sub( model.at(distanceWarehouseArray, model.at(sequence, model.sub(c,1))) , maxHorizon))),
0);

//completing visit after latest_end
LSExpression lateSelector = model.function( i -> model.max(model.sub(model.at(theEnd,i), model.at(latestArray,model.at(sequence,i))),0));
lateness[k] = model.sum(homeLateness[k], model.sum(model.range(0,c),lateSelector));
}

totalLateness = model.sum(lateness);
nbTrucksUsed = model.sum(trucksUsed);
totalDistance = model.div(model.round(model.prod(100,model.sum(routeDistances))),100);

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

model.close();

// Parameterizes the solver.
LSPhase phase = localsolver.createPhase();
phase.setTimeLimit(limit);

localsolver.solve();
}

// Writes the solution in a file with the following format :
// - number of trucks used and total distance
// - for each truck the nodes visited (omitting the start/end at the depot)
private void writeSolution(String fileName) throws IOException {
try(PrintWriter output = new PrintWriter(fileName)) {
output.println(nbTrucksUsed.getValue() + " " + totalDistance.getDoubleValue());
for (int k = 0; k < nbTrucks; k++) {
if (trucksUsed[k].getValue() != 1) continue;
// 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 (int i = 0; i < customersCollection.count(); i++) {
output.print((customersCollection.get(i) + 2) + " ");
}
output.println();
}
}
}

// The input files follow the "Solomon" format.
private void readInputCvrptw(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
int nbNodes = 0;
int dump = 0;

input.nextLine();
input.nextLine();
input.nextLine();
input.nextLine();

nbTrucks = input.nextInt();
truckCapacity = input.nextInt();

input.nextLine();
input.nextLine();
input.nextLine();
input.nextLine();

dump = input.nextInt();
int depotX = input.nextInt();
int depotY = input.nextInt();
dump = input.nextInt();
dump = input.nextInt();
maxHorizon = input.nextInt();
dump = input.nextInt();

List<Integer> customersX = new ArrayList<Integer>();
List<Integer> customersY = new ArrayList<Integer>();
demands = new ArrayList<Integer>();
earliestStart = new ArrayList<Integer>();
latestEnd = new ArrayList<Integer>();
serviceTime = new ArrayList<Integer>();

while (input.hasNextInt()) {
dump = input.nextInt();
int cx = input.nextInt();
int cy = input.nextInt();
int demand = input.nextInt();
int due = input.nextInt();
int service = input.nextInt();

latestEnd.add(due+service);//in input files due date is meant as latest start time
}

nbCustomers = customersX.size();

computeDistanceMatrix(depotX, depotY, customersX, customersY);

}
}

// Computes the distance matrix
private void computeDistanceMatrix(int depotX, int depotY, List<Integer> customersX, List<Integer> customersY) {
distanceMatrix = new double[nbCustomers][nbCustomers];
for (int i = 0; i < nbCustomers; i++) {
distanceMatrix[i][i] = 0;
for (int j = i + 1; j < nbCustomers; j++) {
double dist = computeDist(customersX.get(i), customersX.get(j), customersY.get(i), customersY.get(j));
distanceMatrix[i][j] = dist;
distanceMatrix[j][i] = dist;
}
}

distanceWarehouses = new double[nbCustomers];
for(int i = 0; i < nbCustomers; ++i) {
distanceWarehouses[i] = computeDist(depotX, customersX.get(i), depotY, customersY.get(i));
}
}

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

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

try {
String instanceFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "20";

Cvrptw model = new Cvrptw();