strange (too long) route created by VRoom

[twarogowski-dts]

Hello,

first I want to thank you for a fantastic work on VRoom project. It is a truly great tool, which produces impressive results. Most of the time it gives consistent results, often better than those created by human planner. However, I just noticed one recent anomaly that I cannot explain. Result contains several routes, the weird one is the one with distance 461539 meters. All jobs in this route have same time_windows, so I cannot tell why the route is so long. This result was easily manually post-optimized by my colleague by simply rearranging order of jobs, resulting in distance of 339 km, instead of 461.

vroom_request_1.json.txt
vroom_response_1.json.txt

[jcoupey]

Thanks for reporting and sharing an instance. The response you provide does not contain the full optimization output (only the routes array), can you please also share the full response?

[twarogowski-dts]

Sure, I did not turn off results filtering in Insomnia REST App :)

vroom_response_1_full.json.txt

[jcoupey]

Thanks, this route does indeed look weird. In order to reproduce the problem, could you please share:

• vroom version;
• specific tuning (e.g. -x command-line flag) if any;
• a standalone version of the problem instance.

[twarogowski-dts]

Sure:

I use vroom v1.11
no specific tuning, I use standard docker compose:

version: "3.7"

networks:
  geonet:
    external: true

services:
  vroom_osrm:
    image: vroomvrp/vroom-docker:v1.11.0
    container_name: vroom_osrm
    restart: unless-stopped
    volumes:
      - /opt/geo/vroom_osrm/conf/:/conf
      # ports:
      # - 3000:3000
    environment:
      - VROOM_ROUTER=osrm
    networks:
      - geonet

and this is my conf (part of it):

cliArgs:
  geometry: false # retrieve geometry (-g)
  threads: 4 # number of threads to use (-t)
  explore: 5 # exploration level to use (0..5) (-x)
  limit: "1mb" # max request size
  logdir: "/.." # the path for the logs relative to ./src
  logsize: "10M"
  maxlocations: 1000 # max number of jobs/shipments locations
  maxvehicles: 200 # max number of vehicles
  override: true # allow cli options override (-g, -t and -x)
  path: "" # VROOM path (if not in $PATH)
  port: 3000 # expressjs port
  router: "osrm" # routing backend (osrm, libosrm or ors)
  timeout: 300000 # milli-seconds
  baseurl: "/"

here you have request with matrices in it:

vroom_request_1_matrix.json.txt

[jcoupey]

Thanks for sharing the instance with matrix.

First I can confirm that reordering route for vehicle 4012 in a straightforward round-trip way is both better and valid. Travel time drops from 29249 down to 24043.

This calls for several comments.

Why is this solution not improved internally?

The problematic route goes back and forth through groups of 3 (or more) jobs in different places. Fixing this would require a more complex move that what we have in the current local search process. In other words, we don't have a way to get out this (bad) local minimum.

Why is this happening in the first place?

We're trying to improve several solutions concurrently while solving. It's no surprise that some of them are poor due to the local search limitations explained above. But usually since we return the best solution it's somehow usually "free" of this kind of bias. What is specific here is that this solution is both poor on one of it's route, but it's the only one we have that achieves only 1 unassigned task. All other solutions we have at hand are better in term of duration (and with a "clean" look) but are discarded since they have 2 or more unassigned tasks.

Another factor is that we use different heuristics to solve homogeneous problems (all vehicles having same locations) and heterogeneous problems. This one falls in the latter category since one vehicle end is different, but it's still very similar to a single-depot setup and the homogeneous heuristics would perform better on it.

What should we do to fix this?

Looking at different stages of solving while debugging shows that the ideas already exposed in #737 could definitely help here.

[twarogowski]

Julien,
thank you for detailed explanation. Are there any plans of solving this problem anytime soon?

[jcoupey]

No precise plan right now. I mean, working on #737 is definitely something I'd like to do but we also have other important topics based on feedback from our API clients and feature-funding users.

A good way to move this toward the top of the pile is to somehow contribute to the dev, feel free to reach out to me directly if your company would like to consider this option!

[jcoupey]

The problem reported above is fixed using v1.14.0.rc-3. The new solution looks radically different (and better) so the specific route discussed above is not problematic anymore. Priority score and number of unassigned are the same but cost drops from 172515 with v1.13.0 to 169315 with v1.14.0.rc-3.

I did not dig into this much further but my intuition is that it's another benefit of the PriorityReplace operator introduced in #1021. Turns out that the way it improves priority scores make it also possible to reach to better solutions cost-wise. See #1021 (comment) for details on this.

Closing as fixed.