CVRP: Solver drops orders although there are vehicles available #4033
Unanswered
ammark100
asked this question in
Routing (and legacy CP) questions
Replies: 1 comment
-
Hmm. It seems to me that your statement “I’m using the time callback indexes” is very suspicious. The code:time_callback_index = routing.RegisterTransitCallback(time_callback_fn)Really is just for the routing internals. Do not use the index, use the actual function time_callback_fnJamesOn Dec 24, 2023, at 10:26, Muhammad Ammar Khan ***@***.***> wrote:
Hello,
I have approximately 12K orders and more than 280 vehicles having different capacities. I am encountering a problem where my solver drops almost 50% of the orders while I still have vehicles available.
For example: if I run a solver with 12K orders and 280 vehicles, it will assign only 6K orders to 100 vehicles and does not use rest of 180 vehicles and drops the other 6K orders. I want it to use a vehicle if it is available to assign the remaining orders.
I have few dimensions such as distance, time and capacity. Those seem to work fine. I have also disclosed the dimensions below.
for vehicle_id in range(data['numVehicles']):
vehicle_var_cost = data["vehicleVarCosts"][vehicle_id]
vehicle_fix_cost = data['vehicleFixCosts'][vehicle_id]
vehicle_avg_speed = self.vehicles[vehicle_id]["avgSpeed"]
vehicle_slack = self.vehicles[vehicle_id]["slack"]
cost_callback_fn = self.create_cost_callback(manager, distance_matrix, vehicle_var_cost)
time_callback_fn = self.create_time_callback(manager, distance_matrix, vehicle_avg_speed, vehicle_slack)
cost_callback_index = routing.RegisterTransitCallback(cost_callback_fn)
time_callback_index = routing.RegisterTransitCallback(time_callback_fn)
callback_indices.append(cost_callback_index)
time_callback_indices.append(time_callback_index)
routing.SetFixedCostOfVehicle(vehicle_fix_cost * 100, vehicle_id) #multiplying by 100 since I am multiplying other cost to 100 as well
routing.SetArcCostEvaluatorOfVehicle(cost_callback_index, int(vehicle_id))
dimension_name = 'Distance'.format(vehicle_id)
routing.AddDimension(
cost_callback_index,
0,
150 * 100 * self.vehicles[vehicle_id]["varCost"], # 150 (km) * 100 (factor) * var_cost
True,
dimension_name
). # A vehicle should not travel for more than 150km
and I am using time_callback_indices outside for loop to track that a vehicle should not exceed their shift time i.e. 12 hours
routing.AddDimensionWithVehicleTransits(
time_callback_indices,
15,
720, #12 hours in minutes
True,
'TimeCapacity'
)
time_dimension = routing.GetDimensionOrDie('TimeCapacity')
My create_cost_callback and create_time_callback is:
def create_cost_callback(self, manager, distance_matrix, var_cost):
def cost_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
travel_cost = (distance_matrix[from_node][to_node] * var_cost)
return travel_cost
return cost_callback
def create_time_callback(self, manager, distance_matrix, avg_speed, slack):
def time_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
time = (((distance_matrix[from_node][to_node]) / (avg_speed * 100)) * 60) + slack # avg_speed * 100 is km/hr speed (e.g. 15 km/hr), *60 is converting in minutes, +slack is a slack time
return int(time) #in minutes
return time_callback
and apart from that, there is capacity dimension as mentioned in the docs
# Add Capacity constraint.
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(
demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data['vehicleCapacities'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity')
My search parameters are:
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(self.plan_time_limit_in_sec)
NOTE: All the unassigned/dropped orders are with the distance limit but it is still not using all vehicles and keep the orders unassigned
—Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>
|
Beta Was this translation helpful? Give feedback.
0 replies
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
-
Hello,
I have approximately 12K orders and more than 280 vehicles having different capacities. I am encountering a problem where my solver drops almost 50% of the orders while I still have vehicles available.
For example: if I run a solver with 12K orders and 280 vehicles, it will assign only 6K orders to 100 vehicles and does not use rest of 180 vehicles and drops the other 6K orders. I want it to use a vehicle if it is available to assign the remaining orders.
I have few dimensions such as distance, time and capacity. Those seem to work fine. I have also disclosed the dimensions below.
and I am using
time_callback_indices
outside for loop to track that a vehicle should not exceed their shift time i.e.12 hours
My
create_cost_callback
andcreate_time_callback
is:and apart from that, there is capacity dimension as mentioned in the docs
My search parameters are:
NOTE: All the unassigned/dropped orders are with the distance limit but it is still not using all vehicles and keep the orders unassigned
Beta Was this translation helpful? Give feedback.
All reactions