Expanding Algorithm to More Complex Scenarios

[JY00002]

I would like to express my sincere appreciation for the open-source project that you have made available. The work you have done is not only impressive but also incredibly valuable to the community.
I have found it to be a great tool for many robotic systems problems. However, I am currently facing a challenge where I need to extend the algorithm to more complex scenarios. Specifically, I am looking to add new base capacities and integrate the algorithm with different types of robotic systems.
Here are the details of my inquiry:
1.Adding New Base Capacities: I would like to know if there are any existing mechanisms or modules within the project that can be used to add new base capacities. If not, what would be the recommended approach to implement such features?
2.Integration with Robotic Systems: As I plan to integrate the algorithm with various robotic systems, I am curious about the level of customization and flexibility the algorithm offers in this regard. Are there any considerations or specific requirements I should be aware of when integrating with different robotic platforms?
Thank you once again for your outstanding work.

[fedebotu]

Hi there, I'm glad you appreciate our work :)

1. What do you mean by adding base capacities? Do you mean, for instance, how to model different capacities for each vehicle?
2. This pretty much depends on your case and constraints, so it is hard to know. Could you provide an example?

[JY00002]

Hi there, I'm glad you appreciate our work :)

1. What do you mean by adding base capacities? Do you mean, for instance, how to model different capacities for each vehicle?
2. This pretty much depends on your case and constraints, so it is hard to know. Could you provide an example?

I'm very sorry for not describing it accurately enough, what I meant was: the VRP problem is defined in the article coaxed as a fleet of vehicles (each with capacity Q) departing from a parking lot, serving each customer once, and then returning, with the goal of minimizing the total travel cost.RouteFinder considers a collection of VRP variants that each consist of one or more attributes, resulting in a rich set of routing problems with practical relevance.If our problem is that, for example, a fleet of vehicles has three types, each type of vehicle provides services A, B, and C. For each customer, it is necessary to receive the services in the order of A, B, and C, and then the vehicle returns, with the aim of minimizing the total travel cost. If this is the problem, then we should need to add a new attribute, how to implement it, can it be done under RouteFinder framework?

[fedebotu]

Interesting topic! Are you referring by any chance to the Skill-VRP? If so, @ngastzepeda is working on this right now :)

[ngastzepeda]

Hi @JY00002 ,
right now in the public rl4co repositors we only have a very basic version of the skill vrp implemented which models vehicles with different skill levels, not skill types. An additional difficulty for your use case are the precedence constraints that you mention, which we also have not implemented yet. We have an idea how to do it, but right now this functionality is not provided in rl4co. Depending on how quickly you need it, we could make it happen - or you would need to find another framework to use.

If you have further questions or would like to contribute to the code, feel free to reach out to me via email!

[JY00002]

@fedebotu @ngastzepeda Thank you very much for your quick and professional response, which has allowed me to experience the charm of the open-source community, it's really great! I am very much looking forward to your work on the SVRP！

[ngastzepeda]

We are not aware of any other learning-based frameworks that solve this problem yet, but if you are not set on learning-based methods and just want to solve a specific problem, you could have a look at PyVRP. It allows for modelling client groups and vehicles via profiles, but I don't know if you can also model the precedence constraints you mention.

[JY00002]

We are not aware of any other learning-based frameworks that solve this problem yet, but if you are not set on learning-based methods and just want to solve a specific problem, you could have a look at PyVRP. It allows for modelling client groups and vehicles via profiles, but I don't know if you can also model the precedence constraints you mention.

I have an idea that I'm not sure is feasible, which is to use a mask mechanism for priority constraints. Specifically, for example, when a vehicle with capability B is selecting service targets, it could mask nodes that have not yet received service A, as well as nodes that have already received services B or C. Do you think this approach is applicable to the RouteFinder architecture?

[ngastzepeda]

Yes, I was thinking along those lines, but the precedence constraints themselves would also need to be saved in the TensorDict. For your case the precedence may always be A->B->C, which is easier, because all would be of the same shape and even the same values. But to do this in a general way (i.e. one customer could have A->C, another B->A->D, etc.) we should think a bit more about how to do this in a general, but clean way.

[JY00002]

I am very much looking forward to your solution.

[yjpark1]

Hi everyone,

Thank you for your excellent work on routefinder. After reviewing LKH-3 (http://webhotel4.ruc.dk/~keld/research/LKH-3/), I was wondering if there are any plans to extend routefinder so that it can eventually cover the diverse range of problem types supported by LKH. In addition, is there any roadmap for implementing a more flexible interface that would allow users to input a wide variety of constraints? Such an interface could enable routefinder to address even more complex scenarios, possibly including those not originally envisioned.

As this topic appears to be directly related to our ongoing discussion on expanding the capabilities of RL4CO, I thought it would be appropriate to raise it here.

I would appreciate any insight or updates regarding these potential enhancements.

[fedebotu]

@yjpark1 thanks for your interest :)

Indeed, RouteFinder is just one of the first steps in foundation models for VRPs, and there is much more research that can be done to make such models more interesting in terms of the number of variants solved, their practicality, and their performance.

In terms of modularity, I agree that while right now we have any number of constraints in the same batch, new constraints need to be implemented manually, which is not trivial 👀

This said, we are planning a follow-up in the next couple of months to expand significantly the number of variants at least in the (C)VRP variants ;)