'Problem dropping specific packages on specific points using or-tools
I am currently working on a project that needs to optimize the travel path of a certain number of vehicles. Now, at first, I can consider all my vehicles (only one, at first) starting from the same spot. However, I need to make the following travels:
data['pickups_deliveries'] = [
[1, 2],
[3, 4],
[2, 5],
]
Note that node 2 is both a pickup point and a delivery point.
While doing this travels, I need to:
- Pick something on 1 --> to drop it on 2. (the object I pick in 1, must go to 2. Can't go anywhere else. For example, it may be a machine that only works only on a factory located on 2)
- Pick something on 3 --> drop it on 4. Same here...
- Pick something on 2(6) --> drop it on 5. Same here. What I pick in 2/6 is only useful on 5.
data['pickups_deliveries'] = [
[1, 2], #1,2
[3, 4], #3,4
[6, 5], #5,6
]
In order to make this happen, I understand that node 2 has to be duplicated. Thus, I made a node 6 and add an extra column and an extra row to the distance matrix (element [6,2]=[2,6]=0, as it is the same node.)
The base is at node 0. Code below:
"""Capacity Vehicles Routing Problem (CVRP)."""
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = [
[0 , 2200, 4600, 7000, 2800, 4600, 4600],
[2200, 0 , 5700, 6700, 5000, 3800, 5700],
[4600, 5700, 0 , 3500, 5500, 3400, 0 ],
[7000, 6700, 3500, 0 , 8500, 1800, 3500],
[2800, 5000, 5500, 8500, 0 , 6300, 5500],
[4600, 3800, 3400, 1800, 6300, 0, 3400],
[4600, 5700, 0, 3500, 5500, 3400, 0],
]
data['pickups_deliveries'] = [
[1, 2], #1,2
[3, 4], #3,4
[6, 5], #5,6
]
data['demands'] = [0, # departs empty
1, # load in 1
-1, # unload in 2
1, # load in 3
-1, # unload 4
1, # load in 6 (duplicate of 2)
-1] # unload in 5
data['vehicle_capacities'] = [1]
data['num_vehicles'] = 1
data['depot'] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
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 = solution.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')
# 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.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
if __name__ == '__main__':
main()
The answer I am getting is:
Objective: 27400 Route for vehicle 0: 0 Load(0) -> 1 Load(1) -> 2 Load(0) -> 3 Load(1) -> 6 Load(0) -> 5 Load(1) -> 4 Load(0) -> 0 Load(0) Distance of the route: 27400m Load of the route: 0
- So, first travel is OK. What I picked on 1 was left on 2.
- Then pick something on 3 but unloaded on 6 (also 2!). This package was needed at 4!.
- Then load at 5 (there was no package here to be loaded) and unload at the base (there was nothing to deliver here).
Can anyone point me in the right direction? What variable am I missing? What is going wrong? Is my data["demands"] ok?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
