TSP suite?

[ljwolf]

I now have a collection of vehicle routing problem tools built on top of pyvrp that might be useful for spopt.

The tooling mainly involves data ingestion and conversion to formats/structures that pyvrp can natively work with, and then tools to extract geographical output from pyvrp solutions.

So, things like calculating ETAs in timestamps, conversion of input lon/lats to integer positions and back, creating route geometries, etc.

Is this of interest? I can maintain the public version, but would welcome feedback on API decisions. I think it is substantially different from locate as to warrant a new top level spopt.route module.

An example specification might be:

problem = Route(
    depot_location=(9.2413, 52.2921),
    depot_close=pandas.to_datetime("2025-01-02 20:00:00"),
    depot_name='My Depot',
).add_clients(
    data.geometry,
    data.demand_volume,
    data.time_windows,
    data.source.index,
    data.service_times
).add_trucks_from_frame(
   truck_df
).solve()

[jGaboardi]

Yes! Something like this was in the initial stages of planning/ideas, but has never come to fruition due to time constraints!

• [DO NOT CLOSE] remove proposed functionality from directory, etc. #130

[jGaboardi]

xref: https://github.com/pysal/spopt/wiki/Architecture#module-structure

[jGaboardi]

xref: https://hackmd.io/n7-axu5ITXqjn7mNQNyJlw

[jGaboardi]

Some of our initial ideas (from 5 years ago now) label this kind of thing as route and some label it as transport. I suppose we'll need to determine the most accurate module name.

[gegen07]

This is awesome!

I have another point to think about. We currently use pulp in the locate module, and if we introduce pyvrp for route/transport, that would add another core dependency. This could pose any challenges? How might we manage the environment requirements more smoothly?

Perhaps this would be a good time to meet and discuss our future directions.

[jGaboardi]

@ljwolf This is very exciting. Can your stuff built on top of pyvrp take network distance/travel time as impedance or is bound to euclidean/haversine distance?

[ljwolf]

can your stuff built on top of pyvrp take network distance/travel time as impedance?

Yes. I will post an example if I have time tomorrow. I can't share the examples I have to hand 😄

Currently, it takes lon/lat coordinates for depot and clients, and then builds street route lengths and times from an OSRM table query. Once solved, I build the actual driving route using an OSRM route query. If the routing engine is not found, then it switches to haversine distances, and uses that to estimate durations. Routes are then just straight line.

The ETAs have to be calculated manually to allow for waiting & variable service times per client.

I think for it to be opened, I would need to generalize this routing infrastructure (maybe replace it with routingpy) and expose the option to use pre-calculated duration/distance matrices. I could probably open everything atm, but it wouldn't work without an osrm instance running behind the scenes.

[ljwolf]

One thing I've been looking into and could use advice/help on is using the nanobind bindings to osrm. If we could figure out a conda spell to get that running, then the routing system works without the osrm server process. I have written all the code to use these bindings, but these bindings always segfault on my mac/linux workstations. A client's Windows computer works fine w/ them though.

[jGaboardi]

Yes. I will post an example if I have time tomorrow.

This stuff is amazing... 🤩

[jGaboardi]

Currently, it takes lon/lat coordinates for depot and clients, and then builds street route lengths and times from an OSRM table query. Once solved, I build the actual driving route using an OSRM route query. If the routing engine is not found, then it switches to haversine distances, and uses that to estimate durations. Routes are then just straight line.

So once your new cool stuff gets into spopt this functionality has the potential to be adapted to locate models (in the mid-long term), right??

[ljwolf]

So, here's a reproducible example specifying a model to deliver Guinness from the storehouse to all the pubs in Dublin. In this example, we're dropping off full kegs and picking up empties, and I'm just setting default delivery hours to 7am to 8pm.

The tooling I've built takes you from something like the input clients/depot table and truck spec in the model script to the results map and output tables on stops and routes. The value add comes mainly in making the ingress/egress to pyvrp easier from real geographic data, I'm not doing anything unique (yet) with that codebase.

[jGaboardi]

Very nice!

[qszhao]

Indeed a very nice work @ljwolf!! I think it will worth a good shout on different channels once it is up in our package. Many potential end-users can be there.