vrpcc

Vehicle routing problem with capacity constraints.

Attention: Valid only with Altair Advanced Optimization Extension

Syntax

[CarsUsed,Petals,PetalVol,PetalCost,totalCost] = vrpcc(D, RC, CA, CC, CV)

[CarsUsed,Petals,PetalVol,PetalCost,totalCost] = vrpcc(D, RC, CA, CC, CV, options)

Inputs

D
A distance matrix such that D(i,j) is the distance from site i to site j. Site 1 is the common depot from which all vehicles begin their tours, and the other sites are for the N customers.
RC
The customer requirements, a vector containing the demand from each customer.
CA
The car availabilities, a vector containing the number of vehicles of each of M types in the fleet.
CC
The car costs, either a vector or a matrix containing the cost of each vehicle type.
For a vector, the cost of each vehicle type per unit of distance.
For a matrix, an element CC(i,j,k) is the travel cost from site i to site j for each vehicle type k. The matrix thus has dimensions (N+1) x (N+1) x M. The matrix must be passed as CC(:).
CV
The car volumes, a vector containing the maximum capacity of each vehicle type, in the same units as RC.
options
A struct containing the genetic algorithm option settings.
The available options are:
  • Generations: The maximum number of generations or iterations allowed.
  • PopulationSize: The size of the population.
  • Seed: The seed for the random number generator.
See gaoptimset for details.

Outputs

CarsUsed
A vector containing the type of each vehicle used.
Petals
A column vector of cells, with a cell for each vehicle used. Each cell is a petal, a row vector of customer indices traversed by that vehicle.
PetalVol
A vector containing the number of demand units handled by each vehicle used.
PetalCost
A vector containing the travel cost for each vehicle used, including a return to the depot.
totalCost
The total cost to cover the path distances.

Examples

Find a set of paths through the following customer locations map for a maximum of four vehicles, each of which can visit at most five identical customers.

% create customer site list, transposing locations from columns to rows
custsites = [77, -60, -86,  24,  46, -9,   9, 2, 42, -31, -77, -24,  60, 31, 86, -2, -42, -46;
             59,  55, -27, -10, -88, 70, -70, 9, -2, -48, -59,  10, -55, 48, 27, -9,   2,  88].';
depot = [0, 0];

% create distance matrix
numcus = size(custsites, 1);
numdim = numcus + 1;
D = zeros(numdim);

for jj = 2:numdim	% depot to site distances
	s2 = custsites(jj-1,:);
	D(1,jj) = norm(s2-depot);
	D(jj,1) = D(1,jj);
end

for ii = 2:numdim	% site to site distances
	s1 = custsites(ii-1,:);
	
	for jj = ii:numdim
		s2 = custsites(jj-1,:);
		D(ii,jj) = norm(s2-s1);
		D(jj,ii) = D(ii,jj);
	end
end

% find solution
RC = ones(1,numcus);
CA = 4;
CC = 1;
CV = 5;
options = gaoptimset('Seed', 2023);

[CarsUsed,Petals,PetalVol,PetalCost,totalCost] = vrpcc(D, RC, CA, CC, CV, options)

% plot
scatter(custsites(:,1), custsites(:,2), 'ob', 'markersize', 4);
hold on;
legendCell = {'Sites'};

for ii = 1:length(CarsUsed)
	n = length(Petals{ii});
	petalLoc = zeros(n+2,2);
	petalLoc(1,:) = depot;
	petalLoc([2:n+1],:) = custsites(Petals{ii},:);
	petalLoc(n+2,:) = depot;
	plot(petalLoc(:,1), petalLoc(:,2));
	legendCell{ii + 1} = strcat('Path_', num2str(ii));
end

legend(legendCell);
CarsUsed = [Matrix] 1 x 4
1  1  1  1
Petals = 
{
  [1,1] [Matrix] 1 x 5
  16  10  11  3  17
  [2,1] [Matrix] 1 x 5
  14  1  15  9  4
  [3,1] [Matrix] 1 x 5
  12  2  18  6  8
  [4,1] [Matrix] 1 x 3
  13  5  7
}
PetalVol = [Matrix] 1 x 4
5  5  5  3
PetalCost = [Matrix] 1 x 4
233.10327  236.07362  231.82451  228.96328
totalCost = 929.964679
Figure 1. vrpcc figure 1


The function is implemented as a genetic algorithm. The gaoptimset options and defaults are as follows:

  • Generations: 100
  • PopulationSize: 6
  • Seed: 0

Larger numbers of generations and population size allow the search to proceed longer.

A non-zero seed will make the result repeatable.