Performance Degradation in Distance/Time Matrix Calculation with Avoid Areas when Handling Many Locations

[TiagoDelatorre]

Is there an existing issue for this?

• I have searched the existing issues

Where did you encounter this issue?

self-hosted instance

Request URL

/v2/matrix/driving-car

POST Request Body

{
        "options": {
        "avoid_polygons": {
            "type": "MultiPolygon",
            "coordinates": [
                [
                    [
                        [
                            -46.63611,
                            -23.55052
                        ],
                        [
                            -46.63611,
                            -23.55117
                        ],
                        [
                            -46.63545,
                            -23.55117
                        ],
                        [
                            -46.63545,
                            -23.55052
                        ],
                        [
                            -46.63611,
                            -23.55052
                        ]
                    ]
                ],
                [
                    [
                        [
                            -43.28497,
                            -22.90834
                        ],
                        [
                            -43.28497,
                            -22.90875
                        ],
                        [
                            -43.28440,
                            -22.90875
                        ],
                        [
                            -43.28440,
                            -22.90834
                        ],
                        [
                            -43.28497,
                            -22.90834
                        ]
                    ]
                ]
            ]
        }
    },

    "locations": [
        [
            -47.146171,
            -22.725134
        ],
        [
            -47.141808,
            -23.051743
        ],
        [
            -47.36693,
            -22.55681
        ],
        [
            -47.017374,
            -23.008373
        ],
        [
            -47.046673,
            -23.159878
        ],
        [
            -47.36048,
            -22.61032
        ],
        [
            -46.543768,
            -22.968189
        ],
        [
            -47.199518,
            -22.902881
        ],
        [
            -47.795076,
            -22.971709
        ],
        [
            -47.619172,
            -22.671704
        ],
        [
            -46.91245,
            -23.156171
        ],
        [
            -46.952536,
            -23.091378
        ],
        [
            -47.200871,
            -23.069151
        ],
        [
            -47.587318,
            -22.49004
        ],
        [
            -47.32073,
            -22.7623
        ],
        [
            -47.231034,
            -23.108722
        ],
        [
            -47.154463,
            -22.733774
        ],
        [
            -47.096684,
            -22.910307
        ],
        [
            -47.55591,
            -22.41121
        ],
        [
            -47.673132,
            -22.689884
        ],
        [
            -46.941895,
            -22.386631
        ],
        [
            -47.417212,
            -22.71289
        ],
        [
            -47.042301,
            -22.930757
        ],
        [
            -47.002592,
            -22.96807
        ],
        [
            -47.057506,
            -22.633656
        ],
        [
            -46.583924,
            -23.187371
        ],
        [
            -46.793617,
            -22.879876
        ],
        [
            -46.535694,
            -22.941988
        ],
        [
            -46.895981,
            -22.731305
        ],
        [
            -47.38553,
            -22.350924
        ],
        [
            -46.549453,
            -22.915491
        ],
        [
            -47.045173,
            -23.156104
        ],
        [
            -46.94705,
            -22.34895
        ],
        [
            -47.358362,
            -22.745764
        ],
        [
            -46.985101,
            -23.038304
        ],
        [
            -47.081448,
            -2.819056
        ],
        [
            -47.061219,
            -22.888374
        ],
        [
            -47.630338,
            -22.738883
        ],
        [
            -47.920919,
            -22.550908
        ],
        [
            -47.047058,
            -22.906241
        ],
        [
            -47.385537,
            -22.360389
        ],
        [
            -47.338322,
            -22.747447
        ],
        [
            -47.30686,
            -23.257073
        ],
        [
            -47.745806,
            -23.158759
        ],
        [
            -47.531493,
            -22.459683
        ],
        [
            -46.785821,
            -23.207449
        ],
        [
            -47.202158,
            -22.628901
        ],
        [
            -46.894594,
            -21.631325
        ],
        [
            -47.420881,
            -22.499885
        ],
        [
            -47.296419,
            -22.790139
        ],
        [
            -47.0,
            -21.0
        ],
        [
            -47.230918,
            -22.890563
        ],
        [
            -46.793174,
            -22.884255
        ],
        [
            -47.152097,
            -22.737447
        ],
        [
            -47.675326,
            -22.699817
        ],
        [
            -46.795052,
            -21.984122
        ],
        [
            -46.916814,
            -23.173199
        ],
        [
            -47.61216,
            -22.731486
        ],
        [
            -47.433761,
            -22.562243
        ],
        [
            -47.517263,
            -23.239965
        ],
        [
            -47.261445,
            -21.81495
        ],
        [
            -46.544943,
            -22.951837
        ],
        [
            -47.216195,
            -22.850342
        ],
        [
            -47.37255,
            -23.04154
        ],
        [
            -47.206926,
            -22.891536
        ],
        [
            -47.531749,
            -22.455572
        ],
        [
            -46.577189,
            -21.837253
        ],
        [
            -47.396752,
            -22.18844
        ],
        [
            -46.566992,
            -22.577782
        ],
        [
            -47.673493,
            -22.681148
        ],
        [
            -46.533844,
            -22.976617
        ],
        [
            -46.555261,
            -23.110577
        ],
        [
            -46.556998,
            -23.104027
        ],
        [
            -47.007204,
            -22.996391
        ],
        [
            -47.056226,
            -23.245159
        ],
        [
            -47.044122,
            -23.092303
        ],
        [
            -47.7419,
            -23.156192
        ],
        [
            -47.874357,
            -22.599316
        ],
        [
            -47.573306,
            -22.415654
        ],
        [
            -47.516134,
            -22.462818
        ],
        [
            -47.179668,
            -22.808683
        ],
        [
            -47.210514,
            -22.906544
        ],
        [
            -47.548978,
            -23.428816
        ],
        [
            -47.404341,
            -22.495139
        ],
        [
            -46.913179,
            -23.186963
        ],
        [
            -46.889622,
            -23.195593
        ],
        [
            -47.258897,
            -22.7635
        ],
        [
            -47.550613,
            -22.360144
        ],
        [
            -47.30277,
            -22.749572
        ],
        [
            -47.504442,
            -22.622082
        ],
        [
            -47.1665,
            -22.830434
        ],
        [
            -46.99688,
            -23.066666
        ],
        [
            -47.946384,
            -23.039699
        ],
        [
            -46.953356,
            -22.425976
        ],
        [
            -46.953335,
            -22.425976
        ],
        [
            -48.578364,
            -22.393495
        ],
        [
            -47.270369,
            -23.170865
        ],
        [
            -47.272192,
            -23.051184
        ],
        [
            -46.982324,
            -23.0
        ],
        [
            -46.990116,
            -23.05518
        ],
        [
            -47.233233,
            -22.800485
        ],
        [
            -47.425368,
            -22.570458
        ],
        [
            -46.998479,
            -22.956687
        ],
        [
            -47.553333,
            -23.029745
        ],
        [
            -47.19532,
            -22.80321
        ],
        [
            -47.396939,
            -22.353478
        ],
        [
            -47.232508,
            -22.799739
        ],
        [
            -47.597346,
            -22.752678
        ],
        [
            -47.26643,
            -23.214314
        ],
        [
            -47.320926,
            -22.777777
        ],
        [
            -47.232402,
            -22.800061
        ],
        [
            -47.49797,
            -22.474617
        ],
        [
            -46.634153,
            -22.486031
        ],
        [
            -47.655741,
            -22.710659
        ],
        [
            -47.787637,
            -23.165481
        ],
        [
            -47.318474,
            -22.732374
        ],
        [
            -47.379299,
            -22.553499
        ],
        [
            -47.034456,
            -22.997192
        ],
        [
            -47.325063,
            -22.739473
        ],
        [
            -46.898139,
            -23.190414
        ],
        [
            -46.716844,
            -21.935393
        ],
        [
            -47.367594,
            -22.55939
        ],
        [
            -47.07399,
            -22.89593
        ],
        [
            -46.842002,
            -23.019303
        ],
        [
            -46.872139,
            -23.182151
        ],
        [
            -46.949784,
            -23.083498
        ],
        [
            -46.828052,
            -22.435066
        ],
        [
            -47.056532,
            -22.925614
        ],
        [
            -47.07038,
            -22.929548
        ],
        [
            -47.393368,
            -22.575595
        ],
        [
            -47.108935,
            -22.944418
        ],
        [
            -47.042092,
            -22.831364
        ],
        [
            -47.335961,
            -22.75385
        ],
        [
            -47.277831,
            -22.814256
        ],
        [
            -47.029796,
            -22.900188
        ],
        [
            -46.988915,
            -22.962868
        ],
        [
            -47.603516,
            -22.84474
        ],
        [
            -46.575149,
            -21.785583
        ],
        [
            -46.848078,
            -22.997922
        ],
        [
            -46.872959,
            -23.152711
        ],
        [
            -47.21109,
            -23.106039
        ],
        [
            -46.960281,
            -23.187334
        ]
    ]
}

Response

Not responding

Current behavior

I am experiencing significant performance issues when calculating distance/time matrices using the service that supports avoid areas, particularly when dealing with many locations. Initially, the processing time to generate the matrix between specific points is approximately 2.3 seconds. However, when including designated avoid areas, the processing time increases drastically.

Expected behavior

The distance/time matrix calculation service, which supports avoid areas, is expected to maintain consistent and efficient performance regardless of the inclusion of these additional areas

Openrouteservice Version

8.1.0

Build date

2024-06-05T10:07:23Z

Graph date

2024-07-15T23:16:52Z

Forum Topic Link

No response

[MichaelsJP]

@TiagoDelatorre Thanks for opening this.
I'm a bit surprised and puzzled to see avoid areas in use and working with the Matrix endpoints. So far, we didn't activate/allow this, exactly for the performance issues you seem to encounter. When using our developer dashboard, you can see that options are not available for matrix (yet): https://openrouteservice.org/dev/#/api-docs/v2/matrix/{profile}/post

Please share your openrouteservice config/setup with us so we can better understand what is going on.

[TiagoDelatorre]

Thank you very much for your attention.

I work in Brazil, where unfortunately cargo theft is a constant concern, especially in certain regions considered high-risk. For this reason, it is essential for our operation to use avoidance areas (avoid_polygons), as we need to avoid these zones when routing and generating distance matrices.

I noticed that with a few areas to avoid, the matrix generation works correctly. However, when I specify a larger number of areas in the avoid_polygons parameter, there is a significant drop in performance. Knowing that this feature is not yet officially available on the Matrix endpoint, I would like to ask if there is any way to optimize the use of multiple avoidance areas, or if you have any suggestions to improve this point without compromising the performance of the service.

Thank you again for your willingness to help, and I look forward to your guidance.

Best regards,

@TiagoDelatorre

########docker-compose########
version: '3.8'

services:
ors-app:
build:
context: ./
container_name: ors-app
ports:
- "8080:8082"
- "9001:9001"
image: openrouteservice/openrouteservice:v8.1.0
volumes:
- ./ors-docker:/home/ors
environment:
REBUILD_GRAPHS: False
CONTAINER_LOG_LEVEL: INFO
XMS: 6g
XMX: 12g
ADDITIONAL_JAVA_OPTS: ""

########ors-config########
ors:
engine:
source_file: /home/ors/files/south-america-latest.osm.pbf
init_threads: 1
profiles:
car:
enabled: true

[sfendrich]

Unfortunately, there is no solution for this issue yet. To account for avoid areas, ORS must fall back to a more flexible, but slower routing algorithm. We are in the process of investigating alternative algorithms but this is rather a long-term project.

Depending on your programming skills you might preprocess your OSM dataset and set a very low speed limit in the areas to avoid.