Open ankane opened 4 years ago
Hey, I'm working on VRP at the moment, and would love to try and contribute back to this project if I can. Did you have any thoughts or feelings on what a solution could/should look like in order to fit in with the wider goals of the project? I'd love to try and do this from or-tools if I can.
Cheers.
Hey @rodreegez, thanks for the interest in helping out.
Ideally there'd be a friendly API where you can define the problem with simple concepts (no calls like register_transit_callback
and set_arc_cost_evaluator_of_all_vehicles
). Here's a rough initial idea for VRP, but I'd be curious to see what you come up.
vehicles = [
{id: "v123", latitude: 1.1, longitude: 2.2, capacity: 12},
...
]
deliveries = [
{id: "d123", pickup: {latitude: 1.1, longitude: 2.2}, dropoff: {latitude: 1, longitude: 2}, time_window: start_time...end_time, weight: 3},
...
]
router = ORTools::Router.new(vehicles: vehicles, deliveries: deliveries, multiple_trips: true)
router.trips
It could use haversine distance by default, but also take a proc to allow you to build more complicated models.
Many options could be optional:
capacity
/weight
(probably better names) if vehicles have carrying limits (capacitated variant)time_window
if there are delivery windows (time window variant)multiple_trips
if vehicles can do multiple trips (multiple trip variant)Anyways, these are just some initial thoughts. I think the initial version could start with a specific variant and a rigid set of options, and it could later be expanded to support other cases.
Hey @rodreegez, just fyi, I added a higher level interface for TSP. It's much simpler than VRP, but may provide some inspiration for the API: https://github.com/ankane/or-tools#traveling-salesperson-problem-tsp
@ankane super cool, thanks. I'll see if I can open a PR with where I'm at on VRP soon. I'm sure I can follow your lead and make what I've done so far fit with what you've done here. Nice one, thank you.
Ideas
DoubleLinearExpr
cp_model.py
)More higher level interfaces