Helicopter problem: how to manage optimally demands larger than capacities of transportation units

[SebastienP385]

Hi!

I have had a lot of pleasure using OR-tools, on a pick up and delivery case, to which I added capacity constraints, to model a set of helicopters routes serving multiple stations.
This is what I found and where I need some help:

let's assume I have 23 passengers going from Point A to Point B, using choppers with capacity of 15 (and 5 passengers from Point B to C, etc...)
OR-tools optimal solution is calculated on a demand between A to B. If I set up 23, it does not work because of the constraint. If I put 15+8 (to force 2 choppers to handle the load), it works, but the result might be less optimum than let's say 13+10. I might also have to combine this with a split of the 5 passengers from B to C into 3+2 or 4+1. This leads to more optimal routings, and is realistic as overall I manage 5-9 flights a day, between circa 15 stations, in the current test case.
I currently manage this search of the optimal 'demand splits' via a search algorithm on top of OR tool (genetic search does not work super well, so it is a sort of random search at the end).
Would there be a way to have OR tool calculating the optimal splits/distribution of demand batches?

NB: I have tried to create a lot of sub-demands, let's says 23 individuals demands to go from point A to point B. The drawback is that I have to create 23 pseudo-nodes A, and 23 pseudo-nodes B: this leads to an explosion in the number of nodes, and in calculation time.
I have tried also fancy methods like : 23 = 1+2+3+6+11, to give the chance to OR tool to find the right combination of 2-3 flights. It did not bring as good results as the search, and takes a lot of time. The inconvenient of the search is that it is not very repeatable.

Thanks a lot in advance, and happy (prep of the ) new year 2020!

[hklarner]

I have tried to create a lot of sub-demands, let's says 23 individuals demands to go from point A to point B

I think this is the way to go.

[Mizux]

At its core or-tools routing is a TSP meaning only visit a node once, so auto splitting is not a built-in/supported feature unfortunately... :(

note: there is already few issues on the same subject (#938, #689, #630, #1246, #1323)

[nag96]

Hi Sebastien,

Can you please share the code of how you're achieving splitting demand to sub-demands where the capacity is breached. I'm working on a problem related to this. Please help!

Thanks in advance.

[glazaridis]

Hi Sebastien,

Can you please share the code of how you're achieving splitting demand to sub-demands where the capacity is breached. I'm working on a problem related to this. Please help!

Thanks in advance.

Any news on that?

[nag96]

Nope

…

On Thu, Jan 7, 2021, 9:34 PM Giorgos Lazaridis ***@***.***> wrote: Hi Sebastien, Can you please share the code of how you're achieving splitting demand to sub-demands where the capacity is breached. I'm working on a problem related to this. Please help! Thanks in advance. Any news on that? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#1808 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACNM4VM6SXO4UVVV36QUC2DSYXLRDANCNFSM4J7LUXAQ> .

[lperron]

Demands at the node are fixed. So you decide how to split a load of 100 in multiple chunks. (50, 50) or (50, 25, 25), (33, 33, 34)... It is your problem knowledge that can help you. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le jeu. 7 janv. 2021 à 17:24, Nagarjuna Chidara <notifications@github.com> a écrit :

…

Nope On Thu, Jan 7, 2021, 9:34 PM Giorgos Lazaridis ***@***.***> wrote: > Hi Sebastien, > > Can you please share the code of how you're achieving splitting demand to > sub-demands where the capacity is breached. I'm working on a problem > related to this. Please help! > > Thanks in advance. > > Any news on that? > > — > You are receiving this because you commented. > Reply to this email directly, view it on GitHub > <#1808 (comment)>, > or unsubscribe > < https://github.com/notifications/unsubscribe-auth/ACNM4VM6SXO4UVVV36QUC2DSYXLRDANCNFSM4J7LUXAQ > > . > — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1808 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3NYLIND5PHRSK3KVULSYXN27ANCNFSM4J7LUXAQ> .