Combinatorial Optimization: Shortest distance given sets of drivers and riders

Question

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.

2. 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!

Answer 1

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.