Mizux/cvrptw.py

## cvrptw.py
#!/usr/bin/env python3
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data['time_matrix'] = [
        [0, 6, 9, 8, 7, 3, 6, 2, 3, 2],
        [6, 0, 8, 3, 2, 6, 8, 4, 8, 8],
        [9, 8, 0, 11, 10, 6, 3, 9, 5, 8],
        [8, 3, 11, 0, 1, 7, 10, 6, 10, 10],
        [7, 2, 10, 1, 0, 6, 9, 4, 8, 9],
        [3, 6, 6, 7, 6, 0, 2, 3, 2, 2],
        [6, 8, 3, 10, 9, 2, 0, 6, 2, 5],
        [2, 4, 9, 6, 4, 3, 6, 0, 4, 4],
        [3, 8, 5, 10, 8, 2, 2, 4, 0, 3],
        [2, 8, 8, 10, 9, 2, 5, 4, 3, 0],

    ]
    data['time_windows'] = [
        (0, 5),  # depot
        (7, 12),  # 1
        (10, 15),  # 2
        (16, 18),  # 3
        (10, 13),  # 4
        (0, 5),  # 5
        (5, 10),  # 6
        (0, 4),  # 7
        (5, 10),  # 8
        (0, 3),  # 9

    ]

    data['distance_matrix'] = [
        [
            0, 548, 776, 696, 582, 274, 502, 194, 308, 194],
        [
            548, 0, 684, 308, 194, 502, 730, 354, 696, 742
        ],
        [
            776, 684, 0, 992, 878, 502, 274, 810, 468, 742
        ],
        [
            696, 308, 992, 0, 114, 650, 878, 502, 844, 890
        ],
        [
            582, 194, 878, 114, 0, 536, 764, 388, 730, 776
        ],
        [
            274, 502, 502, 650, 536, 0, 228, 308, 194, 240
        ],
        [
            502, 730, 274, 878, 764, 228, 0, 536, 194, 468
        ],
        [
            194, 354, 810, 502, 388, 308, 536, 0, 342, 388
        ],
        [
            308, 696, 468, 844, 730, 194, 194, 342, 0, 274
        ],
        [
            194, 742, 742, 890, 776, 240, 468, 388, 274, 0
        ],

    ]

    data['pickups_deliveries'] = [
        [1, 3],
        [2, 6],
        [4, 7],
        [5, 8],
     ]

    data['num_vehicles'] = 4
    data['vehicle_capacities'] = [15, 15, 15, 15]
    # data['demands'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1]
    data['demands'] = [0, 1, 1, -1, 4, 2, -1, -4, -2, 0]
    data['depot'] = 0
    assert data['num_vehicles'] == len(data['vehicle_capacities'])
    assert len(data['time_matrix']) == len(data['distance_matrix'])
    assert len(data['time_matrix']) == len(data['time_windows'])
    assert len(data['time_matrix']) == len(data['demands'])
    return data


def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    # Display dropped nodes.
    dropped_nodes = 'Dropped nodes:'
    for node in range(routing.Size()):
        if routing.IsStart(node) or routing.IsEnd(node):
            continue
        if solution.Value(routing.NextVar(node)) == node:
            dropped_nodes += ' {}'.format(manager.IndexToNode(node))
    print(dropped_nodes)
    # Print routes
    time_dimension = routing.GetDimensionOrDie('Time')
    distance_dimension = routing.GetDimensionOrDie('Distance')
    capacity_dimension = routing.GetDimensionOrDie('Capacity')
    total_time = 0
    total_distance = 0
    total_load=0
    for vehicle_id in range(manager.GetNumberOfVehicles()):
        index = routing.Start(vehicle_id)
        plan_output = f'Route for vehicle {vehicle_id}:\n'
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            time_var = time_dimension.CumulVar(index)
            distance_var = distance_dimension.CumulVar(index)
            capacity_var = capacity_dimension.CumulVar(index)
            plan_output += '{0} Time({1},{2}) Distance:{3} Load:{4}  -> '.format(
                node_index,
                solution.Min(time_var), solution.Max(time_var),
                solution.Value(distance_var),
                solution.Value(capacity_var))
            index = solution.Value(routing.NextVar(index))
        node_index = manager.IndexToNode(index)
        time_var = time_dimension.CumulVar(index)
        distance_var = distance_dimension.CumulVar(index)
        capacity_var = capacity_dimension.CumulVar(index)
        plan_output += '{0} Time({1},{2}) Distance:{3} Load:{4})\n'.format(
            manager.IndexToNode(index),
            solution.Min(time_var), solution.Max(time_var),
            solution.Value(distance_var),
            solution.Value(capacity_var))
        plan_output += 'Time of the route: {}min\n'.format(solution.Min(time_var))
        plan_output += 'Distance of the route: {}m\n'.format(solution.Value(distance_var))
        plan_output += 'Load of the route: {}\n'.format(solution.Value(capacity_var))
        print(plan_output)
        total_time += solution.Min(time_var)
        total_distance += solution.Value(distance_var)
        total_load += solution.Value(capacity_var)
    print('Total time of all routes: {}min'.format(total_time))
    print('Total distance of all routes: {}m'.format(total_distance))
    print('Total load of all routes: {}'.format(total_load))


def main():
    """Solve the VRP with time windows."""
    # 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)

    # Allow to drop nodes.
    penalty = 1_000_000
    for node in range(1, len(data['distance_matrix'])):
        routing.AddDisjunction([manager.NodeToIndex(node)], penalty)

    # 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]

    distance_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(distance_callback_index)

    # Add Distance constraint.
    dimension_name = 'Distance'
    routing.AddDimension(
        distance_callback_index,
        0,  # no slack
        10_000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # 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')

    # Add Time Windows constraint.
    def time_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['time_matrix'][from_node][to_node]

    time_callback_index = routing.RegisterTransitCallback(time_callback)

    time = 'Time'
    routing.AddDimension(
        time_callback_index,
        100,  # allow waiting time
        100,  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        time)
    time_dimension = routing.GetDimensionOrDie(time)
    # Add time window constraints for each location except depot.
    for location_idx, time_window in enumerate(data['time_windows']):
        if location_idx == data['depot']:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    # Add time window constraints for each vehicle start node.
    depot_idx = data['depot']
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        time_dimension.CumulVar(index).SetRange(
            data['time_windows'][depot_idx][0],
            data['time_windows'][depot_idx][1])

    # Instantiate route start and end times to produce feasible times.
    for i in range(data['num_vehicles']):
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.End(i)))

    # Define Transportation Requests.
    for request in data['pickups_deliveries']:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        routing.AddPickupAndDelivery(pickup_index, delivery_index)
        routing.solver().Add(
            routing.VehicleVar(pickup_index) == routing.VehicleVar(
                delivery_index))
        routing.solver().Add(
            distance_dimension.CumulVar(pickup_index) <=
            distance_dimension.CumulVar(delivery_index))

    # 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.log_search = True
    search_parameters.time_limit.FromSeconds(5)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(manager, routing, solution)
    else:
        print('no solution found')

if __name__ == '__main__':
    main()

## zz.readme.md

      
    Raw
  

              zz.readme.md
            
          
    Potential output:
./cvrptw.py
Objective: 4157688
Dropped nodes: 2 4 6 7
Route for vehicle 0:
0 Time(0,0) Distance:0 Load:0  -> 0 Time(0,0) Distance:0 Load:0)
Time of the route: 0min
Distance of the route: 0m
Load of the route: 0

Route for vehicle 1:
0 Time(0,0) Distance:0 Load:0  -> 0 Time(0,0) Distance:0 Load:0)
Time of the route: 0min
Distance of the route: 0m
Load of the route: 0

Route for vehicle 2:
0 Time(0,0) Distance:0 Load:0  -> 1 Time(7,12) Distance:548 Load:0  -> 3 Time(16,16) Distance:856 Load:1  -> 0 Time(24,24) Distance:1552 Load:1)
Time of the route: 24min
Distance of the route: 1552m
Load of the route: 1

Route for vehicle 3:
0 Time(0,0) Distance:0 Load:0  -> 9 Time(2,2) Distance:194 Load:0  -> 5 Time(4,4) Distance:434 Load:0  -> 8 Time(6,6) Distance:628 Load:2  -> 0 Time(9,9) Distance:936 Load:2)
Time of the route: 9min
Distance of the route: 936m
Load of the route: 2

Total time of all routes: 33min
Total distance of all routes: 2488m
Total load of all routes: 3
	#!/usr/bin/env python3
	from ortools.constraint_solver import routing_enums_pb2
	from ortools.constraint_solver import pywrapcp

	def create_data_model():
	"""Stores the data for the problem."""
	data = {}
	data['time_matrix'] = [
	[0, 6, 9, 8, 7, 3, 6, 2, 3, 2],
	[6, 0, 8, 3, 2, 6, 8, 4, 8, 8],
	[9, 8, 0, 11, 10, 6, 3, 9, 5, 8],
	[8, 3, 11, 0, 1, 7, 10, 6, 10, 10],
	[7, 2, 10, 1, 0, 6, 9, 4, 8, 9],
	[3, 6, 6, 7, 6, 0, 2, 3, 2, 2],
	[6, 8, 3, 10, 9, 2, 0, 6, 2, 5],
	[2, 4, 9, 6, 4, 3, 6, 0, 4, 4],
	[3, 8, 5, 10, 8, 2, 2, 4, 0, 3],
	[2, 8, 8, 10, 9, 2, 5, 4, 3, 0],

	]
	data['time_windows'] = [
	(0, 5), # depot
	(7, 12), # 1
	(10, 15), # 2
	(16, 18), # 3
	(10, 13), # 4
	(0, 5), # 5
	(5, 10), # 6
	(0, 4), # 7
	(5, 10), # 8
	(0, 3), # 9

	]

	data['distance_matrix'] = [
	[
	0, 548, 776, 696, 582, 274, 502, 194, 308, 194],
	[
	548, 0, 684, 308, 194, 502, 730, 354, 696, 742
	],
	[
	776, 684, 0, 992, 878, 502, 274, 810, 468, 742
	],
	[
	696, 308, 992, 0, 114, 650, 878, 502, 844, 890
	],
	[
	582, 194, 878, 114, 0, 536, 764, 388, 730, 776
	],
	[
	274, 502, 502, 650, 536, 0, 228, 308, 194, 240
	],
	[
	502, 730, 274, 878, 764, 228, 0, 536, 194, 468
	],
	[
	194, 354, 810, 502, 388, 308, 536, 0, 342, 388
	],
	[
	308, 696, 468, 844, 730, 194, 194, 342, 0, 274
	],
	[
	194, 742, 742, 890, 776, 240, 468, 388, 274, 0
	],

	]

	data['pickups_deliveries'] = [
	[1, 3],
	[2, 6],
	[4, 7],
	[5, 8],
	]

	data['num_vehicles'] = 4
	data['vehicle_capacities'] = [15, 15, 15, 15]
	# data['demands'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1]
	data['demands'] = [0, 1, 1, -1, 4, 2, -1, -4, -2, 0]
	data['depot'] = 0
	assert data['num_vehicles'] == len(data['vehicle_capacities'])
	assert len(data['time_matrix']) == len(data['distance_matrix'])
	assert len(data['time_matrix']) == len(data['time_windows'])
	assert len(data['time_matrix']) == len(data['demands'])
	return data


	def print_solution(manager, routing, solution):
	"""Prints solution on console."""
	print(f'Objective: {solution.ObjectiveValue()}')
	# Display dropped nodes.
	dropped_nodes = 'Dropped nodes:'
	for node in range(routing.Size()):
	if routing.IsStart(node) or routing.IsEnd(node):
	continue
	if solution.Value(routing.NextVar(node)) == node:
	dropped_nodes += ' {}'.format(manager.IndexToNode(node))
	print(dropped_nodes)
	# Print routes
	time_dimension = routing.GetDimensionOrDie('Time')
	distance_dimension = routing.GetDimensionOrDie('Distance')
	capacity_dimension = routing.GetDimensionOrDie('Capacity')
	total_time = 0
	total_distance = 0
	total_load=0
	for vehicle_id in range(manager.GetNumberOfVehicles()):
	index = routing.Start(vehicle_id)
	plan_output = f'Route for vehicle {vehicle_id}:\n'
	while not routing.IsEnd(index):
	node_index = manager.IndexToNode(index)
	time_var = time_dimension.CumulVar(index)
	distance_var = distance_dimension.CumulVar(index)
	capacity_var = capacity_dimension.CumulVar(index)
	plan_output += '{0} Time({1},{2}) Distance:{3} Load:{4} -> '.format(
	node_index,
	solution.Min(time_var), solution.Max(time_var),
	solution.Value(distance_var),
	solution.Value(capacity_var))
	index = solution.Value(routing.NextVar(index))
	node_index = manager.IndexToNode(index)
	time_var = time_dimension.CumulVar(index)
	distance_var = distance_dimension.CumulVar(index)
	capacity_var = capacity_dimension.CumulVar(index)
	plan_output += '{0} Time({1},{2}) Distance:{3} Load:{4})\n'.format(
	manager.IndexToNode(index),
	solution.Min(time_var), solution.Max(time_var),
	solution.Value(distance_var),
	solution.Value(capacity_var))
	plan_output += 'Time of the route: {}min\n'.format(solution.Min(time_var))
	plan_output += 'Distance of the route: {}m\n'.format(solution.Value(distance_var))
	plan_output += 'Load of the route: {}\n'.format(solution.Value(capacity_var))
	print(plan_output)
	total_time += solution.Min(time_var)
	total_distance += solution.Value(distance_var)
	total_load += solution.Value(capacity_var)
	print('Total time of all routes: {}min'.format(total_time))
	print('Total distance of all routes: {}m'.format(total_distance))
	print('Total load of all routes: {}'.format(total_load))


	def main():
	"""Solve the VRP with time windows."""
	# 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)

	# Allow to drop nodes.
	penalty = 1_000_000
	for node in range(1, len(data['distance_matrix'])):
	routing.AddDisjunction([manager.NodeToIndex(node)], penalty)

	# 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]

	distance_callback_index = routing.RegisterTransitCallback(distance_callback)

	# Define cost of each arc.
	routing.SetArcCostEvaluatorOfAllVehicles(distance_callback_index)

	# Add Distance constraint.
	dimension_name = 'Distance'
	routing.AddDimension(
	distance_callback_index,
	0, # no slack
	10_000, # vehicle maximum travel distance
	True, # start cumul to zero
	dimension_name)
	distance_dimension = routing.GetDimensionOrDie(dimension_name)
	distance_dimension.SetGlobalSpanCostCoefficient(100)

	# 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')

	# Add Time Windows constraint.
	def time_callback(from_index, to_index):
	"""Returns the travel time between the two nodes."""
	# Convert from routing variable Index to time matrix NodeIndex.
	from_node = manager.IndexToNode(from_index)
	to_node = manager.IndexToNode(to_index)
	return data['time_matrix'][from_node][to_node]

	time_callback_index = routing.RegisterTransitCallback(time_callback)

	time = 'Time'
	routing.AddDimension(
	time_callback_index,
	100, # allow waiting time
	100, # maximum time per vehicle
	False, # Don't force start cumul to zero.
	time)
	time_dimension = routing.GetDimensionOrDie(time)
	# Add time window constraints for each location except depot.
	for location_idx, time_window in enumerate(data['time_windows']):
	if location_idx == data['depot']:
	continue
	index = manager.NodeToIndex(location_idx)
	time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
	# Add time window constraints for each vehicle start node.
	depot_idx = data['depot']
	for vehicle_id in range(data['num_vehicles']):
	index = routing.Start(vehicle_id)
	time_dimension.CumulVar(index).SetRange(
	data['time_windows'][depot_idx][0],
	data['time_windows'][depot_idx][1])

	# Instantiate route start and end times to produce feasible times.
	for i in range(data['num_vehicles']):
	routing.AddVariableMinimizedByFinalizer(
	time_dimension.CumulVar(routing.Start(i)))
	routing.AddVariableMinimizedByFinalizer(
	time_dimension.CumulVar(routing.End(i)))

	# Define Transportation Requests.
	for request in data['pickups_deliveries']:
	pickup_index = manager.NodeToIndex(request[0])
	delivery_index = manager.NodeToIndex(request[1])
	routing.AddPickupAndDelivery(pickup_index, delivery_index)
	routing.solver().Add(
	routing.VehicleVar(pickup_index) == routing.VehicleVar(
	delivery_index))
	routing.solver().Add(
	distance_dimension.CumulVar(pickup_index) <=
	distance_dimension.CumulVar(delivery_index))

	# 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.log_search = True
	search_parameters.time_limit.FromSeconds(5)

	# Solve the problem.
	solution = routing.SolveWithParameters(search_parameters)

	# Print solution on console.
	if solution:
	print_solution(manager, routing, solution)
	else:
	print('no solution found')

	if __name__ == '__main__':
	main()