I am trying to solve a CVRP using Google OR Tools. Below is the table I used after cleaning all the data using pandas. Link: https://i.stack.imgur.com/W0AXa.png (Customer Name and coordinates are hidden for privacy reasons)
The main issue I am facing is that the vehicle capacity constraint is ignored. The algorithm worked well on a small scale network (5 to 10 customers). However in this example where I have 48 customers, I am facing this issue.
Code:
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import scipy
#Distance Matrix
from scipy.spatial.distance import cdist
df_array = df_Demand2[["GeoCodeX", "GeoCodeY"]].to_numpy()
dist_mat = cdist(df_array, df_array)
#Google Code
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = dist_mat
data['demands'] = df_Demand2['Ton'].tolist()
data['vehicle_capacities'] = df_Veh['Payload'].tolist()
#vehicle capacities are : [4, 4, 4, 4, 4, 4, 6, 6, 6, 7, 7, 7, 7, 9, 9, 9, 9, 9, 10, 10, 10]
data['num_vehicles'] = len(df_Veh['Payload']) #equal to 21
data['depot'] = 0
return data
def print_solution(data, manager, routing, assignment):
"""Prints assignment on console."""
print(f'Objective: {assignment.ObjectiveValue()}')
# Display dropped nodes.
dropped_nodes = 'Dropped nodes:'
for node in range(routing.Size()):
if routing.IsStart(node) or routing.IsEnd(node):
continue
if assignment.Value(routing.NextVar(node)) == node:
dropped_nodes += ' {}'.format(manager.IndexToNode(node))
print(dropped_nodes)
# Display routes
total_distance = 0
total_load = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_distance = 0
route_load = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
route_load += data['demands'][node_index]
plan_output += ' {0} Load({1}) -> '.format(node_index, route_load)
previous_index = index
index = assignment.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += ' {0} Load({1})\n'.format(manager.IndexToNode(index),
route_load)
plan_output += 'Distance of the route: {}m\n'.format(route_distance)
plan_output += 'Load of the route: {}\n'.format(route_load)
print(plan_output)
total_distance += route_distance
total_load += route_load
print('Total Distance of all routes: {}m'.format(total_distance))
print('Total Load of all routes: {}'.format(total_load))
def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]
transit_callback_index =routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# 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['vehicle_capacities'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity')
# Allow to drop nodes.
penalty = 0
for node in range(1, len(data['distance_matrix'])):
routing.AddDisjunction([manager.NodeToIndex(node)], penalty)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(1)
# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if assignment:
print_solution(data, manager, routing, assignment)
if __name__ == '__main__':
main()
Output:
Route for vehicle 15:
0 Load(0.0) -> 14 Load(5.325117900000052) -> 2 Load(6.367904300000052) -> 1
Load(9.201462300000053) -> 0 Load(9.201462300000053)
Distance of the route: 0m
Load of the route: 9.201462300000053
Route for vehicle 16:
0 Load(0.0) -> 16 Load(9.0) -> 0 Load(9.0)
Distance of the route: 0m
Load of the route: 9.0
Route for vehicle 17:
0 Load(0.0) -> 21 Load(6.375019300000001) -> 9 Load(8.449955800000001) -> 6 Load(9.7910356)
-> 0 Load(9.7910356)
Distance of the route: 0m
Load of the route: 9.7910356
Route for vehicle 18:
0 Load(0.0) -> 23 Load(1.097403700000001) -> 22 Load(6.269400900000001) -> 19
Load(8.8132836) -> 15 Load(9.8132836) -> 11 Load(11.433122899999999) -> 0
Load(11.433122899999999)
Distance of the route: 0m
Load of the route: 11.433122899999999
Route for vehicle 19:
0 Load(0.0) -> 35 Load(5.312536499999981) -> 33 Load(6.44325249999998) -> 32
Load(9.338866299999982) -> 28 Load(12.298517599999983) -> 0 Load(12.298517599999983)
Distance of the route: 0m
Load of the route: 12.298517599999983
Route for vehicle 20:
0 Load(0.0) -> 38 Load(0.32752620000000016) -> 37 Load(0.6226590000000002) -> 36
Load(10.622659) -> 34 Load(11.2064377) -> 31 Load(11.4892377) -> 30 Load(11.779161) -> 29
Load(12.7502624) -> 27 Load(12.900136700000001) -> 26 Load(12.918321200000001) -> 25
Load(13.271298000000002) -> 24 Load(13.3594985) -> 20 Load(14.348135800000001) -> 18
Load(15.057466400000003) -> 13 Load(15.591705900000003) -> 12 Load(15.901503200000002) ->
10 Load(16.366829600000003) -> 8 Load(16.824547900000002) -> 7 Load(17.061237800000004) ->
5 Load(17.190268900000003) -> 4 Load(17.355464500000004) -> 3 Load(17.484708400000002) -> 0
Load(17.484708400000002)
Distance of the route: 0m
Load of the route: 17.484708400000002
Vehicle 15 and 17's capacity is 9 Tons. Vehicle 18,19 and 20's capacity is 10 Tons. I cannot understand why would the load of the route exceed vehicle's capacity.
Any advice?