Another example of a permutation problem is the capacitated vehicle routing problem (cvrp). In this problem, we are looking for a “partitioned permutation”. A partitioned permutation is a permutation partitioned into subsequences. For example, the permutation {2, 3, 4, 1, 9, 8, 5, 6, 7, 10} could be partitioned into 3 subsequences as follows:
The first subsequence is {2, 3, 4}, the second is {1, 9, 8, 5}, etc. this is exactly what is needed for the capacitated vehicle routing problem.
Problem
A fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. An concrete application is given in cvrp. The models cvrp1, cvrp2, and cvrp3 give MIPformulations of the problem. These formulations are explained in my book Case Studies I.
To interpret this problem as a “partitioned permutation” problem is easy: Starting at a depot, the first vehicle visits the customers in the first subsequence and returns to the depot, the second vehicle, also starting from the depot, visits the customers in the second subsequence and returns to the depot, etc. Note that the depot is not part of the sequences itself.
Modeling Steps
Let i,j ∈ I = {1,…,n  1} be a set of customer locations (n is the number of locations including the warehouse (or the depot) and let k ∈ K = {1,…,m} be a set of trucks. Let the capacity of each truck be CA, and let the demand quantity to deliver to a customer i be dem_{i}. Furthermore, the distance between two customer i and j is d_{i,j}. Finally, the distance from the warehouse – the depot from where the trucks start – to each customer i is dw_{i}.
The customers are enumerated with integers from 1 to n  1. If there were one single truck (that must visits all customers), every permutation sequence of the numbers 1 to n  1 would define a legal tour. Since we have m trucks, to each truck a sequence of a subset of 1 to n  1 must be assigned. Hence, each truck starts at the depot, visiting a (disjoint) subset of customers in a given order and returns to the depot.
The variables can now be formulated as a “partitioned permutation”. In LPL, we can declare these partitioned permutation with a (sparse) permutation variable x_{k,i} ∈ [1…n  1]. For example, for the example above we have :

Note that the twodimensional table is sparse – it only contains n 1 entries. The symbol ““ (dash) means: no entry. Hence, x_{1,1} = 2 means that the customer 2 is visited by the truck 1 right after the depot, x_{1,2} = 3 means that the next customer (after 2) is 3, etc.
The unique constraint that must hold for the partitioned permutation is the capacity of the trucks: each subset sequence must be chosen in such a way that the capacity of the truck is larger than the cumulated demand of the customers that it visits – note, the variables x_{k,i} are used as indexes as well as in the condition of the summation:
We want to minimize the total travel distance of the trucks. Let cc_{k} be the size of the subset k (the numbers of customers that the truck k visits). (In the example above c_{k} = {3, 4, 3}.) Of course, these numbers is variable and cannot be given in advance! Let routeDistances_{k} be the (unknown) travel distance of truck k, then we want to minimize the total distances:
where
The term dw_{xk,1} denotes the distance of the truck k from the depot to the first customer, and dw_{xk,cc k} is the distance of the truck tour k from the last customer to the depot, d_{xk,i1,xk,i} is the distance from a customer to the next, and ∑ _{i∈2..cck}… sums that distances of a tour k.
As a variant we may also minimize, in a first round, the number of trucks used – this is added as a comment in the code:
model cvrp "Capacitated Vehicle Routing Problem";
set i,j "customers";
k "trucks";
parameter
d{i,j} "distances";
dw{i} "distance from/to the warehouse";
dem{i} "demand";
CA "truck capacity";
alldiff x{k,i} 'partition';
expression
cc{k}: count{i} x;
trucksUsed{k}: cc[k] > 0;
routeDistances{k}: sum{i in 2..cc} d[x[k,i1],x[k,i]]
+ if(cc[k]>0, dw[x[k,1]] + dw[x[k,cc[k]]]);
nbTrucksUsed: sum{k} trucksUsed[k];
totalDistance: sum{k} routeDistances[k];
constraint CAP{k}: sum{ix} dem[x[k,i]] <= CA;
minimize obj1: nbTrucksUsed;
minimize obj2: totalDistance;
end
Further Comments
The question is now what solver can solve this kind of model! I developed a simple Tabusearch solver that can deliver near optimal solution for small simple permutation problems, but not for partitioned permutation problems. However, there is a powerful commercial solver called LocalSolver that can find near optimal solutions to large problems. LPL contains an (experimental) interface to that solver.
Solution
The LPL data code reads the “An32k5.vrp” file from the Augerat et al. Set A instances.
model data;
set h; //h is i plus 1, 1 is depot (warehouse)
parameter de{h}; n; m; X{h}; Y{h}; string typ; dum;
Read('An32k5.vrp,%1;1:DIMENSION',dum,dum,n);
Read('An45k6.vrp,%1;1:DIMENSION',dum,dum,n);
Read('%1;1:EDGE_WEIGHT_TYPE',dum,dum,typ);
if typ<>'EUC_2D' then Write('Only EUC_2D is supported' n'); return 0; end;
Read('%1;1:CAPACITY',dum,dum,CA);
Read{h}('%1:NODE_COORD_SECTION:DEMAND_SECTION', dum,X,Y);
Read{h}('%1:DEMAND_SECTION:DEPOT_SECTION', dum,de);
m:=Ceil(sum{h} de/CA);
k:=1..m;
i:=1..n1;
d{i,j}:=Round(Sqrt((X[i+1]X[j+1])^2+(Y[i+1]Y[j+1])^2));
dem{i}:=de[i+1];
dw{i}:=Round(Sqrt((X[i+1]X[1])^2+(Y[i+1]Y[1])^2));
end
The LocalSolver finds the optimal solution (see 6) after 25secs