Introduction
This project is about solving Vehicle Routing Problem which is common task in transportation planning and logistics.
Vehicle Routing Problem
From wiki:
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?". It generalises the well-known travelling salesman problem (TSP).
Determining the optimal solution to VRP is NP-hard, so the size of problems that can be solved, optimally, using mathematical programming or combinatorial optimization may be limited. Therefore, commercial solvers tend to use heuristics due to the size and frequency of real world VRPs they need to solve.
Design
Although performance is constantly in focus, a main idea behind projects' design is extensibility: the project aims to support a very wide range of VRP variations known as Rich VRP. This is achieved through various extension points: custom constraints, objective functions, acceptance criteria, etc.
By default, it provides a metaheuristic which can be roughly described as Multi-objective Parthenogenesis based Evolutionary Algorithm with Ruin and Recreate Mutation Operator.
More details can be found in concepts chapter.
Getting Started
This chapter describes basic information regarding the project and gives some instructions how to start with it.
Features
The main focus of the project is to support solving multiple variations of VRP within their combination. This non-complete list describes common VRP variations supported by the project:
-
Capacitated VRP (CVRP): designs optimal delivery routes where each vehicle only travels one route, each vehicle has the same characteristics and there is only one central depot.
-
Heterogeneous Fleet VRP (HFVRP) aka Mixed Fleet VRP: extend CVRP problem by varying the capacities. Also vehicle profiles example shows how to use different routing matrix profiles for different vehicle types, e.g. truck and car.
-
VRP with Time Windows (VRPTW): assumes that deliveries to a given customer must occur in a certain time interval, which varies from customer to customer.
-
VRP with Pickup and Delivery (VRPPD): goods need to be picked up from a certain location and dropped off at their destination. The pick-up and drop-off must be done by the same vehicle, which is why the pick-up location and drop-off location must be included in the same route.
-
VRP with backhauls (VRPB): a vehicle does deliveries as well as pick-ups in one route. Some customers require deliveries (referred to as linehauls) and others require pick-ups (referred to as backhauls).
-
Multi-Depot VRP (MDVRP): assumes that multiple depots are geographically spread among the customers.
-
Multi-Trip VRP (MTVRP): extends the VRP by adding the following constraint: routes have to be assigned to M vehicles in such a way that the total cost of the routes assigned to the same vehicle does not exceed a time horizon T (for instance the duration of a typical working day). See multiple reloads example.
-
Multi-Objective VRP (MOVRP): this variant addresses a need of real life applications, where decision maker should consider not only one objective (for example, total cost), but multiple ones simultaneously, such as amount of tours, unassigned jobs, work balance, etc. See multiple objectives example.
-
Open VRP (OVRP): usually, a route beginning at a given depot must finish at this depot, but in this variation vehicle ends at the last served customer.
-
VRP with Lunch Break (VRPLB): this problem arises when drivers must take pauses during their shift, for example, for lunch breaks. The project supports different types of break: with/without location, time window, time period. See multiple breaks example.
-
VRP with Route Balance (VRPRB): the majority of the problems encountered in industry, particularly in logistics, are multi-objective in nature. The VRPRB variant tries to minimize not only for the cost, but also for balancing workloads between routes. See one of examples.
-
Periodic VRP (PVRP): is used when planning is made over a certain period and deliveries to the customer can be made in different days. In current implementation each customer is visited only once. See multiple shifts example which shows multi-day planning scenario when vehicle can be used multiple times, but on different days.
-
Time dependent VRP (TDVRP): the travel time and distance between two customers or between a customer and the depot depends on time of day.
-
Skill VRP (SVRP): associates some skill(-s) with jobs which is requirement for vehicle to have in order to serve the job.
-
Traveling Salesman Problem (TSP): this is a specific case of VRP when there is only one vehicle.
In general, all these variations can be combined together in one single problem definition in pragmatic
format.
Installation
Install from Docker
The fastest way to try vrp solver on your environment is to use public docker
image from Github Container Registry
(not performance optimized):
docker run -it -v $(pwd):/repo --name vrp-cli --rm ghcr.io/reinterpretcat/vrp/vrp-cli:1.7.4
Install from source
VRP solver is built in Rust. You would need to install cargo
to built it:
cargo build --release
Built binaries can be found in the ./target/release
directory.
Install from Cargo
You can install vrp solver directly with cargo install
:
cargo install vrp-cli
Ensure that your $PATH
is properly configured to source the Crates binaries, and then run solver using the vrp-cli
command.
Defining problem
In general, expressing an arbitrary VRP problem in one simple and universal format is a challenging task. pragmatic
format aims to do that and there are concept and example
sections which describe multiple features it supports in great details. However, it might take some time to get a huge
problem with a lot of jobs and vehicles converted into it.
A csv import
feature might help here.
CSV import
vrp-cli
supports importing jobs and vehicles into pragmatic
json format by the following command:
vrp-cli import csv -i jobs.csv -i vehicles.csv -o problem.json
As you can see from the command, you need to specify jobs and vehicles in two separate csv files in the exact order.
Jobs csv
Jobs csv defines a plan
of the problem and should have the following columns:
ID
(string): an idLAT
(float): a latitudeLNG
(float): a longitudeDEMAND
(integer): a single dimensional demand. Depending on the value, it models different job activities:- positive:
pickup
- negative:
delivery
- zero:
service
- positive:
DURATION
(integer): job duration in minutesTW_START
(date in RFC3999): earliest time when job can be servedTW_END
(date in RFC3999): latest time when job can be served
To model a job with more than one activity (e.g. pickup + delivery), specify same ID
twice. Example:
ID,LAT,LNG,DEMAND,DURATION,TW_START,TW_END
job1,52.52599,13.45413,2,5,2020-07-04T08:00:00Z,2020-07-04T12:00:00Z
job2,52.5225,13.4095,1,3,,
job2,52.5165,13.3808,-1,3,,
job3,52.5316,13.3884,-3,5,2020-07-04T08:00:00Z,2020-07-04T16:00:00Z
job with job2
id specified twice with positive and negative demand, so it will be considered as pickup and delivery job.
Vehicles csv
Vehicles csv defines a fleet
of the problem and should have the following columns:
ID
(string): an unique vehicle type idLAT
(float): a depot latitudeLNG
(float): a depot longitudeCAPACITY
(unassigned integer): a single dimensional vehicle capacityTW_START
(date in RFC3999): earliest time when vehicle can start at depotTW_END
(date in RFC3999): latest time when vehicle should return to depotAMOUNT
(unassigned integer): a vehicle amount of this typePROFILE
(string): a routing profile
This is example of such csv:
ID,LAT,LNG,CAPACITY,TW_START,TW_END,AMOUNT,PROFILE
vehicle1,52.4664,13.4023,40,2020-07-04T08:00:00Z,2020-07-04T20:00:00Z,10,car
vehicle2,52.4959,13.3539,50,2020-07-04T08:00:00Z,2020-07-04T20:00:00Z,20,truck
Limitations
Please note, to keep csv format simple and easy to use, it's limited to just a few, really basic features known as Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). However, for a few jobs/vehices, you can modify the file manually as post-processing step.
Acquiring routing info
Once the problem is represented in pragmatic
format, it's time to get matrix routing data.
Routing locations
The solver does not provide routing functionality, that's why you need to get it manually using unique locations from the problem definition. The process of getting locations for matrix routing and its usage is described here.
Routing matrix approximation
For quick prototyping, pragmatic
format supports distance approximation using haversine formula
within fixed speed for durations. This helps you quickly check how solver works on specific problem variant without
need to acquire routing matrix.
The speed is 10m/s
by default and can be tweaked by setting optional speed
property in a each profile separately.
To use this feature, simply do not pass any matrix by omitting -m
parameter.
Running solver
To run the solver, simply use:
vrp-cli solve pragmatic problem.json -o solution.json -g solution.geojson --log
If you specify --log
option, it will produce some log output which contains various information regarding refinement
process such as costs, amount of routes, time, etc.:
provided 0 initial solutions to start with
configured to use default max-generations (3000) and max-time (300secs)
problem has total jobs: 1000, actors: 250
[0s] created 1 of 1 initial solutions in 471ms
[0s] generation 0 took 472ms, rank: 0, cost: 70928.74(0.000%), tours: 104, unassigned: 0, fitness: (0.000, 104.000, 70928.735)
[0s] population state (phase: initial, speed: 0.00 gen/sec, improvement ratio: 1.000:1.000):
rank: 0, cost: 70928.74(0.000%), tours: 104, unassigned: 0, fitness: (0.000, 104.000, 70928.735)
[3s] generation 100 took 23ms, rank: 0, cost: 65448.21(0.000%), tours: 101, unassigned: 0, fitness: (0.000, 101.000, 65448.214)
[5s] generation 200 took 22ms, rank: 0, cost: 63573.34(0.000%), tours: 101, unassigned: 0, fitness: (0.000, 101.000, 63573.343)
...
[24s] generation 900 took 21ms, rank: 0, cost: 58896.38(0.000%), tours: 98, unassigned: 0, fitness: (0.000, 98.000, 58896.376)
[27s] generation 1000 took 25ms, rank: 0, cost: 58698.43(0.000%), tours: 98, unassigned: 0, fitness: (0.000, 98.000, 58698.427)
[27s] population state (phase: exploration, speed: 36.57 gen/sec, improvement ratio: 0.244:0.243):
rank: 0, cost: 58698.43(0.000%), tours: 98, unassigned: 0, fitness: (0.000, 98.000, 58698.427)
rank: 1, cost: 58698.76(0.001%), tours: 98, unassigned: 0, fitness: (0.000, 98.000, 58698.755)
[30s] generation 1100 took 27ms, rank: 0, cost: 58118.80(0.000%), tours: 98, unassigned: 0, fitness: (0.000, 98.000, 58118.802)
...
[82s] population state (phase: exploitation, speed: 36.48 gen/sec, improvement ratio: 0.178:0.173):
rank: 0, cost: 55847.51(0.000%), tours: 94, unassigned: 0, fitness: (0.000, 94.000, 55847.507)
rank: 1, cost: 55848.46(0.002%), tours: 94, unassigned: 0, fitness: (0.000, 94.000, 55848.457)
[82s] total generations: 3000, speed: 36.48 gen/sec
Once the problem is solved, it will save solution in pragmatic
and geojson
(optional) format.
Extra options
The vrp-cli
supports extra command line arguments which affects behavior of the algorithm.
Search mode
By default, search is mostly performed in exploration mode (broad
) which allows the algorithm to perform better
exploration of a solution space. However, it has slower overall convergence in better local optimum.
You can switch to exploitation mode with deep
setting:
vrp-cli solve pragmatic problem.json --search-mode=deep
In this mode, the algorithm memorizes only the last discovered best known solutions, so it can jump quicker to relatively good local optimum, but suffers more from premature convergence.
A general recommendation is to use deep
on relatively simple dataset and/or when strict time limits should be applied.
Termination criteria
Termination criteria defines when refinement algorithm should stop and return best known solution. At the moment, there are three types which can be used simultaneously:
Max time
Max time specifies duration of solving in seconds:
vrp-cli solve pragmatic problem.json --max-time=600
Max generations
Generation is one refinement step and it can be limited via max-generations parameter:
vrp-cli solve pragmatic problem.json --max-generations=1000
Cost variation
Cost variation stops refinement process when cost does not significantly change:
vrp-cli solve pragmatic problem.json --cost-variation=200,0.1
It calculates coefficient of variation of cost change over
specific amount of generations specified by sample
and stops algorithm when it is below specified threshold
.
Default behavior
Default termination criteria is max 3000 generations and 300 seconds at max.
Initial solution
You can supply initial solution to start with using -i
option.
Writing solution to file
Writing solution into file is controlled by -o
or --out-result
setting. When it is omitted, then solution is written
in std out.
Pragmatic format supports option -g
or --geo-json
which writes solution in separate file in geojson format.
Analyzing results
In this example, solution is returned in a pragmatic
format which model is described in details
here. However, analyzing VRP solution might be a difficult task. That's why
pragmatic
format supports output in geojson format which can be simply
visualized in numerous web based front ends, e.g. geojson.io or using open source tools such
as leaflet
:
To return solution in geojson
format, use extra -g
or --geo-json
option.
Jupyter notebooks
You might want to look at this project. It provides some scripts and jupyter notebooks in order to perform deeper analysis of algorithm behaviour.
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
pragmatic
is 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
,profiles
are 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": {
"size": 1,
"methods": [
{
"weight": 1,
"type": "cheapest"
}
]
},
"population": {
"type": "rosomaxa",
"selectionSize": 12,
"maxEliteSize": 2,
"maxNodeSize": 2,
"spreadFactor": 0.25,
"reductionFactor": 0.1,
"distributionFactor": 0.25,
"learningRate": 0.1,
"rebalanceMemory": 500,
"rebalanceCount": 4,
"explorationRatio": 0.9
}
},
"hyper": {
"type": "static-selective",
"mutations": [
{
"type": "decomposition",
"maxSelected": 2,
"repeat": 4,
"routes": {
"min": 2,
"max": 4
},
"probability": {
"threshold": {
"jobs": 300,
"routes": 10
},
"phases": [
{
"type": "exploration",
"chance": 0.01
},
{
"type": "exploitation",
"chance": 0.02
}
]
}
},
{
"type": "local-search",
"probability": {
"scalar": 0.05
},
"times": {
"min": 1,
"max": 2
},
"operators": [
{
"weight": 100,
"type": "inter-route-best",
"noise": {
"probability": 0.1,
"min": 0.9,
"max": 1.1
}
},
{
"weight": 30,
"type": "inter-route-random",
"noise": {
"probability": 0.1,
"min": 0.9,
"max": 1.1
}
},
{
"weight": 30,
"type": "intra-route-random",
"noise": {
"probability": 1,
"min": 0.9,
"max": 1.1
}
}
]
},
{
"type": "ruin-recreate",
"probability": {
"scalar": 1
},
"ruins": [
{
"weight": 100,
"methods": [
{
"probability": 1,
"type": "adjusted-string",
"lmax": 10,
"cavg": 10,
"alpha": 0.01
},
{
"probability": 0.1,
"type": "neighbour",
"min": 4,
"max": 8,
"threshold": 0.05
},
{
"probability": 0.05,
"type": "random-job",
"min": 4,
"max": 8,
"threshold": 0.05
},
{
"probability": 0.01,
"type": "random-route",
"min": 1,
"max": 2,
"threshold": 0.05
}
]
},
{
"weight": 10,
"methods": [
{
"probability": 1,
"type": "neighbour",
"min": 8,
"max": 16,
"threshold": 0.1
},
{
"probability": 0.15,
"type": "random-job",
"min": 8,
"max": 16,
"threshold": 0.1
},
{
"probability": 0.05,
"type": "random-route",
"min": 1,
"max": 4,
"threshold": 0.1
}
]
},
{
"weight": 5,
"methods": [
{
"probability": 1,
"type": "worst-job",
"skip": 4,
"min": 8,
"max": 16,
"threshold": 0.1
},
{
"probability": 0.05,
"type": "random-job",
"min": 8,
"max": 16,
"threshold": 0.1
},
{
"probability": 0.01,
"type": "random-route",
"min": 1,
"max": 4,
"threshold": 0.1
}
]
},
{
"weight": 2,
"methods": [
{
"probability": 1,
"type": "random-job",
"min": 8,
"max": 16,
"threshold": 0.1
},
{
"probability": 0.1,
"type": "random-route",
"min": 1,
"max": 4,
"threshold": 0.1
}
]
},
{
"weight": 2,
"methods": [
{
"probability": 1,
"type": "random-route",
"min": 1,
"max": 4,
"threshold": 0.1
},
{
"probability": 0.1,
"type": "random-job",
"min": 8,
"max": 16,
"threshold": 0.1
}
]
},
{
"weight": 1,
"methods": [
{
"probability": 1,
"type": "cluster",
"min": 8,
"max": 16,
"cmin": 3,
"cmax": 9,
"threshold": 0.1
},
{
"probability": 0.05,
"type": "random-job",
"min": 8,
"max": 16,
"threshold": 0.1
},
{
"probability": 0.01,
"type": "random-route",
"min": 1,
"max": 4,
"threshold": 0.1
}
]
}
],
"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.8,
"max": 1.2
},
{
"weight": 5,
"type": "skip-best",
"start": 3,
"end": 4
},
{
"weight": 5,
"type": "gaps",
"min": 2
},
{
"weight": 5,
"type": "blinks"
},
{
"weight": 2,
"type": "farthest"
},
{
"weight": 2,
"type": "skip-best",
"start": 4,
"end": 8
},
{
"weight": 1,
"type": "nearest"
}
]
},
{
"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.9,
"max": 1.1
}
},
{
"weight": 30,
"type": "inter-route-random",
"noise": {
"probability": 0.1,
"min": 0.9,
"max": 1.1
}
},
{
"weight": 30,
"type": "intra-route-random",
"noise": {
"probability": 1,
"min": 0.9,
"max": 1.1
}
}
]
}
]
},
"termination": {
"maxTime": 300,
"maxGenerations": 3000,
"variation": {
"sample": 3000,
"cv": 1
}
},
"telemetry": {
"logging": {
"enabled": true,
"logBest": 100,
"logPopulation": 1000,
"dumpPopulation": false
},
"metrics": {
"enabled": false,
"trackPopulation": 1000
}
},
"environment": {
"parallelism": {
"numThreadPools": 6,
"threadsPerPool": 8
}
}
}
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.
Concepts
This section describes the ways how VRP problem can be specified in order to run the solver. At the moment, there are two options:
- pragmatic: a json format used to model a real world VRP problems
- scientific a set of text formats used to benchmark various algorithms in scientific literature.
Pragmatic
Pragmatic format aims to model a multiple VRP variants through single problem and solution model schemas which are described in details in next sections.
Performance
There is no limit on problem size, solver should be able to solve problems with thousands of jobs in fairly reasonable amount of time depending on your termination criteria (e.g. time or amount of iterations/generations). However, exact performance depends on VRP variant (e.g. VRPPD is slower than CVRPTW).
Quality of results
Although results seems to be comparable with alternative solutions, default metaheuristic still can be improved.
Examples
A various examples can be found in pragmatic examples section.
Problem model
In general a pragmatic problem is split into two required and one optional parts:
plan
(required) models a work to be performed by vehicles taking into account all related constraints, such as time windows, demand, skills, etc.fleet
(required) models available resources defined by vehicle types.objectives
(optional) defines objective functions as goal of whole optimization.
Modeling jobs
A work which has to be done is model by list of jobs defined in plan
.
Check next job section for detailed explanation.
Modeling vehicles
Vehicles are defined by fleet.vehicles
property which specifies array of vehicle types, not specific vehicles.
More details can be found in vehicle type section.
Relation between jobs and vehicles
An optional plan.relations
property specifies relations between multiple jobs and single vehicle. It is useful to
lock jobs to a specific vehicle in any or predefined order.
Check relations section for more details.
Job and vehicle constraints
There are multiple strict constraints that should be matched on jobs and vehicles.
Demand and capacity
Each job should have demand
property which models a good size in abstract integral units:
"demand": [
1
]
It is required, but you can set demand to zero in case it is not needed. It can be multidimensional array.
A capacity
property is a vehicle characteristic which constraints amount of jobs can be served by vehicle of specific
type based on accumulated demand value. Total demand should not exceed capacity value.
Time windows
Optionally, each job can have one or more time window:
"times": [
[
"2019-07-04T09:00:00Z",
"2019-07-04T18:00:00Z"
],
[
"2019-07-05T09:00:00Z",
"2019-07-05T18:00:00Z"
]
]
Time windows are strict: if no vehicle can visit a job in given time ranges, then the job is considered as unassigned.
Vehicle time is limited per each shift and has required start optional end time:
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
More details about shift
property can be found in vehicle type section.
Job
A job is used to model customer demand, additionally, with different constraints, such as time, skills, etc. A job schema consists of the following properties:
-
id (required): an unique job id
-
pickups (optional): a list of pickup tasks
-
deliveries (optional): a list of delivery tasks
-
replacements (optional): a list of replacement tasks
-
services (optional): a list of service tasks
-
priority (optional): a job priority which makes preferable to serve some jobs before others. Priority is represented as integer in range
[1, MAX_INT]
where the lower value means higher priority. By default value is set to 1. -
skills (optional): job skills defined by
allOf
,oneOf
ornoneOf
conditions:"skills": { "allOf": [ "fridge" ], "noneOf": [ "washing_machine" ] }
These conditions are tested against vehicle's skills.
A job should have at least one task property specified.
Tasks
A delivery, pickup, replacement and service lists specify multiple job tasks
and at least one of such tasks has to be
defined. Each task has the following properties:
- places (required): list of possible places from which only one has to be visited
- demand (optional/required): a task demand. It is required for all job types, except service
- tag (optional): a job tag which will be returned within job's activity in result solution
Places
Each place
consists of the following properties:
- location (required): a place location
- duration (required): service (operational) time to serve task here
- times (optional): time windows
Multiple places on single task can help model variable job location, e.g. visit customer at different location depending on time of the day.
Pickup job
Pickup job is a job with job.pickups
property specified, without job.deliveries
:
{
"id": "job2",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 240.0,
"times": [
[
"2019-07-04T10:00:00Z",
"2019-07-04T16:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
The vehicle picks some good
at pickup locations, which leads to capacity growth according to job.pickups.demand
value,
and brings it till the end of the tour. Each pickup task has its own properties such as demand
and places
.
Delivery job
Delivery job is a job with job.deliveries
property specified, without job.pickups
:
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0,
"times": [
[
"2019-07-04T09:00:00Z",
"2019-07-04T18:00:00Z"
],
[
"2019-07-05T09:00:00Z",
"2019-07-05T18:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
The vehicle picks some goods
at the start stop, which leads to initial capacity growth, and brings it to job's locations,
where capacity is decreased based on job.deliveries.demand
values. Each delivery task has its own properties such as
demand
and places
.
Pickup and delivery job
Pickup and delivery job is a job with both job.pickups
and job.deliveries
properties specified:
{
"id": "job3",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 300.0
}
],
"demand": [
1
],
"tag": "p1"
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"duration": 300.0
}
],
"demand": [
1
],
"tag": "d1"
}
]
}
The vehicle picks some goods
at one or multiple job.pickups.location
, which leads to capacity growth, and brings
them to one or many job.deliveries.location
. The job has the following rules:
- all pickup/delivery tasks should be done or none of them.
- assignment order is not defined except all pickups should be assigned before any of deliveries.
- sum of pickup demand should be equal to sum of delivery demand
A good example of such job is a job with more than two places with variable demand:
{
"id": "multi_job1",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5622847,
"lng": 13.4023099
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "p1"
},
{
"places": [
{
"location": {
"lat": 52.5330881,
"lng": 13.3973059
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "p2"
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5252832,
"lng": 13.4188422
},
"duration": 240.0
}
],
"demand": [
2
],
"tag": "d1"
}
]
},
This job contains two pickups and one delivery. Interpretation of such job can be "bring two parcels from two different places to one single customer".
Another example is one pickup and two deliveries:
{
"id": "multi_job2",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 240.0
}
],
"demand": [
2
],
"tag": "p1"
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4928,
"lng": 13.4597
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "d1"
},
{
"places": [
{
"location": {
"lat": 52.4989,
"lng": 13.3917
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "d2"
}
]
}
]
},
Replacement job
A replacement job is a job with job.replacement
property specified:
{
"id": "simple_replacement_job",
"replacements": [
{
"places": [
{
"location": {
"lat": 52.5622847,
"lng": 13.4023099
},
"duration": 3600.0,
"times": [
[
"2019-07-04T09:00:00Z",
"2019-07-04T18:00:00Z"
]
]
}
],
"demand": [
3
]
}
]
},
It models an use case when something big has to be replaced at the customer's location. This task requires a new good
to be loaded at the beginning of the journey and old replaced one brought to journey's end.
Service job
A service job is a job with job.service
property specified:
{
"id": "simple_service_job",
"services": [
{
"places": [
{
"location": {
"lat": 52.5330881,
"lng": 13.3973059
},
"duration": 3600.0,
"times": [
[
"2019-07-04T08:00:00Z",
"2019-07-04T12:00:00Z"
],
[
"2019-07-04T14:00:00Z",
"2019-07-04T18:00:00Z"
]
]
}
]
}
]
},
This job models some work without demand (e.g. handyman visit).
Mixing job tasks
You can specify multiple tasks properties to get some mixed job:
{
"id": "mixed_job",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5252832,
"lng": 13.4188422
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "p1"
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "d1"
}
],
"replacements": [
{
"places": [
{
"location": {
"lat": 52.4928,
"lng": 13.4597
},
"duration": 2400.0
}
],
"demand": [
2
],
"tag": "r1"
}
],
"services": [
{
"places": [
{
"location": {
"lat": 52.4989,
"lng": 13.3917
},
"duration": 1800.0
}
],
"tag": "s1"
}
]
Similar pickup and delivery job, all these tasks has to be executed or none of them. The order is not specified except pickups must be scheduled before any delivery, replacement or service.
Hint
Use tag
property on each job task if you want to use initial solution or checker features.
Related errors
- E1100 duplicated job ids
- E1101 invalid job task demand
- E1102 invalid pickup and delivery demand
- E1103 invalid time windows in jobs
- E1104 reserved job id is used
- E1105 empty job
- E1106 job has negative duration
- E1107 job has negative demand
Examples
Please refer to basic job usage examples to see how to specify problem with different job types.
Vehicle types
A vehicle types are defined by fleet.types
property and their schema has the following properties:
- typeId (required): a vehicle type id
"typeId": "vehicle",
- vehicleIds (required): a list of concrete vehicle ids available for usage.
"vehicleIds": [
"vehicle_1"
],
- profile (required): a name of routing profile
"profile": "normal_car",
-
costs (required): specifies how expensive is vehicle usage. It has three properties:
- fixed: a fixed cost per vehicle tour
- time: a cost per time unit
- distance: a cost per distance unit
-
shifts (required): specify one or more vehicle shift. See detailed description below.
-
capacity (required): specifies vehicle capacity symmetric to job demand
"capacity": [
10
]
- skills (optional): vehicle skills needed by some jobs
"skills": [
"handyman"
]
-
limits (optional): vehicle limits. There are two:
-
shiftTime (optional): max shift time
-
maxDistance (optional): max distance
-
tourSize (optional): max amount of activities in the tour (without departure/arrival)
-
allowedAreas (optional): a list of areas where vehicle is allowed to serve jobs. Each area is defined by:
- priority (optional): an area priority, bigger value - less important. You can use this property to prioritize jobs in one area over another.
- outerShape (required): closed polygon specified by coordinates. No area restrictions when omitted.
-
An example:
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
}
],
"capacity": [
10
]
}
Shift
Essentially, shift specifies vehicle constraints such as time, start/end locations, etc.:
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
}
At least one shift has to be specified. More than one vehicle shift with different times means that this vehicle can be used more than once. This is useful for multi day scenarios. An example can be found here.
Each shift can have the following properties:
- start (required) specifies vehicle start place defined via location, earliest (required) and latest (optional) departure time
- end (optional) specifies vehicle end place defined via location, earliest (reserved) and latest (required) arrival time. When omitted, then vehicle ends on last job location
- dispatch (optional) a list of dispatch places. When specified, shift start location is not considered as depot and vehicle has to navigate first to one of these places to load goods with dispatching constraints. Check example here
- breaks (optional) a list of vehicle breaks. A break is specified by:
- time window or interval after which a break should happen (e.g. between 3 or 4 hours after start)
- duration of the break
- optional locations. When present, one of locations is used for break. If it is omitted then break is stick to location of job served before break. Please not that break is soft constraint and can be unassigned in some cases due to other hard constraints, such as time windows. See example here
- reloads (optional) a list of vehicle reloads. A reload is a place where vehicle can load new deliveries and unload pickups. It can be used to model multi trip routes. See examples here.
Related errors
- E1300 duplicated vehicle type ids
- E1301 duplicated vehicle ids
- E1302 invalid start or end times in vehicle shift
- E1303 invalid break time windows in vehicle shift
- E1304 invalid reload time windows in vehicle shift
- E1305 invalid allowed area definition in vehicle limits
- E1306 invalid dispatch in vehicle shift
Relations
Relation is a mechanism to lock jobs to specific vehicles. List of relations is a part of plan
schema and each relation
has the following properties:
- type (required): one of three relation types: tour, fixed, or sequence. See description below.
- vehicleId (required): a specific vehicle id
- jobs (required): list of job ids including reserved:
departure
,arrival
,break
andreload
- shiftIndex (optional): a vehicle shift index. If not specified, a first, zero indexed, shift assumed
You can use more than one relation per vehicle.
Any type
A any
relation is used to lock specific jobs to certain vehicle in any order:
{
"type": "any",
"jobs": [
"job1",
"job3"
],
"vehicleId": "vehicle_1"
}
Sequence type
A sequence
relation is used to lock specific jobs to certain vehicle in fixed order allowing insertion of new jobs in
between.
Strict type
In contrast to sequence
relation, strict
locks jobs to certain vehicle without ability to insert new jobs in between:
{
"type": "strict",
"jobs": [
"departure",
"job4",
"job1"
],
"vehicleId": "vehicle_1"
}
In this example, new jobs can be inserted only after job with id job1
.
Important notes
Please consider the following notes:
-
jobs specified in
sequence
andstrict
are not checked for constraint violations. This might lead to non-feasible solutions (e.g. routes with capacity or time window violation). -
relation with jobs which have multiple pickups or deliveries are not yet supported
Related errors
- E1200 relation has job id which does not present in the plan
- E1201 relation has vehicle id which does not present in the fleet
- E1202 relation has empty job id list
- E1203 strict or sequence relation has job with multiple places or time windows
- E1204 job is assigned to different vehicles in relations
- E1205 relation has invalid shift index
- E1206 relation has special job id which is not defined on vehicle shift
Examples
Please refer to complete example to see how to specify problem with relations.
Objectives
A classical objective function (or simply objective) for VRP is minimization of total cost. However, real life scenarios require different objective function or even more than one considered simultaneously. That's why the solver has a concept of multi objective.
Understanding multi objective structure
A multi objective is defined by objectives
and consists of two properties:
- primary (required): a list of primary objectives, at least one must be present
- secondary (optional): a list of secondary objectives
Splitting multiple objectives into two separate collections serves the purpose to solve the problem that many objectives are conflicting by their nature. So, secondary objectives are considered only if objectives in primary list cannot detect the change in newly discovered solution.
Available objectives
The solver already provides multiple built-in objectives distinguished by their type
. All these objectives can be
split into two groups.
Scalar objectives
This objectives targeting for some scalar characteristic of solution:
minimize-cost
: minimizes total transport cost calculated for all routesminimize-unassigned
: minimizes amount of unassigned jobs. Although, solver tries to minimize amount of unassigned jobs all the time, it is possible that solution, discovered during refinement, has more unassigned jobs than previously accepted. The reason of that can be conflicting objective (e.g. minimize tours) and restrictive constraints such as time windows. The objective has the following optional parameter:breaks
: a multiplicative coefficient to make breaks more preferable for assignment. Default value is 1. Setting this parameter to a value bigger than 1 is useful when it is highly desirable to have break assigned but its assignment leads to more jobs unassigned.
minimize-tours
: minimizes total amount of tours present in solutionmaximize-tours
: maximizes total amount of tours present in solution
Work balance objectives
There are four work balance objectives available:
balance-max-load
: balances max load in tourbalance-activites
: balances amount of activities performed in tourbalance-distance
: balances travelled distance per tourbalance-duration
: balances tour durations
Each objective has optional parameters defined by option
property:
threshold
: a target coefficient of variation value which specifies desired minimum balancing level. All values below threshold are considered equal which helps the search algorithm to optimize conflicting objectives.tolerance
: a step tolerance by variation coefficient. Algorithm considers two fitness values equal if they differ not more thantolerance
value.
It is recommended to set both option values to guide the search towards optimum for conflicting objectives, e.g. cost minimization and any of work balance.
An usage example:
{
"type": "balance-max-load",
"options": {
"tolerance": 0.05,
"threshold": 0.01
}
}
Default behaviour
By default, decision maker minimizes amount of routes, unassigned jobs and total cost which is equal to the following definition:
"objectives": {
"primary": [
{
"type": "minimize-tours"
},
{
"type": "minimize-unassigned"
}
],
"secondary": [
{
"type": "minimize-cost"
}
]
}
Here, cost minimization is a secondary objective which corresponds to a classical hierarchical objective used
by Solomon
benchmark.
Hints
- if you're getting unassigned jobs, want to minimize their count, but not all vehicles are used, then try the following objective:
"objectives": {
"primary": [
{
"type": "minimize-unassigned"
}
],
"secondary": [
{
"type": "minimize-cost"
}
]
}
- if you're using balancing objective and getting high cost or non-realistic, but balanced routes, try to add a tolerance and threshold to balancing objective:
"objectives": {
"primary": [
{
"type": "minimize-unassigned"
},
{
"type": "minimize-tours"
}
],
"secondary": [
{
"type": "minimize-cost"
},
{
"type": "balance-distance",
"options": {
"tolerance": 0.01,
"threshold": 0.005
}
}
]
}
Related errors
Examples
Please refer to examples section to see more examples.
Routing data
In order to solve real life VRP, you need to provide routing information, such as distances and durations between all locations in the problem. Getting this data is not a part of the solver, you need to use some external service to get it. Once received, it has to be passed within VRP definition in specific routing matrix format.
When no routing matrix information supplied, the solver uses haversine distance approximation. See more information about such behavior here.
Location format
Location can be represented as one of two types:
- location as geocoodinate
"location": {
"lat": 52.52599,
"lng": 13.45413
},
- location as index reference in routing matrix
"location": {
"index": 0
},
Please note, that you cannot mix these types in one problem definition. Also routing approximation cannot be used with location indices.
Related errors
- E0002 cannot create transport costs
- E1500 duplicate profile names
- E1501 empty profile collection
- E1502 mixing different location types
- E1503 location indices requires routing matrix to be specified
- E1504 area limit constraint requires coordinates to be used everywhere
- E1505 amount of locations does not match matrix dimension
Routing matrix format
In general, routing matrix has the following schema:
profile
(required for time dependent VRP) is name of vehicle profiletimestamp
(optional) a date in RFC3999 for which routing info is applicable. Can be used for time dependent VRP.travelTimes
(required) is square matrix of durations in abstract time units represented via single dimensional arraydistances
(required) is square matrix of distances in abstract distance unit represented via single dimensional arrayerrorCodes
(optional): must be present if there is no route between some locations. Non-zero value signalizes about routing error.
Both durations and distances are mapped to the list of unique locations generated from the problem definition. In this list, locations are specified in the order they defined. For example, if you have two jobs with locations A and B, one vehicle type with depot location C, then you have the following location list: A,B,C. It corresponds to the matrix (durations or distances):
| | | | |----|----|----| | 0 | AB | AC | | BA | 0 | BC | | CA | CB | 0 |
where
0
: zero duration or distanceXY
: distance or duration from X location to Y
As single dimensional array it looks like:
[0,AB,AC,BA,0,BC,CA,CB,0]
vrp-cli
command provides a helper command to get it as well as pragmatic
lib exposes method to get the list
pragmatically:
vrp-cli solve pragmatic problem.json --get-locations -o locations.json
The output format is a simply array of unique geo locations:
[
{
"lat": 52.52599,
"lng": 13.45413
},
{
"lat": 52.5225,
"lng": 13.4095
},
{
"lat": 52.5165,
"lng": 13.3808
},
{
"lat": 52.5316,
"lng": 13.3884
}
]
You can use it to get a routing matrix from any of routing services of your choice, but the order in resulting matrix should be kept as expected.
Routing matrix example:
{
"profile": "normal_car",
"travelTimes": [
0,
609,
981,
906,
813,
0,
371,
590,
1055,
514,
0,
439,
948,
511,
463,
0
],
"distances": [
0,
3840,
5994,
5333,
4696,
0,
2154,
3226,
5763,
2674,
0,
2145,
5112,
2470,
2152,
0
]
}
If you have already your routing matrix, you can use location indices instead of geocoordinates as described here.
Routing profiles
In order to solve VRP, you need to specify at least one routing profile.
Usage
Routing profiles are defined in fleet.profiles
:
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
The name
must be unique for each profile and it should referenced by profile
property defined on vehicle:
"profile": "normal_car",
Use -m
option to pass the matrix:
vrp-cli solve pragmatic problem.json -m routing_matrix.json -o solution.json
If you don't pass any routing matrix, then haversine formula is used to
calculate distances between geo locations. Durations are calculated using speed value defined via speed
property in
each profile. It is optional, default value is 10
which corresponds to 10m/s
.
Multiple profiles
In general, you're not limited to one single routing profile. You can define multiple ones and pass their matrices to the solver:
vrp-cli solve pragmatic problem.json -m routing_matrix_car.json -m routing_matrix_truck.json
Make sure that for all profile names in fleet.profiles
you have the corresponding matrix specified.
See multiple profiles example.
Time dependent routing
In order to use this feature, specify more than one routing matrix for each profile with timestamp property set.
Pragmatic solution
A pragmatic solution is a result of metaheuristic work and, essentially, consists of three main parts:
- statistic
- list of tours
- list of unassigned jobs
Tour list
List of tours is essentially individual vehicle routes. Each tour consists of the following properties:
-
typeId: id of vehicle type
"typeId": "vehicle",
-
vehicleId: id of used vehicle. Id of the vehicle is generated from the tour using pattern
$typeId_sequenceIndex
:"vehicleId": "vehicle_1",
-
shiftIndex: vehicle's shift index:
"shiftIndex": 0,
-
stops: list of stops. See stop structure below
-
statistic: statistic of the tour.
} ], "statistic": { "cost": 41.504842000000004, "distance": 13251, "duration": 3507, "times": { "driving": 2367, "serving": 1140, "waiting": 0, "break": 0
Stop structure
Stop represents a location vehicle has to visit within activities to be performed. It has the following properties:
- location: a stop location
- time: arrival and departure time from the stop
- distance: distance traveled since departure from start location
- load: vehicle capacity after departure from the stop
- activities: list of activities to be performed at the stop. Each stop can have more than one activity. See activity structure below.
Activity structure
An activity specifies work to be done and has the following structure:
- jobId: id of the job or special id (
departure
,arrival
,break
,reload
) - type: activity type:
departure
,arrival
,break
,reload
,pickup
ordelivery
- location (optional): activity location. Omitted if stop list has one activity
- time (optional): start and end time of activity. Omitted if stop list has one activity
- jobTag (optional): a job place tag
Examples
An example of stop with one activity:
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:51:29Z"
},
"distance": 0,
"load": [
1
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
An example of stop with two activities:
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"arrival": "2019-07-04T10:22:26Z",
"departure": "2019-07-04T10:31:26Z"
},
"distance": 8952,
"load": [
2
],
"activities": [
{
"jobId": "job2",
"type": "pickup",
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"start": "2019-07-04T10:22:26Z",
"end": "2019-07-04T10:26:26Z"
}
},
{
"jobId": "job3",
"type": "pickup",
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"start": "2019-07-04T10:26:26Z",
"end": "2019-07-04T10:31:26Z"
},
"jobTag": "p1"
}
]
Statistic
A statistic entity represents total statistic for the whole solution or one tour. It has the following structure:
- cost: a cost in abstract units
- distance: a total distance in distance units
- duration: a total duration in duration units
- times: a duration split into specific groups:
- driving: a total driving duration
- serving: a total serving jobs duration
- waiting: a total waiting time for time windows
- break: a total break duration
A solution statistic example:
"statistic": {
"cost": 41.504842000000004,
"distance": 13251,
"duration": 3507,
"times": {
"driving": 2367,
"serving": 1140,
"waiting": 0,
"break": 0
}
Unassigned jobs
When job cannot be assigned, it goes to the list of unassigned jobs:
"unassigned": [
{
"jobId": "job2",
"reasons": [
{
"code": "REACHABLE_CONSTRAINT",
"description": "location unreachable"
}
]
}
]
Each item in this list has job id, reason code and description.
Reasons of unassigned jobs
| code | description | possible action |
|-------------------------|----------------------------------------------------------------|---------------------------------------------------------|
| NO_REASON_FOUND | unknown
| |
| SKILL_CONSTRAINT | cannot serve required skill
| allocate more vehicles with given skill? |
| TIME_WINDOW_CONSTRAINT | cannot be visited within time window
| allocate more vehicles, relax time windows, etc.? |
| CAPACITY_CONSTRAINT | does not fit into any vehicle due to capacity
| allocate more vehicles? |
| REACHABLE_CONSTRAINT | location unreachable
| change job location to routable place? |
| MAX_DISTANCE_CONSTRAINT | cannot be assigned due to max distance constraint of vehicle
| allocate more vehicles? |
| SHIFT_TIME_CONSTRAINT | cannot be assigned due to shift time constraint of vehicle
| allocate more vehicles? |
| BREAK_CONSTRAINT | break is not assignable
| correct break location or/and time window? |
| LOCKING_CONSTRAINT | cannot be served due to relation lock
| review relations? |
| PRIORITY_CONSTRAINT | cannot be served due to priority
| allocate more vehicles, relax priorities? |
| AREA_CONSTRAINT | cannot be assigned due to area constraint
| make sure that jobs inside allowed areas |
| DISPATCH_CONSTRAINT | cannot be assigned due to vehicle dispatch
| make sure that vehicle dispatch definition is correct |
| TOUR_SIZE_CONSTRAINT | cannot be assigned due to tour size constraint of vehicle
| make sure that there are enough vehicles to serve jobs |
Example
An example of problem with unassigned jobs can be found here.
Violations
Some of the constraints, specified by the problem, are considered as soft and can be violated under certain circumstances.
Violations are listed in violations
collection and divided in to specific groups.
Vehicle Break violation
A vehicle break is considered as soft constraint and can be violated if the solver is not able to assign it. When it is violated, the following object is returned:
{
"type": "break",
"vehicleId": "my_vehicle_id",
"shiftIndex": 0,
"reason": "cannot be visited within time window"
}
Error Index
This page lists errors produced by the solver.
E0xxx Error
Errors from E0xxx range are generic.
E0000
cannot deserialize problem
is returned when problem definition cannot be deserialized from the input stream.
E0001
cannot deserialize matrix
is returned when routing matrix definition cannot be deserialized from the input stream.
E0002
cannot create transport costs
is returned when problem cannot be matched within routing matrix data passed.
There are two options to consider, when specifying routing matrix data:
- time dependent VRP requires all matrices to have
profile
andtimestamp
properties to be se - time agnostic VRP requires
timestamp
property to be omitted,profile
property either set or skipped for all matrices
E0003
cannot find any solution
is returned when no solution is found. In this case, please submit a bug and share original
problem and routing matrix.
E0004
cannot read config
is returned when algorithm configuration cannot be created. To fix it, make sure that config has
a valid json schema and valid parameters.
E1xxx: Validation errors
Errors from E1xxx range are used by validation engine which checks logical correctness of the rich VRP definition.
E11xx: Jobs
These errors are related to plan.jobs
property definition.
E1100
duplicated job ids
error is returned when plan.jobs
has jobs with the same ids:
{
"plan": {
"jobs": [
{
"id": "job1",
/** omitted **/
},
{
/** Error: this id is already used by another job **/
"id": "job1",
/** omitted **/
}
/** omitted **/
]
}
}
Duplicated job ids are not allowed, so you need to remove all duplicates in order to fix the error.
E1101
invalid job task demand
error is returned when job has invalid demand: pickup
, delivery
, replacement
job types should
have demand specified on each job task, service
type should have no demand specified:
{
"id": "job1",
"deliveries": [
{
/** omitted **/
/** Error: delivery task should have demand set**/
"demand": null
}
],
"services": [
{
/** omitted **/
/** Error: service task should have no demand specified**/
"demand": [1]
}
]
}
To fix the error, make sure that each job task has proper demand.
E1102
invalid pickup and delivery demand
error code is returned when job has both pickups and deliveries, but the sum of
pickups demand does not match to the sum of deliveries demand:
{
"id": "job",
"pickups": [
{
"places": [/** omitted **/],
"demand": [1],
},
{
"places": [/** omitted **/],
"demand": [1]
}
],
"deliveries": [
{
"places": [/** omitted **/],
/** Error: should be 2 as the sum of pickups is 2 **/
"demand": [1]
}
]
}
E1103
invalid time windows in jobs
error is returned when there is a job which has invalid time windows, e.g.:
{
/** Error: end time is one hour earlier than start time**/
"times": [
[
"2020-07-04T12:00:00Z",
"2020-07-04T11:00:00Z"
]
]
}
Each time window must satisfy the following criteria:
- array of two strings each of these specifies date in RFC3339 format. The first is considered as start, the second - as end
- start date is earlier than end date
- if multiple time windows are specified, they must not intersect, e.g.:
{
/** Error: second time window intersects with first one: [13:00, 14:00] **/
"times": [
[
"2020-07-04T10:00:00Z",
"2020-07-04T14:00:00Z"
],
[
"2020-07-04T13:00:00Z",
"2020-07-04T17:00:00Z"
]
]
}
E1104
reserved job id is used
error is returned when there is a job which has reserved job id:
{
/** Error: 'departure' is reserved job id **/
"id": "departure"
}
To avoid confusion, the following ids are reserved: departure
, arrival
, dispatch
, break
, and reload
. These
ids are not allowed to be used within job.id
property.
E1105
empty job
error is returned when there is a job which has no or empty job tasks:
{
/** Error: at least one job task has to be defined **/
"id": "job1",
"pickups": null,
"deliveries": []
}
To fix the error, remove job from the plan or add at least one job task to it.
E1106
job has negative duration
error is returned when there is a job place with negative duration:
{
"id": "job",
"pickups": [
{
"places": [{
/** Error: negative duration does not make sense **/
"duration": -10,
"location": {/* omitted */}
}]
/* omitted */
}
]
}
To fix the error, make sure that all durations are non negative.
E1107
job has negative demand
error is returned when there is a job with negative demand in any of dimensions:
{
"id": "job",
"pickups": [
{
"places": [/* omitted */],
/** Error: negative demand is not allowed **/
"demand": [10, -1]
}
]
}
To fix the error, make sure that all demand values are non negative.
E12xx: Relations
These errors are related to plan.relations
property definition.
E1200
relation has job id which does not present in the plan
error is returned when plan.relations
has relations with
job ids, not present in plan.jobs
.
E1201
relation has vehicle id which does not present in the fleet
error is returned when plan.relations
has relations with
vehicle ids, not present in plan.fleet
.
E1202
relation has empty job id list
error is returned when plan.relations
has relations with empty jobs
list or it has
only reserved ids such as departure
, arrival
, break
, reload
.
E1203
strict or sequence relation has job with multiple places or time windows
error is returned when plan.relations
has
strict or sequence relation which refers one or many jobs with multiple places and/or time windows.
This is currently not allowed due to matching problem.
E1204
job is assigned to different vehicles in relations
error is returned when plan.relations
has a job assigned to several
relations with different vehicle ids:
{
"plan": {
"relations": [
{
"vehicleId": "vehicle_1",
"jobs": ["job1"],
/** omitted **/
},
{
/** Error: this job id is already assigned to another vehicle **/
"vehicleId": "vehicle_2",
"jobs": ["job1"],
/** omitted **/
}
]
}
}
To fix this, remove job id from one of relations.
E1205
relation has invalid shift index
error is returned when plan.relations
has shiftIndex
value and no corresponding
shift
is present in list of shifts.
E1206
relation has special job id which is not defined on vehicle shift
error is returned when plan.relations
has reserved
job id and corresponding property on fleet.vehicles.shifts
is not defined. Reserved ids are break
, dispatch
, reload
and arrival
.
E13xx: Vehicles
These errors are related to fleet.vehicles
property definition.
E1300
duplicated vehicle type ids
error is returned when fleet.vehicles
has vehicle types with the same typeId
:
{
"fleet": {
"vehicles": [
{
"typeId": "vehicle_1",
/** omitted **/
},
{
/** Error: this id is already used by another vehicle type **/
"typeId": "vehicle_1",
/** omitted **/
}
/** omitted **/
]
}
}
E1301
duplicated vehicle ids
error is returned when fleet.vehicles
has vehicle types with the same vehicleIds
:
{
"fleet": {
"vehicles": [
{
"typeId": "vehicle_1",
"vehicleIds": [
"vehicle_1_a",
"vehicle_1_b",
/** Error: vehicle_1_b is used second time **/
"vehicle_1_b"
],
/** omitted **/
},
{
"typeId": "vehicle_2",
"vehicleIds": [
/** Error: vehicle_1_a is used second time **/
"vehicle_1_a",
"vehicle_2_b"
],
/** omitted **/
}
/** omitted **/
]
}
}
Please note that vehicle id should be unique across all vehicle types.
E1302
invalid start or end times in vehicle shift
error is returned when vehicle has start/end shift times violating one of
time windows rules defined for jobs in E1103.
E1303
invalid break time windows in vehicle shift
error is returned when vehicle has invalid time window of a break. List of
break should follow time window rules defined for jobs in E1103. Additionally, break time should be inside vehicle shift
it is specified:
{
"start": {
"time": "2019-07-04T08:00:00Z",
/** omitted **/
},
"end": {
"time": "2019-07-04T15:00:00Z",
/** omitted **/
},
"breaks": [
{
/** Error: break is outside of vehicle shift times **/
"times": [
[
"2019-07-04T17:00:00Z",
"2019-07-04T18:00:00Z"
]
],
"duration": 3600.0
}
]
}
E1304
invalid reload time windows in vehicle shift
error is returned when vehicle has invalid time window of a reload. Reload
list should follow time window rules defined for jobs in E1003 except multiple reloads can have time window intersections.
Additionally, reload time should be inside vehicle shift it is specified:
{
"start": {
"time": "2019-07-04T08:00:00Z",
/** omitted **/
},
"end": {
"time": "2019-07-04T15:00:00Z",
/** omitted **/
},
"reloads": [
{
/** Error: reload is outside of vehicle shift times **/
"times": [
[
"2019-07-04T17:00:00Z",
"2019-07-04T18:00:00Z"
]
],
"location": { /** omitted **/ },
"duration": 3600.0
}
]
}
E1305
invalid allowed area definition in vehicle limits
error is returned when allowedArea
property in fleet.vehicles
violates one of the following rules:
- no empty arrays
- each area has more than 2 coordinates
{
"limits": {
"allowedAreas": [
/** Error: at least three locations has to be defined **/
[
{ "lat": 52.12, "lng": 13.14 },
{ "lat": 52.13, "lng": 13.15 }
]
]
}
}
E1306
invalid dispatch in vehicle shift
error is returned when dispatch
property in fleet.vehicles
violates one of the
following rules:
- has dispatch with the same location
- has invalid time
- has time window outside of vehicle shift time
- has total sum of max not equal to amount of vehicle ids
E15xx: Routing profiles
These errors are related to routing locations and fleet.profiles
property definitions.
E1500
duplicate profile names
error is returned when fleet.profiles
has more than one profile with the same name:
{
"profiles": [
{
"name": "vehicle_profile",
"type": "car"
},
{
"name": "vehicle_profile",
"type": "truck"
}
]
}
To fix the issue, remove all duplicates.
E1501
empty profile collection
error is returned when fleet.profiles
is empty:
{
"profiles": []
}
E1502
mixing different location types
error is returned when problem contains locations in different formats. In order to
fix the issue, change the problem definition to use one specific location type: index reference or geocoordinate.
E1503
location indices requires routing matrix to be specified
is returned when location indices are used, but no
routing matrix provided.
E1504
area limit constraint requires coordinates to be used everywhere
is returned when location indices are used within
area limit on fleet.vehicles.limits.allowedAreas
.
E1505
amount of locations does not match matrix dimension
is returned when:
- location indices are used and max index is greater than matrix size
- amount of total locations is higher than matrix size
Check locations in problem definition and matrix size.
E1506
unknown vehicle profile name
is returned when vehicle has fleet.vehicles.profile
name with value which is not
specified in fleet.profiles
collection. To fix issue, either change value to one specified or add a corresponding
profile in profiles collection.
E16xx: Objectives
These errors are related to objectives
property definition.
E1600
an empty objective specified
error is returned when objective property is present in the problem, but no single
objective is set, e.g.:
{
"objectives": {
"primary":[]
}
}
objectives
property is optional, just remove it to fix the problem and use default objectives.
E1610
duplicate objective specified
error is returned when objective of specific type specified more than once:
{
"objectives": {
"primary": [
{
"type": "minimize-unassigned"
},
{
"type": "minimize-unassigned"
}
],
"secondary": [
{
"type": "minimize-cost"
}
]
}
}
To fix this issue, just remove one, e.g. minimize-unassigned
.
E1611
missing cost objective
error is returned when no cost objective specified (at the moment, only minimize-cost
supported):
{
"objectives": {
"primary": [
{
"type": "minimize-unassigned"
}
]
}
}
This objective is used to calculate final costs, so it is required to be specified.
Scientific formats
The project supports two text formats widely used for benchmarking various a algorithms in scientific papers:
- Solomon: specifies CVRPTW
- Li&Lim: specifies VRPPD
Solomon problems
To run the problem from solomon
set, simply specify solomon as a type. The following command solves solomon problem
defined in RC1_10_1.txt and stores solution in RC1_10_1_solution.txt:
vrp-cli solve solomon RC1_10_1.txt -o RC1_10_1_solution.txt
Optionally, you can specify initial solution to start with:
vrp-cli solve solomon RC1_10_1.txt --init-solution RC1_10_1_solution_initial.txt -o RC1_10_1_solution_improved.txt
For details see Solomon benchmark.
Li&Lim
To run the problem from Li&Lim set, simply specify lilim as a type:
vrp-cli solve lilim LC1_10_2.txt -o LC1_10_2_solution.txt
For details see Li&Lim benchmark.
Examples
This section contains data and code examples.
Pragmatic examples
Here you can find multiple examples how to use different features such as break, reload, multi job, etc.
Each example consists of:
- problem definition: a json file with complete problem definition.
- solution: a json file with one of the possible solutions
For selected examples:
- geojson visualization with
leaflet
- ordered list of unique locations: a json file with list of locations in specific order which can be used to request a routing matrix. More info can be found here
- routing matrix: a json file with routing matrix described here
- CLI command command line which can be used to reproduce results locally using
vrp-cli
tool. Original data can be found inexamples
folder or copy-pasted from example pages and stored locally.
Basic usage
This section contains minimalistic examples to demonstrate how to use various features.
Basic job usage
This section demonstrates how to use different job task types.
You can find more details about job type schema on job concept section.
Basic pickup and delivery usage
In this example, there is one delivery, one pickup, and one pickup and delivery job with one dimensional demand.
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0,
"times": [
[
"2019-07-04T09:00:00Z",
"2019-07-04T18:00:00Z"
],
[
"2019-07-05T09:00:00Z",
"2019-07-05T18:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 240.0,
"times": [
[
"2019-07-04T10:00:00Z",
"2019-07-04T16:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 300.0
}
],
"demand": [
1
],
"tag": "p1"
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"duration": 300.0
}
],
"demand": [
1
],
"tag": "d1"
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
}
],
"capacity": [
10
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Solution
{
"statistic": {
"cost": 41.504842000000004,
"distance": 13251,
"duration": 3507,
"times": {
"driving": 2367,
"serving": 1140,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:51:29Z"
},
"distance": 0,
"load": [
1
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T10:07:17Z",
"departure": "2019-07-04T10:12:17Z"
},
"distance": 5112,
"load": [
0
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"arrival": "2019-07-04T10:22:26Z",
"departure": "2019-07-04T10:31:26Z"
},
"distance": 8952,
"load": [
2
],
"activities": [
{
"jobId": "job2",
"type": "pickup",
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"start": "2019-07-04T10:22:26Z",
"end": "2019-07-04T10:26:26Z"
}
},
{
"jobId": "job3",
"type": "pickup",
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"start": "2019-07-04T10:26:26Z",
"end": "2019-07-04T10:31:26Z"
},
"jobTag": "p1"
}
]
},
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"time": {
"arrival": "2019-07-04T10:37:37Z",
"departure": "2019-07-04T10:42:37Z"
},
"distance": 11106,
"load": [
1
],
"activities": [
{
"jobId": "job3",
"type": "delivery",
"jobTag": "d1"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T10:49:56Z",
"departure": "2019-07-04T10:49:56Z"
},
"distance": 13251,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 41.504842000000004,
"distance": 13251,
"duration": 3507,
"times": {
"driving": 2367,
"serving": 1140,
"waiting": 0,
"break": 0
}
}
}
]
}
As problem has two job task places with exactly same location, solution contains one stop with two activities.
Multiple pickups and deliveries
This example contains two multi jobs with slightly different parameters.
Problem
{
"plan": {
"jobs": [
{
"id": "multi_job1",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5622847,
"lng": 13.4023099
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "p1"
},
{
"places": [
{
"location": {
"lat": 52.5330881,
"lng": 13.3973059
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "p2"
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5252832,
"lng": 13.4188422
},
"duration": 240.0
}
],
"demand": [
2
],
"tag": "d1"
}
]
},
{
"id": "multi_job2",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 240.0
}
],
"demand": [
2
],
"tag": "p1"
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4928,
"lng": 13.4597
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "d1"
},
{
"places": [
{
"location": {
"lat": 52.4989,
"lng": 13.3917
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "d2"
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
}
}
],
"capacity": [
10
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Solution
{
"statistic": {
"cost": 74.412666,
"distance": 52738,
"duration": 8711,
"times": {
"driving": 7271,
"serving": 1440,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5622847,
"lng": 13.4023099
},
"time": {
"arrival": "2019-07-04T09:32:24Z",
"departure": "2019-07-04T09:36:24Z"
},
"distance": 17547,
"load": [
1
],
"activities": [
{
"jobId": "multi_job1",
"type": "pickup",
"tag": "p1"
}
]
},
{
"location": {
"lat": 52.5330881,
"lng": 13.3973059
},
"time": {
"arrival": "2019-07-04T09:49:48Z",
"departure": "2019-07-04T09:53:48Z"
},
"distance": 22014,
"load": [
2
],
"activities": [
{
"jobId": "multi_job1",
"type": "pickup",
"tag": "p2"
}
]
},
{
"location": {
"lat": 52.5252832,
"lng": 13.4188422
},
"time": {
"arrival": "2019-07-04T10:00:48Z",
"departure": "2019-07-04T10:04:48Z"
},
"distance": 23849,
"load": [
0
],
"activities": [
{
"jobId": "multi_job1",
"type": "delivery",
"tag": "d1"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T10:12:17Z",
"departure": "2019-07-04T10:16:17Z"
},
"distance": 26552,
"load": [
2
],
"activities": [
{
"jobId": "multi_job2",
"type": "pickup",
"tag": "p1"
}
]
},
{
"location": {
"lat": 52.4928,
"lng": 13.4597
},
"time": {
"arrival": "2019-07-04T10:38:25Z",
"departure": "2019-07-04T10:42:25Z"
},
"distance": 35242,
"load": [
1
],
"activities": [
{
"jobId": "multi_job2",
"type": "delivery",
"tag": "d1"
}
]
},
{
"location": {
"lat": 52.4989,
"lng": 13.3917
},
"time": {
"arrival": "2019-07-04T10:57:57Z",
"departure": "2019-07-04T11:01:57Z"
},
"distance": 40617,
"load": [
0
],
"activities": [
{
"jobId": "multi_job2",
"type": "delivery",
"tag": "d2"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "2019-07-04T11:25:11Z",
"departure": "2019-07-04T11:25:11Z"
},
"distance": 52738,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 74.412666,
"distance": 52738,
"duration": 8711,
"times": {
"driving": 7271,
"serving": 1440,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
Mixing job task types
You can mix job task types in one job:
Problem
{
"plan": {
"jobs": [
{
"id": "simple_replacement_job",
"replacements": [
{
"places": [
{
"location": {
"lat": 52.5622847,
"lng": 13.4023099
},
"duration": 3600.0,
"times": [
[
"2019-07-04T09:00:00Z",
"2019-07-04T18:00:00Z"
]
]
}
],
"demand": [
3
]
}
]
},
{
"id": "simple_service_job",
"services": [
{
"places": [
{
"location": {
"lat": 52.5330881,
"lng": 13.3973059
},
"duration": 3600.0,
"times": [
[
"2019-07-04T08:00:00Z",
"2019-07-04T12:00:00Z"
],
[
"2019-07-04T14:00:00Z",
"2019-07-04T18:00:00Z"
]
]
}
]
}
]
},
{
"id": "mixed_job",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5252832,
"lng": 13.4188422
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "p1"
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 240.0
}
],
"demand": [
1
],
"tag": "d1"
}
],
"replacements": [
{
"places": [
{
"location": {
"lat": 52.4928,
"lng": 13.4597
},
"duration": 2400.0
}
],
"demand": [
2
],
"tag": "r1"
}
],
"services": [
{
"places": [
{
"location": {
"lat": 52.4989,
"lng": 13.3917
},
"duration": 1800.0
}
],
"tag": "s1"
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
}
}
],
"capacity": [
10
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Solution
{
"statistic": {
"cost": 124.587306,
"distance": 52738,
"duration": 19151,
"times": {
"driving": 7271,
"serving": 11880,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
5
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5622847,
"lng": 13.4023099
},
"time": {
"arrival": "2019-07-04T09:32:24Z",
"departure": "2019-07-04T10:32:24Z"
},
"distance": 17547,
"load": [
5
],
"activities": [
{
"jobId": "simple_replacement_job",
"type": "replacement"
}
]
},
{
"location": {
"lat": 52.5330881,
"lng": 13.3973059
},
"time": {
"arrival": "2019-07-04T10:45:48Z",
"departure": "2019-07-04T11:45:48Z"
},
"distance": 22014,
"load": [
5
],
"activities": [
{
"jobId": "simple_service_job",
"type": "service"
}
]
},
{
"location": {
"lat": 52.5252832,
"lng": 13.4188422
},
"time": {
"arrival": "2019-07-04T11:52:48Z",
"departure": "2019-07-04T11:56:48Z"
},
"distance": 23849,
"load": [
6
],
"activities": [
{
"jobId": "mixed_job",
"type": "pickup",
"tag": "p1"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T12:04:17Z",
"departure": "2019-07-04T12:08:17Z"
},
"distance": 26552,
"load": [
5
],
"activities": [
{
"jobId": "mixed_job",
"type": "delivery",
"tag": "d1"
}
]
},
{
"location": {
"lat": 52.4928,
"lng": 13.4597
},
"time": {
"arrival": "2019-07-04T12:30:25Z",
"departure": "2019-07-04T13:10:25Z"
},
"distance": 35242,
"load": [
5
],
"activities": [
{
"jobId": "mixed_job",
"type": "replacement",
"tag": "r1"
}
]
},
{
"location": {
"lat": 52.4989,
"lng": 13.3917
},
"time": {
"arrival": "2019-07-04T13:25:57Z",
"departure": "2019-07-04T13:55:57Z"
},
"distance": 40617,
"load": [
5
],
"activities": [
{
"jobId": "mixed_job",
"type": "service",
"tag": "s1"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "2019-07-04T14:19:11Z",
"departure": "2019-07-04T14:19:11Z"
},
"distance": 52738,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 124.587306,
"distance": 52738,
"duration": 19151,
"times": {
"driving": 7271,
"serving": 11880,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
Multi day/shift
This example demonstrates how to simulate multi day/shift planning scenario. The problem has jobs with time windows of different days and one vehicle type with two shifts on different days.
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0,
"times": [
[
"2019-07-04T09:00:00Z",
"2019-07-04T18:00:00Z"
],
[
"2019-07-05T09:00:00Z",
"2019-07-05T18:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 240.0,
"times": [
[
"2019-07-04T10:00:00Z",
"2019-07-04T16:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"duration": 300.0,
"times": [
[
"2019-07-04T10:00:00Z",
"2019-07-04T16:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
{
"id": "job4",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5145,
"lng": 13.3513
},
"duration": 300.0,
"times": [
[
"2019-07-05T10:00:00Z",
"2019-07-05T16:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
},
{
"start": {
"earliest": "2019-07-05T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-05T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
}
],
"capacity": [
2
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Solution
{
"statistic": {
"cost": 75.30316200000001,
"distance": 26105,
"duration": 5427,
"times": {
"driving": 4287,
"serving": 1140,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 1,
"stops": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-05T09:00:00Z",
"departure": "2019-07-05T09:48:41Z"
},
"distance": 0,
"load": [
2
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5145,
"lng": 13.3513
},
"time": {
"arrival": "2019-07-05T10:00:00Z",
"departure": "2019-07-05T10:05:00Z"
},
"distance": 5245,
"load": [
1
],
"activities": [
{
"jobId": "job4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-05T10:26:14Z",
"departure": "2019-07-05T10:31:14Z"
},
"distance": 14053,
"load": [
0
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-05T10:47:22Z",
"departure": "2019-07-05T10:47:22Z"
},
"distance": 19336,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 42.789126,
"distance": 19336,
"duration": 3521,
"times": {
"driving": 2921,
"serving": 600,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:51:52Z"
},
"distance": 0,
"load": [
2
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"arrival": "2019-07-04T10:00:00Z",
"departure": "2019-07-04T10:04:00Z"
},
"distance": 2470,
"load": [
1
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"time": {
"arrival": "2019-07-04T10:10:58Z",
"departure": "2019-07-04T10:15:58Z"
},
"distance": 4624,
"load": [
0
],
"activities": [
{
"jobId": "job3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T10:23:38Z",
"departure": "2019-07-04T10:23:38Z"
},
"distance": 6769,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 32.514036000000004,
"distance": 6769,
"duration": 1906,
"times": {
"driving": 1366,
"serving": 540,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
Vehicles dispatch
The vehicle dispatch feature is useful in the following cases:
- there is a fixed loading time at the beginning of the tour
- vehicles does not start at the depot
- a depot has certain capacity limitation on amount of vehicles loaded simultaneously
When the problem specifies more than one dispatch place, one of those is chosen as next from departure stop. Decision is made based on the following criteria:
- how close dispatch's location to vehicle's start location
- how much time vehicle has to wait till dispatch is open
- how long is dispatch's duration
Example
The problem definition has one dispatch place with three different time slots with maximum capacity of one vehicle. As result, three vehicles are dispatched at different times.
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 240.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1",
"vehicle_2",
"vehicle_3"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5352,
"lng": 13.3909
}
},
"dispatch": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"limits": [
{
"max": 1,
"start": "2019-07-04T09:20:00Z",
"end": "2019-07-04T09:30:00Z"
},
{
"max": 1,
"start": "2019-07-04T09:30:00Z",
"end": "2019-07-04T09:40:00Z"
},
{
"max": 1,
"start": "2019-07-04T09:40:00Z",
"end": "2019-07-04T09:50:00Z"
}
]
}
]
}
],
"capacity": [
1
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Solution
{
"statistic": {
"cost": 85.033838,
"distance": 9310,
"duration": 3573,
"times": {
"driving": 933,
"serving": 2640,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_2",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5352,
"lng": 13.3909
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:29:16Z"
},
"distance": 0,
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:30:00Z",
"departure": "2019-07-04T09:40:00Z"
},
"distance": 435,
"load": [
1
],
"activities": [
{
"jobId": "dispatch",
"type": "dispatch"
}
]
},
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"arrival": "2019-07-04T09:42:55Z",
"departure": "2019-07-04T09:46:55Z"
},
"distance": 2187,
"load": [
0
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
}
],
"statistic": {
"cost": 27.526954,
"distance": 2187,
"duration": 1059,
"times": {
"driving": 219,
"serving": 840,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5352,
"lng": 13.3909
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:19:16Z"
},
"distance": 0,
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:20:00Z",
"departure": "2019-07-04T09:30:00Z"
},
"distance": 435,
"load": [
1
],
"activities": [
{
"jobId": "dispatch",
"type": "dispatch"
}
]
},
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"time": {
"arrival": "2019-07-04T09:32:56Z",
"departure": "2019-07-04T09:37:56Z"
},
"distance": 2193,
"load": [
0
],
"activities": [
{
"jobId": "job3",
"type": "delivery"
}
]
}
],
"statistic": {
"cost": 27.82132,
"distance": 2193,
"duration": 1120,
"times": {
"driving": 220,
"serving": 900,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_3",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5352,
"lng": 13.3909
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:39:16Z"
},
"distance": 0,
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:40:00Z",
"departure": "2019-07-04T09:50:00Z"
},
"distance": 435,
"load": [
1
],
"activities": [
{
"jobId": "dispatch",
"type": "dispatch"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T09:57:30Z",
"departure": "2019-07-04T10:02:30Z"
},
"distance": 4930,
"load": [
0
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
}
],
"statistic": {
"cost": 29.685564,
"distance": 4930,
"duration": 1394,
"times": {
"driving": 494,
"serving": 900,
"waiting": 0,
"break": 0
}
}
}
]
}
Vehicle break
This example demonstrates how to use vehicle break with omitted location and time window.
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0,
"times": [
[
"2019-07-04T09:00:00Z",
"2019-07-04T12:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 240.0,
"times": [
[
"2019-07-04T12:00:00Z",
"2019-07-04T14:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"duration": 300.0,
"times": [
[
"2019-07-04T16:00:00Z",
"2019-07-04T18:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"breaks": [
{
"time": [
"2019-07-04T12:00:00Z",
"2019-07-04T14:00:00Z"
],
"duration": 3600.0
}
]
}
],
"capacity": [
10
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Solution
{
"statistic": {
"cost": 101.964322,
"distance": 13251,
"duration": 16087,
"times": {
"driving": 2367,
"serving": 840,
"waiting": 9280,
"break": 3600
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T11:44:12Z"
},
"distance": 0,
"load": [
3
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T12:00:00Z",
"departure": "2019-07-04T13:05:00Z"
},
"distance": 5112,
"load": [
2
],
"activities": [
{
"jobId": "job1",
"type": "delivery",
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"start": "2019-07-04T12:00:00Z",
"end": "2019-07-04T12:05:00Z"
}
},
{
"jobId": "break",
"type": "break",
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"start": "2019-07-04T12:05:00Z",
"end": "2019-07-04T13:05:00Z"
}
}
]
},
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"arrival": "2019-07-04T13:15:09Z",
"departure": "2019-07-04T13:19:09Z"
},
"distance": 8952,
"load": [
1
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"time": {
"arrival": "2019-07-04T13:25:20Z",
"departure": "2019-07-04T16:05:00Z"
},
"distance": 11106,
"load": [
0
],
"activities": [
{
"jobId": "job3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T16:12:19Z",
"departure": "2019-07-04T16:12:19Z"
},
"distance": 13251,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 101.964322,
"distance": 13251,
"duration": 16087,
"times": {
"driving": 2367,
"serving": 840,
"waiting": 9280,
"break": 3600
}
}
}
],
"unassigned": []
}
Multiple trips
These examples demonstrates how to use vehicle reload feature which is designed to overcome vehicle capacity limitation in order to perform multiple trips (tours).
Essentially, reload is a place where vehicle can unload static
pickups and load new static
deliveries. Here, static
correspond to static demand
concept which is defined via standalone pickup or delivery jobs, not by single pickup and
delivery job.
Same location reload
In this scenario, once some jobs are delivered, the vehicle returns to the original depot to load next goods.
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 240.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job4",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5145,
"lng": 13.3513
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"reloads": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"duration": 600.0
}
]
}
],
"capacity": [
2
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Solution
{
"statistic": {
"cost": 52.651224000000006,
"distance": 20995,
"duration": 5504,
"times": {
"driving": 3764,
"serving": 1740,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
2
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T09:14:49Z",
"departure": "2019-07-04T09:19:49Z"
},
"distance": 5090,
"load": [
1
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"arrival": "2019-07-04T09:31:22Z",
"departure": "2019-07-04T09:35:22Z"
},
"distance": 8930,
"load": [
0
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:45:02Z",
"departure": "2019-07-04T09:55:02Z"
},
"distance": 12156,
"load": [
2
],
"activities": [
{
"jobId": "reload",
"type": "reload"
}
]
},
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"time": {
"arrival": "2019-07-04T10:02:31Z",
"departure": "2019-07-04T10:07:31Z"
},
"distance": 14308,
"load": [
1
],
"activities": [
{
"jobId": "job3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5145,
"lng": 13.3513
},
"time": {
"arrival": "2019-07-04T10:15:03Z",
"departure": "2019-07-04T10:20:03Z"
},
"distance": 17092,
"load": [
0
],
"activities": [
{
"jobId": "job4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T10:31:44Z",
"departure": "2019-07-04T10:31:44Z"
},
"distance": 20995,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 52.651224000000006,
"distance": 20995,
"duration": 5504,
"times": {
"driving": 3764,
"serving": 1740,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
Multiple reloads with different locations
In this scenario, vehicle picks goods and flushes them on two different locations during single tour. This can be used to model waste collection use case.
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 240.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job4",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5145,
"lng": 13.3513
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job5",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.4922,
"lng": 13.4593
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job6",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.4989,
"lng": 13.3917
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"reloads": [
{
"location": {
"lat": 52.5103,
"lng": 13.3898
},
"duration": 600.0
},
{
"location": {
"lat": 52.5043,
"lng": 13.4091
},
"duration": 600.0
}
]
}
],
"capacity": [
2
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Solution
{
"statistic": {
"cost": 52.38156800000001,
"distance": 23876,
"duration": 5328,
"times": {
"driving": 2388,
"serving": 2940,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"arrival": "2019-07-04T09:02:55Z",
"departure": "2019-07-04T09:06:55Z"
},
"distance": 1752,
"load": [
1
],
"activities": [
{
"jobId": "job2",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"time": {
"arrival": "2019-07-04T09:10:21Z",
"departure": "2019-07-04T09:15:21Z"
},
"distance": 3808,
"load": [
2
],
"activities": [
{
"jobId": "job3",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.5103,
"lng": 13.3898
},
"time": {
"arrival": "2019-07-04T09:16:53Z",
"departure": "2019-07-04T09:26:53Z"
},
"distance": 4729,
"load": [
0
],
"activities": [
{
"jobId": "reload",
"type": "reload"
}
]
},
{
"location": {
"lat": 52.5145,
"lng": 13.3513
},
"time": {
"arrival": "2019-07-04T09:31:18Z",
"departure": "2019-07-04T09:36:18Z"
},
"distance": 7379,
"load": [
1
],
"activities": [
{
"jobId": "job4",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.4989,
"lng": 13.3917
},
"time": {
"arrival": "2019-07-04T09:41:42Z",
"departure": "2019-07-04T09:46:42Z"
},
"distance": 10621,
"load": [
2
],
"activities": [
{
"jobId": "job6",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.5043,
"lng": 13.4091
},
"time": {
"arrival": "2019-07-04T09:48:54Z",
"departure": "2019-07-04T09:58:54Z"
},
"distance": 11944,
"load": [
0
],
"activities": [
{
"jobId": "reload",
"type": "reload"
}
]
},
{
"location": {
"lat": 52.4922,
"lng": 13.4593
},
"time": {
"arrival": "2019-07-04T10:05:00Z",
"departure": "2019-07-04T10:10:00Z"
},
"distance": 15603,
"load": [
1
],
"activities": [
{
"jobId": "job5",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T10:16:18Z",
"departure": "2019-07-04T10:21:18Z"
},
"distance": 19381,
"load": [
2
],
"activities": [
{
"jobId": "job1",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T10:28:48Z",
"departure": "2019-07-04T10:28:48Z"
},
"distance": 23876,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 52.38156800000001,
"distance": 23876,
"duration": 5328,
"times": {
"driving": 2388,
"serving": 2940,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
Relations
These examples demonstrates how to use relation feature.
Relation of Any type
In this example, any
relation locks two jobs to specific vehicle in any order.
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 240.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job4",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5145,
"lng": 13.3513
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
}
],
"relations": [
{
"type": "any",
"jobs": [
"job1",
"job3"
],
"vehicleId": "vehicle_1"
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1",
"vehicle_2"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
}
}
],
"capacity": [
2
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Solution
{
"statistic": {
"cost": 107.17656600000001,
"distance": 64505,
"duration": 10461,
"times": {
"driving": 9321,
"serving": 1140,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_2",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
2
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5145,
"lng": 13.3513
},
"time": {
"arrival": "2019-07-04T09:21:41Z",
"departure": "2019-07-04T09:26:41Z"
},
"distance": 8996,
"load": [
1
],
"activities": [
{
"jobId": "job4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"arrival": "2019-07-04T09:41:26Z",
"departure": "2019-07-04T09:45:26Z"
},
"distance": 14028,
"load": [
0
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "2019-07-04T10:18:32Z",
"departure": "2019-07-04T10:18:32Z"
},
"distance": 27524,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 50.150672,
"distance": 27524,
"duration": 4712,
"times": {
"driving": 4172,
"serving": 540,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
2
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T09:41:15Z",
"departure": "2019-07-04T09:46:15Z"
},
"distance": 19648,
"load": [
1
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"time": {
"arrival": "2019-07-04T10:02:31Z",
"departure": "2019-07-04T10:07:31Z"
},
"distance": 25642,
"load": [
0
],
"activities": [
{
"jobId": "job3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "2019-07-04T10:35:49Z",
"departure": "2019-07-04T10:35:49Z"
},
"distance": 36981,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 57.02589400000001,
"distance": 36981,
"duration": 5749,
"times": {
"driving": 5149,
"serving": 600,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
Relation of Strict type
In this example, strict
relation locks two jobs to specific vehicle starting from departure.
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 240.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job4",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5145,
"lng": 13.3513
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
}
],
"relations": [
{
"type": "strict",
"jobs": [
"departure",
"job4",
"job1"
],
"vehicleId": "vehicle_1"
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
}
}
],
"capacity": [
10
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Solution
{
"statistic": {
"cost": 60.354318000000006,
"distance": 34303,
"duration": 6553,
"times": {
"driving": 5413,
"serving": 1140,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
4
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5145,
"lng": 13.3513
},
"time": {
"arrival": "2019-07-04T09:22:23Z",
"departure": "2019-07-04T09:27:23Z"
},
"distance": 8621,
"load": [
3
],
"activities": [
{
"jobId": "job4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T09:48:51Z",
"departure": "2019-07-04T09:53:51Z"
},
"distance": 16956,
"load": [
2
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"arrival": "2019-07-04T10:04:40Z",
"departure": "2019-07-04T10:08:40Z"
},
"distance": 20810,
"load": [
1
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"time": {
"arrival": "2019-07-04T10:14:29Z",
"departure": "2019-07-04T10:19:29Z"
},
"distance": 22964,
"load": [
0
],
"activities": [
{
"jobId": "job3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "2019-07-04T10:49:13Z",
"departure": "2019-07-04T10:49:13Z"
},
"distance": 34303,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 60.354318000000006,
"distance": 34303,
"duration": 6553,
"times": {
"driving": 5413,
"serving": 1140,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
Skills
This example demonstrates how to use the skills feature with jobs and vehicles. In general, the skills feature is useful for locking specific jobs to specific vehicles.
Complete problem json
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0
}
],
"demand": [
1
]
}
],
"skills": {
"allOf": [
"fridge"
],
"noneOf": [
"washing_machine"
]
}
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 240.0
}
],
"demand": [
1
]
}
],
"skills": {
"allOf": [
"handyman"
]
}
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle_with_fridge",
"vehicleIds": [
"vehicle_with_fridge_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
}
],
"capacity": [
2
],
"skills": [
"fridge"
]
},
{
"typeId": "vehicle_with_handyman",
"vehicleIds": [
"vehicle_with_handyman_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
}
],
"capacity": [
2
],
"skills": [
"handyman"
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Complete solution json
{
"statistic": {
"cost": 64.31331800000001,
"distance": 16188,
"duration": 3553,
"times": {
"driving": 3013,
"serving": 540,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_with_handyman_1",
"typeId": "vehicle_with_handyman",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
1
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"arrival": "2019-07-04T09:08:28Z",
"departure": "2019-07-04T09:12:28Z"
},
"distance": 2470,
"load": [
0
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:22:06Z",
"departure": "2019-07-04T09:22:06Z"
},
"distance": 5138,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 29.400356000000002,
"distance": 5138,
"duration": 1326,
"times": {
"driving": 1086,
"serving": 240,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_with_fridge_1",
"typeId": "vehicle_with_fridge",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
1
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T09:15:12Z",
"departure": "2019-07-04T09:20:12Z"
},
"distance": 5112,
"load": [
0
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:37:07Z",
"departure": "2019-07-04T09:37:07Z"
},
"distance": 11050,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 34.912962,
"distance": 11050,
"duration": 2227,
"times": {
"driving": 1927,
"serving": 300,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
Multiple routing profiles
This example demonstrates how to use multiple routing profiles: car
and truck
.
List of problem locations
[
{
"lat": 52.52599,
"lng": 13.45413
},
{
"lat": 52.5225,
"lng": 13.4095
},
{
"lat": 52.5316,
"lng": 13.3884
}
]
Routing matrix for car
{
"profile": "normal_car",
"travelTimes": [
0,
681,
905,
750,
0,
546,
891,
502,
0
],
"distances": [
0,
3840,
5283,
4696,
0,
2668,
5112,
2470,
0
]
}
Routing matrix for truck
{
"profile": "normal_truck",
"travelTimes": [
0,
906,
1218,
970,
0,
750,
1152,
644,
0
],
"distances": [
0,
3840,
5283,
4482,
0,
2768,
5112,
2357,
0
]
}
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 240.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 600.0
}
],
"demand": [
10
]
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "my_car",
"vehicleIds": [
"my_car_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
}
],
"capacity": [
1
]
},
{
"typeId": "my_truck",
"vehicleIds": [
"my_truck_1"
],
"profile": "normal_truck",
"costs": {
"fixed": 44.0,
"distance": 0.0003,
"time": 0.005
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
}
],
"capacity": [
10
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
},
{
"name": "normal_truck",
"type": "truck"
}
]
}
}
Solution
{
"statistic": {
"cost": 89.371516,
"distance": 15520,
"duration": 4030,
"times": {
"driving": 3190,
"serving": 840,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "my_car_1",
"typeId": "my_car",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
1
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T09:14:51Z",
"departure": "2019-07-04T09:18:51Z"
},
"distance": 5112,
"load": [
0
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:33:56Z",
"departure": "2019-07-04T09:33:56Z"
},
"distance": 10395,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 33.864016,
"distance": 10395,
"duration": 2036,
"times": {
"driving": 1796,
"serving": 240,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "my_truck_1",
"typeId": "my_truck",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
10
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"time": {
"arrival": "2019-07-04T09:10:44Z",
"departure": "2019-07-04T09:20:44Z"
},
"distance": 2357,
"load": [
0
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:33:14Z",
"departure": "2019-07-04T09:33:14Z"
},
"distance": 5125,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 55.5075,
"distance": 5125,
"duration": 1994,
"times": {
"driving": 1394,
"serving": 600,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
Usage with cli
vrp-cli solve pragmatic profiles.basic.problem.json -m profiles.basic.matrix.car.json -m profiles.basic.matrix.truck -o profiles.basic.solution.json
Unassigned jobs
This example demonstrates one job which is unassigned due to unreachable location.
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0,
"times": [
[
"2019-07-04T09:00:00Z",
"2019-07-04T18:00:00Z"
],
[
"2019-07-05T09:00:00Z",
"2019-07-05T18:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4576,
"lng": 13.1778
},
"duration": 240.0,
"times": [
[
"2019-07-04T10:00:00Z",
"2019-07-04T16:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"duration": 300.0
}
],
"demand": [
1
]
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"latest": {
"time": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
}
],
"capacity": [
10
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
Solution
{
"statistic": {
"cost": 43.091514000000004,
"distance": 13687,
"duration": 3819,
"times": {
"driving": 3219,
"serving": 600,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T09:00:00Z",
"departure": "2019-07-04T09:00:00Z"
},
"distance": 0,
"load": [
2
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"time": {
"arrival": "2019-07-04T09:12:41Z",
"departure": "2019-07-04T09:17:41Z"
},
"distance": 2641,
"load": [
1
],
"activities": [
{
"jobId": "job3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"time": {
"arrival": "2019-07-04T09:38:22Z",
"departure": "2019-07-04T09:43:22Z"
},
"distance": 8404,
"load": [
0
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5316,
"lng": 13.3884
},
"time": {
"arrival": "2019-07-04T10:03:39Z",
"departure": "2019-07-04T10:03:39Z"
},
"distance": 13687,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 43.091514000000004,
"distance": 13687,
"duration": 3819,
"times": {
"driving": 3219,
"serving": 600,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": [
{
"jobId": "job2",
"reasons": [
{
"code": "REACHABLE_CONSTRAINT",
"description": "location unreachable"
}
]
}
]
}
Objective examples
Examples in this section demonstrate how different objectives affect final solution. All of them use the same problem variant with different objectives.
Essentially, the problem definition has the following parameters:
50
deliveries with demand1
5
vehicles with capacity20
- fixed vehicle cost is
20
- no time windows
Information regarding objective schema can be found here.
Default behavior: fleet and cost minimization
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5697304,
"lng": 13.3848221
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5060419,
"lng": 13.5152641
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5421315,
"lng": 13.5189513
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job4",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5243421,
"lng": 13.4619776
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job5",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4629002,
"lng": 13.4757055
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job6",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4960479,
"lng": 13.3915876
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job7",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5372914,
"lng": 13.3996298
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job8",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5429597,
"lng": 13.3989552
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job9",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5678751,
"lng": 13.4231417
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job10",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4945572,
"lng": 13.4698049
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job11",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4989511,
"lng": 13.4740528
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job12",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4658835,
"lng": 13.4461224
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job13",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5685168,
"lng": 13.3690720
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job14",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4742821,
"lng": 13.3628588
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job15",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5650163,
"lng": 13.3027992
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job16",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5496702,
"lng": 13.4286263
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job17",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5058684,
"lng": 13.4750990
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job18",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5473416,
"lng": 13.3327894
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job19",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5276784,
"lng": 13.5465640
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job20",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5192039,
"lng": 13.3044440
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job21",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5228904,
"lng": 13.4418623
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job22",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4828453,
"lng": 13.4363713
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job23",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5291335,
"lng": 13.3668934
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job24",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5261554,
"lng": 13.5062954
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job25",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5189653,
"lng": 13.3890068
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job26",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5090143,
"lng": 13.4368189
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job27",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4940454,
"lng": 13.3788834
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job28",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5065998,
"lng": 13.3689955
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job29",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5473490,
"lng": 13.3733163
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job30",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4695374,
"lng": 13.4914662
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job31",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4868236,
"lng": 13.3353656
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job32",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4661617,
"lng": 13.3226920
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job33",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4917198,
"lng": 13.5251532
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job34",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5431264,
"lng": 13.4416407
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job35",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5426716,
"lng": 13.5161692
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job36",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4708241,
"lng": 13.3598752
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job37",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4737341,
"lng": 13.3866700
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job38",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5404107,
"lng": 13.3914127
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job39",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5492619,
"lng": 13.3693560
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job40",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4827319,
"lng": 13.3157235
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job41",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4711004,
"lng": 13.3321906
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job42",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4871049,
"lng": 13.5423247
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job43",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5614441,
"lng": 13.4194712
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job44",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5414557,
"lng": 13.5276390
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job45",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5425207,
"lng": 13.4139155
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job46",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5632095,
"lng": 13.2940051
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job47",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5146285,
"lng": 13.2852959
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job48",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4855438,
"lng": 13.3832067
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job49",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5279215,
"lng": 13.4995315
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job50",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4959052,
"lng": 13.3539713
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1",
"vehicle_2",
"vehicle_3",
"vehicle_4",
"vehicle_5"
],
"profile": "car",
"costs": {
"fixed": 20.0,
"distance": 0.0002,
"time": 0.005
},
"shifts": [
{
"start": {
"earliest": "1970-01-01T00:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
},
"end": {
"latest": "1970-01-01T23:59:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
}
}
],
"capacity": [
20
]
}
],
"profiles": [
{
"name": "car",
"type": "car"
}
]
},
"objectives": {
"primary": [
{
"type": "minimize-tours"
},
{
"type": "minimize-unassigned"
}
],
"secondary": [
{
"type": "minimize-cost"
}
]
}
}
Solution
{
"statistic": {
"cost": 185.74319999999997,
"distance": 115366,
"duration": 20534,
"times": {
"driving": 11534,
"serving": 9000,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
10
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.4827319,
"lng": 13.3157235
},
"time": {
"arrival": "1970-01-01T00:04:56Z",
"departure": "1970-01-01T00:07:56Z"
},
"distance": 2960,
"load": [
9
],
"activities": [
{
"jobId": "job40",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4868236,
"lng": 13.3353656
},
"time": {
"arrival": "1970-01-01T00:10:17Z",
"departure": "1970-01-01T00:13:17Z"
},
"distance": 4367,
"load": [
8
],
"activities": [
{
"jobId": "job31",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4959052,
"lng": 13.3539713
},
"time": {
"arrival": "1970-01-01T00:15:59Z",
"departure": "1970-01-01T00:18:59Z"
},
"distance": 5983,
"load": [
7
],
"activities": [
{
"jobId": "job50",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4940454,
"lng": 13.3788834
},
"time": {
"arrival": "1970-01-01T00:21:49Z",
"departure": "1970-01-01T00:24:49Z"
},
"distance": 7684,
"load": [
6
],
"activities": [
{
"jobId": "job27",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4960479,
"lng": 13.3915876
},
"time": {
"arrival": "1970-01-01T00:26:18Z",
"departure": "1970-01-01T00:29:18Z"
},
"distance": 8573,
"load": [
5
],
"activities": [
{
"jobId": "job6",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4855438,
"lng": 13.3832067
},
"time": {
"arrival": "1970-01-01T00:31:28Z",
"departure": "1970-01-01T00:34:28Z"
},
"distance": 9873,
"load": [
4
],
"activities": [
{
"jobId": "job48",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4742821,
"lng": 13.3628588
},
"time": {
"arrival": "1970-01-01T00:37:34Z",
"departure": "1970-01-01T00:40:34Z"
},
"distance": 11737,
"load": [
3
],
"activities": [
{
"jobId": "job14",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4708241,
"lng": 13.3598752
},
"time": {
"arrival": "1970-01-01T00:41:17Z",
"departure": "1970-01-01T00:44:17Z"
},
"distance": 12172,
"load": [
2
],
"activities": [
{
"jobId": "job36",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4711004,
"lng": 13.3321906
},
"time": {
"arrival": "1970-01-01T00:47:25Z",
"departure": "1970-01-01T00:50:25Z"
},
"distance": 14050,
"load": [
1
],
"activities": [
{
"jobId": "job41",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4661617,
"lng": 13.322692
},
"time": {
"arrival": "1970-01-01T00:51:50Z",
"departure": "1970-01-01T00:54:50Z"
},
"distance": 14897,
"load": [
0
],
"activities": [
{
"jobId": "job32",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:59:31Z",
"departure": "1970-01-01T00:59:31Z"
},
"distance": 17708,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 41.3966,
"distance": 17708,
"duration": 3571,
"times": {
"driving": 1771,
"serving": 1800,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_4",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
20
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.4737341,
"lng": 13.38667
},
"time": {
"arrival": "1970-01-01T00:12:00Z",
"departure": "1970-01-01T00:15:00Z"
},
"distance": 7195,
"load": [
19
],
"activities": [
{
"jobId": "job37",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4828453,
"lng": 13.4363713
},
"time": {
"arrival": "1970-01-01T00:20:52Z",
"departure": "1970-01-01T00:23:52Z"
},
"distance": 10714,
"load": [
18
],
"activities": [
{
"jobId": "job22",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4945572,
"lng": 13.4698049
},
"time": {
"arrival": "1970-01-01T00:28:13Z",
"departure": "1970-01-01T00:31:13Z"
},
"distance": 13329,
"load": [
17
],
"activities": [
{
"jobId": "job10",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4989511,
"lng": 13.4740528
},
"time": {
"arrival": "1970-01-01T00:32:10Z",
"departure": "1970-01-01T00:35:10Z"
},
"distance": 13897,
"load": [
16
],
"activities": [
{
"jobId": "job11",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5058684,
"lng": 13.475099
},
"time": {
"arrival": "1970-01-01T00:36:27Z",
"departure": "1970-01-01T00:39:27Z"
},
"distance": 14670,
"load": [
15
],
"activities": [
{
"jobId": "job17",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5090143,
"lng": 13.4368189
},
"time": {
"arrival": "1970-01-01T00:43:49Z",
"departure": "1970-01-01T00:46:49Z"
},
"distance": 17287,
"load": [
14
],
"activities": [
{
"jobId": "job26",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5228904,
"lng": 13.4418623
},
"time": {
"arrival": "1970-01-01T00:49:27Z",
"departure": "1970-01-01T00:52:27Z"
},
"distance": 18869,
"load": [
13
],
"activities": [
{
"jobId": "job21",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5243421,
"lng": 13.4619776
},
"time": {
"arrival": "1970-01-01T00:54:44Z",
"departure": "1970-01-01T00:57:44Z"
},
"distance": 20241,
"load": [
12
],
"activities": [
{
"jobId": "job4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5279215,
"lng": 13.4995315
},
"time": {
"arrival": "1970-01-01T01:02:01Z",
"departure": "1970-01-01T01:05:01Z"
},
"distance": 22815,
"load": [
11
],
"activities": [
{
"jobId": "job49",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5261554,
"lng": 13.5062954
},
"time": {
"arrival": "1970-01-01T01:05:51Z",
"departure": "1970-01-01T01:08:51Z"
},
"distance": 23313,
"load": [
10
],
"activities": [
{
"jobId": "job24",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5426716,
"lng": 13.5161692
},
"time": {
"arrival": "1970-01-01T01:12:07Z",
"departure": "1970-01-01T01:15:07Z"
},
"distance": 25269,
"load": [
9
],
"activities": [
{
"jobId": "job35",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5421315,
"lng": 13.5189513
},
"time": {
"arrival": "1970-01-01T01:15:27Z",
"departure": "1970-01-01T01:18:27Z"
},
"distance": 25467,
"load": [
8
],
"activities": [
{
"jobId": "job3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5414557,
"lng": 13.527639
},
"time": {
"arrival": "1970-01-01T01:19:26Z",
"departure": "1970-01-01T01:22:26Z"
},
"distance": 26060,
"load": [
7
],
"activities": [
{
"jobId": "job44",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5276784,
"lng": 13.546564
},
"time": {
"arrival": "1970-01-01T01:25:46Z",
"departure": "1970-01-01T01:28:46Z"
},
"distance": 28059,
"load": [
6
],
"activities": [
{
"jobId": "job19",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5060419,
"lng": 13.5152641
},
"time": {
"arrival": "1970-01-01T01:34:07Z",
"departure": "1970-01-01T01:37:07Z"
},
"distance": 31268,
"load": [
5
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4917198,
"lng": 13.5251532
},
"time": {
"arrival": "1970-01-01T01:40:00Z",
"departure": "1970-01-01T01:43:00Z"
},
"distance": 32997,
"load": [
4
],
"activities": [
{
"jobId": "job33",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4871049,
"lng": 13.5423247
},
"time": {
"arrival": "1970-01-01T01:45:07Z",
"departure": "1970-01-01T01:48:07Z"
},
"distance": 34269,
"load": [
3
],
"activities": [
{
"jobId": "job42",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4695374,
"lng": 13.4914662
},
"time": {
"arrival": "1970-01-01T01:54:43Z",
"departure": "1970-01-01T01:57:43Z"
},
"distance": 38233,
"load": [
2
],
"activities": [
{
"jobId": "job30",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4629002,
"lng": 13.4757055
},
"time": {
"arrival": "1970-01-01T01:59:53Z",
"departure": "1970-01-01T02:02:53Z"
},
"distance": 39532,
"load": [
1
],
"activities": [
{
"jobId": "job5",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4658835,
"lng": 13.4461224
},
"time": {
"arrival": "1970-01-01T02:06:16Z",
"departure": "1970-01-01T02:09:16Z"
},
"distance": 41566,
"load": [
0
],
"activities": [
{
"jobId": "job12",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T02:27:54Z",
"departure": "1970-01-01T02:27:54Z"
},
"distance": 52748,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 74.91959999999997,
"distance": 52748,
"duration": 8874,
"times": {
"driving": 5274,
"serving": 3600,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_5",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
20
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5065998,
"lng": 13.3689955
},
"time": {
"arrival": "1970-01-01T00:12:24Z",
"departure": "1970-01-01T00:15:24Z"
},
"distance": 7442,
"load": [
19
],
"activities": [
{
"jobId": "job28",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5189653,
"lng": 13.3890068
},
"time": {
"arrival": "1970-01-01T00:18:37Z",
"departure": "1970-01-01T00:21:37Z"
},
"distance": 9374,
"load": [
18
],
"activities": [
{
"jobId": "job25",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5291335,
"lng": 13.3668934
},
"time": {
"arrival": "1970-01-01T00:24:45Z",
"departure": "1970-01-01T00:27:45Z"
},
"distance": 11251,
"load": [
17
],
"activities": [
{
"jobId": "job23",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5404107,
"lng": 13.3914127
},
"time": {
"arrival": "1970-01-01T00:31:13Z",
"departure": "1970-01-01T00:34:13Z"
},
"distance": 13332,
"load": [
16
],
"activities": [
{
"jobId": "job38",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5372914,
"lng": 13.3996298
},
"time": {
"arrival": "1970-01-01T00:35:19Z",
"departure": "1970-01-01T00:38:19Z"
},
"distance": 13988,
"load": [
15
],
"activities": [
{
"jobId": "job7",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5429597,
"lng": 13.3989552
},
"time": {
"arrival": "1970-01-01T00:39:22Z",
"departure": "1970-01-01T00:42:22Z"
},
"distance": 14621,
"load": [
14
],
"activities": [
{
"jobId": "job8",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5425207,
"lng": 13.4139155
},
"time": {
"arrival": "1970-01-01T00:44:03Z",
"departure": "1970-01-01T00:47:03Z"
},
"distance": 15635,
"load": [
13
],
"activities": [
{
"jobId": "job45",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5431264,
"lng": 13.4416407
},
"time": {
"arrival": "1970-01-01T00:50:11Z",
"departure": "1970-01-01T00:53:11Z"
},
"distance": 17513,
"load": [
12
],
"activities": [
{
"jobId": "job34",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5496702,
"lng": 13.4286263
},
"time": {
"arrival": "1970-01-01T00:55:05Z",
"departure": "1970-01-01T00:58:05Z"
},
"distance": 18656,
"load": [
11
],
"activities": [
{
"jobId": "job16",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5614441,
"lng": 13.4194712
},
"time": {
"arrival": "1970-01-01T01:00:30Z",
"departure": "1970-01-01T01:03:30Z"
},
"distance": 20106,
"load": [
10
],
"activities": [
{
"jobId": "job43",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5678751,
"lng": 13.4231417
},
"time": {
"arrival": "1970-01-01T01:04:46Z",
"departure": "1970-01-01T01:07:46Z"
},
"distance": 20864,
"load": [
9
],
"activities": [
{
"jobId": "job9",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5697304,
"lng": 13.3848221
},
"time": {
"arrival": "1970-01-01T01:12:06Z",
"departure": "1970-01-01T01:15:06Z"
},
"distance": 23465,
"load": [
8
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5685168,
"lng": 13.369072
},
"time": {
"arrival": "1970-01-01T01:16:53Z",
"departure": "1970-01-01T01:19:53Z"
},
"distance": 24539,
"load": [
7
],
"activities": [
{
"jobId": "job13",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.547349,
"lng": 13.3733163
},
"time": {
"arrival": "1970-01-01T01:23:50Z",
"departure": "1970-01-01T01:26:50Z"
},
"distance": 26913,
"load": [
6
],
"activities": [
{
"jobId": "job29",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5492619,
"lng": 13.369356
},
"time": {
"arrival": "1970-01-01T01:27:24Z",
"departure": "1970-01-01T01:30:24Z"
},
"distance": 27255,
"load": [
5
],
"activities": [
{
"jobId": "job39",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5473416,
"lng": 13.3327894
},
"time": {
"arrival": "1970-01-01T01:34:32Z",
"departure": "1970-01-01T01:37:32Z"
},
"distance": 29739,
"load": [
4
],
"activities": [
{
"jobId": "job18",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5650163,
"lng": 13.3027992
},
"time": {
"arrival": "1970-01-01T01:42:15Z",
"departure": "1970-01-01T01:45:15Z"
},
"distance": 32566,
"load": [
3
],
"activities": [
{
"jobId": "job15",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5632095,
"lng": 13.2940051
},
"time": {
"arrival": "1970-01-01T01:46:18Z",
"departure": "1970-01-01T01:49:18Z"
},
"distance": 33194,
"load": [
2
],
"activities": [
{
"jobId": "job46",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5192039,
"lng": 13.304444
},
"time": {
"arrival": "1970-01-01T01:57:33Z",
"departure": "1970-01-01T02:00:33Z"
},
"distance": 38143,
"load": [
1
],
"activities": [
{
"jobId": "job20",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5146285,
"lng": 13.2852959
},
"time": {
"arrival": "1970-01-01T02:02:52Z",
"departure": "1970-01-01T02:05:52Z"
},
"distance": 39537,
"load": [
0
],
"activities": [
{
"jobId": "job47",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T02:14:49Z",
"departure": "1970-01-01T02:14:49Z"
},
"distance": 44910,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 69.42699999999999,
"distance": 44910,
"duration": 8089,
"times": {
"driving": 4489,
"serving": 3600,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
By default, primary objective for the solver is to minimize fleet usage and amount of unassigned jobs, the secondary objective is total cost minimization:
"objectives": {
"primary": [
{
"type": "minimize-tours"
},
{
"type": "minimize-unassigned"
}
],
"secondary": [
{
"type": "minimize-cost"
}
]
}
As result, solution has minimum amount of vehicles used to serve all jobs (3
).
Note, that load between these vehicles is not equally distributed as it increases the total cost.
Balance max load
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5697304,
"lng": 13.3848221
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5060419,
"lng": 13.5152641
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5421315,
"lng": 13.5189513
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job4",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5243421,
"lng": 13.4619776
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job5",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4629002,
"lng": 13.4757055
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job6",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4960479,
"lng": 13.3915876
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job7",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5372914,
"lng": 13.3996298
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job8",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5429597,
"lng": 13.3989552
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job9",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5678751,
"lng": 13.4231417
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job10",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4945572,
"lng": 13.4698049
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job11",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4989511,
"lng": 13.4740528
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job12",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4658835,
"lng": 13.4461224
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job13",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5685168,
"lng": 13.3690720
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job14",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4742821,
"lng": 13.3628588
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job15",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5650163,
"lng": 13.3027992
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job16",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5496702,
"lng": 13.4286263
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job17",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5058684,
"lng": 13.4750990
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job18",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5473416,
"lng": 13.3327894
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job19",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5276784,
"lng": 13.5465640
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job20",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5192039,
"lng": 13.3044440
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job21",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5228904,
"lng": 13.4418623
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job22",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4828453,
"lng": 13.4363713
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job23",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5291335,
"lng": 13.3668934
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job24",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5261554,
"lng": 13.5062954
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job25",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5189653,
"lng": 13.3890068
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job26",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5090143,
"lng": 13.4368189
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job27",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4940454,
"lng": 13.3788834
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job28",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5065998,
"lng": 13.3689955
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job29",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5473490,
"lng": 13.3733163
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job30",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4695374,
"lng": 13.4914662
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job31",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4868236,
"lng": 13.3353656
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job32",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4661617,
"lng": 13.3226920
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job33",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4917198,
"lng": 13.5251532
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job34",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5431264,
"lng": 13.4416407
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job35",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5426716,
"lng": 13.5161692
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job36",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4708241,
"lng": 13.3598752
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job37",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4737341,
"lng": 13.3866700
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job38",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5404107,
"lng": 13.3914127
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job39",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5492619,
"lng": 13.3693560
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job40",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4827319,
"lng": 13.3157235
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job41",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4711004,
"lng": 13.3321906
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job42",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4871049,
"lng": 13.5423247
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job43",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5614441,
"lng": 13.4194712
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job44",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5414557,
"lng": 13.5276390
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job45",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5425207,
"lng": 13.4139155
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job46",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5632095,
"lng": 13.2940051
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job47",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5146285,
"lng": 13.2852959
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job48",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4855438,
"lng": 13.3832067
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job49",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5279215,
"lng": 13.4995315
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job50",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4959052,
"lng": 13.3539713
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1",
"vehicle_2",
"vehicle_3",
"vehicle_4",
"vehicle_5"
],
"profile": "car",
"costs": {
"fixed": 20.0,
"distance": 0.0002,
"time": 0.005
},
"shifts": [
{
"start": {
"earliest": "1970-01-01T00:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
},
"end": {
"latest": "1970-01-01T23:59:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
}
}
],
"capacity": [
20
]
}
],
"profiles": [
{
"name": "car",
"type": "car"
}
]
},
"objectives": {
"primary": [
{
"type": "minimize-unassigned"
}
],
"secondary": [
{
"type": "minimize-cost"
},
{
"type": "balance-max-load",
"options": {
"tolerance": 0.05,
"threshold": 0.075
}
}
]
}
}
Solution
{
"statistic": {
"cost": 223.78519999999997,
"distance": 141126,
"duration": 23112,
"times": {
"driving": 14112,
"serving": 9000,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
12
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.4827319,
"lng": 13.3157235
},
"time": {
"arrival": "1970-01-01T00:04:56Z",
"departure": "1970-01-01T00:07:56Z"
},
"distance": 2960,
"load": [
11
],
"activities": [
{
"jobId": "job40",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4868236,
"lng": 13.3353656
},
"time": {
"arrival": "1970-01-01T00:10:17Z",
"departure": "1970-01-01T00:13:17Z"
},
"distance": 4367,
"load": [
10
],
"activities": [
{
"jobId": "job31",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4959052,
"lng": 13.3539713
},
"time": {
"arrival": "1970-01-01T00:15:59Z",
"departure": "1970-01-01T00:18:59Z"
},
"distance": 5983,
"load": [
9
],
"activities": [
{
"jobId": "job50",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5065998,
"lng": 13.3689955
},
"time": {
"arrival": "1970-01-01T00:21:36Z",
"departure": "1970-01-01T00:24:36Z"
},
"distance": 7549,
"load": [
8
],
"activities": [
{
"jobId": "job28",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4940454,
"lng": 13.3788834
},
"time": {
"arrival": "1970-01-01T00:27:11Z",
"departure": "1970-01-01T00:30:11Z"
},
"distance": 9099,
"load": [
7
],
"activities": [
{
"jobId": "job27",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4960479,
"lng": 13.3915876
},
"time": {
"arrival": "1970-01-01T00:31:40Z",
"departure": "1970-01-01T00:34:40Z"
},
"distance": 9988,
"load": [
6
],
"activities": [
{
"jobId": "job6",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4855438,
"lng": 13.3832067
},
"time": {
"arrival": "1970-01-01T00:36:50Z",
"departure": "1970-01-01T00:39:50Z"
},
"distance": 11288,
"load": [
5
],
"activities": [
{
"jobId": "job48",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4737341,
"lng": 13.38667
},
"time": {
"arrival": "1970-01-01T00:42:04Z",
"departure": "1970-01-01T00:45:04Z"
},
"distance": 12623,
"load": [
4
],
"activities": [
{
"jobId": "job37",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4742821,
"lng": 13.3628588
},
"time": {
"arrival": "1970-01-01T00:47:46Z",
"departure": "1970-01-01T00:50:46Z"
},
"distance": 14239,
"load": [
3
],
"activities": [
{
"jobId": "job14",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4708241,
"lng": 13.3598752
},
"time": {
"arrival": "1970-01-01T00:51:29Z",
"departure": "1970-01-01T00:54:29Z"
},
"distance": 14674,
"load": [
2
],
"activities": [
{
"jobId": "job36",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4711004,
"lng": 13.3321906
},
"time": {
"arrival": "1970-01-01T00:57:37Z",
"departure": "1970-01-01T01:00:37Z"
},
"distance": 16552,
"load": [
1
],
"activities": [
{
"jobId": "job41",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4661617,
"lng": 13.322692
},
"time": {
"arrival": "1970-01-01T01:02:02Z",
"departure": "1970-01-01T01:05:02Z"
},
"distance": 17399,
"load": [
0
],
"activities": [
{
"jobId": "job32",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T01:09:43Z",
"departure": "1970-01-01T01:09:43Z"
},
"distance": 20210,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 44.956999999999994,
"distance": 20210,
"duration": 4183,
"times": {
"driving": 2023,
"serving": 2160,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_3",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
12
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5189653,
"lng": 13.3890068
},
"time": {
"arrival": "1970-01-01T00:15:36Z",
"departure": "1970-01-01T00:18:36Z"
},
"distance": 9357,
"load": [
11
],
"activities": [
{
"jobId": "job25",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5372914,
"lng": 13.3996298
},
"time": {
"arrival": "1970-01-01T00:22:12Z",
"departure": "1970-01-01T00:25:12Z"
},
"distance": 11520,
"load": [
10
],
"activities": [
{
"jobId": "job7",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5425207,
"lng": 13.4139155
},
"time": {
"arrival": "1970-01-01T00:27:05Z",
"departure": "1970-01-01T00:30:05Z"
},
"distance": 12649,
"load": [
9
],
"activities": [
{
"jobId": "job45",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5429597,
"lng": 13.3989552
},
"time": {
"arrival": "1970-01-01T00:31:46Z",
"departure": "1970-01-01T00:34:46Z"
},
"distance": 13663,
"load": [
8
],
"activities": [
{
"jobId": "job8",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5404107,
"lng": 13.3914127
},
"time": {
"arrival": "1970-01-01T00:35:44Z",
"departure": "1970-01-01T00:38:44Z"
},
"distance": 14247,
"load": [
7
],
"activities": [
{
"jobId": "job38",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.547349,
"lng": 13.3733163
},
"time": {
"arrival": "1970-01-01T00:41:09Z",
"departure": "1970-01-01T00:44:09Z"
},
"distance": 15695,
"load": [
6
],
"activities": [
{
"jobId": "job29",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5492619,
"lng": 13.369356
},
"time": {
"arrival": "1970-01-01T00:44:43Z",
"departure": "1970-01-01T00:47:43Z"
},
"distance": 16037,
"load": [
5
],
"activities": [
{
"jobId": "job39",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5473416,
"lng": 13.3327894
},
"time": {
"arrival": "1970-01-01T00:51:51Z",
"departure": "1970-01-01T00:54:51Z"
},
"distance": 18521,
"load": [
4
],
"activities": [
{
"jobId": "job18",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5650163,
"lng": 13.3027992
},
"time": {
"arrival": "1970-01-01T00:59:34Z",
"departure": "1970-01-01T01:02:34Z"
},
"distance": 21348,
"load": [
3
],
"activities": [
{
"jobId": "job15",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5632095,
"lng": 13.2940051
},
"time": {
"arrival": "1970-01-01T01:03:37Z",
"departure": "1970-01-01T01:06:37Z"
},
"distance": 21976,
"load": [
2
],
"activities": [
{
"jobId": "job46",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5192039,
"lng": 13.304444
},
"time": {
"arrival": "1970-01-01T01:14:52Z",
"departure": "1970-01-01T01:17:52Z"
},
"distance": 26925,
"load": [
1
],
"activities": [
{
"jobId": "job20",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5146285,
"lng": 13.2852959
},
"time": {
"arrival": "1970-01-01T01:20:11Z",
"departure": "1970-01-01T01:23:11Z"
},
"distance": 28319,
"load": [
0
],
"activities": [
{
"jobId": "job47",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T01:32:08Z",
"departure": "1970-01-01T01:32:08Z"
},
"distance": 33692,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 54.37839999999999,
"distance": 33692,
"duration": 5528,
"times": {
"driving": 3368,
"serving": 2160,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_4",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
13
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.4828453,
"lng": 13.4363713
},
"time": {
"arrival": "1970-01-01T00:17:48Z",
"departure": "1970-01-01T00:20:48Z"
},
"distance": 10676,
"load": [
12
],
"activities": [
{
"jobId": "job22",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4945572,
"lng": 13.4698049
},
"time": {
"arrival": "1970-01-01T00:25:09Z",
"departure": "1970-01-01T00:28:09Z"
},
"distance": 13291,
"load": [
11
],
"activities": [
{
"jobId": "job10",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4989511,
"lng": 13.4740528
},
"time": {
"arrival": "1970-01-01T00:29:06Z",
"departure": "1970-01-01T00:32:06Z"
},
"distance": 13859,
"load": [
10
],
"activities": [
{
"jobId": "job11",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5058684,
"lng": 13.475099
},
"time": {
"arrival": "1970-01-01T00:33:23Z",
"departure": "1970-01-01T00:36:23Z"
},
"distance": 14632,
"load": [
9
],
"activities": [
{
"jobId": "job17",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5243421,
"lng": 13.4619776
},
"time": {
"arrival": "1970-01-01T00:40:07Z",
"departure": "1970-01-01T00:43:07Z"
},
"distance": 16872,
"load": [
8
],
"activities": [
{
"jobId": "job4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5228904,
"lng": 13.4418623
},
"time": {
"arrival": "1970-01-01T00:45:24Z",
"departure": "1970-01-01T00:48:24Z"
},
"distance": 18244,
"load": [
7
],
"activities": [
{
"jobId": "job21",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5431264,
"lng": 13.4416407
},
"time": {
"arrival": "1970-01-01T00:52:09Z",
"departure": "1970-01-01T00:55:09Z"
},
"distance": 20497,
"load": [
6
],
"activities": [
{
"jobId": "job34",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5496702,
"lng": 13.4286263
},
"time": {
"arrival": "1970-01-01T00:57:03Z",
"departure": "1970-01-01T01:00:03Z"
},
"distance": 21640,
"load": [
5
],
"activities": [
{
"jobId": "job16",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5614441,
"lng": 13.4194712
},
"time": {
"arrival": "1970-01-01T01:02:28Z",
"departure": "1970-01-01T01:05:28Z"
},
"distance": 23090,
"load": [
4
],
"activities": [
{
"jobId": "job43",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5678751,
"lng": 13.4231417
},
"time": {
"arrival": "1970-01-01T01:06:44Z",
"departure": "1970-01-01T01:09:44Z"
},
"distance": 23848,
"load": [
3
],
"activities": [
{
"jobId": "job9",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5697304,
"lng": 13.3848221
},
"time": {
"arrival": "1970-01-01T01:14:04Z",
"departure": "1970-01-01T01:17:04Z"
},
"distance": 26449,
"load": [
2
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5685168,
"lng": 13.369072
},
"time": {
"arrival": "1970-01-01T01:18:51Z",
"departure": "1970-01-01T01:21:51Z"
},
"distance": 27523,
"load": [
1
],
"activities": [
{
"jobId": "job13",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5291335,
"lng": 13.3668934
},
"time": {
"arrival": "1970-01-01T01:29:10Z",
"departure": "1970-01-01T01:32:10Z"
},
"distance": 31910,
"load": [
0
],
"activities": [
{
"jobId": "job23",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T01:47:18Z",
"departure": "1970-01-01T01:47:18Z"
},
"distance": 40988,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 60.38759999999999,
"distance": 40988,
"duration": 6438,
"times": {
"driving": 4098,
"serving": 2340,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_5",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
13
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.4658835,
"lng": 13.4461224
},
"time": {
"arrival": "1970-01-01T00:18:38Z",
"departure": "1970-01-01T00:21:38Z"
},
"distance": 11182,
"load": [
12
],
"activities": [
{
"jobId": "job12",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4629002,
"lng": 13.4757055
},
"time": {
"arrival": "1970-01-01T00:25:01Z",
"departure": "1970-01-01T00:28:01Z"
},
"distance": 13216,
"load": [
11
],
"activities": [
{
"jobId": "job5",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4695374,
"lng": 13.4914662
},
"time": {
"arrival": "1970-01-01T00:30:11Z",
"departure": "1970-01-01T00:33:11Z"
},
"distance": 14515,
"load": [
10
],
"activities": [
{
"jobId": "job30",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4871049,
"lng": 13.5423247
},
"time": {
"arrival": "1970-01-01T00:39:47Z",
"departure": "1970-01-01T00:42:47Z"
},
"distance": 18479,
"load": [
9
],
"activities": [
{
"jobId": "job42",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4917198,
"lng": 13.5251532
},
"time": {
"arrival": "1970-01-01T00:44:54Z",
"departure": "1970-01-01T00:47:54Z"
},
"distance": 19751,
"load": [
8
],
"activities": [
{
"jobId": "job33",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5060419,
"lng": 13.5152641
},
"time": {
"arrival": "1970-01-01T00:50:47Z",
"departure": "1970-01-01T00:53:47Z"
},
"distance": 21480,
"load": [
7
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5276784,
"lng": 13.546564
},
"time": {
"arrival": "1970-01-01T00:59:08Z",
"departure": "1970-01-01T01:02:08Z"
},
"distance": 24689,
"load": [
6
],
"activities": [
{
"jobId": "job19",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5414557,
"lng": 13.527639
},
"time": {
"arrival": "1970-01-01T01:05:28Z",
"departure": "1970-01-01T01:08:28Z"
},
"distance": 26688,
"load": [
5
],
"activities": [
{
"jobId": "job44",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5421315,
"lng": 13.5189513
},
"time": {
"arrival": "1970-01-01T01:09:27Z",
"departure": "1970-01-01T01:12:27Z"
},
"distance": 27281,
"load": [
4
],
"activities": [
{
"jobId": "job3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5426716,
"lng": 13.5161692
},
"time": {
"arrival": "1970-01-01T01:12:47Z",
"departure": "1970-01-01T01:15:47Z"
},
"distance": 27479,
"load": [
3
],
"activities": [
{
"jobId": "job35",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5261554,
"lng": 13.5062954
},
"time": {
"arrival": "1970-01-01T01:19:03Z",
"departure": "1970-01-01T01:22:03Z"
},
"distance": 29435,
"load": [
2
],
"activities": [
{
"jobId": "job24",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5279215,
"lng": 13.4995315
},
"time": {
"arrival": "1970-01-01T01:22:53Z",
"departure": "1970-01-01T01:25:53Z"
},
"distance": 29933,
"load": [
1
],
"activities": [
{
"jobId": "job49",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5090143,
"lng": 13.4368189
},
"time": {
"arrival": "1970-01-01T01:33:47Z",
"departure": "1970-01-01T01:36:47Z"
},
"distance": 34674,
"load": [
0
],
"activities": [
{
"jobId": "job26",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T01:56:03Z",
"departure": "1970-01-01T01:56:03Z"
},
"distance": 46236,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 64.06219999999999,
"distance": 46236,
"duration": 6963,
"times": {
"driving": 4623,
"serving": 2340,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
This objective balances max load across vehicles:
"objectives": {
"primary": [
{
"type": "minimize-unassigned"
}
],
"secondary": [
{
"type": "minimize-cost"
},
{
"type": "balance-max-load",
"options": {
"tolerance": 0.05,
"threshold": 0.075
}
}
]
}
As minimize-tours
objective is not set, all available vehicles are used serving 10
jobs per vehicle. Result total
cost is higher than for default objective.
Balance activities with fleet minimization
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5697304,
"lng": 13.3848221
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5060419,
"lng": 13.5152641
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5421315,
"lng": 13.5189513
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job4",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5243421,
"lng": 13.4619776
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job5",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4629002,
"lng": 13.4757055
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job6",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4960479,
"lng": 13.3915876
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job7",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5372914,
"lng": 13.3996298
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job8",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5429597,
"lng": 13.3989552
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job9",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5678751,
"lng": 13.4231417
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job10",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4945572,
"lng": 13.4698049
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job11",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4989511,
"lng": 13.4740528
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job12",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4658835,
"lng": 13.4461224
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job13",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5685168,
"lng": 13.3690720
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job14",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4742821,
"lng": 13.3628588
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job15",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5650163,
"lng": 13.3027992
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job16",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5496702,
"lng": 13.4286263
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job17",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5058684,
"lng": 13.4750990
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job18",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5473416,
"lng": 13.3327894
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job19",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5276784,
"lng": 13.5465640
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job20",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5192039,
"lng": 13.3044440
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job21",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5228904,
"lng": 13.4418623
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job22",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4828453,
"lng": 13.4363713
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job23",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5291335,
"lng": 13.3668934
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job24",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5261554,
"lng": 13.5062954
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job25",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5189653,
"lng": 13.3890068
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job26",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5090143,
"lng": 13.4368189
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job27",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4940454,
"lng": 13.3788834
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job28",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5065998,
"lng": 13.3689955
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job29",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5473490,
"lng": 13.3733163
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job30",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4695374,
"lng": 13.4914662
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job31",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4868236,
"lng": 13.3353656
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job32",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4661617,
"lng": 13.3226920
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job33",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4917198,
"lng": 13.5251532
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job34",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5431264,
"lng": 13.4416407
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job35",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5426716,
"lng": 13.5161692
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job36",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4708241,
"lng": 13.3598752
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job37",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4737341,
"lng": 13.3866700
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job38",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5404107,
"lng": 13.3914127
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job39",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5492619,
"lng": 13.3693560
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job40",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4827319,
"lng": 13.3157235
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job41",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4711004,
"lng": 13.3321906
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job42",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4871049,
"lng": 13.5423247
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job43",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5614441,
"lng": 13.4194712
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job44",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5414557,
"lng": 13.5276390
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job45",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5425207,
"lng": 13.4139155
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job46",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5632095,
"lng": 13.2940051
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job47",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5146285,
"lng": 13.2852959
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job48",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4855438,
"lng": 13.3832067
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job49",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5279215,
"lng": 13.4995315
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job50",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4959052,
"lng": 13.3539713
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1",
"vehicle_2",
"vehicle_3",
"vehicle_4",
"vehicle_5"
],
"profile": "car",
"costs": {
"fixed": 20.0,
"distance": 0.0002,
"time": 0.005
},
"shifts": [
{
"start": {
"earliest": "1970-01-01T00:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
},
"end": {
"latest": "1970-01-01T23:59:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
}
}
],
"capacity": [
20
]
}
],
"profiles": [
{
"name": "car",
"type": "car"
}
]
},
"objectives": {
"primary": [
{
"type": "minimize-unassigned"
},
{
"type": "minimize-tours"
}
],
"secondary": [
{
"type": "minimize-cost"
},
{
"type": "balance-activities",
"options": {
"tolerance": 0.05,
"threshold": 0.01
}
}
]
}
}
Solution
{
"statistic": {
"cost": 189.47459999999995,
"distance": 120698,
"duration": 21067,
"times": {
"driving": 12067,
"serving": 9000,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
16
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.4827319,
"lng": 13.3157235
},
"time": {
"arrival": "1970-01-01T00:04:56Z",
"departure": "1970-01-01T00:07:56Z"
},
"distance": 2960,
"load": [
15
],
"activities": [
{
"jobId": "job40",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4868236,
"lng": 13.3353656
},
"time": {
"arrival": "1970-01-01T00:10:17Z",
"departure": "1970-01-01T00:13:17Z"
},
"distance": 4367,
"load": [
14
],
"activities": [
{
"jobId": "job31",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4959052,
"lng": 13.3539713
},
"time": {
"arrival": "1970-01-01T00:15:59Z",
"departure": "1970-01-01T00:18:59Z"
},
"distance": 5983,
"load": [
13
],
"activities": [
{
"jobId": "job50",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5065998,
"lng": 13.3689955
},
"time": {
"arrival": "1970-01-01T00:21:36Z",
"departure": "1970-01-01T00:24:36Z"
},
"distance": 7549,
"load": [
12
],
"activities": [
{
"jobId": "job28",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5291335,
"lng": 13.3668934
},
"time": {
"arrival": "1970-01-01T00:28:47Z",
"departure": "1970-01-01T00:31:47Z"
},
"distance": 10061,
"load": [
11
],
"activities": [
{
"jobId": "job23",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5404107,
"lng": 13.3914127
},
"time": {
"arrival": "1970-01-01T00:35:15Z",
"departure": "1970-01-01T00:38:15Z"
},
"distance": 12142,
"load": [
10
],
"activities": [
{
"jobId": "job38",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5429597,
"lng": 13.3989552
},
"time": {
"arrival": "1970-01-01T00:39:13Z",
"departure": "1970-01-01T00:42:13Z"
},
"distance": 12726,
"load": [
9
],
"activities": [
{
"jobId": "job8",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5425207,
"lng": 13.4139155
},
"time": {
"arrival": "1970-01-01T00:43:54Z",
"departure": "1970-01-01T00:46:54Z"
},
"distance": 13740,
"load": [
8
],
"activities": [
{
"jobId": "job45",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5372914,
"lng": 13.3996298
},
"time": {
"arrival": "1970-01-01T00:48:47Z",
"departure": "1970-01-01T00:51:47Z"
},
"distance": 14869,
"load": [
7
],
"activities": [
{
"jobId": "job7",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5189653,
"lng": 13.3890068
},
"time": {
"arrival": "1970-01-01T00:55:23Z",
"departure": "1970-01-01T00:58:23Z"
},
"distance": 17032,
"load": [
6
],
"activities": [
{
"jobId": "job25",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4940454,
"lng": 13.3788834
},
"time": {
"arrival": "1970-01-01T01:03:09Z",
"departure": "1970-01-01T01:06:09Z"
},
"distance": 19890,
"load": [
5
],
"activities": [
{
"jobId": "job27",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4855438,
"lng": 13.3832067
},
"time": {
"arrival": "1970-01-01T01:07:48Z",
"departure": "1970-01-01T01:10:48Z"
},
"distance": 20881,
"load": [
4
],
"activities": [
{
"jobId": "job48",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4742821,
"lng": 13.3628588
},
"time": {
"arrival": "1970-01-01T01:13:54Z",
"departure": "1970-01-01T01:16:54Z"
},
"distance": 22745,
"load": [
3
],
"activities": [
{
"jobId": "job14",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4708241,
"lng": 13.3598752
},
"time": {
"arrival": "1970-01-01T01:17:37Z",
"departure": "1970-01-01T01:20:37Z"
},
"distance": 23180,
"load": [
2
],
"activities": [
{
"jobId": "job36",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4711004,
"lng": 13.3321906
},
"time": {
"arrival": "1970-01-01T01:23:45Z",
"departure": "1970-01-01T01:26:45Z"
},
"distance": 25058,
"load": [
1
],
"activities": [
{
"jobId": "job41",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4661617,
"lng": 13.322692
},
"time": {
"arrival": "1970-01-01T01:28:10Z",
"departure": "1970-01-01T01:31:10Z"
},
"distance": 25905,
"load": [
0
],
"activities": [
{
"jobId": "job32",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T01:35:51Z",
"departure": "1970-01-01T01:35:51Z"
},
"distance": 28716,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 54.49819999999999,
"distance": 28716,
"duration": 5751,
"times": {
"driving": 2871,
"serving": 2880,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_3",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
17
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.4960479,
"lng": 13.3915876
},
"time": {
"arrival": "1970-01-01T00:13:38Z",
"departure": "1970-01-01T00:16:38Z"
},
"distance": 8175,
"load": [
16
],
"activities": [
{
"jobId": "job6",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5090143,
"lng": 13.4368189
},
"time": {
"arrival": "1970-01-01T00:22:17Z",
"departure": "1970-01-01T00:25:17Z"
},
"distance": 11563,
"load": [
15
],
"activities": [
{
"jobId": "job26",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5228904,
"lng": 13.4418623
},
"time": {
"arrival": "1970-01-01T00:27:55Z",
"departure": "1970-01-01T00:30:55Z"
},
"distance": 13145,
"load": [
14
],
"activities": [
{
"jobId": "job21",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5243421,
"lng": 13.4619776
},
"time": {
"arrival": "1970-01-01T00:33:12Z",
"departure": "1970-01-01T00:36:12Z"
},
"distance": 14517,
"load": [
13
],
"activities": [
{
"jobId": "job4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5431264,
"lng": 13.4416407
},
"time": {
"arrival": "1970-01-01T00:40:22Z",
"departure": "1970-01-01T00:43:22Z"
},
"distance": 17021,
"load": [
12
],
"activities": [
{
"jobId": "job34",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5496702,
"lng": 13.4286263
},
"time": {
"arrival": "1970-01-01T00:45:16Z",
"departure": "1970-01-01T00:48:16Z"
},
"distance": 18164,
"load": [
11
],
"activities": [
{
"jobId": "job16",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5614441,
"lng": 13.4194712
},
"time": {
"arrival": "1970-01-01T00:50:41Z",
"departure": "1970-01-01T00:53:41Z"
},
"distance": 19614,
"load": [
10
],
"activities": [
{
"jobId": "job43",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5678751,
"lng": 13.4231417
},
"time": {
"arrival": "1970-01-01T00:54:57Z",
"departure": "1970-01-01T00:57:57Z"
},
"distance": 20372,
"load": [
9
],
"activities": [
{
"jobId": "job9",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5697304,
"lng": 13.3848221
},
"time": {
"arrival": "1970-01-01T01:02:17Z",
"departure": "1970-01-01T01:05:17Z"
},
"distance": 22973,
"load": [
8
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5685168,
"lng": 13.369072
},
"time": {
"arrival": "1970-01-01T01:07:04Z",
"departure": "1970-01-01T01:10:04Z"
},
"distance": 24047,
"load": [
7
],
"activities": [
{
"jobId": "job13",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.547349,
"lng": 13.3733163
},
"time": {
"arrival": "1970-01-01T01:14:01Z",
"departure": "1970-01-01T01:17:01Z"
},
"distance": 26421,
"load": [
6
],
"activities": [
{
"jobId": "job29",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5492619,
"lng": 13.369356
},
"time": {
"arrival": "1970-01-01T01:17:35Z",
"departure": "1970-01-01T01:20:35Z"
},
"distance": 26763,
"load": [
5
],
"activities": [
{
"jobId": "job39",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5473416,
"lng": 13.3327894
},
"time": {
"arrival": "1970-01-01T01:24:43Z",
"departure": "1970-01-01T01:27:43Z"
},
"distance": 29247,
"load": [
4
],
"activities": [
{
"jobId": "job18",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5650163,
"lng": 13.3027992
},
"time": {
"arrival": "1970-01-01T01:32:26Z",
"departure": "1970-01-01T01:35:26Z"
},
"distance": 32074,
"load": [
3
],
"activities": [
{
"jobId": "job15",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5632095,
"lng": 13.2940051
},
"time": {
"arrival": "1970-01-01T01:36:29Z",
"departure": "1970-01-01T01:39:29Z"
},
"distance": 32702,
"load": [
2
],
"activities": [
{
"jobId": "job46",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5192039,
"lng": 13.304444
},
"time": {
"arrival": "1970-01-01T01:47:44Z",
"departure": "1970-01-01T01:50:44Z"
},
"distance": 37651,
"load": [
1
],
"activities": [
{
"jobId": "job20",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5146285,
"lng": 13.2852959
},
"time": {
"arrival": "1970-01-01T01:53:03Z",
"departure": "1970-01-01T01:56:03Z"
},
"distance": 39045,
"load": [
0
],
"activities": [
{
"jobId": "job47",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T02:05:00Z",
"departure": "1970-01-01T02:05:00Z"
},
"distance": 44418,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 66.38359999999999,
"distance": 44418,
"duration": 7500,
"times": {
"driving": 4440,
"serving": 3060,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_2",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
17
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.4737341,
"lng": 13.38667
},
"time": {
"arrival": "1970-01-01T00:12:00Z",
"departure": "1970-01-01T00:15:00Z"
},
"distance": 7195,
"load": [
16
],
"activities": [
{
"jobId": "job37",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4828453,
"lng": 13.4363713
},
"time": {
"arrival": "1970-01-01T00:20:52Z",
"departure": "1970-01-01T00:23:52Z"
},
"distance": 10714,
"load": [
15
],
"activities": [
{
"jobId": "job22",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4945572,
"lng": 13.4698049
},
"time": {
"arrival": "1970-01-01T00:28:13Z",
"departure": "1970-01-01T00:31:13Z"
},
"distance": 13329,
"load": [
14
],
"activities": [
{
"jobId": "job10",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4989511,
"lng": 13.4740528
},
"time": {
"arrival": "1970-01-01T00:32:10Z",
"departure": "1970-01-01T00:35:10Z"
},
"distance": 13897,
"load": [
13
],
"activities": [
{
"jobId": "job11",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5058684,
"lng": 13.475099
},
"time": {
"arrival": "1970-01-01T00:36:27Z",
"departure": "1970-01-01T00:39:27Z"
},
"distance": 14670,
"load": [
12
],
"activities": [
{
"jobId": "job17",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5279215,
"lng": 13.4995315
},
"time": {
"arrival": "1970-01-01T00:44:23Z",
"departure": "1970-01-01T00:47:23Z"
},
"distance": 17631,
"load": [
11
],
"activities": [
{
"jobId": "job49",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5261554,
"lng": 13.5062954
},
"time": {
"arrival": "1970-01-01T00:48:13Z",
"departure": "1970-01-01T00:51:13Z"
},
"distance": 18129,
"load": [
10
],
"activities": [
{
"jobId": "job24",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5426716,
"lng": 13.5161692
},
"time": {
"arrival": "1970-01-01T00:54:29Z",
"departure": "1970-01-01T00:57:29Z"
},
"distance": 20085,
"load": [
9
],
"activities": [
{
"jobId": "job35",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5421315,
"lng": 13.5189513
},
"time": {
"arrival": "1970-01-01T00:57:49Z",
"departure": "1970-01-01T01:00:49Z"
},
"distance": 20283,
"load": [
8
],
"activities": [
{
"jobId": "job3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5414557,
"lng": 13.527639
},
"time": {
"arrival": "1970-01-01T01:01:48Z",
"departure": "1970-01-01T01:04:48Z"
},
"distance": 20876,
"load": [
7
],
"activities": [
{
"jobId": "job44",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5276784,
"lng": 13.546564
},
"time": {
"arrival": "1970-01-01T01:08:08Z",
"departure": "1970-01-01T01:11:08Z"
},
"distance": 22875,
"load": [
6
],
"activities": [
{
"jobId": "job19",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5060419,
"lng": 13.5152641
},
"time": {
"arrival": "1970-01-01T01:16:29Z",
"departure": "1970-01-01T01:19:29Z"
},
"distance": 26084,
"load": [
5
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4917198,
"lng": 13.5251532
},
"time": {
"arrival": "1970-01-01T01:22:22Z",
"departure": "1970-01-01T01:25:22Z"
},
"distance": 27813,
"load": [
4
],
"activities": [
{
"jobId": "job33",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4871049,
"lng": 13.5423247
},
"time": {
"arrival": "1970-01-01T01:27:29Z",
"departure": "1970-01-01T01:30:29Z"
},
"distance": 29085,
"load": [
3
],
"activities": [
{
"jobId": "job42",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4695374,
"lng": 13.4914662
},
"time": {
"arrival": "1970-01-01T01:37:05Z",
"departure": "1970-01-01T01:40:05Z"
},
"distance": 33049,
"load": [
2
],
"activities": [
{
"jobId": "job30",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4629002,
"lng": 13.4757055
},
"time": {
"arrival": "1970-01-01T01:42:15Z",
"departure": "1970-01-01T01:45:15Z"
},
"distance": 34348,
"load": [
1
],
"activities": [
{
"jobId": "job5",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4658835,
"lng": 13.4461224
},
"time": {
"arrival": "1970-01-01T01:48:38Z",
"departure": "1970-01-01T01:51:38Z"
},
"distance": 36382,
"load": [
0
],
"activities": [
{
"jobId": "job12",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T02:10:16Z",
"departure": "1970-01-01T02:10:16Z"
},
"distance": 47564,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 68.59279999999998,
"distance": 47564,
"duration": 7816,
"times": {
"driving": 4756,
"serving": 3060,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
This objective balances amount of activities and minimizes fleet usage at the same time:
"objectives": {
"primary": [
{
"type": "minimize-unassigned"
},
{
"type": "minimize-tours"
}
],
"secondary": [
{
"type": "minimize-cost"
},
{
"type": "balance-activities",
"options": {
"tolerance": 0.05,
"threshold": 0.01
}
}
]
}
Only three vehicles used approximately 16 jobs per vehicle. If you remove minimize-tours
, results should be similar
to results on previous page.
Balance travelled distance
Problem
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5697304,
"lng": 13.3848221
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5060419,
"lng": 13.5152641
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5421315,
"lng": 13.5189513
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job4",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5243421,
"lng": 13.4619776
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job5",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4629002,
"lng": 13.4757055
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job6",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4960479,
"lng": 13.3915876
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job7",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5372914,
"lng": 13.3996298
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job8",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5429597,
"lng": 13.3989552
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job9",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5678751,
"lng": 13.4231417
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job10",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4945572,
"lng": 13.4698049
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job11",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4989511,
"lng": 13.4740528
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job12",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4658835,
"lng": 13.4461224
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job13",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5685168,
"lng": 13.3690720
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job14",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4742821,
"lng": 13.3628588
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job15",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5650163,
"lng": 13.3027992
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job16",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5496702,
"lng": 13.4286263
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job17",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5058684,
"lng": 13.4750990
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job18",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5473416,
"lng": 13.3327894
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job19",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5276784,
"lng": 13.5465640
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job20",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5192039,
"lng": 13.3044440
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job21",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5228904,
"lng": 13.4418623
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job22",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4828453,
"lng": 13.4363713
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job23",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5291335,
"lng": 13.3668934
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job24",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5261554,
"lng": 13.5062954
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job25",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5189653,
"lng": 13.3890068
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job26",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5090143,
"lng": 13.4368189
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job27",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4940454,
"lng": 13.3788834
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job28",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5065998,
"lng": 13.3689955
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job29",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5473490,
"lng": 13.3733163
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job30",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4695374,
"lng": 13.4914662
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job31",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4868236,
"lng": 13.3353656
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job32",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4661617,
"lng": 13.3226920
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job33",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4917198,
"lng": 13.5251532
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job34",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5431264,
"lng": 13.4416407
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job35",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5426716,
"lng": 13.5161692
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job36",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4708241,
"lng": 13.3598752
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job37",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4737341,
"lng": 13.3866700
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job38",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5404107,
"lng": 13.3914127
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job39",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5492619,
"lng": 13.3693560
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job40",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4827319,
"lng": 13.3157235
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job41",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4711004,
"lng": 13.3321906
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job42",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4871049,
"lng": 13.5423247
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job43",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5614441,
"lng": 13.4194712
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job44",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5414557,
"lng": 13.5276390
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job45",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5425207,
"lng": 13.4139155
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job46",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5632095,
"lng": 13.2940051
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job47",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5146285,
"lng": 13.2852959
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job48",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4855438,
"lng": 13.3832067
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job49",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5279215,
"lng": 13.4995315
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
},
{
"id": "job50",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.4959052,
"lng": 13.3539713
},
"duration": 180.0
}
],
"demand": [
1
]
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1",
"vehicle_2",
"vehicle_3",
"vehicle_4",
"vehicle_5"
],
"profile": "car",
"costs": {
"fixed": 20.0,
"distance": 0.0002,
"time": 0.005
},
"shifts": [
{
"start": {
"earliest": "1970-01-01T00:00:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
},
"end": {
"latest": "1970-01-01T23:59:00Z",
"location": {
"lat": 52.4664257,
"lng": 13.2812488
}
}
}
],
"capacity": [
20
]
}
],
"profiles": [
{
"name": "car",
"type": "car"
}
]
},
"objectives": {
"primary": [
{
"type": "minimize-unassigned"
}
],
"secondary": [
{
"type": "minimize-cost"
},
{
"type": "balance-distance",
"options": {
"tolerance": 0.05,
"threshold": 0.075
}
}
]
}
}
Solution
{
"statistic": {
"cost": 273.0455999999999,
"distance": 182928,
"duration": 27292,
"times": {
"driving": 18292,
"serving": 9000,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "vehicle_1",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
10
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.4960479,
"lng": 13.3915876
},
"time": {
"arrival": "1970-01-01T00:13:38Z",
"departure": "1970-01-01T00:16:38Z"
},
"distance": 8175,
"load": [
9
],
"activities": [
{
"jobId": "job6",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5090143,
"lng": 13.4368189
},
"time": {
"arrival": "1970-01-01T00:22:17Z",
"departure": "1970-01-01T00:25:17Z"
},
"distance": 11563,
"load": [
8
],
"activities": [
{
"jobId": "job26",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5261554,
"lng": 13.5062954
},
"time": {
"arrival": "1970-01-01T00:33:45Z",
"departure": "1970-01-01T00:36:45Z"
},
"distance": 16641,
"load": [
7
],
"activities": [
{
"jobId": "job24",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5276784,
"lng": 13.546564
},
"time": {
"arrival": "1970-01-01T00:41:18Z",
"departure": "1970-01-01T00:44:18Z"
},
"distance": 19373,
"load": [
6
],
"activities": [
{
"jobId": "job19",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5060419,
"lng": 13.5152641
},
"time": {
"arrival": "1970-01-01T00:49:39Z",
"departure": "1970-01-01T00:52:39Z"
},
"distance": 22582,
"load": [
5
],
"activities": [
{
"jobId": "job2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4989511,
"lng": 13.4740528
},
"time": {
"arrival": "1970-01-01T00:57:29Z",
"departure": "1970-01-01T01:00:29Z"
},
"distance": 25484,
"load": [
4
],
"activities": [
{
"jobId": "job11",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4945572,
"lng": 13.4698049
},
"time": {
"arrival": "1970-01-01T01:01:26Z",
"departure": "1970-01-01T01:04:26Z"
},
"distance": 26052,
"load": [
3
],
"activities": [
{
"jobId": "job10",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4828453,
"lng": 13.4363713
},
"time": {
"arrival": "1970-01-01T01:08:47Z",
"departure": "1970-01-01T01:11:47Z"
},
"distance": 28667,
"load": [
2
],
"activities": [
{
"jobId": "job22",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4742821,
"lng": 13.3628588
},
"time": {
"arrival": "1970-01-01T01:20:14Z",
"departure": "1970-01-01T01:23:14Z"
},
"distance": 33741,
"load": [
1
],
"activities": [
{
"jobId": "job14",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4711004,
"lng": 13.3321906
},
"time": {
"arrival": "1970-01-01T01:26:45Z",
"departure": "1970-01-01T01:29:45Z"
},
"distance": 35851,
"load": [
0
],
"activities": [
{
"jobId": "job41",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T01:35:34Z",
"departure": "1970-01-01T01:35:34Z"
},
"distance": 39345,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 56.538999999999994,
"distance": 39345,
"duration": 5734,
"times": {
"driving": 3934,
"serving": 1800,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_5",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
10
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.5146285,
"lng": 13.2852959
},
"time": {
"arrival": "1970-01-01T00:08:57Z",
"departure": "1970-01-01T00:11:57Z"
},
"distance": 5373,
"load": [
9
],
"activities": [
{
"jobId": "job47",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5192039,
"lng": 13.304444
},
"time": {
"arrival": "1970-01-01T00:14:16Z",
"departure": "1970-01-01T00:17:16Z"
},
"distance": 6767,
"load": [
8
],
"activities": [
{
"jobId": "job20",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5632095,
"lng": 13.2940051
},
"time": {
"arrival": "1970-01-01T00:25:31Z",
"departure": "1970-01-01T00:28:31Z"
},
"distance": 11716,
"load": [
7
],
"activities": [
{
"jobId": "job46",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5650163,
"lng": 13.3027992
},
"time": {
"arrival": "1970-01-01T00:29:34Z",
"departure": "1970-01-01T00:32:34Z"
},
"distance": 12344,
"load": [
6
],
"activities": [
{
"jobId": "job15",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5473416,
"lng": 13.3327894
},
"time": {
"arrival": "1970-01-01T00:37:17Z",
"departure": "1970-01-01T00:40:17Z"
},
"distance": 15171,
"load": [
5
],
"activities": [
{
"jobId": "job18",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5685168,
"lng": 13.369072
},
"time": {
"arrival": "1970-01-01T00:45:57Z",
"departure": "1970-01-01T00:48:57Z"
},
"distance": 18575,
"load": [
4
],
"activities": [
{
"jobId": "job13",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5697304,
"lng": 13.3848221
},
"time": {
"arrival": "1970-01-01T00:50:44Z",
"departure": "1970-01-01T00:53:44Z"
},
"distance": 19649,
"load": [
3
],
"activities": [
{
"jobId": "job1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5492619,
"lng": 13.369356
},
"time": {
"arrival": "1970-01-01T00:57:55Z",
"departure": "1970-01-01T01:00:55Z"
},
"distance": 22156,
"load": [
2
],
"activities": [
{
"jobId": "job39",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5291335,
"lng": 13.3668934
},
"time": {
"arrival": "1970-01-01T01:04:40Z",
"departure": "1970-01-01T01:07:40Z"
},
"distance": 24403,
"load": [
1
],
"activities": [
{
"jobId": "job23",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5065998,
"lng": 13.3689955
},
"time": {
"arrival": "1970-01-01T01:11:51Z",
"departure": "1970-01-01T01:14:51Z"
},
"distance": 26915,
"load": [
0
],
"activities": [
{
"jobId": "job28",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T01:27:15Z",
"departure": "1970-01-01T01:27:15Z"
},
"distance": 34357,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 53.0464,
"distance": 34357,
"duration": 5235,
"times": {
"driving": 3435,
"serving": 1800,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_4",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
10
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.547349,
"lng": 13.3733163
},
"time": {
"arrival": "1970-01-01T00:18:16Z",
"departure": "1970-01-01T00:21:16Z"
},
"distance": 10957,
"load": [
9
],
"activities": [
{
"jobId": "job29",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5404107,
"lng": 13.3914127
},
"time": {
"arrival": "1970-01-01T00:23:41Z",
"departure": "1970-01-01T00:26:41Z"
},
"distance": 12405,
"load": [
8
],
"activities": [
{
"jobId": "job38",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5429597,
"lng": 13.3989552
},
"time": {
"arrival": "1970-01-01T00:27:39Z",
"departure": "1970-01-01T00:30:39Z"
},
"distance": 12989,
"load": [
7
],
"activities": [
{
"jobId": "job8",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5614441,
"lng": 13.4194712
},
"time": {
"arrival": "1970-01-01T00:34:47Z",
"departure": "1970-01-01T00:37:47Z"
},
"distance": 15471,
"load": [
6
],
"activities": [
{
"jobId": "job43",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5678751,
"lng": 13.4231417
},
"time": {
"arrival": "1970-01-01T00:39:03Z",
"departure": "1970-01-01T00:42:03Z"
},
"distance": 16229,
"load": [
5
],
"activities": [
{
"jobId": "job9",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5496702,
"lng": 13.4286263
},
"time": {
"arrival": "1970-01-01T00:45:29Z",
"departure": "1970-01-01T00:48:29Z"
},
"distance": 18289,
"load": [
4
],
"activities": [
{
"jobId": "job16",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5431264,
"lng": 13.4416407
},
"time": {
"arrival": "1970-01-01T00:50:23Z",
"departure": "1970-01-01T00:53:23Z"
},
"distance": 19432,
"load": [
3
],
"activities": [
{
"jobId": "job34",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5425207,
"lng": 13.4139155
},
"time": {
"arrival": "1970-01-01T00:56:31Z",
"departure": "1970-01-01T00:59:31Z"
},
"distance": 21310,
"load": [
2
],
"activities": [
{
"jobId": "job45",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5372914,
"lng": 13.3996298
},
"time": {
"arrival": "1970-01-01T01:01:24Z",
"departure": "1970-01-01T01:04:24Z"
},
"distance": 22439,
"load": [
1
],
"activities": [
{
"jobId": "job7",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5189653,
"lng": 13.3890068
},
"time": {
"arrival": "1970-01-01T01:08:00Z",
"departure": "1970-01-01T01:11:00Z"
},
"distance": 24602,
"load": [
0
],
"activities": [
{
"jobId": "job25",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T01:26:36Z",
"departure": "1970-01-01T01:26:36Z"
},
"distance": 33959,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 52.77179999999999,
"distance": 33959,
"duration": 5196,
"times": {
"driving": 3396,
"serving": 1800,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_2",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
10
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.4661617,
"lng": 13.322692
},
"time": {
"arrival": "1970-01-01T00:04:41Z",
"departure": "1970-01-01T00:07:41Z"
},
"distance": 2811,
"load": [
9
],
"activities": [
{
"jobId": "job32",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4708241,
"lng": 13.3598752
},
"time": {
"arrival": "1970-01-01T00:11:58Z",
"departure": "1970-01-01T00:14:58Z"
},
"distance": 5385,
"load": [
8
],
"activities": [
{
"jobId": "job36",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4737341,
"lng": 13.38667
},
"time": {
"arrival": "1970-01-01T00:18:03Z",
"departure": "1970-01-01T00:21:03Z"
},
"distance": 7231,
"load": [
7
],
"activities": [
{
"jobId": "job37",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4658835,
"lng": 13.4461224
},
"time": {
"arrival": "1970-01-01T00:27:56Z",
"departure": "1970-01-01T00:30:56Z"
},
"distance": 11356,
"load": [
6
],
"activities": [
{
"jobId": "job12",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4629002,
"lng": 13.4757055
},
"time": {
"arrival": "1970-01-01T00:34:19Z",
"departure": "1970-01-01T00:37:19Z"
},
"distance": 13390,
"load": [
5
],
"activities": [
{
"jobId": "job5",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4695374,
"lng": 13.4914662
},
"time": {
"arrival": "1970-01-01T00:39:29Z",
"departure": "1970-01-01T00:42:29Z"
},
"distance": 14689,
"load": [
4
],
"activities": [
{
"jobId": "job30",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4871049,
"lng": 13.5423247
},
"time": {
"arrival": "1970-01-01T00:49:05Z",
"departure": "1970-01-01T00:52:05Z"
},
"distance": 18653,
"load": [
3
],
"activities": [
{
"jobId": "job42",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4917198,
"lng": 13.5251532
},
"time": {
"arrival": "1970-01-01T00:54:12Z",
"departure": "1970-01-01T00:57:12Z"
},
"distance": 19925,
"load": [
2
],
"activities": [
{
"jobId": "job33",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5058684,
"lng": 13.475099
},
"time": {
"arrival": "1970-01-01T01:03:26Z",
"departure": "1970-01-01T01:06:26Z"
},
"distance": 23665,
"load": [
1
],
"activities": [
{
"jobId": "job17",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4855438,
"lng": 13.3832067
},
"time": {
"arrival": "1970-01-01T01:17:29Z",
"departure": "1970-01-01T01:20:29Z"
},
"distance": 30291,
"load": [
0
],
"activities": [
{
"jobId": "job48",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T01:32:32Z",
"departure": "1970-01-01T01:32:32Z"
},
"distance": 37524,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 55.264799999999994,
"distance": 37524,
"duration": 5552,
"times": {
"driving": 3752,
"serving": 1800,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "vehicle_3",
"typeId": "vehicle",
"shiftIndex": 0,
"stops": [
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T00:00:00Z",
"departure": "1970-01-01T00:00:00Z"
},
"distance": 0,
"load": [
10
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.4827319,
"lng": 13.3157235
},
"time": {
"arrival": "1970-01-01T00:04:56Z",
"departure": "1970-01-01T00:07:56Z"
},
"distance": 2960,
"load": [
9
],
"activities": [
{
"jobId": "job40",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4868236,
"lng": 13.3353656
},
"time": {
"arrival": "1970-01-01T00:10:17Z",
"departure": "1970-01-01T00:13:17Z"
},
"distance": 4367,
"load": [
8
],
"activities": [
{
"jobId": "job31",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4959052,
"lng": 13.3539713
},
"time": {
"arrival": "1970-01-01T00:15:59Z",
"departure": "1970-01-01T00:18:59Z"
},
"distance": 5983,
"load": [
7
],
"activities": [
{
"jobId": "job50",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5228904,
"lng": 13.4418623
},
"time": {
"arrival": "1970-01-01T00:30:06Z",
"departure": "1970-01-01T00:33:06Z"
},
"distance": 12653,
"load": [
6
],
"activities": [
{
"jobId": "job21",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5243421,
"lng": 13.4619776
},
"time": {
"arrival": "1970-01-01T00:35:23Z",
"departure": "1970-01-01T00:38:23Z"
},
"distance": 14025,
"load": [
5
],
"activities": [
{
"jobId": "job4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5426716,
"lng": 13.5161692
},
"time": {
"arrival": "1970-01-01T00:45:23Z",
"departure": "1970-01-01T00:48:23Z"
},
"distance": 18224,
"load": [
4
],
"activities": [
{
"jobId": "job35",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5421315,
"lng": 13.5189513
},
"time": {
"arrival": "1970-01-01T00:48:43Z",
"departure": "1970-01-01T00:51:43Z"
},
"distance": 18422,
"load": [
3
],
"activities": [
{
"jobId": "job3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5414557,
"lng": 13.527639
},
"time": {
"arrival": "1970-01-01T00:52:42Z",
"departure": "1970-01-01T00:55:42Z"
},
"distance": 19015,
"load": [
2
],
"activities": [
{
"jobId": "job44",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.5279215,
"lng": 13.4995315
},
"time": {
"arrival": "1970-01-01T00:59:45Z",
"departure": "1970-01-01T01:02:45Z"
},
"distance": 21442,
"load": [
1
],
"activities": [
{
"jobId": "job49",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4940454,
"lng": 13.3788834
},
"time": {
"arrival": "1970-01-01T01:17:45Z",
"departure": "1970-01-01T01:20:45Z"
},
"distance": 30444,
"load": [
0
],
"activities": [
{
"jobId": "job27",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.4664257,
"lng": 13.2812488
},
"time": {
"arrival": "1970-01-01T01:32:55Z",
"departure": "1970-01-01T01:32:55Z"
},
"distance": 37743,
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 55.42359999999999,
"distance": 37743,
"duration": 5575,
"times": {
"driving": 3775,
"serving": 1800,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": []
}
This objective balances tour distances for all tours:
"objectives": {
"primary": [
{
"type": "minimize-unassigned"
}
],
"secondary": [
{
"type": "minimize-cost"
},
{
"type": "balance-distance",
"options": {
"tolerance": 0.05,
"threshold": 0.075
}
}
]
}
All used vehicles should have total tour distance close to each other.
The same way you can balance by travel duration using balance-duration
objective.
Programmatic usage
This section contains examples which show how to call the solver from other languages.
Java
This is example how to call solver methods from java. You need to make sure that vrp-cli
library is available
in runtime, e.g. by copying corresponding binary (libvrp_cli.so
on Linux) to resources
directory. To build it, use
the following command:
cargo build --release
package vrp.example.java;
import com.sun.jna.Callback;
import com.sun.jna.Library;
import com.sun.jna.Native;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
/** Encapsulate Vehicle Routing Problem solver behavior. */
interface Solver extends Library {
/** Gets list of routing matrix locations. **/
void get_routing_locations(String problem, OnSuccess onSuccess, OnError onError);
/** Converts problem to pragmatic format. **/
void convert_to_pragmatic(String format, String[] inputs, int inputsLen, OnSuccess onSuccess, OnError onError);
/** Solves pragmatic problem. **/
void solve_pragmatic(String problem, String[] matrices,
int matricesSize,
String config,
OnSuccess onSuccess, OnError onError);
}
interface OnSuccess extends Callback {
void result(String json);
}
interface OnError extends Callback {
void result(String error);
}
class Application {
public static void main(String[] args) throws IOException {
if (args.length < 1) {
throw new IllegalStateException("Specify problem and, optionally, routing matrices paths");
}
String problem = new String(Files.readAllBytes(Paths.get(args[0])));
String[] matrices = new String[args.length - 1];
for (int i = 1; i < args.length; i++) {
matrices[i] = new String(Files.readAllBytes(Paths.get(args[i])));
}
Solver solver = Native.load("vrp_cli", Solver.class);
solver.get_routing_locations(problem,
new OnSuccess() {
@Override
public void result(String json) {
System.out.println(json);
}
}, new OnError() {
@Override
public void result(String error) {
System.out.println(error);
}
});
solver.solve_pragmatic(problem, matrices, matrices.length, "{}",
new OnSuccess() {
@Override
public void result(String json) {
System.out.println(json);
}
}, new OnError() {
@Override
public void result(String error) {
System.out.println(error);
}
});
}
}
You can check the project repository for complete example.
Kotlin
This is example how to call solver methods from kotlin. You need to make sure that vrp-cli
library is available
in runtime, e.g. by copying corresponding binary (libvrp_cli.so
on Linux) to resources
directory. To build it, use
the following command;
cargo build --release
package vrp.example.kotlin
import com.sun.jna.Callback
import com.sun.jna.Library
import com.sun.jna.Native
import java.nio.file.Files
import java.nio.file.Paths
/** Encapsulate Vehicle Routing Problem solver behavior. */
private interface Solver : Library {
/** Gets list of routing matrix locations **/
fun get_routing_locations(problem: String, onSuccess: OnSuccess, onError: OnError)
/** Converts problem to pragmatic format. **/
fun convert_to_pragmatic(format: String, inputs: Array<String>, inputsLen: Int, onSuccess: OnSuccess, onError: OnError)
/** Solves pragmatic problem. **/
fun solve_pragmatic(problem: String,
matrices: Array<String>,
matricesLen: Int,
config: String,
onSuccess: OnSuccess, onError: OnError)
}
private interface OnSuccess : Callback {
fun result(json: String)
}
private interface OnError : Callback {
fun result(error: String)
}
fun main(args: Array<String>) {
if (args.count() < 1) {
throw IllegalStateException("Specify problem and, optionally, routing matrices paths")
}
val problem = String(Files.readAllBytes(Paths.get(args[0])))
val matrices = args.drop(1).map { String(Files.readAllBytes(Paths.get(it))) }.toTypedArray()
val solver = Native.load("vrp_cli", Solver::class.java)
solver.get_routing_locations(problem,
onSuccess = object : OnSuccess {
override fun result(json: String) {
println("locations: $json")
}
},
onError = object : OnError {
override fun result(error: String) {
println(error)
}
}
)
solver.solve_pragmatic(problem, matrices, matrices.size, "{}",
onSuccess = object : OnSuccess {
override fun result(json: String) {
println("solution: $json")
}
},
onError = object : OnError {
override fun result(error: String) {
println(error)
}
}
)
}
You can check the project repository for complete example.
Javascript
This is example how to call solver methods from javascript in browser. You need to build vrp-cli
library for
WebAssembly
target. To do this, you can use wasm-pack:
cd vrp-cli
wasm-pack build --target web
It should generate wasm
build + some javascript files for you. If you want to have a smaller binary, you can try
to build without default features: csv-format
, hre-format
, scientific-format
.
To test it, use the following index.html file:
<html>
<head>
<meta content="text/html;charset=utf-8" http-equiv="Content-Type"/>
</head>
<body>
<script type="module">
import init, { get_routing_locations, solve_pragmatic } from './pkg/vrp_cli.js';
async function run() {
await init();
const pragmatic_problem = JSON.parse(`
{
"plan": {
"jobs": [
{
"id": "job1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.52599,
"lng": 13.45413
},
"duration": 300.0,
"times": [
[
"2019-07-04T09:00:00Z",
"2019-07-04T18:00:00Z"
],
[
"2019-07-05T09:00:00Z",
"2019-07-05T18:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
{
"id": "job2",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 240.0,
"times": [
[
"2019-07-04T10:00:00Z",
"2019-07-04T16:00:00Z"
]
]
}
],
"demand": [
1
]
}
]
},
{
"id": "job3",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5225,
"lng": 13.4095
},
"duration": 300.0
}
],
"demand": [
1
],
"tag": "p1"
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5165,
"lng": 13.3808
},
"duration": 300.0
}
],
"demand": [
1
],
"tag": "d1"
}
]
}
]
},
"fleet": {
"vehicles": [
{
"typeId": "vehicle",
"vehicleIds": [
"vehicle_1"
],
"profile": "normal_car",
"costs": {
"fixed": 22.0,
"distance": 0.0002,
"time": 0.004806
},
"shifts": [
{
"start": {
"earliest": "2019-07-04T09:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
},
"end": {
"latest": "2019-07-04T18:00:00Z",
"location": {
"lat": 52.5316,
"lng": 13.3884
}
}
}
],
"capacity": [
10
]
}
],
"profiles": [
{
"name": "normal_car",
"type": "car"
}
]
}
}
`);
const locations = get_routing_locations(pragmatic_problem);
console.log(`routing locations are:\n ${locations}`);
// NOTE let's assume we got routing matrix data for locations somehow
// NOTE or just pass an empty array to use great-circle distance approximation
const matrix_data= [
{
"profile": "normal_car",
"travelTimes": [
0, 609, 981, 906,
813, 0, 371, 590,
1055, 514, 0, 439,
948, 511, 463, 0
],
"distances": [
0, 3840, 5994, 5333,
4696, 0, 2154, 3226,
5763, 2674, 0, 2145,
5112, 2470, 2152, 0
]
}
];
// config provides the way to tweak algorithm behavior
const config = {
"termination": {
"maxTime": 10,
"maxGenerations": 1000
}
};
const solution = solve_pragmatic(pragmatic_problem, matrix_data, config);
console.log(`solution is:\n ${solution}`);
}
run();
</script>
</body>
</html>
Python
The easiest way to run the solver from python is to use subprocess
to run vrp-cli
:
import subprocess
import json
# NOTE: ensure that paths are correct on your environment
cli_path = "./target/release/vrp-cli"
problem_path = "./examples/data/pragmatic/simple.basic.problem.json"
solution_path = "./examples/data/pragmatic/simple.basic.solution.json"
geojson_solution_path = "./examples/data/pragmatic/simple.basic.solution.geojson"
class Deserializer:
@classmethod
def from_dict(cls, dict):
obj = cls()
obj.__dict__.update(dict)
return obj
class SolverClient:
def __init__(self, cli_path):
self.cli_path = cli_path
def solve_pragmatic(self, problem_path, solution_path, geojson_solution_path):
# NOTE: modify example to pass matrix, config, initial solution, etc.
p = subprocess.run([self.cli_path, 'solve', 'pragmatic', problem_path,
'-o', solution_path, '-g', geojson_solution_path, '--log'])
if p.returncode == 0:
with open(solution_path, 'r') as f:
solution_str = f.read()
return json.loads(solution_str, object_hook=Deserializer.from_dict)
else:
pass
solver = SolverClient(cli_path)
solution = solver.solve_pragmatic(problem_path, solution_path, geojson_solution_path)
print(f"Total cost is {solution.statistic.cost}, tours: {len(solution.tours)}")
Internals
This chapter describes some internals of the project.
Overview
Mind map which describes in short project's goals, used algorithms, and challenges.
ROSOMAXA
ROSOMAXA
stands for Routing Optimizations with Self-Organizing Maps And EXtrAs - a custom algorithm which addresses
the problem of population diversity: ability to retain different individuals in the population and use them as an input
for the search procedure. This is important to prevent premature convergence in local optimum.
Key ideas
The rosomaxa
algorithm is based on the following key ideas:
- use Growing Self-Organizing Map to cluster discovered solutions and retain good, but different ones
- choice clustering characteristics which are specific to solution geometry rather to objectives
- use 2D visualization to analyze and understand algorithm behavior
Clustering
Solution clustering is preformed by custom implementation of a growing self-organizing map (GSOM)
which is a growing variant of a self-organizing map. In rosomaxa
, it has the following characteristics:
- each node maintains a small population which keeps track of a few solutions selected by elitism approach
- nodes are created and split based on selected solution characteristics, such as:
- vehicle max load variance
- standard deviation of the number of customer per tour
- mean of route durations
- mean of route distances
- mean of route waiting times
- average distance between route medoids
- periodically, the network is compacted and rebalanced to keep search analyzing most prominent local optimums
Visualization
This animation shows some insights how algorithms performs over time:
Here:
u_matrix
is unified distance matrix calculated using solution characteristicst_matrix
andl_matrix
shows how often nodes are updatedobjective_0
,objective_1
,objective_2
: objective values such as amount of unassigned jobs, tours, and cost
Further research
- experiment with different solution characteristics
- rebalance GSOM parameters based on search progression
- analyze "heat" map dynamically to adjust GSOM parameters
- add control of
exploration
vsexploitation
ratio