Inital pass at higher level VRP implementation

[rodreegez]

Accepts a list of locations and the number of vehicles in use and calculates the appropriate number of routes.

Issues

With the location data supplied in test/vrp_test.rb, if I calculate the distance matrix and scale distances with DISTANCE_SCALE the program segfaults (note, the sample locations data is "real world" and represents several locations broadly within one city). If I use the locations data from test/tsp_test.rb without scaling distances, the program segfaults. Seems that there is a point at which is makes sense to scale distances, but until that point is reached doing so causes problems. I wonder if the DISTANCE_SCALE should be either dynamic based on the distances between the points being routed, or user configurable?

Refactorings

I've basically duplicated the distance matrix calculation from the TSP solution. Could this be extracted into it's own class?

Similarly, right now TSP returns an instance of itself with four attr_accessors: route, route_indexes, distances, total_distance. VRP currently simply returns an instance of itself with the attr_accessor routes, which is an array of arrays containing the routed locations. I feel like it would be cool if there were a Route class that would tie up route, route_indexes, distances and total_distance. TSP would then return a simple instance of the Route class, VRP would return an array of Route classes. wdyt?

This is a real basic first pass. Please let me know if there are any changes that should be made at this stage.

:v:

[ankane]

Hey @rodreegez, thanks for the PR! Overall, the code looks good. My initial impression is it might be a bit too simple for a real-world case, which is what I'd like to aim for with this one (unlike the TSP class). If you're using it in your current work, can you give a bit more context about it?

Re scaling: I can help look into the segfault once it's merged. It's really an implementation detail, so I don't think we should expose it to the user. Re duplication: I like the way you've currently done it for the initial implementation. We can dedup in the future. Re Route class: It's an interesting idea. I wouldn't worry too much about making it consistent with the TSP class, but if there's significant advantages for the VRP to returning Route objects instead of hashes, happy to discuss.

Also, I added .so to the .gitignore so it's not checked in.

[rodreegez]

Also, I added .so to the .gitignore so it's not checked in.

:facepalm: didn't spot that - will rebase and remove that.

Re scaling: I can help look into the segfault once it's merged. It's really an implementation detail, so I don't think we should expose it to the user.

Cool. I'll add the constant back in and calculate the distances as per the TSP implementation.

Re duplication: I like the way you've currently done it for the initial implementation. We can dedup in the future.

Cool cool cool.

Re Route class: It's an interesting idea. I wouldn't worry too much about making it consistent with the TSP class, but if there's significant advantages for the VRP to returning Route objects instead of hashes, happy to discuss.

I think there probably is a case for returning something more usable than a hash, and a case for returning something consistently from both TSP and VRP, but I also think that might be a conversation to be had further down the road? Happy to punt on this for now for sure.

My initial impression is it might be a bit too simple for a real-world case, which is what I'd like to aim for with this one (unlike the TSP class). If you're using it in your current work, can you give a bit more context about it?

Yes, this is about as simple as it could possibly be. You mentioned elsewhere you're keen to see the ability to add and configure capacity/weight constraints, time windows and multi-trip variants of the solution. I'm keen to add these, too.

As for how I'm currently using it, this is the script (don't judge me):

class RoutePlanningService
  attr_reader :drivers, :jobs

  def initialize(drivers, jobs)
    @drivers = drivers
    @jobs = jobs
  end

  def call
    job_attrs = jobs.map { |j| { reference: j.reference, latitude: j.latitude, longitude: j.longitude } }
    if jobs.count == 1
      return if jobs.first.is_a? Depot
      job = jobs.first
      job.update(user: drivers.first)
      job.set_list_position(1, true)
    elsif drivers.count == 1 && jobs.count >= 2
      route = ORTools::TSP.new(job_attrs).route
      route.each_with_index do |job_attrs, position|
        job = jobs.find_by(reference: job_attrs[:reference])
        next if job.is_a? Depot
        job.update(user: drivers.first)
        job.set_list_position(position, true)
      end
    else
      routes = ORTools::VRP.new(job_attrs, drivers.count).routes
      routes.each_with_index do |route,index|
        driver = drivers[index]
        route.each_with_index do |job_attrs, position|
          job = jobs.find_by(reference: job_attrs[:reference])
          next if job.is_a? Depot
          job.update(user: driver)
          job.set_list_position(position, true)
        end
      end
    end
  end
end

As you can see, I'm passing in an array of jobs (AR objects as an array rather than a ARel relation because I unshift the driver's assigned Depot record onto the front of the array in order to set the start point for each driver), and an array of Drivers. Depending on how many jobs and drivers I have I decide how to deal with them (1 driver and one job is a simple assignment, 1 driver and multiple jobs is TSP, multiple drivers and multiple jobs is VRP).

For my v1 right now, this is about as complicated as I need to get. However, I can absolutely see requirements to support more complex VRP solutions in the future, so keen to work on supporting that here.

I have some ideas how to support various kinds of constraints. Will take a run at that and see what happens...

[ankane]

Thanks for sharing.

The way the problem is set up (one depo, one trip per driver) seems similar to package or business delivery, where trucks load up at the start of the day, make their deliveries, and return to the depo at the end of it. In my experience, there's typically a time component to it where you have a prediction of when the driver will arrive at each location.

Are you doing any time estimates outside of the RoutePlanningService class?

[ankane]

Another thought: it probably makes sense to separate out the depo location from job locations in the VRP initializer.

[rodreegez]

Are you doing any time estimates outside of the RoutePlanningService class?

No. You are correct in that this is a pretty simple use case, but no, there is (currently) no time estimates for deliveries. I appreciate you currently work on a somewhat more sophisticated logistics platform, however :wink:

it probably makes sense to separate out the depo location from job locations in the VRP initializer

Does it? I am currently laboring under the impression that the depot is part of the route, i.e. the routes are calculated so that they start and end at the location denoted by the depot integer of locations both of which are passed in when initializing VRP - therefore, the Depot records (which are an implementation detail of my broader approach to modeling my domain) have to be part of the routes returned by VRP? As I understand it, the "depot" could equally be a regular type of location like all the rest passed in. We are essentially using the depot to tell VRP "start and end here", is that right? In which case, it seems like it's up whatever picks up the VRP route to deal with the depot however it sees fit? Please do correct me if I'm wrong!

Anyway, I've had a go at making the current VRP solution more flexible, and I'm a bit confused as to what direction I should be going in here. I've added an add_dimension method in order to create a seem at which the VRP can be configured, however right now it's pretty tightly coupled to the Distance dimension from the basic VRP example. My thought was that it would then be possible to add multiple of, and multiple types of, dimensions to create any given solver you might need. However, the more I think about this, the more I wonder if that's what the lower level API is supposed to be for, and if this higher level API should be less flexible.

I can see a pretty clear path to having several VRP classes; CVRP is a prepacked solution for Capacitated VRP, VRPTW allows for easily configuring a solution with time windows, and some acronym for a "pickup and delivery" orientated solution.

But perhaps there's a middle ground I haven't properly understood yet?

Do let me know if you have any thoughts on any of the above. Would love to get my head around what the solution we're collectively looking for here looks like!

[ankane]

Hey @rodreegez, sorry for falling off. I don't think I'm ready to include/support a higher level VRP class right now, so it's probably best as a separate gem if you're still using it.

In any case, thanks again for the PR.