Feeding VRP a sparse matrix

[do-me]

Hi,
we have a short question whether it would be possible to feed VRP a sparse matrix for very large computations.

Background

We have a very large location-allocation problem with 300k jobs and like 100 depots in all of Germany, where each depot has a max radius of e.g. 2h or 200km.

Problem

With 300k distinct addresses, OSRM expectedly gives us OOM errors on our machine.

Solution Idea

As the depots radii are limited, a full matrix is not needed. A depot in Munich will not serve addresses in Berlin.
Hence our idea was to "glue together" smaller matrices (depot + addresses in 2h radius + buffer) from the single depots to a big sparse matrix.

Can VRP use such a sparse matrix and e.g. just assume an arbitrarily high value for missing distances?

[reinterpretcat]

Hi,

Out of box this is not supported, but you can extend TransportCost trait to support this scenario, see its API and SimpleTransportCost as example:

https://github.com/reinterpretcat/vrp/blob/master/vrp-core/src/models/problem/costs.rs#L56-L125

You would need to think about your internal data structure to represent a sparse matrix and modify the code to pass it from outside.

[do-me]

Thanks a lot for the pointer! I'm still looking for alternatives to model this problem in a better way but this sounds like it's possible.
If I decide to go this way, I'll come back here.

[pvojnisek]

Hi,

I have a follow-up question regarding the sparse matrix discussion. Given that implementing a custom TransportCost trait requires significant development effort, I'm considering a simpler workaround and would like to understand the performance implications.

My situation:

• Similar large-scale problem
• Most job-job combinations are infeasible due to distance/time constraints
• I can identify infeasible combinations beforehand

Proposed workaround:
Instead of implementing sparse matrices, I'm considering setting very large penalty distances (e.g., 5000 km) for infeasible depot-job combinations while keeping realistic distances for feasible ones.

Since the algorithm would still process a full dense matrix (just with penalty values), would this approach provide any meaningful performance improvement over a standard dense matrix? Or does the real performance gain only come from the memory/computational savings of a true sparse implementation?

[reinterpretcat]

Hi,

approach with large distances/duration should definitely work (assuming you have explicit or implicit shift or time limit to prevent 5000km+ tours..). Regarding performance implications: I would recommend simply measure it using some perf test as the runtime performance depends on your actual implementation of sparse matrix, problem scale and other, less obvious, conditions.