search

Kuifje02 / vrpy

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

Distribution & collection option with cspy #14

Closed Kuifje02 closed 4 years ago

Kuifje02 commented 4 years ago

The following variant described in Salani and Righini's article should be fairly easy to implement, now that we are confident with time windows and its cutom REF :

image

For the backwards custom REF :

image

torressa commented 4 years ago

Cool, I'll make a start on this probably tomorrow

torressa commented 4 years ago

I think this works, I'm a bit confused by the difference between pick-delivery vs distribution-collection. Will read up on it. Also, the ortools test I've added seems to be faster than the LP.

Kuifje02 commented 4 years ago

Great, I will take a look !

I'm a bit confused by the difference between pick-delivery vs distribution-collection.

Pickup and delivery : you have to pickup a good from a vertex A and bring it to a vertex B. Pairs (A,B) are given and called "requests" (B requests a good from A).

Distribution and collection : you have to service each node with a pickup and a delivery : when you reach a vertex A, you have to deliver its demand d(A) (which is loaded at the depot)+ pick up some waste matter p(A) and bring it back to the depot.

torressa commented 4 years ago

Sweet! Thanks Just had a quick google about the pickup and delivery and found this paper. End of page 10 basically says that the bidirectional algorithm won't work due to dominance conditions for backward labels. Might still be worth running these with direction="forward" after we figure out how to model it

Kuifje02 commented 4 years ago

great work @torressa !