search

graphhopper / jsprit

jsprit is a java based, open source toolkit for solving rich vehicle routing problems
https://www.graphhopper.com/open-source/
Apache License 2.0
1.64k stars 605 forks source link

Pick-one-of-many target: could it be done? #529

Closed balage1551 closed 2 years ago

balage1551 commented 3 years ago

Hi!

I'm back with a new challenge. I have to find a TSP solution of a flow-network: a non-complete graph, where the vertexes has dimension, so distance of A and B differs depending on the previous steps of the path. As it can't be handles due to the algorithm ruin-and-rebuild nature, I though another way to solve it.

Each vertex (destination) has a few possible entry and exit points. So I could represent the graph by adding altering steps: inter-vertex and in-vertex. But the algorithm have to pick only one of the in-vertex entry-exit points.

An example: The graph edges are

A-B, B-C, C-D, B-D

Each node has several entry and exit points, lets call them A1e, A2e,... for entries of A, and A1x, A2x,... for exits.

So the graph would be something like this:

(A1x, A2x) -> (B1e, B2e, B3e) (B1e, B2e, B3e) -> (B1x, B2x, B3x) (B1x, B2x) -> (C1e) (C1e) -> (C1x, C2x) (C1x, C2x) -> (D1e) ...

The algorithm should pick exactly one from each set of nodes (grouped in parentheses).

More formally, is there a way to give "pick exactly one of many targets" to the problem?

Thanks, Balage

balage1551 commented 3 years ago

To rephrase the question:

Can I make a context-dependent distance matrix? In other word: a distance calculation doesn't only depend on the two nodes, but the current route itself. (Or in my case: the step before from.)