Thank you for the help! I've never looked into ILPs before and I was misunderstanding you at first, but I get it now!

Thank you! I have some questions if that's ok with you. Your formulation goes from car to car, and using their available seats it tries to find all combinations of passengers and calculate the shortest path for each combination, correct? I guess I would need to use this solver twice. 1 to group riders with drivers, 2 to group clusters between themselves? And sometimes the combined shortest dist is clusters traveling separately, That's where the zero-or-one variable comes in? The chosen S for each car would be one combination without the other cars, meaning they would travel separately.

Euclidean distances for a non-directed graph. Only one edge between nodes. For proper traveling distances, it would need to be a directed graph. I found that distance using roads aren't always the same going from A to B and from B to A (one-way streets, road-work, etc.) Euclidean distances seem like a good option for me (?).

@Vince Participant numbers in each computation will be fairly small. Although I'm studying a general solution, given the intended scope I don't expect participant numbers (drivers and riders combined) to exceed double-digits per calculation often, if ever. The problem does seem to mirror a general TSP, but the TSP has some clear rules that my problem doesn't follow (listed in the proposed COVRP solution). I don't know how I can adapt it. I am interested in heuristic solutions. As a matter of fact, I've implemented one solution based around Voronoi Cells, but the results weren't great.

Thank you for the help! I'd never heard of the bin packing problem, so thank you for mentioning it to me. I didn't fully understand the 2nd paragraph of your answer (sorry), but you suggested sorting by bin capacity first before running the algorithm. I edited my original question with mention of your answer and an adaptation based on your suggestion if you could give it another look. Thank you!