Explore RPP (no depot)

[BrunoRosendo]

this is for or tools https://developers.google.com/optimization/routing/routing_tasks#allowing_arbitrary_start_and_end_locations this is a paper for modelling it https://www.researchgate.net/publication/366190303_Modeling_routing_problems_in_QUBO_with_application_to_ride-hailing

[BrunoRosendo]

It is important to note this proposition:

The causality condition can be fulfilled by either incentivizing
all feasible solutions or penalizing all infeasible solutions, and whichever uses
fewer terms in the QUBO is sufficient.

This is part of the RPP formulation and I'll try to implement the incentives by adding (or subtracting) them from the objective function directly. Constraints would result in more slack variables

[BrunoRosendo]

I will try to formulate it removing the starting points of the vehicles (I could use the variables instead, without a fixed start). Alternatively, give all vehicles the same starting point with cost 0 to all nodes or remove the starting point from the objective function. This is differently from changing cvrp, because I still need to consider pickups and deliveries

[BrunoRosendo]

the article is god. It also proposes ways to reduce the number of variables in the last section

[BrunoRosendo]

I will try to formulate it removing the starting points of the vehicles (I could use the variables instead, without a fixed start). Alternatively, give all vehicles the same starting point with cost 0 to all nodes or remove the starting point from the objective function. This is differently from changing cvrp, because I still need to consider pickups and deliveries

What I'm doing is leaving the variable for the starting point and omitting the cost from the objective function, since it's simply 0. This way, there is no need for a specific starting location

[BrunoRosendo]

RPP is implemented and working without capacity. Next steps:

• Implement RPP with capacities (handled in the paper)
• Reduce variables according to the paper

Next issues:

• Implement RPP in google OR tools
• Re-formulation CVRP with the changes explained in this paper
• Refactor after the previous change
• Try to implement without a starting point, to reduce variables
• Simplify the formulations as much as possible