This page is for an old version of Hexaly Optimizer.
We recommend that you update your version and read the documentation for the
latest stable release.
Pick-up and delivery with time windows¶
Principles learned¶
- Add multiple list decision variables
- Use a lambda expression to define a recursive array
- Define a sequence of expressions
- Use of “contains” and “indexOf” operators
Problem¶
In the pickup-and-delivery problem with tiwe-windows (PDPTW), a fleet of delivery vehicles with uniform capacity must collect and deliver items according to the demand of customers, and must do so during their opening hours. 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 to assign a sequence of customers to each truck of the fleet minimizing the total distance traveled such that each item is picked up then delivered by the same vehicle, and the capacity of the truck is respected at any point in the tour.
Download the exampleData¶
The instances provided come from the Li & Lim instances.
The format of the data files is as follows:
The first line gives the number of vehicules, the capacity and the speed (not used)
From the 2nd 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
- The index of the corresponding pickup order (0 if the order is a delivery)
- The index of the corresponding delivery order (0 if the order is a pickup).
Program¶
The LocalSolver model is an extension of the CVRPTW model. We refer the reader to this model for the routing and the time-windows aspects of the problem.
The situation of the pickup-and-delivery problem induces three new constraints:
- Each pickup/delivery pair must be assigned to the same tour
- Within this tour, the pickup cannot be visited after the delivery (we cannot deliver an item that has not been picked up yet)
- The weight of the truck will vary along the tour (increasing upon pickups and decreasing upon deliveries) and the capacity constraint must be satisfied at any time during the tour.
Considering each list in the LocalSolver model, the first requirement for a
pickup/delivery pair (a,b) means that either a and b both belong to the list or none
of them belongs to the list. Literally it means that
contains(sequence[k], a) == contains(sequence[k], b).
As for the ordering of the pair within the list, it is related to the position of a
and b within the list, which can be obtained with the indexOf operator:
constraint indexOf(sequence[k], a) <= indexOf(sequence[k], b).
Note that indexOf takes values -1 when searching for an item that is not contained in
the list. Consequently writing a strict inequality on this constraint would be an
error because it would not allow both items to be outside of the list.
As mentioned above, the last specificity is that the capacity constraint must now be checked after each visit. To do this, we need to define the weight after a visit as the weight before the visit plus the weight of the current item (positive if loaded, negative if delivered).
The objectives are the same as for the CVRTW problem: we minimize the total lateness, the number of trucks used, and the total distance traveled by all the trucks.
- Execution:
- localsolver pdptw.lsp inFileName=instances/lc101.txt [lsTimeLimit=] [solFileName=]
/********** pdptw.lsp **********/
use io;
/* The input files follow the "Li & Lim" format.*/
function input() {
usage = "\nUsage: localsolver pdptw.lsp "
+ "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]\n";
if (inFileName == nil) throw usage;
readInputPdptw();
// Compute distance matrix
computeDistanceMatrix();
if (nbMaxTrucks != nil) {
nbTrucks = nbMaxTrucks;
}
}
/* Declares the optimization model. */
function model() {
customersSequences[k in 1..nbTrucks] <- list(nbCustomers);
// All customers must be visited by the trucks
constraint partition[k in 1..nbTrucks](customersSequences[k]);
for[k in 1..nbTrucks] {
local sequence <- customersSequences[k];
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
// at any point in the sequence
routeQuantity[k] <- array(0..c-1, (i, prev) => prev + demands[sequence[i]]);
constraint and(0..c-1, i => routeQuantity[k][i] <= truckCapacity);
// Pickups and deliveries are done in the same route and delivery is done
// after pickup :
for[i in 0..nbCustomers-1 : pickupIndex[i] == -1]{
constraint contains(sequence, i) == contains(sequence, deliveryIndex[i]);
constraint indexOf(sequence, i) <= indexOf(sequence, deliveryIndex[i]);
}
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
totalDistance <- round(100 * sum[k in 1..nbTrucks](routeDistances[k]))/100;
minimize totalLateness;
if (nbMaxTrucks == nil) 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;
for [customer in customersSequences[k].value] {
outfile.print(customer + 1, " ");
}
outfile.println();
}
}
function readInputPdptw() {
local inFile = io.openRead(inFileName);
// Truck related data
nbTrucks = inFile.readInt();
truckCapacity = inFile.readInt();
speed = inFile.readInt(); // not used
// Warehouse data
local line = inFile.readln().split(" ");
warehouseIndex = line[0].toInt();
warehouseX = line[1].toInt();
warehouseY = line[2].toInt();
maxHorizon = line[5].toInt();
// Customers data
i = 0;
while (!inFile.eof()) {
inLine = inFile.readln();
line = inLine.split(" ");
if(count(line) == 0) break;
if(count(line) != 9) 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
pickupIndex[i] = line[7].toInt() - 1;
deliveryIndex[i] = line[8].toInt() - 1;
i = i + 1;
}
nbCustomers = i;
inFile.close();
}
function skipLines(inFile,nbLines) {
if (nbLines < 1) return;
local dump = inFile.readln();
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 pdptw.py instances\lc101.txt
- Execution (Linux)
- export PYTHONPATH=/opt/localsolver_XXX/bin/python27/python pdptw.py instances/lc101.txt
########## pdptw.py ##########
import localsolver
import sys
import math
def read_elem(filename):
with open(filename) as f:
return [str(elem) for elem in f.read().split()]
def main(instance_file, str_time_limit, sol_file):
#
# Reads instance data
#
(nb_customers, nb_trucks, truck_capacity, distance_matrix, distance_warehouses, demands, service_time, earliest_start,latest_end, pickUpIndex, deliveryIndex, max_horizon) = read_input_pdptw(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_array.add_operand(model.array(distance_matrix[n]))
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)
# The quantity needed in each route must not exceed the truck capacity at any point in the sequence
demand_cumulator = model.function(lambda i, prev: prev + model.at(demands_array, sequence[i]))
route_quantity = model.array(model.range(0, c), demand_cumulator)
quantity_checker = model.function(lambda i: model.at(route_quantity, i) <= truck_capacity)
model.constraint(model.and_(model.range(0, c), quantity_checker))
# Pickups and deliveries
for i in range(nb_customers) :
if pickUpIndex[i] == -1 :
model.constraint(model.contains(sequence, i) == model.contains(sequence, deliveryIndex[i]))
model.constraint(model.index(sequence, i) <= model.index(sequence, deliveryIndex[i]))
# Distance travelled 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 (must be 0 for the solution to be valid)
total_lateness = model.sum(lateness)
# Total distance traveled
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.param.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 %.2f\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 "Li & Lim" format
def read_input_pdptw(filename):
file_it = iter(read_elem(sys.argv[1]))
nb_trucks = int(next(file_it))
truck_capacity = int(next(file_it))
speed = int(next(file_it))
next(file_it)
warehouse_x = int(next(file_it))
warehouse_y = int(next(file_it))
for i in range(2): next(file_it)
max_horizon = int(next(file_it))
for i in range(3): next(file_it)
customers_x = []
customers_y = []
demands = []
earliest_start = []
latest_end = []
service_time = []
pickUpIndex = []
deliveryIndex = []
while(1):
val = next(file_it, None)
if (val is None) : break
i = int(val) - 1
customers_x.append(int(next(file_it)))
customers_y.append(int(next(file_it)))
demands.append(int(next(file_it)))
ready = int(next(file_it))
due = int(next(file_it))
stime = int(next(file_it))
pick = int(next(file_it))
delivery = int(next(file_it))
earliest_start.append(ready)
latest_end.append(due + stime) # in input files due date is meant as latest start time
service_time.append(stime)
pickUpIndex.append(pick - 1)
deliveryIndex.append(delivery - 1)
nb_customers = i + 1
# Computes 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, pickUpIndex, deliveryIndex, 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 the 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 pdptw.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 pdptw.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver.dll.libpdptw instances\lc101.txt
- Compilation / Execution (Linux)
- g++ pdptw.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o pdptw./pdptw instances/lc101.txt
/********** pdptw.cpp **********/
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <cmath>
#include "localsolver.h"
using namespace localsolver;
using namespace std;
class Pdptw {
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;
// Index for pickup for each node
vector<lsint> pickUpIndex;
// Index for delivery for each node
vector<lsint> deliveryIndex;
// Distance matrix between customers
vector<vector<lsdouble> > distanceMatrix;
// Distances between customers and warehouse
vector<lsdouble> distanceWarehouses;
// Number of trucks
int nbTrucks;
// Decision variables
vector<LSExpression> customersSequences;
// 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 traveled by all the trucks
LSExpression totalDistance;
// Constructor
Pdptw() {
}
// Reads instance data
void readInstance(const string& fileName) {
readInputPdptw(fileName);
}
void solve(int limit) {
// Declares the optimization model
LSModel model = localsolver.getModel();
// Sequence of customers visited by each truck
customersSequences.resize(nbTrucks);
for (int k = 0; k < nbTrucks; k++) {
customersSequences[k] = model.listVar(nbCustomers);
}
// All customers must be visited by the trucks
model.constraint(model.partition(customersSequences.begin(), customersSequences.end()));
// 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 access it with an "at" operator
LSExpression distanceArray = model.array();
for (int n = 0; n < nbCustomers; n++) {
distanceArray.addOperand(model.array(distanceMatrix[n].begin(), distanceMatrix[n].end()));
}
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 sequence = customersSequences[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 at any point in the sequence
LSExpression demandCumulator = model.createFunction([&](LSExpression i, LSExpression prev) { return prev + demandsArray[sequence[i]]; });
LSExpression routeQuantity = model.array(model.range(0, c), demandCumulator);
LSExpression quantityChecker = model.createFunction([&](LSExpression i) { return routeQuantity[i] <= truckCapacity; });
model.constraint(model.and_(model.range(0, c), quantityChecker));
// Pickups and deliveries
for (int i = 0; i<nbCustomers; i++) {
if (pickUpIndex[i] == -1){
model.constraint(model.contains(sequence, i) == model.contains(sequence, deliveryIndex[i]));
model.constraint(model.indexOf(sequence, i) <= model.indexOf(sequence, deliveryIndex[i]));
}
}
// Distance travelled 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 number of trucks used
nbTrucksUsed = model.sum(trucksUsed.begin(), trucksUsed.end());
// Total distance traveled
totalDistance = model.round(100 * model.sum(routeDistances.begin(), routeDistances.end()))/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
localsolver.getParam().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.exceptions(ofstream::failbit | ofstream::badbit);
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)
LSCollection customersCollection = customersSequences[k].getCollectionValue();
for (lsint i = 0; i < customersCollection.count(); i++) {
outfile << customersCollection[i] + 2 << " ";
}
outfile << endl;
}
}
private:
// The input files follow the "Li & Lim" format.
void readInputPdptw(const string& fileName) {
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;
infile >> nbTrucks;
infile >> truckCapacity;
infile >> dump;
infile >> dump;
infile >> depotX;
infile >> depotY;
infile >> dump;
infile >> dump;
infile >> maxHorizon;
infile >> dump;
infile >> dump;
infile >> dump;
while (!infile.eof()) {
int cx,cy,demand,ready,due,service,pick,delivery;
infile >> dump;
infile >> cx;
infile >> cy;
infile >> demand;
infile >> ready;
infile >> due;
infile >> service;
infile >> pick;
infile >> delivery;
customersX.push_back(cx);
customersY.push_back(cy);
demands.push_back(demand);
earliestStart.push_back(ready);
latestEnd.push_back(due+service); // in input files due date is meant as latest start time
serviceTime.push_back(service);
pickUpIndex.push_back(pick - 1);
deliveryIndex.push_back(delivery - 1);
}
nbCustomers = customersX.size();
// Computes 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: pdptw inputFile [outputFile] [timeLimit]" << endl;
return 1;
}
const char* instanceFile = argv[1];
const char* solFile = argc > 2 ? argv[2] : NULL;
const char* strTimeLimit = argc > 3 ? argv[3] : "20";
try {
Pdptw model;
model.readInstance(instanceFile);
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 Pdptw.cs /reference:localsolvernet.dllPdptw instances\lc101.txt
/********** Pdptw.cs **********/
using System;
using System.IO;
using System.Collections.Generic;
using localsolver;
public class Pdptw : IDisposable
{
// Solver
LocalSolver localsolver;
// Number of customers
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;
// Index for pick up for each node
List<int> pickUpIndex;
// Index for delivery for each node
List<int> deliveryIndex;
// Distance matrix between customers
double[][] distanceMatrix;
// Distances between customers and warehouse
double[] distanceWarehouses;
// Number of trucks
int nbTrucks;
// Decision variables
LSExpression[] customersSequences;
// Are the trucks actually used
LSExpression[] trucksUsed;
// Distance traveled 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 traveled by all the trucks
LSExpression totalDistance;
public Pdptw()
{
localsolver = new LocalSolver();
}
// Reads instance data.
void ReadInstance(string fileName)
{
ReadInputPdptw(fileName);
}
public void Dispose()
{
if (localsolver != null)
localsolver.Dispose();
}
void Solve(int limit)
{
// Declares the optimization model
LSModel model = localsolver.GetModel();
trucksUsed = new LSExpression[nbTrucks];
customersSequences = 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++)
customersSequences[k] = model.List(nbCustomers);
// All customers must be visited by the trucks
model.Constraint(model.Partition(customersSequences));
// Create demands and distances as arrays to be able to access them 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 sequence = customersSequences[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 at any point in the sequence
LSExpression demandCumulator = model.Function((i, prev) => prev + demandsArray[sequence[i]]);
LSExpression routeQuantity = model.Array(model.Range(0, c), demandCumulator);
LSExpression quantityChecker = model.Function(i => routeQuantity[i] <= truckCapacity);
model.Constraint(model.And(model.Range(0, c), quantityChecker));
// Pickups and deliveries
for (int i = 0; i < nbCustomers; i++)
{
if (pickUpIndex[i] == -1)
{
model.Constraint(model.Contains(sequence, i) == model.Contains(sequence, deliveryIndex[i]));
model.Constraint(model.IndexOf(sequence, i) <= model.IndexOf(sequence, deliveryIndex[i]));
}
}
// Distance traveled 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
localsolver.GetParam().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)
LSCollection customersCollection = customersSequences[k].GetCollectionValue();
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: Pdptw 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 (Pdptw model = new Pdptw())
{
model.ReadInstance(instanceFile);
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
private string[] SplitInput(StreamReader input) {
string line = input.ReadLine();
if (line == null) return new string[0];
return line.Split(new [] {'\t'}, StringSplitOptions.RemoveEmptyEntries);
}
// The input files follow the "Li & Lim" format
private void ReadInputPdptw(string fileName)
{
using (StreamReader input = new StreamReader(fileName))
{
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>();
pickUpIndex = new List<int>();
deliveryIndex = new List<int>();
while(!input.EndOfStream)
{
splitted = SplitInput(input);
if (splitted.Length < 9) break;
customersX.Add(int.Parse(splitted[1]));
customersY.Add(int.Parse(splitted[2]));
demands.Add(int.Parse(splitted[3]));
int ready = int.Parse(splitted[4]);
int due = int.Parse(splitted[5]);
int service = int.Parse(splitted[6]);
pickUpIndex.Add(int.Parse(splitted[7]) - 1);
deliveryIndex.Add(int.Parse(splitted[8]) - 1);
earliestStart.Add(ready);
latestEnd.Add(due + service); // in input files due date is meant as latest start time
serviceTime.Add(service);
}
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 Pdptw.java -cp %LS_HOME%\bin\localsolver.jarjava -cp %LS_HOME%\bin\localsolver.jar;. Pdptw instances\lc101.txt
- Compilation / Execution (Linux)
- javac Pdptw.java -cp /opt/localsolver_XXX/bin/localsolver.jarjava -cp /opt/localsolver_XXX/bin/localsolver.jar:. Pdptw instances/lc101.txt
/********** Pdptw.java **********/
import java.util.*;
import java.io.*;
import localsolver.*;
public class Pdptw {
// Solver
private LocalSolver localsolver;
// Number of customers
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;
// Index for pick up for each node
List<Integer> pickUpIndex;
// Index for delivery for each node
List<Integer> deliveryIndex;
// Distance matrix between customers
private double[][] distanceMatrix;
// Distances between customers and warehouse
private double[] distanceWarehouses;
// Number of trucks
private int nbTrucks;
// Decision variables
private LSExpression[] customersSequences;
// Are the trucks actually used
private LSExpression[] trucksUsed;
// Distance traveled 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 Pdptw() {
localsolver = new LocalSolver();
}
// Reads instance data
private void readInstance(String fileName) throws IOException {
readInputPdptw(fileName);
}
private void solve(int limit) {
// Declares the optimization model
LSModel model = localsolver.getModel();
trucksUsed = new LSExpression[nbTrucks];
customersSequences = 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++)
customersSequences[k] = model.listVar(nbCustomers);
// All customers must be visited by the trucks
model.constraint(model.partition(customersSequences));
// Create demands and distances as arrays to be able to access them 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 sequence = customersSequences[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 at any point in the sequence
LSExpression demandCumulator = model.function((i, prev) -> model.sum(prev, model.at(demandsArray, model.at(sequence, i))));
LSExpression routeQuantity = model.array(model.range(0, c), demandCumulator);
LSExpression quantityChecker = model.function(i -> model.leq(model.at(routeQuantity, i), truckCapacity));
model.constraint(model.and(model.range(0, c), quantityChecker));
// Pickups and deliveries
for (int i = 0; i < nbCustomers; i++) {
if (pickUpIndex.get(i) == -1) {
model.constraint(model.eq(model.contains(sequence, i), model.contains(sequence, deliveryIndex.get(i))));
model.constraint(model.leq(model.indexOf(sequence, i), model.indexOf(sequence, deliveryIndex.get(i))));
}
}
// 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
localsolver.getParam().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)
LSCollection customersCollection = customersSequences[k].getCollectionValue();
for (int i = 0; i < customersCollection.count(); i++) {
output.print((customersCollection.get(i) + 2) + " ");
}
output.println();
}
}
}
// The input files follow the "Li & Lim" format
private void readInputPdptw(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
int nbNodes = 0;
int dump = 0;
nbTrucks = input.nextInt();
truckCapacity = input.nextInt();
dump = input.nextInt();
dump = input.nextInt();
int depotX = input.nextInt();
int depotY = input.nextInt();
dump = input.nextInt();
dump = input.nextInt();
maxHorizon = input.nextInt();
dump = input.nextInt();
dump = 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>();
pickUpIndex = new ArrayList<Integer>();
deliveryIndex = new ArrayList<Integer>();
while (input.hasNextInt()) {
dump = input.nextInt();
int cx = input.nextInt();
int cy = input.nextInt();
int demand = input.nextInt();
int ready = input.nextInt();
int due = input.nextInt();
int service = input.nextInt();
int pick = input.nextInt();
int delivery = input.nextInt();
customersX.add(cx);
customersY.add(cy);
demands.add(demand);
earliestStart.add(ready);
latestEnd.add(due+service); // in input files due date is meant as latest start time
serviceTime.add(service);
pickUpIndex.add(pick - 1);
deliveryIndex.add(delivery - 1);
}
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 Pdptw inputFile [outputFile] [timeLimit]");
System.exit(1);
}
try {
String instanceFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "20";
Pdptw model = new Pdptw();
model.readInstance(instanceFile);
model.solve(Integer.parseInt(strTimeLimit));
if (outputFile != null) {
model.writeSolution(outputFile);
}
} catch(Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
}