Plan

[ankane]

Ideas

• Add support for DoubleLinearExpr
• Move SAT linear expression building to Ruby (see cp_model.py)

More higher level interfaces

• Hourly scheduler - people needed per hour as input - output could be shifts or assignments (if availability is given)
• Vehicle routing
• Planting schedule

[rodreegez]

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.

[ankane]

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.

[ankane]

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

[rodreegez]

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