Evaluating performance
This section is mostly intended for developers and researchers who is interested to understand the solver's performance.
A generate command
A generate command is designed to simplify the process of generating realistic problems in pragmatic format.
It has the following parameters:
- type (required): a format of the problem. So far, only
pragmaticis supported - prototypes (required): a list of files with problem prototype definition. At the moment, it has to be path to
problem in pragmatic format. The prototype problem should contain at least three prototype jobs and one vehicle type,
their properties are used with equal probability to generate jobs/vehicles in the problem. Other properties like
objectives,profilesare copied as is - output (required): a path where to store generated problem
- jobs size (required): amount of jobs to be generated in the plan.
- vehicles size (required): amount of vehicle types to be generated in the fleet.
- area size (optional): half size of the bounding box's side (in meters). The center is identified from bounding box of prototype jobs which is used also when the parameter is omitted.
- locations (optional): a path to the file with list of locations which should be used for jobs instead of generated randomly inside specific bounding box.
Using generate command, you can quickly generate different VRP variants. Usage example:
vrp-cli generate pragmatic -p prototype.json -o generated.json -j 100 -v 5 -a 10000
This command generates a new problem definition with 100 jobs spread uniformly in bounding box with half side 10000 meters.
A check command
A check command is intended to prove feasibility of calculated solution. Both, the problem definition and calculated
solution, are required:
vrp-cli check pragmatic -p problem.json -s solution.json
Algorithm fine tuning
Actual algorithm parameters can be tweaked by supplying configuration file, e.g.:
vrp-cli solve pragmatic problem.json -s solution.json --config tweak.json
Configuration file
{
"evolution": {
"initial": {
"method": {
"type": "cheapest",
"weight": 1
},
"alternatives": {
"methods": [
{
"type": "farthest",
"weight": 1
},
{
"type": "nearest",
"weight": 1
},
{
"type": "gaps",
"min": 2,
"max": 20,
"weight": 1
},
{
"type": "skip-best",
"start": 1,
"end": 2,
"weight": 1
},
{
"type": "regret",
"start": 2,
"end": 3,
"weight": 1
},
{
"type": "blinks",
"weight": 1
},
{
"type": "perturbation",
"probability": 0.33,
"min": -0.2,
"max": 0.2,
"weight": 1
}
],
"maxSize": 4,
"quota": 0.05
}
},
"population": {
"type": "rosomaxa",
"selectionSize": 8,
"maxEliteSize": 2,
"maxNodeSize": 2,
"spreadFactor": 0.75,
"distributionFactor": 0.75,
"rebalanceMemory": 100,
"explorationRatio": 0.9
}
},
"hyper": {
"type": "static-selective",
"operators": [
{
"type": "decomposition",
"maxSelected": 2,
"repeat": 4,
"routes": {
"min": 2,
"max": 4
},
"probability": {
"threshold": {
"jobs": 300,
"routes": 10
},
"phases": [
{
"type": "exploration",
"chance": 0.05
},
{
"type": "exploitation",
"chance": 0.05
}
]
}
},
{
"type": "local-search",
"probability": {
"scalar": 0.05
},
"times": {
"min": 1,
"max": 2
},
"operators": [
{
"weight": 200,
"type": "swap-star"
},
{
"weight": 100,
"type": "inter-route-best",
"noise": {
"probability": 0.1,
"min": -0.1,
"max": 0.1
}
},
{
"weight": 30,
"type": "inter-route-random",
"noise": {
"probability": 0.1,
"min": -0.1,
"max": 0.1
}
},
{
"weight": 30,
"type": "intra-route-random",
"noise": {
"probability": 1,
"min": -0.1,
"max": 0.1
}
}
]
},
{
"type": "ruin-recreate",
"probability": {
"scalar": 1
},
"ruins": [
{
"weight": 100,
"methods": [
{
"probability": 1,
"type": "adjusted-string",
"lmax": 10,
"cavg": 10,
"alpha": 0.01
}
]
},
{
"weight": 10,
"methods": [
{
"probability": 1,
"type": "neighbour",
"min": 8,
"max": 16
}
]
},
{
"weight": 10,
"methods": [
{
"probability": 1,
"type": "worst-job",
"skip": 4,
"min": 8,
"max": 16
}
]
},
{
"weight": 5,
"methods": [
{
"probability": 1,
"type": "cluster",
"min": 8,
"max": 16,
"minItems": 4
}
]
},
{
"weight": 2,
"methods": [
{
"probability": 1,
"type": "close-route"
},
{
"probability": 0.1,
"type": "random-job",
"min": 8,
"max": 16
}
]
},
{
"weight": 1,
"methods": [
{
"probability": 1,
"type": "worst-route"
},
{
"probability": 0.1,
"type": "random-job",
"min": 8,
"max": 16
}
]
},
{
"weight": 1,
"methods": [
{
"probability": 1,
"type": "random-route",
"min": 1,
"max": 4
},
{
"probability": 0.1,
"type": "random-job",
"min": 8,
"max": 16
}
]
}
],
"recreates": [
{
"weight": 50,
"type": "skip-best",
"start": 1,
"end": 2
},
{
"weight": 20,
"type": "regret",
"start": 2,
"end": 3
},
{
"weight": 20,
"type": "cheapest"
},
{
"weight": 10,
"type": "perturbation",
"probability": 0.33,
"min": -0.2,
"max": 0.2
},
{
"weight": 5,
"type": "skip-best",
"start": 3,
"end": 4
},
{
"weight": 5,
"type": "gaps",
"min": 2,
"max": 20
},
{
"weight": 5,
"type": "blinks"
},
{
"weight": 2,
"type": "farthest"
},
{
"weight": 2,
"type": "skip-best",
"start": 4,
"end": 8
},
{
"weight": 1,
"type": "nearest"
},
{
"weight": 1,
"type": "skip-random"
},
{
"weight": 1,
"type": "slice"
}
]
},
{
"type": "local-search",
"probability": {
"scalar": 0.01
},
"times": {
"min": 1,
"max": 2
},
"operators": [
{
"weight": 100,
"type": "inter-route-best",
"noise": {
"probability": 0.1,
"min": -0.1,
"max": 0.1
}
},
{
"weight": 30,
"type": "inter-route-random",
"noise": {
"probability": 0.1,
"min": -0.1,
"max": 0.1
}
},
{
"weight": 30,
"type": "intra-route-random",
"noise": {
"probability": 1,
"min": -0.1,
"max": 0.1
}
},
{
"weight": 100,
"type": "sequence"
}
]
}
]
},
"termination": {
"maxTime": 300,
"maxGenerations": 3000,
"variation": {
"intervalType": "sample",
"value": 3000,
"cv": 1,
"isGlobal": true
}
},
"telemetry": {
"progress": {
"enabled": true,
"logBest": 100,
"logPopulation": 1000,
"dumpPopulation": false
},
"metrics": {
"enabled": false,
"trackPopulation": 1000
}
},
"environment": {
"parallelism": {
"numThreadPools": 6,
"threadsPerPool": 8
},
"logging": {
"enabled": true,
"prefix": "[config.full]"
},
"isExperimental": false
},
"output": {
"includeGeojson": true
}
}
All main parameters are optional and can be omitted to stick with defaults. Check the source code for details.
Intermediate solutions
You can record parameters of intermediate solutions if you enable telemetry via configuration file.