search

Kuifje02 / vrpy

A python framework for solving the VRP and its variants with column generation.
MIT License
173 stars 42 forks source link

Source and Sink terms #114

Closed orlandombaa closed 2 years ago

orlandombaa commented 2 years ago

Hello every one

I have a doubt about the terms used in the library. In the examples when you generate the distance matrix you start with the rows which correspond "from source" that I assumed means the depot. The last rows of the matrix have values of 0 and it corresponds to "From Sink". What does the sink mean in this case and why it has a value of 0?

Thank you!

Kuifje02 commented 2 years ago

Hi ! The depot is modeled by two differents nodes, the Source and Sink, which have the same location. The Source is the depot from which vehicles start their route, while the Sink is depot where the vehicles end their route. So there cannot be any incoming edges into the Source, and no outgoing edges from the Sink, hence the zeros in the distance matrix.

Does this clarify things ?

orlandombaa commented 2 years ago

Hello @Kuifje02 thank you for the answer. Yes, it clarifies the situation with the Source and Sink.

However, one more doubt emerges from this. So, the optimal solution that the model generates takes into consideration the return cost of the vehicles to the depot?. Because if the Sink is the Depot too but It has values of 0 in the distance matrix, the cost from returning the vehicles to the depot is 0 too isn't ?

Kuifje02 commented 2 years ago

So, the optimal solution that the model generates takes into consideration the return cost of the vehicles to the depot?

yes, this cost is taken into account, on the edges TO the Sink.

Because if the Sink is the Depot too but It has values of 0 in the distance matrix, the cost from returning the vehicles to the depot is 0 too isn't ?

The 0s in the distance matrix are on the edges LEAVING the Sink (and not entering), as these edges cannot exist.

orlandombaa commented 2 years ago

Thank you @Kuifje02 !