reinterpretcat / vrp Goto Github PK

Hey,
I've found an issue that seems to appear randomly when trying to solve a problem. Sometimes the tour states to wait some amount of time before departure. I can't really figure out why tho.
This times also varies from try to try, sometimes the departure works as expected (06:00) and sometimes it wait for a minute or an hour.
Is this a known problem and do you know any fix for that?
Thanks in advance.

routing_matrix.txt
solution.txt
problem.txt
.

FYI:

Got an error while trying to install v. 1.10 on a Ubuntu 20.04. LTS:

cargo --verbose install vrp-cli

Compiling vrp-core v1.10.0 Runningrustc --crate-name vrp_core --edition=2018 /home/username/.cargo/registry/src/github.com-1ecc6299db9ec823/vrp-core-1.10.0/src/lib.rs --error-format=json --json=diagnostic-rendered-ansi,artifacts --crate-type lib --emit=dep-info,metadata,link -C opt-level=3 -Cembed-bitcode=no -C metadata=b2341bfc8b060633 -C extra-filename=-b2341bfc8b060633 --out-dir /tmp/cargo-installWE2m31/release/deps -L dependency=/tmp/cargo-installWE2m31/release/deps --extern hashbrown=/tmp/cargo-installWE2m31/release/deps/libhashbrown-02cde05fa3bef28d.rmeta --extern num_cpus=/tmp/cargo-installWE2m31/release/deps/libnum_cpus-7872687f52fab9da.rmeta --extern rand=/tmp/cargo-installWE2m31/release/deps/librand-743de0627dcf690c.rmeta --extern rayon=/tmp/cargo-installWE2m31/release/deps/librayon-8d6ec85410d72779.rmeta --cap-lints allowerror[E0658]: use of unstable library feature 'clamp' --> /home/frank/.cargo/registry/src/github.com-1ecc6299db9ec823/vrp-core-1.10.0/src/solver/population/rosomaxa.rs:264:103 | 264 | 1. / (1. + std::f64::consts::E.powf(-10. * (statistics.termination_estimate - 0.75))).clamp(0.1, 1.); | ^^^^^ | = note: see issue #44095 <https://github.com/rust-lang/rust/issues/44095> for more information
Preverious versions did compile without any problems.

Hi - first of all, huge compliments on what seems to be an amazing and all-encompassing project - I was delighted when I saw all the features you are covering and can't wait to interface with it and give it a go with our use-cases!

There is just one thing that I would be missing at this moment - ability to specify a speed factor for a vehicle (whether this vehicle is quicker or slower than distance matrix travel times), which is of very high value when dealing with different levels of experience / performance in drivers - some are more experienced or just generally faster than the baseline, and some are slower. In case of dense deliveries (e.g. food) with narrow time-windows, it can make a lot of difference.

I was curious if there was something in the project that can potentially be used as a workaround for this use-case?

Thank you very much!

Hello,
I am running vrp-cli and when i am trying to execute a command that contains a space in the path
vrp-cli solve pragmatic "C:/my projects/vrp-cli/problem.json" -o "C:/my projects/vrp-cli/solution.json" --log
I am getting an error:

error: Found argument 'projects/vrp-cli/problem.json"' which wasn't expected, or isn't vali
d in this context

USAGE:
    vrp-cli solve [FLAGS] [OPTIONS] <FORMAT> <PROBLEM>

For more information try --help

I tried to google it but i didn't find anything helpful, is there a fix to it?
Thank you

In vrp-core/src/solver/builder.rs:

 pub fn with_termination(mut self, termination: Arc<dyn Termination + Send + Sync>) -> Self {
        self.config.telemetry.log("configured to use custom termination parameters");
        self.config.termination = termination;
        self
    }

but below in:

pub fn build(self) -> Result<Solver, String>

termination configuration overrides by this line:

config.termination = Arc::new(CompositeTermination::new(criterias));

Hi,
According to the document:

tour-order: controls desired activity order in tours
is_constrained: violating order is not allowed, even if it leads to less assigned jobs (default is false).

is_constrained is snake case but throws the error:

check input json: 'missing field `isConstrained`

So it should be refactored as isConstrained

https://reinterpretcat.github.io/vrp/concepts/pragmatic/problem/objectives.html?highlight=tour-order#scalar-objectives

I have a specific use case that seems not possible to model with vrp-cli. But I may have missed something or thought about it in the wrong way.
Would it be possible to have a task, a job skill, assigned to a vehicle, that can be done in several places but only one should be selected at the end. It is similar to a location problem and thus somehow similar to dispatch or reloads, but without capacity question.

A current example of this problem is the integration of the refueling of the vehicles.
This task has to be done during the vehicle shift. It has to be done, but only once and only in few specific petrol stations (for accounting question). Therefore, the location/allocation of the petrol station should be done to a vehicle and integrated into its tours.

I thought first to loop over petrol stations, solve each problem and then keep the less costly one. But there may be a better option?

Hello, i'm testing this great solver ("congrats!"). I do multiples probes with fews jobs (10 and 20) that includes external distance matrix without problem. I'm a big test with 133 jobs and distance matrix to this number of jobs 133*133. But when run the solver i have a next Error: "'E1505, cause: 'amount of locations does not match matrix dimension', action: 'check matrix size: max location index ('127') should be less than matrix size ('133')'.'". If run this problem without external distance matrix, run perfect and find a solution. I have checked the information several times to avoid formatting errors in the profile json. Can you help me? The number of jobs is 132 and the matrix is 133 x 133. how to send you this files ? Thank you for your response.

I don't know if it is feasible or not but it would be nice to have solver log in javascript for gaining knowledge on termination criteria and their impact. Of course, I could export the pragmatic problem and run the vrp-cli in the shell with --log option.
I am not an expert in neither rust, javascript, or WebAssembly, but I guess that javascript layer may have some performance impact, that is why I am trying to have a better assessment of the solver results directly in my configuration.

Aside from this log question, I have some doubt about the correct way of passing cost-variation criteria in javascript:
As a string: "costVariation": "200,0.1"?
as an array: "costVariation": [200,0.1]?
In tests, neither options thrown error
Thanks a lot !

In JavaScript, when I am passing a config object such as the following, the solver work perfectly :

  const config = {
      "termination": {
          "maxTime": 120,
          "maxGenerations": 1000
      }
  };

But, following your advice in a previous discussion:

I would recommend setting only a time limit with --max-time

I then wanted to remove the maxGenerations criteria.
But when passing the config object with only maxTime criteria:

  const config = {
      "termination": {
          "maxTime": 120,
      }
  };

The solver never stops running and the CPU seems to keep working. This issue appears on the current version of vrp-cli, v1.8.0.
Is it a normal behavior and a default value should always be given?
Thanks a lot.

Hello again,
I have a problem with Routing matrix format? I am using osrm database, once i fetch the distance matrix i am getting:

durations: [
    [ 0, 558.2, 2449, 836.9 ],
    [ 576.5, 0, 2794.3, 1188.9 ],
    [ 2504.2, 2761.7, 0, 2096.3 ],
    [ 859.6, 1098.7, 2028.4, 0 ]
]

but in docs it's says I need the travelTimes and the distances:

{
  "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
  ]
}

How do i get kind of matrix? I have durations( i assume it's travelTimes) but i don't have distances, the only distances i can get is from osrm database:

 {
  code: 'Ok',
  routes: [
    {
      geometry: 'qcjuGhl{_Me]yMh]erAilDqvAygDqd@mCr[{SaFjA~V}~@bIqgCu|@icCcG_dAutAbIhN_d@`dAteBbqKycA~nQlRxaD~mEjtKlgBpg@fcBvmE~aAdr@rvAheBpSbdBwIlk@epJrbPc\\la@c\\{W{e@|}@ze@
}}@`j@hVruO_kXd|Aeh@pgAahD@igB~h@ee@yjAgeBms@qjC{y@ckAsaBevEsrEgtClPwn@juEcnFlp@_qC|cAuqCum@}V',
      legs: [Array],
      distance: 108110.8,
      duration: 5858.9,
      weight_name: 'routability',
      weight: 5858.9
    }
  ],
  waypoints: [
    {
      hint: 'F8EBgP___38fAAAAPwAAAAAAAAAAAAAA_k4KQhvXDEIAAAAAAAAAAB8AAAA_AAAAAAAAAAAAAAC5AwAArMed-93etwLmx537jd-3AgAAvxF-_wId',
      distance: 20.077371,
      name: 'Boulevard Joseph-Renaud',
      location: [Array]
    },
    {
      hint: 'elgUgJtYFIAiAAAADAAAAA4AAAAAAAAABui8QVPMA0F09x5BAAAAACIAAAAMAAAADgAAAAAAAAC5AwAAIFOe-5m0uALjUp77KrS4AgEALxJ-_wId',
      distance: 13.22092,
      name: 'Rue Charles Goulet',
      location: [Array]
    },
    {
      hint: 'ptMIgBTUCIAkAAAAOAAAADICAAAAAAAA-WHLQctDGUIBc8NDAAAAACQAAAA4AAAAMgIAAAAAAAC5AwAAQ7OX--touQJDspf7b2m5AgcATwJ-_wId',
      distance: 24.747056,
      name: 'Rue du Noroît',
      location: [Array]
    },
    {
      hint: 'F8EBgP___38fAAAAPwAAAAAAAAAAAAAA_k4KQhvXDEIAAAAAAAAAAB8AAAA_AAAAAAAAAAAAAAC5AwAArMed-93etwLmx537jd-3AgAAvxF-_wId',
      distance: 20.077371,
      name: 'Boulevard Joseph-Renaud',
      location: [Array]
    }
  ]
}

So how do i get the matrix as described in docs https://reinterpretcat.github.io/vrp/concepts/pragmatic/routing/format.html
Thanks

At the moment, current algorithm uses naive implementation which does not work really well. So, there is a need to implement some more sophisticated algorithm, e.g. aware about Pareto optimization front concepts, etc. (NSGA-II?)

Hello,
I have a question, how to balance capacity with the driver time shift? In my case we have two drivers with total of 20 jobs, one driver starts his shift at 8:00 and ends at 10:00, the other driver starts from 8:00 and ends his shift at 17:00 (full working day). In most cases all drivers have a full day shift (from 8:00 to 17:00) and in this case i can calculate capacity for each driver( we divide total jobs with total amount of drivers, for example 20 jobs/2 drivers= 10 jobs each ) but, sometimes we have drivers who can do only half day or few hours shift, so in this case we can't divide total jobs between two drivers because the driver that has shift of few hours the total capacity is unknown for me. In this case we need that driver that has few hours a day will get jobs for few hours and the rest jobs will be assigned to other drivers base on time shift.

So here is how we solve the capacities between the two drivers for 20 jobs with same time shift:
Driver 1 capacity: jobs.length/drivers.length = 10 - shift = 8:00-17:00
Driver 2 capacity: jobs.length/drivers.length = 10 - shift = 8:00-17:00

Here is a how we are trying to solve the problem with two drivers but with different time shift:
Driver 1 capacity: jobs.length/drivers.length = 10 - shift = 8:00-17:00
Driver 2 capacity: jobs.length/drivers.length = 10 - shift = 8:00-10:00

As you can see the red driver (Driver 1) gets his 10 jobs and the driver in green (Driver 2) gets 3 jobs but there is 7 unsigned jobs that need to be assigned to Driver 1 (red).

Thank you

First: You're doing an awesome job!

While playing around i noticed a strange behavior:
I tried to group Stops together (whatever Vehicle takes them - they should be delivered together). At a certain point ( a few jobs had as much as 11 or 12 deliveries ) the solver took forever for an initial solution.

It is stuck at 100% CPU (Just one Core) with the preparation task. This means nothing happened after Log entry "problem has a total of n jobs..."

Running this task without grouped deliveries works like a charm.

Do you have any idea what is going on and if there may be a simple workaround?

I'm not sure if it makes sense to include it in the scope of the project, but it could be an optional flag.

I've used VROOM for some time, and the polyline flag was very useful.

It seems related to degree of parallelism which has to be limited in inner loops.

In the current vrp-cli, only maximal capacity can be fixed for each vehicle of the fleet
In our case, it would be interesting to also set up a minimal load by truck to ensure their good use (e.g for the rented ones).
With defaults options, the solvers minimize the number of tours, thus it usually picks up solutions with vehicles at their maximal capacity or close. But, in our configuration, to minimize the driver load (and because it is our organization until low), we use all the cars available. So we set objectives to maximize-tours.
It is obviously not optimal from a cost point of view but none the less it is still our strategy for now. But we end up with some trucks not loaded enough. My guess is that a hard constraint on minimal vehicle capacity, would probably solve this issue.
Or maybe I miss used some objectives options ?
Thanks again for your apps !

It seems reasonable to have demand/capacity optional. At the moment, there is no validation rule to check empty capacity, so the solver fails in fleet_reader.rs

When set, skills from deliveries and fleets should match in the solving process.

It becomes useful in some cases, including when you need to direct valuable items to an experienced driver.

I see VRP has been released with >1.0 a while ago. A belated congratulations 👏

Does this mean the status of the project is no longer experimental like mentioned in the Readme? And if not, is there something that would make it more production ready?

Thanks a lot for the developpement of the very useful vrp-cli.
I am building a small web app for optimizing local food products. Your documentation is very nice, but I did struggle to figure out that the pragmatic format is not the same between the cli interface and when using through JavaScript :
For example:
for CLI usage:

    "jobs": [
      {
        "id": "job1",
        "deliveries": [
          {
            "places": [
              { ...

For JavaScript (places.delivery instead of deliveries.places ):

    "jobs": [
      {
        "id": "job",
        "places": {
          "delivery": {
            "location": {

Or
for CLI usage:

        "shifts": [{
            "start": {
              "earliest": "2019-07-04T09:00:00Z",
              "location": {

For JavaScript (time instead of earliest ):

        "shifts": [{
          "start": {
            "time": "2020-04-07T00:00:00Z",

Therefore, it is not possible to produce a pragmatic problem usable for both interface which could be useful at some point.

A side comment, I am really struggling to import vrp-cli (generated through wasm-pack) in JavaScript (NodeJs/Express, bundle with parcel). For a strange and unknown reason it did work on a project, but fails in any new projects. Did you have any experience or tips on that matter?

A use case:

• many jobs are in the problem (e.g. 1000)
• only few tours can be created (e.g. 2)
• most of the jobs are unassigned (e.g. 900)

In such situation, all unassigned jobs will be tried to inserted multiple times. Theoretically, insertion failure results can be cached and search stopped earlier.

Hi,
I am attempting to use the pkg folder in the latest release of vrp_cli_wasm.zip with a index.html file containing the contents on the documentation page here, however instead of the result being printed to the javascript console, I am presented with this error in the console:

I haven't modified any files in 'pkg' or the contents of 'index.html', and the routing locations are successfully printed to the console prior to the error message.

I am not sure if this is a bug or if I am doing something wrong, but I can't see why it shouldn't work as is.
Thanks in advance for any help.

Thank you very much for this amazing application!

We are modelling a situation where there are multiple depot locations for the same type of vehicles, so we would like to reuse the same profiles (and distance matrices). However, when we give the same profile name multiple times, we get an error:

cannot read pragmatic problem from 'problem.json': 'E1500, cause: 'duplicated profile names', action: 'remove duplicates of profiles with the names: 'truck, car''.

As a workaround, we could of course copy the matrices and fix it that way, but that is not very ergonomic. Is there a reason that duplicated profiles checked?

This test can be used to reproduce the issue:

use crate::format::problem::*;
use crate::format::Location;
use crate::helpers::solve_with_metaheuristic_and_iterations;

#[test]
fn run_test() {
    for _ in 0..1000 {
        let problem = Problem {
            plan: Plan {
                jobs: vec![
                    Job {
                        id: "job1".to_string(),
                        pickups: None,
                        deliveries: Some(vec![JobTask {
                            places: vec![JobPlace {
                                location: Location::Coordinate { lat: 52.437842517427846, lng: 13.3829646081322 },
                                duration: 6.0,
                                times: Some(vec![vec!["2020-07-04T09:00:00Z".to_string(), "2020-07-04T13:00:00Z".to_string()]]),
                                tag: None,
                            }],
                            demand: Some(vec![1]),
                            order: None,
                        }]),
                        replacements: None,
                        services: None,
                        skills: None,
                        value: None,
                        group: None,
                    },
                    Job {
                        id: "job2".to_string(),
                        pickups: None,
                        deliveries: Some(vec![JobTask {
                            places: vec![JobPlace {
                                location: Location::Coordinate { lat: 52.504574435265766, lng: 13.512204487216097 },
                                duration: 4.0,
                                times: Some(vec![vec!["2020-07-04T09:00:00Z".to_string(), "2020-07-04T11:00:00Z".to_string()]]),
                                tag: None,
                            }],
                            demand: Some(vec![1]),
                            order: None,
                        }]),
                        replacements: None,
                        services: None,
                        skills: None,
                        value: None,
                        group: None,
                    },
                    Job {
                        id: "job3".to_string(),
                        pickups: Some(vec![JobTask {
                            places: vec![JobPlace {
                                location: Location::Coordinate { lat: 52.51627010959871, lng: 13.515165894434492 },
                                duration: 4.0,
                                times: Some(vec![
                                    vec!["2020-07-04T09:00:00Z".to_string(), "2020-07-04T13:00:00Z".to_string()],
                                    vec!["2020-07-04T14:00:00Z".to_string(), "2020-07-04T16:00:00Z".to_string()],
                                ]),
                                tag: None,
                            }],
                            demand: Some(vec![1]),
                            order: None,
                        }]),
                        deliveries: None,
                        replacements: None,
                        services: None,
                        skills: None,
                        value: None,
                        group: None,
                    },
                    Job {
                        id: "job4".to_string(),
                        pickups: Some(vec![JobTask {
                            places: vec![JobPlace {
                                location: Location::Coordinate { lat: 52.49739587223939, lng: 13.499267072502096 },
                                duration: 3.0,
                                times: Some(vec![vec!["2020-07-04T14:00:00Z".to_string(), "2020-07-04T16:00:00Z".to_string()]]),
                                tag: None,
                            }],
                            demand: Some(vec![2]),
                            order: None,
                        }]),
                        deliveries: None,
                        replacements: None,
                        services: None,
                        skills: None,
                        value: None,
                        group: None,
                    },
                    Job {
                        id: "job5".to_string(),
                        pickups: None,
                        deliveries: Some(vec![JobTask {
                            places: vec![JobPlace {
                                location: Location::Coordinate { lat: 52.47816437518683, lng: 13.480325156196248 },
                                duration: 8.0,
                                times: Some(vec![
                                    vec!["2020-07-04T09:00:00Z".to_string(), "2020-07-04T11:00:00Z".to_string()],
                                    vec!["2020-07-04T14:00:00Z".to_string(), "2020-07-04T16:00:00Z".to_string()],
                                ]),
                                tag: None,
                            }],
                            demand: Some(vec![3]),
                            order: None,
                        }]),
                        replacements: None,
                        services: None,
                        skills: None,
                        value: None,
                        group: None,
                    },
                    Job {
                        id: "job6".to_string(),
                        pickups: Some(vec![JobTask {
                            places: vec![JobPlace {
                                location: Location::Coordinate { lat: 52.44030727908021, lng: 13.433537947080476 },
                                duration: 3.0,
                                times: Some(vec![vec!["2020-07-04T14:00:00Z".to_string(), "2020-07-04T18:00:00Z".to_string()]]),
                                tag: None,
                            }],
                            demand: Some(vec![1]),
                            order: None,
                        }]),
                        deliveries: None,
                        replacements: None,
                        services: None,
                        skills: None,
                        value: None,
                        group: None,
                    },
                ],
                relations: None,
            },
            fleet: Fleet {
                vehicles: vec![VehicleType {
                    type_id: "vehicle1".to_string(),
                    vehicle_ids: vec!["vehicle1_1".to_string()],
                    profile: VehicleProfile { matrix: "car".to_string(), scale: None },
                    costs: VehicleCosts { fixed: Some(20.), distance: 0.002, time: 0.003 },
                    shifts: vec![VehicleShift {
                        start: ShiftStart {
                            earliest: "2020-07-04T09:00:00Z".to_string(),
                            latest: None,
                            location: Location::Coordinate { lat: 52.44105158292253, lng: 13.424429791168873 },
                        },
                        end: Some(ShiftEnd {
                            earliest: None,
                            latest: "2020-07-04T18:00:00Z".to_string(),
                            location: Location::Coordinate { lat: 52.44105158292253, lng: 13.424429791168873 },
                        }),
                        dispatch: None,
                        breaks: Some(vec![VehicleBreak {
                            time: VehicleBreakTime::TimeWindow(vec!["2020-07-04T12:00:00Z".to_string(), "2020-07-04T14:00:00Z".to_string()]),
                            places: vec![VehicleBreakPlace { duration: 3600.0, location: None, tag: None }],
                            policy: None,
                        }]),
                        reloads: None,
                    }],
                    capacity: vec![5],
                    skills: None,
                    limits: None,
                }],
                profiles: vec![MatrixProfile { name: "car".to_string(), speed: None }],
            },
            objectives: None,
        };
        let matrices = create_approx_matrices(&problem);
        solve_with_metaheuristic_and_iterations(problem, Some(matrices), 1);
    }
}

Exact reason is not clear, but it seems that without break it is not reproducible which is strange

The original jemalloc your using is not maintaned, rustc and other projects switched to use a fork https://crates.io/crates/tikv-jemallocator

Илья, доброго времени суток!

У меня есть предложение относительно сущностей Dispatch и Reload.
По условиям местоположение Dispatch быть уникальным, но есть предложение снять уникальность, т.к., например, транспорт может находиться на стоянке у склада в самом начале маршрута.
Также есть предложение распространить ограничения Dispatch на Reload и наоборот т.к. они с большой вероятностью могут быть одним и тем же местом. Т.е. в начале маршрута необходимо учитывать время на погрузку, а при перезагрузке необходимо учитывать ограничения одновременных загрузок. Или в таком случае может быть стоит выделить отдельную сущность как "Cклад", которая будет сочетать свойства Dispatch и Reload?

I have tried this command to compile 1.10.0 version but looks like it tries to compile with vrp-core=1.10.4 and vrp-pragmatic=1.10.4,

root@c7751a4f9151:/# ~/.cargo/bin/cargo install vrp-cli --vers 1.10.0
    Updating crates.io index
  Installing vrp-cli v1.10.0
   Compiling autocfg v1.0.1
   Compiling libc v0.2.94
   Compiling cfg-if v1.0.0
   Compiling lazy_static v1.4.0
   Compiling proc-macro2 v1.0.27
   Compiling unicode-xid v0.2.2
   Compiling syn v1.0.72
   Compiling rayon-core v1.9.1
   Compiling serde_derive v1.0.126
   Compiling version_check v0.9.3
   Compiling scopeguard v1.1.0
   Compiling serde v1.0.126
   Compiling ppv-lite86 v0.2.10
   Compiling once_cell v1.7.2
   Compiling memchr v2.4.0
   Compiling ryu v1.0.5
   Compiling either v1.6.1
   Compiling bitflags v1.2.1
   Compiling serde_json v1.0.64
   Compiling itoa v0.4.7
   Compiling byteorder v1.4.3
   Compiling unicode-width v0.1.8
   Compiling ansi_term v0.11.0
   Compiling strsim v0.8.0
   Compiling vec_map v0.8.2
   Compiling ahash v0.7.2
   Compiling crossbeam-utils v0.8.4
   Compiling memoffset v0.6.3
   Compiling rayon v1.5.1
   Compiling num-traits v0.2.14
   Compiling num-integer v0.1.44
   Compiling textwrap v0.11.0
   Compiling regex-automata v0.1.9
   Compiling csv-core v0.1.10
   Compiling quote v1.0.9
   Compiling getrandom v0.2.3
   Compiling num_cpus v1.13.0
   Compiling time v0.1.43
   Compiling atty v0.2.14
   Compiling rand_core v0.6.2
   Compiling clap v2.33.3
   Compiling crossbeam-epoch v0.9.4
   Compiling crossbeam-channel v0.5.1
   Compiling rand_chacha v0.3.0
   Compiling hashbrown v0.11.2
   Compiling crossbeam-deque v0.8.0
   Compiling rand v0.8.3
   Compiling chrono v0.4.19
   Compiling vrp-core v1.10.4
   Compiling vrp-scientific v1.10.4
   Compiling bstr v0.2.16
   Compiling csv v1.1.6
   Compiling vrp-pragmatic v1.10.4
   Compiling vrp-cli v1.10.0
error[E0560]: struct `vrp_pragmatic::format::problem::Job` has no field named `priority`
  --> /root/.cargo/registry/src/github.com-1ecc6299db9ec823/vrp-cli-1.10.0/src/extensions/generate/plan.rs:67:17
   |
67 |                 priority: job_proto.priority,
   |                 ^^^^^^^^ `vrp_pragmatic::format::problem::Job` does not have this field
   |
   = note: available fields are: `id`, `pickups`, `deliveries`, `replacements`, `services` ... and 3 others

error[E0609]: no field `priority` on type `&vrp_pragmatic::format::problem::Job`
  --> /root/.cargo/registry/src/github.com-1ecc6299db9ec823/vrp-cli-1.10.0/src/extensions/generate/plan.rs:67:37
   |
67 |                 priority: job_proto.priority,
   |                                     ^^^^^^^^ unknown field
   |
   = note: available fields are: `id`, `pickups`, `deliveries`, `replacements`, `services` ... and 3 others

error[E0560]: struct `vrp_pragmatic::format::problem::Job` has no field named `priority`
   --> /root/.cargo/registry/src/github.com-1ecc6299db9ec823/vrp-cli-1.10.0/src/extensions/import/csv.rs:100:17
    |
100 |                 priority: None,
    |                 ^^^^^^^^ `vrp_pragmatic::format::problem::Job` does not have this field
    |
    = note: available fields are: `id`, `pickups`, `deliveries`, `replacements`, `services` ... and 3 others

error[E0560]: struct `vrp_pragmatic::format::problem::Job` has no field named `priority`
   --> /root/.cargo/registry/src/github.com-1ecc6299db9ec823/vrp-cli-1.10.0/src/extensions/import/hre.rs:287:21
    |
287 |                     priority: job.priority.as_ref().copied(),
    |                     ^^^^^^^^ `vrp_pragmatic::format::problem::Job` does not have this field
    |
    = note: available fields are: `id`, `pickups`, `deliveries`, `replacements`, `services` ... and 3 others

error[E0609]: no field `priority` on type `&vrp_pragmatic::format::problem::Job`
   --> /root/.cargo/registry/src/github.com-1ecc6299db9ec823/vrp-cli-1.10.0/src/extensions/import/hre.rs:442:39
    |
442 |                         priority: job.priority,
    |                                       ^^^^^^^^ unknown field
    |
    = note: available fields are: `id`, `pickups`, `deliveries`, `replacements`, `services` ... and 3 others

error[E0599]: no method named `with_cost_variation` found for struct `vrp_core::solver::Builder` in the current scope
   --> /root/.cargo/registry/src/github.com-1ecc6299db9ec823/vrp-cli-1.10.0/src/extensions/solve/config.rs:517:27
    |
517 |         builder = builder.with_cost_variation(config.variation.as_ref().map(|v| (v.sample, v.cv)));
    |                           ^^^^^^^^^^^^^^^^^^^ method not found in `vrp_core::solver::Builder`

error: aborting due to 6 previous errors

Some errors have detailed explanations: E0560, E0599, E0609.
For more information about an error, try `rustc --explain E0560`.
error: failed to compile `vrp-cli v1.10.0`, intermediate artifacts can be found at `/tmp/cargo-installZ6HHcC`

Caused by:
  could not compile `vrp-cli`

Hi, I've several questions to understand more how to run the tool more effectively.

• What is the time complexity of this solver?

• Does it depend on the number of objective functions?

• And how is it related to Job and Vehicle counts?

• And how to increase speed?

• How much does increasing the thread pool affect?

• And what's the maximum limit of threads?

• How to choose a stopping point? What do you advise, and how to make choose the trade-off between time and optimal solution.

I know there are many questions here but to understand further, I wanted to open an issue. Maybe we can elaborate them later in a document or a post to light the way for after-comers.

Hi ,

I'm trying to use the java example you published - i had a success with get_routing_locations and solve_pragmatic

In the answer i don't see the geojson output as i get it from vrp-cli command

how can i get the goejson also from the java code

Thanks in advance

What if I have sequence of pickup and dropoff with fixed order like (PU - PU - PU - DO - PU - DO) and would like to assign this whole sequence to 1 vehicle. Do this project support optimizing this scenario?

From the document, I see that [group] property of job could do something similar to my requirement (all tasks in groups would be assigned in 1 tour or drop them all) but look like It don't support to assign task with defined order and I didn't find example about this property.

First of all, thank you for the wonderful library, it works really great and produces high-quality solutions for our use cases.

I am wondering if it is possible to introduce dynamic costs in the optimization. In particular, I would like to take into account load-dependent transport costs. Especially if the weight of the goods is highly unequal in a tour, it might be worth visiting the clients with massive demands first, so that we can save the extra consumption and amortization costs. Can you give me a hint where to start with the implementation? Note that it might not be required to implement these variable costs at the global optimization level, which might slow down the whole optimization substantially - we could just add it as a post-processing step at the level of individual tours to optimize the order of visits.

Hey, i want to optimize a job with multiple shifts over a month, teams and tours. When i solve this problem i get a solution thats spreads the tour dates randomly over this time period even so the problem can be done in half the time period. I want the tours to be as early as possible, so the teams are free for the rest of the time.

Is there a possibility to archive this or can you program a new objective for this?

Thanks for your hard work - again!

I just found a strange inconsistency between shift time limit and shift end position.

Task Constraints:

• Maximum Driving Time: 5 Hours
• Maximum Distance: 140km
• Should Return to Depot afterwards

a) Ich specify job the "proper" way

        "limits": { "maxDistance": 140000 },
        "costs": { "fixed": 22, "distance": 0.0002, "time": 0.004806 },
        "shifts": [
          {
            "start": { "earliest": "2023-02-21T16:30:00Z", "location": { "lat": 47.4157792, "lng": 8.3939315 } },
            "end": { "latest": "2023-02-21T21:30:00Z", "location": { "lat": 47.4157792, "lng":8.3939315 } }
          }

=> The Result ist remarkable bad. Around 40 unassigned Stops. 29 Tours!

b) I specify shiftTime Limit as 4 hours and shorten Max Distance to calculate Backroute manually
I specify shiftTime Backroute as 100 km

"limits": { "maxDistance": 100000, "shiftTime": 14400 },
   "shifts": [
      {
        "start": { "earliest": "2023-02-21T16:30:00Z", "location": { "lat": xxxxx, "lng": xxxxxx } }
       }

At the end i add the route back to depot manually and everything is fine and well in time constraint of 5 hours and except one overflow of 3 km i got a great solution with 26 Tours. The Overflow is completely gone when i lower my distance limit to 95. Still with a saving of 2 tours compared to the other solution. (With a little processing afterwards to handle distance overflows the result would be even better)

This is such a large difference that i got curious what is going on.

Possible steps to reproduce:

• define complex problem, meaning unassigned jobs might have to be present in solution
• define interval break on vehicle types
• use strict time windows
• run solver once for short time, get solution
• pass received solution as initial, use check option, repeat

Output:
cannot read initial solution 'cannot match job '276568'
Job cannot be matched due to time window violation.

Reproducibility
Random

Possible reasons:
Original schedule must be restored as it is?
Restoring departure time optimization value is not working properly?

Is there any plans of giving this library a name other than vrp? Making benchmarks for several VRP-solvers made this a challenge.

It seems calculation is incorrect. A test to reproduce:

5915b83

I've been trying to formulate our VRP using the pragmatic format as described in the docs, but ran into some issues with the routing matrix.

According to the docs, the routing matrix should be on the following format.

0	BA	CA
AB	0	CB
AC	BC	0

where

• 0: zero duration or distance
• XY: distance or duration from X location to Y

As single dimensional array it looks like:

[0,BA,CA,AB,0,CB,AC,BC,0]

Providing the matrix on that format does not give us correct distances when evaluating the solution. If we instead transpose the matrix everything seems to work fine.

 [0,AB,AC,BA,0,BC,CA,CB,0]

Are the docs outdated or do you know if we're doing something wrong?

Hello,

I want to tank you for doing this library in Rust :)

I wonder if its possible to modell with pickup deliveries fixed time windows, fixed breaks and exclusion((Some drivers can only use certain cars due to several criteria like drivers license, and cant be in same Car as certain gods(example:people that hate each other, or is allergic to dog))), certain goods cant be combined either - constraints for many Drivers vs many Cars?.

Thanks
Gustav
.

Hi,
Tried different combinations of objectives and came up with solutions that only have one tour (without using any constraints such as times, capacity etc..) except if I use maximize-tours. Some examples:

Returns a route with just one tour:

    "objectives": [
        [
            {
                "type": "minimize-unassigned"
            }
        ],
        [
            {
                "type": "minimize-cost"
            }
        ]
    ]

    "objectives": [
      [
        {
          "type": "minimize-unassigned"
        }
      ],
      [
        {
          "type": "tour-order",
         "options": {
            "isConstrained": false
          }
        }
      ],
      [
        {
          "type": "minimize-cost"
        },
        {
          "type": "balance-activities",
          "options": {
            "threshold": 0.01
          }
        }
      ]
    ]

and so on..

Only if I add maximize-tours to the objectives I get more than one tour.

    "objectives": [
        [
            {
                "type": "minimize-unassigned"
            }
        ],
      [
        {
          "type": "maximize-tours"
        }
      ],
        [
            {
                "type": "minimize-cost"
            }
        ]
    ]

Is minimize-tours a default objective in any case? If not, I'm totally sure that there are such cases that are less costly by using more vehicles (i.e. more tours).

• (improvement) Let user to decide likeness of break insertion: do not apply negative cost internally all the time. This might improve solver ability to find better insertion place for a break
• (bug to verify) Offset break time window is not respected sometimes. Also checker seems not able to detect this.

It would be awesome to use vrp solver as a web API.

Hi! I am very glad that there is a similar solution on rust, it is really very cool!
I recently started learning rust, and I wanted to create an example based on your solution in the following bundle actix-web -> vrp-pragmatic.
for example

    let environment = Arc::new(Environment::default());
    let core_problem = (request.problem.clone(), vec![request.matrix.clone()]).read_pragmatic();
    let core_problem = Arc::new(core_problem.unwrap_or_else(|errors| {
        panic!("cannot read pragmatic problem: {}", FormatError::format_many(errors.as_slice(), "\t\n"))
    }));
    let solver = Builder::new(core_problem.clone(), environment.clone())
        .with_max_time(Some(60))
        .with_max_generations(Some(100))
        .build()
        .unwrap();
    let (solution, _cost, _) = solver.solve().unwrap();

With this approach, I may have (not sure) detected a memory leak, because the memory is not released between load testing using the AB utility. I am using Instruments (mac os) to find the problem.

As far as I understand, one of the problems is

I will be grateful for any hint where to look next

The general goal of this ticket is to have more stable search result, possible improvement areas:

• GSOM implementation: experiment with smoothing phase, improve growing phase
• tweak rosomaxa intermal logic (TBD)

Basic idea is to extract rosomaxa as separate crate and make it work on non VRP related data. Then it should be possible to use various metaheuristic benchmarks (e.g. Rosenbrock function) to check its quality. Requires some work and research on how to do such benchmarking. Additionally, it would be nice to have some visualizations (?).

Hi. Firstly, apologies if this belongs on a mailing list (I looked but couldn’t find one) but I wanted to have a discussion about the handling of driver breaks.

I’ve used jsprit now for various projects for the last 6 years and I kicked off the discussion originally that got the first iteration of breaks running there. I’m running on the assumption that you have some familiarity with jsprit given the setup of this library, and it looks like you’re making great progress in some of the shortfalls experienced there.

The one thing that causes no end of problems is driver breaks and it appears that you’ve taken the same default as jsprit did - the break inherits the location of the previous, tangible job and your own docs

The problem with this is that breaks are non-trivial in the solution itself. Because of things like EU regulations it simply isn’t good enough in a solution to have them modelled as soft constraints because the solution breaks the law if the break jobs get kicked out. Across jsprit, OR-Tools (broken for ages), VROOM and this library, I cannot find an implementation that can adequately address this.

Fundamentally, this falls down on the location inheritance. If I need to travel 5 hours from the north of the UK down to Cornwall, on a 9-5 shift (for argument’s sake), with a break in the middle, it’s totally impossible for a solution to ever do this job unless there is some stepping-stone job on the way. Tough luck if you're dispatching a full truck for a single order. The stark reality is that vehicles will park up to satisfy the Tachograph at an intermediate location, but this is not possible either with a forward- or a backward-looking location inheritance.

This has led me down all sorts of paths, with instantaneous services at the warehouse immediately before a break just to try fudge this location inheritance, amongst other hacks. They never properly work. I think we need to move away from breaks being considered as a job that can be inserted into a route and, instead, have something time-based.

I’m engaged with a number of large logistics clients with complex constraints, and I have a wrapper library that calls custom and open-source solvers interchangeably, so I can test a number of very different scenarios. Given that you’re so active in your development at the moment and the fact that you’re addressing issues with the solvers that came before, I’d love to assist in testing if you have any ideas on how this long-standing problem can be fixed. Have you had any thoughts in this space and is this something you’d like to explore?

Thanks,

Josh

Hello,
Im trying to build a javascript package by following this example:

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

But I am getting an error:

Error: failed to parse manifest: C:\Users\Vadim Korolov\Desktop\work\@avrora\ui\lib\examples\routing\bin\vrp\Cargo.toml
Caused by: missing field `package`

I am not an expert on rust and cant figure out how to fix it, I tried to google it but no results there...

Thank you

rustc --version = 1.58.1 (db9d1b20b 2022-01-20)
cargo --version = 1.58.0 (f01b232bc 2022-01-19)
Microsoft Windows 10 Enterprise 10.0.18363

Hi, what's the default (expected) unit for distance and duration across all the project? For example, in costs, what's the unit for distance? Is it in meters, kilometers, feet etc..?

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

It is more a comment that an issue.
I am building Geojson directly in JavaScript as it seems that the vrp-cli do not export GeoJson in this configuration.
I did add the unassigned jobs to the GeoJson and to build the map (grey circles in the map below) as it is an important information to get in the planning process (at least in our case).

The only issue here is that in the solution object (solution.json), the location of the unassigned jobs are not provided, contrary to the served one. It requires then to join the solution with the raw data. It is not a big issue, but I wonder if there is a specific reason not returning this information in the solution object.
Thanks a lot.

For some of my use cases, the solution returned by vrp-cli contains lots of unassigned jobs (>10%). The problem at hand contains shops with time windows, but I know that the problem can be solved with the given constraints. To me it seems vrp-cli tries to balance the tour durations even though I specify only the following objectives:

  "objectives": [
    [
      {
        "type": "minimize-unassigned"
      }
    ],
    [
      {
        "type": "minimize-cost"
      }
    ]
  ]

vrp-cli reports that the job can not be served due to time constraints:

  {
      "jobId": "106365",
      "reasons": [
        {
          "code": "SHIFT_TIME_CONSTRAINT",
          "description": "cannot be assigned due to shift time constraint of vehicle"
        }
      ]
   }

However, this is clearly not the case as the delivery location can be reached from the depot within the specified fleet.vehicles[0].limits.shiftTime constraint. Sometimes the unassigned job is not even at the perimeter of the geographic area... I can manually assign the job to the nearby tour without breaking any constraint.

Do you have any idea why that can happen, and how I can enforce the algorithm to try harder to avoid unassigned jobs? I experimented with setting value: 99999 for every job and putting maximize-value objective as the top priority, but it did not eliminate the issue.

time window or interval after which a break should happen (e.g. between 3 or 4 hours after start)

Can you please explain, how to define break intervals? I.e. every 4 hours? Documentation is not clear and i can't find any example.

BTW, great tool.