how does alternate stops work?

[pchtsp]

I'm reading on https://www.nextmv.io/docs/use-cases/vehicle-routing/features/alternate-stops trying to understand how they work. The documentation is not very clear on the purpose for the functionality.

I initially thought that it was similar to ortools AddDisjunction + penalties (https://developers.google.com/optimization/routing/penalties) where a list of mutually exclusive stops is given a penalty for not being satisfied. Or PyVRP "Client Group" (https://pyvrp.readthedocs.io/en/latest/api/pyvrp.html#pyvrp.Model.Model.add_client_group), which works in a similar way (at-most-one or exactly-one depending on whether required=True).

But then I see that Alternate Stops are defined not as a subset of all stops but as a separate list of stops. And that it can (should?) be expressed by vehicle.

More broadly what I'm modelling is the following: I have three nodes per client, and I want to assign at most one of those nodes to some vehicle (at most one vehicle). If no vehicle is assigned to one of those three nodes, I apply a penalty as the client was not served. How would that be modeled in nextRoute?

thanks again.

[merschformann]

Hi @pchtsp,

Thank you for this question. We’ve had several other users ask about this as well. You are correct that AlternateStops are defined as a separate list of stops. The main motivation behind this feature was to model breaks in a route (hence the separation of stops from alternate stops).

In order to do this in nextroute, you would need to first pass in all the node options (per client) as stops in the input stops array (e.g. pickup_order_A, dropoff_order_A_option_1, dropoff_order_A_option_2, dropoff_order_A_option_3), and then you'd need to create a custom constraint and a custom objective.

The custom constraint would return a violation if more than 1 node option (for a given client) was placed in a route (i.e. if a route includes pickup_order_A and dropoff_order_A_option_1, then it may not include dropoff_order_A_option_2 or dropoff_order_A_option_3).
The custom objective would work the same way as the out-of-the-box unplanned objective; however, for stops which are part of a group of "optionals", you'd only want to count the unplanned cost once (not 3 times).

Keep performance in mind though when implementing custom constraints and/or objectives, as they get executed frequently. If our docs and/or the code in this repository (see out-of-the-box constraints/objectives) are not sufficient as an explanation, feel free to reach out. We are always happy to help out and improve. 😊

[pchtsp]

Thank you for the detailed response.

In a link about Custom Apps, I saw code for both Go and python.

But following the link to the custom constraints and custom objective you shared, I see that the changes need to be implemented in Go in order for the engine to use it. Which is reasonable.

Finally, it's not clear to me how I would be able to call the nextroute solver from python once I've modified the Go Model with the additional constraint + modified objective.

Or maybe if I modify the Go model with custom constraints/objective, I'm forced to call the go solver from a command line locally.

Thanks again.

[nilsbeck]

The solver is written in Go and when using Python to interact with the solver it works as a wrapper for the standard functionalities (correct me, if I'm wrong here, @merschformann).

So, indeed you need to implement the model in Go by implementing the functions as described earlier. You can then build the model as single file binary for the platform you want to use and call it from python as a command line tool, just like you suggested.

I hope this helps 😃

[merschformann]

Hey @pchtsp !

Sorry for dropping the ball on this. @nilsbeck is correct (thanks for already replying ❤ ).

It is not possible yet to do custom objectives or constraints in Python. This is something we would be interested in adding in the future, but so far didn't get a lot of asks for. Customizing in Go is certainly supported though. Let us know if you are interested and need assistance with it. 😊

[nilsbeck]

Hey @pchtsp,

I created a repository that handles your case here
For simplicity, I did not implement a special objective but that should be okay if all the customer have the same number of optional locations (of which you always want to assign exactly 1 or none).

You can read the README.md to learn how to build for different platforms or how to directly run it. If you have any questions, let me know.

[pchtsp]

hello @nilsbeck @merschformann, thanks to both for your answers!

@nilsbeck thanks a lot for the demo repo. I have to admit that last week I experimented with Go + reading the nextroute class documentation, so I could add a custom constraint and did not get too far: the class names+ descriptions are very cryptic: SolutionPlanStopsUnit, SolutionPlanUnit, SolutionStop, ModelPlanStopsUnit, etc.

Also, I suspect the docs need to be updated. In this page, you mention that the EstimateIsViolated method has two arguments (Move and Solution). In fact, from what I understand, Solution is now inside Move.

I took a quick look at the constraint.go file. I'm new to Go but I get that you're storing inside the constraint a map that returns if a client is being visited (clientsVisited), and you edit this map at two different times: UpdateConstraintStopData and UpdateConstraintSolutionData (my guess is when the solution changes?) with the help of stopsToClients map with which you initialized the constraint. And then you use that map in the EstimateIsViolated if one of the stops in the move is already visited.

I'm guessing if I wanted to make it a bit more clean (instead of mapping stops to clients via the name of the stop), I'd have to fill the custom_data property inside the stop? Then everything inside the constraint would stay the same.

[nilsbeck]

Yes, the description is indeed confusing. As far as I remember the EstimateIsViolated has always had only the move as an argument. And in the example below (all code in the docs is tested through integration tests btw) it is being used correctly.

what you say about the usage: yes, the UpdateConstraintStopData and UpdateConstraintSolutionData are in a way helper functions to create some book-keeping data which can then be accessed in the EstimateIsViolated. But they are not strictly necessary since you could do the calculations directly in the EstimateIsViolated itself. Depending on the type of evaluation this may drag performance though.

And yes, you could do what you suggest to separate data. I updated the repository for you. But it may still be useful to create a map stopToclient up front to not access the data "on the fly" in the constraint. There are some interfaces involved to read the data and at least for large problems this may reduce performance.

[merschformann]

Awesome @nilsbeck ! ❤
I will have a look at it later.