Closed BrunoRosendo closed 5 months ago
Architecture-wise, I think it's too much to do subclasses, so maybe I just use if statements for pickups
check this, but not sure if it helps https://arxiv.org/pdf/1606.01935.pdf
this paper describes the ride pooling problem. It's slightly different but might make sense for my application https://www.researchgate.net/publication/366190303_Modeling_routing_problems_in_QUBO_with_application_to_ride-hailing
consider this shit, might save a lot of variables. Instead of using a 3D matrix with vehicle index:
If successful, consider using the same technique for the diff cap model
this paper seems to have a nice formulation for pickup and deliveries https://core.ac.uk/download/pdf/19477982.pdf
This has 2 great formulations worth considering for same capacity:
The approach I'm following for same cap is explained in detail in this paper https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2266430
for no cap, try using the same approach without upper limit for aux vars, and try using a high constant (N?) instead of Q
for diff cap, I can follow a similar approach to without PD. Instead, I can adapt the pickup-delivery constraints and still use the 3D matrix for capacity constraints
CVRPSPD IS NOT the problem Im looking for, that's pickup and deliveries of homogeneous goods, not trips...
This is the failed model
from src.model.cplex.cvrp.ConstantCVRP import ConstantCVRP
class ConstantCVRPPD(ConstantCVRP):
"""
A class to represent a CPLEX math formulation of the CVRP model with pickups and deliveries
with all vehicles having the same capacity.
Attributes:
num_vehicles (int): Number of vehicles available.
capacity (int): Capacity of each vehicle.
trips (list): List of tuples, where each tuple contains the pickup and delivery locations, and the amount of customers for a trip.
depot (int): Index of the depot, which is the starting and ending point for each vehicle.
distance_matrix (list): Matrix with the distance between each pair of locations.
locations (list): List of coordinates for each location.
use_deliveries (bool): Whether the problem uses deliveries or not (always yes).
cplex (Model): CPLEX model for the CVRP
simplify (bool): Whether to simplify the problem by removing unnecessary variables.
"""
def create_vars(self):
"""
Create the variables for the CPLEX model.
"""
self.x = self.cplex.binary_var_matrix(
self.num_locations, self.num_locations, name="x"
)
# amount of load after visiting customer
self.p = self.cplex.integer_var_list(self.num_locations, name="l")
# amount of load that has to be delivered to location i and to all other following locations
self.d = self.cplex.integer_var_list(self.num_locations, name="d")
def create_constraints(self):
"""
Create the constraints for the CPLEX model.
"""
self.create_location_constraints()
self.create_vehicle_constraints()
self.create_pickup_delivery_constraints()
def create_pickup_delivery_constraints(self):
"""
Create the pickup and delivery constraints for the CPLEX model.
It also takes care of capacity constraints and subtour elimination.
"""
for i in range(self.num_locations):
for j in range(1, self.num_locations):
self.cplex.add_constraint(
self.d[i]
>= self.d[j]
+ self.get_location_delivery(i)
- self.capacity * (1 - self.x[i, j]),
)
self.cplex.add_constraint(self.d[i] >= self.get_location_delivery(i))
self.cplex.add_constraint(self.d[i] <= self.capacity)
for i in range(1, self.num_locations):
for j in range(1, self.num_locations):
self.cplex.add_constraint(
self.p[j]
>= self.p[i]
+ self.get_location_demand(j)
- self.capacity * (1 - self.x[i, j])
)
self.cplex.add_constraint(self.p[i] >= self.get_location_pickup(i))
self.cplex.add_constraint(self.p[i] <= self.capacity)
self.cplex.add_constraint(
self.p[i] >= self.d[i] + self.get_location_demand(i)
)
consider this shit, might save a lot of variables. Instead of using a 3D matrix with vehicle index:
* Mantain 2D for i and j (x) for the edges and add another 2D for i and k (y). That way, we have the order and the vehicle assignment * Constraint 1: yik = yjk for each pickup i->j (need to make some connection to xij too) * Constraint 2: ui < uj for each pickup i->j, to guarantee the right order
If successful, consider using the same technique for the diff cap model
let's try to use this one again. With the new variable list (y list does not contain depot): every trip (i, j) every k -> yik = yjk every i every j every k -> xij yik = xij yjk substitute all y0k for 1
This is not right, all vehicles would follow all routes Also, I still need the u constraint try to reduce constraints, but I don't think it's possible
I tried to implement and there's an open branch. However, it was not successful and I gave up because it would also have too many variables. I think I should instead focus on using quantum algorithms with the simplest problem and then explore RPP, as explained in #26
this seems tricky for the same cap model, since the vehicles are not tracked. Maybe it's enough to use a u for each vehicle?
I need to search for formulations, to try and not increase the number of variables too much