lperron
commented
4 years ago This is most likely a modeling problem. Not an issue of the solver. Please use the mailing list. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00
Le lun. 8 juin 2020 à 03:30, CTL notifications@github.com a écrit :
What version of OR-tools and what language are you using? Version: 7.6.7691 Language: Python
Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi) Routing Solver What operating system (Linux, Windows, ...) and version? mac What did you do? i use the offical code, but i change the distance matrix & demands matrix & vehicle_capacities, but it run for a long time without result.. this is my code
"""Capacited Vehicles Routing Problem (CVRP).""" from future import print_function from ortools.constraint_solver import pywrapcpfrom ortools.constraint_solver import routing_enums_pb2
def create_data_model(): """Stores the data for the problem.""" data = {} data['distance_matrix'] = [ [0, 1098, 1091, 804, 7801, 1736, 8798, 9194, 8698, 1214, 3920, 4309, 3903, 1203, 3869, 2168, 3791, 3907, 7374, 6622, 3813, 3903, 7099, 4309, 3903, 1203, 3869, 2168, 3791, 3907, 7374, 6622], [1098, 0, 7, 294, 7376, 918, 8936, 8884, 8671, 1162, 3211, 3611, 3181, 1173, 3147, 1107, 3069, 3185, 6456, 5354, 3091, 3181, 7305, 3611, 3181, 1173, 3147, 1107, 3069, 3185, 6456, 5354], [1091, 7, 0, 287, 7369, 911, 8929, 8877, 8664, 1155, 3204, 3604, 3174, 1166, 3140, 1100, 3062, 3178, 6449, 5347, 3084, 3174, 7298, 3604, 3174, 1166, 3140, 1100, 3062, 3178, 6449, 5347], [804, 294, 287, 0, 7552, 1094, 8861, 9060, 8847, 1338, 3387, 3787, 3357, 1349, 3323, 1283, 3245, 3361, 6632, 5530, 3267, 3357, 7057, 3787, 3357, 1349, 3323, 1283, 3245, 3361, 6632, 5530], [7801, 7376, 7369, 7552, 0, 6823, 2226, 1986, 1407, 7022, 6968, 7207, 7836, 7033, 7802, 6634, 7724, 7840, 9314, 5312, 7642, 7836, 1888, 7207, 7836, 7033, 7802, 6634, 7724, 7840, 9314, 5312], [1736, 918, 911, 1094, 6823, 0, 8292, 8240, 8027, 522, 2329, 2729, 2299, 533, 2265, 225, 2187, 2303, 5574, 4472, 2209, 2299, 7049, 2729, 2299, 533, 2265, 225, 2187, 2303, 5574, 4472], [8798, 8936, 8929, 8861, 2226, 8292, 0, 1157, 1391, 8617, 8563, 8802, 9431, 8628, 9397, 8229, 9319, 9435, 10909, 6907, 9237, 9431, 2719, 8802, 9431, 8628, 9397, 8229, 9319, 9435, 10909, 6907], [9194, 8884, 8877, 9060, 1986, 8240, 1157, 0, 900, 8562, 8508, 8747, 9376, 8573, 9342, 8174, 9264, 9380, 10396, 6852, 9182, 9376, 3115, 8747, 9376, 8573, 9342, 8174, 9264, 9380, 10396, 6852], [8698, 8671, 8664, 8847, 1407, 8027, 1391, 900, 0, 8043, 7989, 8228, 8857, 8054, 8823, 7655, 8745, 8861, 9476, 6030, 8663, 8857, 2619, 8228, 8857, 8054, 8823, 7655, 8745, 8861, 9476, 6030], [1214, 1162, 1155, 1338, 7022, 522, 8617, 8562, 8043, 0, 3151, 3551, 3121, 11, 3087, 1047, 3009, 3125, 6396, 5294, 3031, 3121, 7414, 3551, 3121, 11, 3087, 1047, 3009, 3125, 6396, 5294], [3920, 3211, 3204, 3387, 6968, 2329, 8563, 8508, 7989, 3151, 0, 500, 1498, 2717, 1464, 2509, 1386, 1502, 3871, 2796, 1420, 1498, 7454, 500, 1498, 2717, 1464, 2509, 1386, 1502, 3871, 2796], [4309, 3611, 3604, 3787, 7207, 2729, 8802, 8747, 8228, 3551, 500, 0, 1887, 3106, 1853, 2898, 1775, 1891, 4103, 2927, 1809, 1887, 7678, 1, 1887, 3106, 1853, 2898, 1775, 1891, 4103, 2927], [3903, 3181, 3174, 3357, 7836, 2299, 9431, 9376, 8857, 3121, 1498, 1887, 0, 2700, 34, 2634, 112, 4, 4219, 4320, 194, 1, 8548, 1911, 1, 2700, 34, 2634, 112, 4, 4219, 4320], [1203, 1173, 1166, 1349, 7033, 533, 8628, 8573, 8054, 11, 2717, 3106, 2700, 0, 3076, 1036, 2998, 3114, 6385, 5283, 3020, 3110, 7403, 3540, 3110, 1, 3076, 1036, 2998, 3114, 6385, 5283], [3869, 3147, 3140, 3323, 7802, 2265, 9397, 9342, 8823, 3087, 1464, 1853, 34, 3076, 0, 2600, 79, 38, 4185, 4286, 160, 34, 8514, 1877, 34, 2666, 1, 2600, 79, 38, 4185, 4286], [2168, 1107, 1100, 1283, 6634, 225, 8229, 8174, 7655, 1047, 2509, 2898, 2634, 1036, 2600, 0, 2175, 2291, 5562, 4293, 2197, 2287, 6834, 2717, 2287, 965, 2253, 213, 2175, 2291, 5562, 4293], [3791, 3069, 3062, 3245, 7724, 2187, 9319, 9264, 8745, 3009, 1386, 1775, 112, 2998, 79, 2175, 0, 116, 4107, 4208, 82, 112, 8436, 1799, 112, 2588, 79, 2522, 1, 116, 4107, 4208], [3907, 3185, 3178, 3361, 7840, 2303, 9435, 9380, 8861, 3125, 1502, 1891, 4, 3114, 38, 2291, 116, 0, 4223, 4324, 198, 4, 8552, 1915, 4, 2704, 38, 2638, 116, 1, 4223, 4324], [7374, 6456, 6449, 6632, 9314, 5574, 10909, 10396, 9476, 6396, 3871, 4103, 4219, 6385, 4185, 5562, 4107, 4223, 0, 4425, 4231, 4425, 10636, 4314, 4425, 6171, 4391, 6105, 4313, 4429, 1, 4425], [6622, 5354, 5347, 5530, 5312, 4472, 6907, 6852, 6030, 5294, 2796, 2927, 4320, 5283, 4286, 4293, 4208, 4324, 4425, 0, 4747, 5183, 6159, 3433, 5183, 5419, 5193, 4992, 4829, 5187, 4869, 1], [3813, 3091, 3084, 3267, 7642, 2209, 9237, 9182, 8663, 3031, 1420, 1809, 194, 3020, 160, 2197, 82, 198, 4231, 4747, 0, 194, 8458, 1823, 194, 2610, 160, 2544, 82, 198, 4025, 4126], [3903, 3181, 3174, 3357, 7836, 2299, 9431, 9376, 8857, 3121, 1498, 1887, 1, 3110, 34, 2287, 112, 4, 4425, 5183, 194, 0, 8548, 1911, 1, 2700, 34, 2634, 112, 4, 4219, 4320], [7099, 7305, 7298, 7057, 1888, 7049, 2719, 3115, 2619, 7414, 7454, 7678, 8548, 7403, 8514, 6834, 8436, 8552, 10636, 6159, 8458, 8548, 0, 7529, 8158, 7019, 8124, 6589, 8046, 8162, 9636, 5634], [4309, 3611, 3604, 3787, 7207, 2729, 8802, 8747, 8228, 3551, 500, 1, 1911, 3540, 1877, 2717, 1799, 1915, 4314, 3433, 1823, 1911, 7529, 0, 1887, 3540, 1853, 2898, 1775, 1891, 4103, 2927], [3903, 3181, 3174, 3357, 7836, 2299, 9431, 9376, 8857, 3121, 1498, 1887, 1, 3110, 34, 2287, 112, 4, 4425, 5183, 194, 1, 8158, 1887, 0, 2700, 34, 2634, 112, 4, 4219, 4320], [1203, 1173, 1166, 1349, 7033, 533, 8628, 8573, 8054, 11, 2717, 3106, 2700, 1, 2666, 965, 2588, 2704, 6171, 5419, 2610, 2700, 7019, 3540, 2700, 0, 3076, 1036, 2998, 3114, 6385, 5283], [3869, 3147, 3140, 3323, 7802, 2265, 9397, 9342, 8823, 3087, 1464, 1853, 34, 3076, 1, 2253, 79, 38, 4391, 5193, 160, 34, 8124, 1853, 34, 3076, 0, 2600, 79, 38, 4185, 4286], [2168, 1107, 1100, 1283, 6634, 225, 8229, 8174, 7655, 1047, 2509, 2898, 2634, 1036, 2600, 213, 2522, 2638, 6105, 4992, 2544, 2634, 6589, 2898, 2634, 1036, 2600, 0, 2175, 2291, 5562, 4293], [3791, 3069, 3062, 3245, 7724, 2187, 9319, 9264, 8745, 3009, 1386, 1775, 112, 2998, 79, 2175, 1, 116, 4313, 4829, 82, 112, 8046, 1775, 112, 2998, 79, 2175, 0, 116, 4107, 4208], [3907, 3185, 3178, 3361, 7840, 2303, 9435, 9380, 8861, 3125, 1502, 1891, 4, 3114, 38, 2291, 116, 1, 4429, 5187, 198, 4, 8162, 1891, 4, 3114, 38, 2291, 116, 0, 4223, 4324], [7374, 6456, 6449, 6632, 9314, 5574, 10909, 10396, 9476, 6396, 3871, 4103, 4219, 6385, 4185, 5562, 4107, 4223, 1, 4869, 4025, 4219, 9636, 4103, 4219, 6385, 4185, 5562, 4107, 4223, 0, 4425], [6622, 5354, 5347, 5530, 5312, 4472, 6907, 6852, 6030, 5294, 2796, 2927, 4320, 5283, 4286, 4293, 4208, 4324, 4425, 1, 4126, 4320, 5634, 2927, 4320, 5283, 4286, 4293, 4208, 4324, 4425, 0]] data['demands'] = [0, 644, 630, 631, 593, 621, 691, 651, 636, 656, 649, 671, 688, 672, 554, 597, 680, 639, 579, 688, 566, 553, 637, 631, 564, 681, 582, 614, 558, 614, 671, 639] data['vehicle_capacities'] = [8000, 5000, 5000, 1480] data['num_vehicles'] = 4 data['depot'] = 0 return data
def print_solution(data, manager, routing, solution): """Prints solution on console.""" 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) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution)if name == 'main': main()
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/2061, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3KMA5MG3QIL6BCMV4LRVQ5JZANCNFSM4NX2PPUA .
Mizux
What version of OR-tools and what language are you using? Version: 7.6.7691 Language: Python
Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi) Routing Solver What operating system (Linux, Windows, ...) and version? mac What did you do? i use the offical code, but i change the distance matrix & demands matrix & vehicle_capacities, but it run for a long time without result.. this is my code