# Combinatorial Optimization: Shortest distance given sets of drivers and riders

Problem:

I have 2 sets, one of drivers and one of riders. All my participants need to reach one common destination. I wish to calculate the shortest combined distance in order for all participant to reach said destination. Although the goal is not to reduce the number of cars, drivers can be considered as passengers if the resulting distance is smaller.

Constraints:

• Riders and drivers have distinct starting locations
• All participants must reach the destination (common to all)
• The riders need to be picked up by a driver
• The drivers' cars have limited capacity and the capacity is individual to each car

I'm failing to understand what type of problem I'm facing, and I'm seeking some help.

1. Vehicle Routing Problem

I've thought of solving it as the Vehicle Routing Problem. A Capacitated Open Vehicle Routing Problem (COVRP) to be more exact. Drivers would act as the vehicle fleet and riders as the customers. A capacitated version because cars have limited seats, and an open version because drivers depart from unique positions and don't return to the "depot" but instead end on the destination.

Problem: In the VRP, not all vehicles of the fleet are used, and the remaining ones are left in their respective "depots". For my problem, I would need all participants to reach the final destination, so I need for existing vehicles to be considered as possible pick-ups for other vehicles.

I could just send the remaining drivers straight to the destination. But that wouldn't really provide a minimum distance solution to my problem, as better ones could be accomplished if the drivers could serve as customers.

1. Minimum Spanning Tree

As an MST problem, I could use the destination as the root and my participants (drivers and riders) as nodes. Each sub-graph originating from the root would be a cluster to be picked up by a driver.

Problem: The sub-graphs aren't guaranteed to have a driver's node in one end (to be used as a starting point and prevent doubling back on edges), and the sub-graphs may have paths with more nodes than available seats.

The capacitated MST variant introduces capacity to the solution, but it is a fixed capacity. Driver's cars have different capacities, so the MST sub-graphs would need to have individual sizes and each sub-graph would need to encompass the driver of the corresponding capacity.

Am I wrongfully categorizing my scenario as a combinatorial optimization problem? I appreciate any help to fix the above-mentioned problems or to correctly categorize my computational problem.

Edit: If I managed to group the riders with drivers (with the use of some heuristic), then the remaining set would be drivers and their assigned passengers, or basically a list of clusters of 1+ participants.

I could then apply a capacitated MST solution to this collection. With the destination as root, the sub-graphs would be groupings of the previous clusters. Ideally, each sub-graph would have different capacities in accordance with the seats of the containing cars.

I'm not sure that's possible, so I thought about doing a loop:

• What're the most available seats in a single car?
• Run the capacitated MST with that seat capacity
• Get the sub-graph containing the car of the corresponding capacity
• Remove all the clusters of that sub-graph from future computations
• Repeat with the remaining cluster, until no more computations are possible

The problem I see arising is if the selected pivot car is in the middle of the sub-graph, meaning that it would need to double-back on edges because it wasn't a terminal node.

Still doesn't feel like a proper solution...

Thanks for the help!

• This problem is clearly NP complete as a global extension of TSP. Can both the number of drivers and riders be very large ? Are you interested on a heuristic solution ? – Optidad Mar 15 '19 at 10:31
• @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. – Ricardo Jesus Mar 15 '19 at 15:10
• okay and what about distance ? Is it euclidian distance ? – Optidad Mar 15 '19 at 21:32
• 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 (?). – Ricardo Jesus Mar 16 '19 at 0:17

These kinds of scheduling problems tend to be hard (e.g., NP-hard to solve exactly; and messy because of all of the different constraints you have).

My favorite "big hammer" for this kind of scheduling problem is to use integer linear programming, as that has been used successfully for a number of different scheduling and operations research tasks.

The best way to formulate this as an ILP problem may depend on the parameters (how many drivers and riders you have), but let me describe one illustrative approach. Suppose each car can have up to 5 riders. Then consider all possible ways to choose a combination $$S$$ of 1 driver and up to 5 riders. For each such, compute the total distance $$d_S$$ of the shortest route that involves that driver picking up all riders and taking them to the destination (this might involve $$5!=120$$ shortest-path computations). Now introduce a zero-or-one variable $$x_S$$ for each combination $$S$$, with the intended meaning that $$x_S=1$$ means we select that combination. We require that each participant is selected exactly once; thus, for each participant $$p$$, we add the equality $$\sum_S x_S = 1$$, where $$S$$ ranges over all combinations with $$p \in S$$. Then, we minimize the linear objective $$\sum_S d_S x_S$$, where $$S$$ ranges over all combinations. This ensures we minimize the total distance, while ensuring every participant reaches the destination.

Then, apply an off-the-shelf ILP solver. If the number of riders and drivers is small enough, it should find an optimal solution. If it is taking too long, many ILP solvers will let you terminate them early and report the best solution found so far, which may be effective at finding a good but not optimal solution.

This particular formulation might work well if the number of riders is not too large. If the number of riders is very large, you might need to consider other formulations.

• 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. – Ricardo Jesus Mar 16 '19 at 0:38
• @RicardoJesus, no, you'd use the ILP solver once. You'd have one variable per possible combination. There are many (overlapping) combinations: e.g., with 10 drivers and 20 riders, there would be something like $10 \times {20 \choose 5}$ combinations. You'd figure out all possible combinations in advance, generate one variable per, create a giant linear system, and feed it all to the ILP solver. The ILP solver would solve the whole thing in one go. – D.W. Mar 16 '19 at 0:42
• Zero-or-one is because you either select a participant or don't (you can't put half a rider in a car). Yes, each $x_S=1$ corresponds to one car; each car drives separately. – D.W. Mar 16 '19 at 0:42
• Thank you for the help! I've never looked into ILPs before and I was misunderstanding you at first, but I get it now! – Ricardo Jesus Mar 19 '19 at 0:01