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