No solution is found for simple CVRP problem #2306

glazaridis · 2020-12-31T15:52:27Z

glazaridis
Dec 31, 2020

Hi all, in my capacitated VRP problem,

I have 21 locations in which, at the same time, 1 of them serves as the depot itself.
As a result, I end up with a 22x22 distance matrix.
I am also enforcing a specific constraint so that each vehicle can visit one location from the depot and then return back to the depot: that is to not allow a vehicle to go from location to location but always to need to return to depot for refuelling and then start again for a new location.
I have a different capacity in each location and each vehicle has the same capacity.
I am wondering why the solver can not find a solution and is always None.
Any help would be highly appreciated.

    data = {
'distance_matrix': [
 [0.0, 485.9, 1467.7, 0.0, 6274.5, 1113.1, 1045.5, 1050.7, 540.7, 1027.3, 789.0, 834.7, 487.6, 1661.4, 698.9, 1908.6, 1037.8, 1307.6, 483.1, 1392.9, 1361.5, 805.5],
 [4.5, 0.0, 1472.2, 4.5, 6279.0, 1117.6, 1050.0, 1055.1, 545.1, 1031.8, 793.5, 839.1, 1.6, 1665.9, 703.4, 1913.0, 1042.3, 1312.1, 487.6, 1397.3, 1366.0, 810.0],
 [1133.2, 1128.7, 0.0, 1133.2, 6094.2, 1582.1, 1514.5, 1519.6, 1183.4, 1496.2, 1431.8, 745.9, 1130.3, 1481.1, 1341.6, 2377.5, 1506.7, 1776.6, 1125.8, 1212.5, 1181.2, 1274.5],
 [0.0, 485.9, 1467.7, 0.0, 6274.5, 1113.1, 1045.5, 1050.7, 540.7, 1027.3, 789.0, 834.7, 487.6, 1661.4, 698.9, 1908.6, 1037.8, 1307.6, 483.1, 1392.9, 1361.5, 805.5],
 [6156.4, 6151.9, 4803.5, 6156.4, 0.0, 4511.2, 4543.7, 4873.0, 6206.6, 4561.9, 6455.0, 5053.0, 6153.5, 4698.7, 6364.8, 5730.9, 4435.8, 4705.7, 6149.0, 5602.0, 5570.6, 4203.6],
 [1436.3, 1431.8, 2177.2, 1436.3, 6275.6, 0.0, 430.1, 621.0, 1486.5, 411.9, 1734.9, 1544.1, 1433.4, 1905.3, 1644.7, 1234.6, 947.6, 1217.5, 1428.9, 2102.3, 2070.9, 414.8],
 [1174.3, 1169.8, 1732.8, 1174.3, 6518.8, 396.8, 0.0, 359.0, 1224.5, 18.2, 1472.9, 1282.1, 1171.5, 1628.0, 1382.8, 1216.9, 670.3, 940.2, 1167.0, 1840.3, 1809.0, 438.1],
 [1795.9, 1791.4, 2536.7, 1795.9, 6338.3, 554.9, 789.7, 0.0, 1846.1, 771.5, 2094.5, 1903.7, 1793.0, 2417.7, 2004.3, 857.9, 1460.0, 1729.9, 1788.5, 2461.9, 2430.5, 948.0],
 [289.7, 285.2, 1624.1, 289.7, 6430.9, 1269.5, 1201.9, 1207.0, 0.0, 1183.6, 644.3, 991.0, 286.9, 1817.8, 554.1, 2064.9, 1194.1, 1464.0, 282.4, 1549.2, 1517.9, 961.9],
 [1156.1, 1151.6, 1751.0, 1156.1, 6500.6, 378.6, 18.2, 340.8, 1206.3, 0.0, 1454.7, 1263.9, 1153.2, 1646.2, 1364.5, 1198.7, 688.6, 958.4, 1148.7, 1822.1, 1790.7, 520.8],
 [382.3, 377.8, 1716.7, 382.3, 6523.4, 1362.1, 1294.4, 1299.6, 230.4, 1276.2, 0.0, 1083.6, 379.4, 1910.4, 135.4, 2157.5, 1286.7, 1556.6, 374.9, 1641.8, 1610.4, 1054.5],
 [1098.3, 1093.9, 633.1, 1098.3, 5439.8, 1547.3, 1479.6, 1484.8, 1148.6, 1461.4, 1396.9, 0.0, 1095.5, 826.8, 1306.8, 2342.7, 1471.9, 1741.8, 1091.0, 558.2, 526.8, 1239.7],
 [2.9, 488.8, 1470.6, 2.9, 6277.4, 1116.0, 1048.4, 1053.5, 543.5, 1030.2, 791.9, 837.5, 0.0, 1664.3, 701.7, 1911.4, 1040.6, 1310.5, 485.9, 1395.7, 1364.4, 808.4],
 [726.2, 721.7, 987.4, 726.2, 5794.1, 1175.1, 1107.5, 1112.6, 776.4, 1089.2, 1024.8, 354.3, 723.3, 0.0, 934.6, 1970.5, 1099.7, 1369.6, 718.8, 912.5, 881.1, 867.5],
 [472.5, 468.0, 1806.8, 472.5, 6613.6, 1452.3, 1384.6, 1389.8, 320.6, 1366.4, 90.2, 1173.8, 469.6, 2000.6, 0.0, 2247.7, 1376.9, 1646.7, 465.1, 1732.0, 1700.6, 1144.6],
 [1907.1, 1902.6, 2648.0, 1907.1, 6634.5, 1384.7, 1128.7, 897.9, 1957.3, 1110.4, 2205.7, 2014.9, 1904.2, 2785.7, 2115.6, 0.0, 1828.0, 2097.9, 1899.8, 2573.1, 2541.7, 1595.8],
 [1683.8, 1679.3, 1062.5, 1683.8, 6751.8, 2132.7, 2065.1, 2070.3, 1734.0, 2046.9, 1982.4, 1311.9, 1680.9, 957.6, 1892.2, 2928.2, 0.0, 257.6, 1676.4, 1870.1, 1838.8, 1825.1],
 [1484.8, 1480.3, 863.5, 1484.8, 6552.7, 1933.7, 1866.1, 1871.2, 1535.0, 1847.9, 1783.4, 1112.9, 1481.9, 758.6, 1693.2, 2729.1, 1858.3, 0.0, 1477.4, 1671.1, 1639.7, 1626.1],
 [7.4, 2.9, 1475.1, 7.4, 6281.9, 1120.5, 1052.9, 1058.0, 548.0, 1034.6, 796.4, 842.0, 4.5, 1668.8, 706.2, 1915.9, 1045.1, 1315.0, 0.0, 1400.2, 1368.9, 812.9],
 [1267.7, 1263.2, 646.4, 1267.7, 6335.7, 1716.7, 1649.0, 1654.2, 1317.9, 1630.8, 1566.3, 895.8, 1264.8, 541.6, 1476.2, 2512.1, 1641.3, 1911.1, 1260.4, 0.0, 96.2, 1409.0],
 [1236.4, 1231.9, 615.1, 1236.4, 6304.3, 1685.3, 1617.7, 1622.8, 1286.6, 1599.4, 1535.0, 864.5, 1233.5, 510.2, 1444.8, 2480.7, 1609.9, 1879.8, 1229.0, 96.2, 0.0, 1377.7],
 [1514.5, 1510.0, 1595.3, 1514.5, 6883.8, 608.2, 340.1, 699.1, 1564.7, 358.4, 1813.1, 1622.2, 1511.6, 1490.5, 1722.9, 1557.0, 532.8, 802.7, 1507.1, 2180.4, 2149.1, 0.0]
],
'demands': [0.0, 0.42857142857142855, 4.571428571428571, 3.0, 0.5714285714285714, 7.0, 6.714285714285714, 10.285714285714286, 1.7142857142857142, 7.428571428571429, 11.285714285714286, 5.0, 0.14285714285714285, 0.7142857142857143, 2.2857142857142856, 8.714285714285714, 3.4285714285714284, 2.142857142857143, 19.0, 23.428571428571427, 0.14285714285714285, 0.8571428571428571],
'vehicle_capacities': [22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22], 'num_vehicles': 50,
'depot': 0}

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    total_distance = 0
    total_load = 0
    total_vehicles_needed = 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
        total_vehicles_needed += 1 if route_load != 0.0 else 0
    print('Total distance of all routes: {}m'.format(total_distance))
    print('Total load of all routes: {}'.format(total_load))
    print('Total vehicles need: {} from total vehicles: {}'.format(total_vehicles_needed,
                                                                   num_of_vehicles))

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

    # Create counter
    def counter_callback(from_index):
        """Returns 1 for any locations except depot."""
        # Convert from routing variable Index to user NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return 1 if (from_node != 0) else 0

    counter_callback_index = routing.RegisterUnaryTransitCallback(counter_callback)

    routing.AddDimensionWithVehicleCapacity(
        counter_callback_index,
        0,  # null slack
        [1] * data['num_vehicles'],  # maximum locations per vehicle
        True,  # start cumul to zero
        'Counter')

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

Answered by Mizux

Dec 31, 2020

All your callbacks must return value of type int i.e. fix your demand callback or update your data...
Try to allow nodes to be dropped to see what's happen
ref: https://developers.google.com/optimization/routing/penalties#overview
you have demand of 23 for node 19, with a vehicle capacity of 22 without allowing node to be dropped -> your problem is infeasible...
since I use int() to round your demand you have demand of 0 so your counter of active vehicle didn't work so I replace it by route_distance since your start/end node is the same location i.e. 0
your vehicle capacity list contains 100 values while you specified 50 vehicles... -> data ill formed

here few fix to make it work, (you …

View full answer

Mizux · 2020-12-31T16:30:22Z

Mizux
Dec 31, 2020
Maintainer

All your callbacks must return value of type int i.e. fix your demand callback or update your data...
Try to allow nodes to be dropped to see what's happen
ref: https://developers.google.com/optimization/routing/penalties#overview
you have demand of 23 for node 19, with a vehicle capacity of 22 without allowing node to be dropped -> your problem is infeasible...
since I use int() to round your demand you have demand of 0 so your counter of active vehicle didn't work so I replace it by route_distance since your start/end node is the same location i.e. 0
your vehicle capacity list contains 100 values while you specified 50 vehicles... -> data ill formed

here few fix to make it work, (you can diff this one with your to see the update):

#!/usr/bin/env python3
"""Capacity Vehicles Routing Problem (CVRP)."""

from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

data = {
    'distance_matrix':
    [[
        0.0, 485.9, 1467.7, 0.0, 6274.5, 1113.1, 1045.5, 1050.7, 540.7, 1027.3,
        789.0, 834.7, 487.6, 1661.4, 698.9, 1908.6, 1037.8, 1307.6, 483.1,
        1392.9, 1361.5, 805.5
    ],
     [
         4.5, 0.0, 1472.2, 4.5, 6279.0, 1117.6, 1050.0, 1055.1, 545.1, 1031.8,
         793.5, 839.1, 1.6, 1665.9, 703.4, 1913.0, 1042.3, 1312.1, 487.6,
         1397.3, 1366.0, 810.0
     ],
     [
         1133.2, 1128.7, 0.0, 1133.2, 6094.2, 1582.1, 1514.5, 1519.6, 1183.4,
         1496.2, 1431.8, 745.9, 1130.3, 1481.1, 1341.6, 2377.5, 1506.7, 1776.6,
         1125.8, 1212.5, 1181.2, 1274.5
     ],
     [
         0.0, 485.9, 1467.7, 0.0, 6274.5, 1113.1, 1045.5, 1050.7, 540.7,
         1027.3, 789.0, 834.7, 487.6, 1661.4, 698.9, 1908.6, 1037.8, 1307.6,
         483.1, 1392.9, 1361.5, 805.5
     ],
     [
         6156.4, 6151.9, 4803.5, 6156.4, 0.0, 4511.2, 4543.7, 4873.0, 6206.6,
         4561.9, 6455.0, 5053.0, 6153.5, 4698.7, 6364.8, 5730.9, 4435.8,
         4705.7, 6149.0, 5602.0, 5570.6, 4203.6
     ],
     [
         1436.3, 1431.8, 2177.2, 1436.3, 6275.6, 0.0, 430.1, 621.0, 1486.5,
         411.9, 1734.9, 1544.1, 1433.4, 1905.3, 1644.7, 1234.6, 947.6, 1217.5,
         1428.9, 2102.3, 2070.9, 414.8
     ],
     [
         1174.3, 1169.8, 1732.8, 1174.3, 6518.8, 396.8, 0.0, 359.0, 1224.5,
         18.2, 1472.9, 1282.1, 1171.5, 1628.0, 1382.8, 1216.9, 670.3, 940.2,
         1167.0, 1840.3, 1809.0, 438.1
     ],
     [
         1795.9, 1791.4, 2536.7, 1795.9, 6338.3, 554.9, 789.7, 0.0, 1846.1,
         771.5, 2094.5, 1903.7, 1793.0, 2417.7, 2004.3, 857.9, 1460.0, 1729.9,
         1788.5, 2461.9, 2430.5, 948.0
     ],
     [
         289.7, 285.2, 1624.1, 289.7, 6430.9, 1269.5, 1201.9, 1207.0, 0.0,
         1183.6, 644.3, 991.0, 286.9, 1817.8, 554.1, 2064.9, 1194.1, 1464.0,
         282.4, 1549.2, 1517.9, 961.9
     ],
     [
         1156.1, 1151.6, 1751.0, 1156.1, 6500.6, 378.6, 18.2, 340.8, 1206.3,
         0.0, 1454.7, 1263.9, 1153.2, 1646.2, 1364.5, 1198.7, 688.6, 958.4,
         1148.7, 1822.1, 1790.7, 520.8
     ],
     [
         382.3, 377.8, 1716.7, 382.3, 6523.4, 1362.1, 1294.4, 1299.6, 230.4,
         1276.2, 0.0, 1083.6, 379.4, 1910.4, 135.4, 2157.5, 1286.7, 1556.6,
         374.9, 1641.8, 1610.4, 1054.5
     ],
     [
         1098.3, 1093.9, 633.1, 1098.3, 5439.8, 1547.3, 1479.6, 1484.8, 1148.6,
         1461.4, 1396.9, 0.0, 1095.5, 826.8, 1306.8, 2342.7, 1471.9, 1741.8,
         1091.0, 558.2, 526.8, 1239.7
     ],
     [
         2.9, 488.8, 1470.6, 2.9, 6277.4, 1116.0, 1048.4, 1053.5, 543.5,
         1030.2, 791.9, 837.5, 0.0, 1664.3, 701.7, 1911.4, 1040.6, 1310.5,
         485.9, 1395.7, 1364.4, 808.4
     ],
     [
         726.2, 721.7, 987.4, 726.2, 5794.1, 1175.1, 1107.5, 1112.6, 776.4,
         1089.2, 1024.8, 354.3, 723.3, 0.0, 934.6, 1970.5, 1099.7, 1369.6,
         718.8, 912.5, 881.1, 867.5
     ],
     [
         472.5, 468.0, 1806.8, 472.5, 6613.6, 1452.3, 1384.6, 1389.8, 320.6,
         1366.4, 90.2, 1173.8, 469.6, 2000.6, 0.0, 2247.7, 1376.9, 1646.7,
         465.1, 1732.0, 1700.6, 1144.6
     ],
     [
         1907.1, 1902.6, 2648.0, 1907.1, 6634.5, 1384.7, 1128.7, 897.9, 1957.3,
         1110.4, 2205.7, 2014.9, 1904.2, 2785.7, 2115.6, 0.0, 1828.0, 2097.9,
         1899.8, 2573.1, 2541.7, 1595.8
     ],
     [
         1683.8, 1679.3, 1062.5, 1683.8, 6751.8, 2132.7, 2065.1, 2070.3,
         1734.0, 2046.9, 1982.4, 1311.9, 1680.9, 957.6, 1892.2, 2928.2, 0.0,
         257.6, 1676.4, 1870.1, 1838.8, 1825.1
     ],
     [
         1484.8, 1480.3, 863.5, 1484.8, 6552.7, 1933.7, 1866.1, 1871.2, 1535.0,
         1847.9, 1783.4, 1112.9, 1481.9, 758.6, 1693.2, 2729.1, 1858.3, 0.0,
         1477.4, 1671.1, 1639.7, 1626.1
     ],
     [
         7.4, 2.9, 1475.1, 7.4, 6281.9, 1120.5, 1052.9, 1058.0, 548.0, 1034.6,
         796.4, 842.0, 4.5, 1668.8, 706.2, 1915.9, 1045.1, 1315.0, 0.0, 1400.2,
         1368.9, 812.9
     ],
     [
         1267.7, 1263.2, 646.4, 1267.7, 6335.7, 1716.7, 1649.0, 1654.2, 1317.9,
         1630.8, 1566.3, 895.8, 1264.8, 541.6, 1476.2, 2512.1, 1641.3, 1911.1,
         1260.4, 0.0, 96.2, 1409.0
     ],
     [
         1236.4, 1231.9, 615.1, 1236.4, 6304.3, 1685.3, 1617.7, 1622.8, 1286.6,
         1599.4, 1535.0, 864.5, 1233.5, 510.2, 1444.8, 2480.7, 1609.9, 1879.8,
         1229.0, 96.2, 0.0, 1377.7
     ],
     [
         1514.5, 1510.0, 1595.3, 1514.5, 6883.8, 608.2, 340.1, 699.1, 1564.7,
         358.4, 1813.1, 1622.2, 1511.6, 1490.5, 1722.9, 1557.0, 532.8, 802.7,
         1507.1, 2180.4, 2149.1, 0.0
     ]],
    'demands': [
        0.0, 0.42857142857142855, 4.571428571428571, 3.0, 0.5714285714285714,
        7.0, 6.714285714285714, 10.285714285714286, 1.7142857142857142,
        7.428571428571429, 11.285714285714286, 5.0, 0.14285714285714285,
        0.7142857142857143, 2.2857142857142856, 8.714285714285714,
        3.4285714285714284, 2.142857142857143, 19.0, 23.428571428571427,
        0.14285714285714285, 0.8571428571428571
    ],
    'vehicle_capacities': [22 for i in range(50)],
    'num_vehicles':
    50,
    'depot':
    0
}


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    # 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 += f' {manager.IndexToNode(node)}'
    print(dropped_nodes)
    # Display routes.
    total_distance = 0
    total_load = 0
    total_vehicles_needed = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = f'Route for vehicle {vehicle_id}:\n'
        route_distance = 0
        route_load = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_load += int(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
        total_vehicles_needed += 1 if route_distance != 0 else 0
    print('Total distance of all routes: {}m'.format(total_distance))
    print('Total load of all routes: {}'.format(total_load))
    print('Total vehicles need: {} from total vehicles: {}'.format(
        total_vehicles_needed, data['num_vehicles']))


def main():
    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 int(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 int(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 = 1000000
    for node in range(1, len(data['distance_matrix'])):
        routing.AddDisjunction([manager.NodeToIndex(node)], penalty)

    # Create counter
    def counter_callback(from_index):
        """Returns 1 for any locations except depot."""
        # Convert from routing variable Index to user NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return 1 if (from_node != 0) else 0

    counter_callback_index = routing.RegisterUnaryTransitCallback(
        counter_callback)

    routing.AddDimensionWithVehicleCapacity(
        counter_callback_index,
        0,  # null slack
        [1] * data['num_vehicles'],  # maximum locations per vehicle
        True,  # start cumul to zero
        'Counter')

    # 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)
    else:
        print("No solution found !")


if __name__ == '__main__':
    main()

possible output

[^v^]─mizux@nuc10i7 %./2306_cvrp.py
Dropped nodes: 19
Route for vehicle 0:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

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

Route for vehicle 2:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 3:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 4:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 5:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 6:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 7:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 8:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 9:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 10:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 11:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 12:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 13:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 14:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 15:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 16:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 17:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 18:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 19:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 20:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 21:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 22:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 23:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 24:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 25:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 26:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 27:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 28:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 29:
 0 Load(0) ->  0 Load(0)
Distance of the route: 0m
Load of the route: 0

Route for vehicle 30:
 0 Load(0) ->  4 Load(0) ->  0 Load(0)
Distance of the route: 12430m
Load of the route: 0

Route for vehicle 31:
 0 Load(0) ->  15 Load(8) ->  0 Load(8)
Distance of the route: 3815m
Load of the route: 8

Route for vehicle 32:
 0 Load(0) ->  13 Load(0) ->  0 Load(0)
Distance of the route: 2387m
Load of the route: 0

Route for vehicle 33:
 0 Load(0) ->  2 Load(4) ->  0 Load(4)
Distance of the route: 2600m
Load of the route: 4

Route for vehicle 34:
 0 Load(0) ->  20 Load(0) ->  0 Load(0)
Distance of the route: 2597m
Load of the route: 0

Route for vehicle 35:
 0 Load(0) ->  17 Load(2) ->  0 Load(2)
Distance of the route: 2791m
Load of the route: 2

Route for vehicle 36:
 0 Load(0) ->  5 Load(7) ->  0 Load(7)
Distance of the route: 2549m
Load of the route: 7

Route for vehicle 37:
 0 Load(0) ->  7 Load(10) ->  0 Load(10)
Distance of the route: 2845m
Load of the route: 10

Route for vehicle 38:
 0 Load(0) ->  6 Load(6) ->  0 Load(6)
Distance of the route: 2219m
Load of the route: 6

Route for vehicle 39:
 0 Load(0) ->  16 Load(3) ->  0 Load(3)
Distance of the route: 2720m
Load of the route: 3

Route for vehicle 40:
 0 Load(0) ->  9 Load(7) ->  0 Load(7)
Distance of the route: 2183m
Load of the route: 7

Route for vehicle 41:
 0 Load(0) ->  11 Load(5) ->  0 Load(5)
Distance of the route: 1932m
Load of the route: 5

Route for vehicle 42:
 0 Load(0) ->  21 Load(0) ->  0 Load(0)
Distance of the route: 2319m
Load of the route: 0

Route for vehicle 43:
 0 Load(0) ->  10 Load(11) ->  0 Load(11)
Distance of the route: 1171m
Load of the route: 11

Route for vehicle 44:
 0 Load(0) ->  14 Load(2) ->  0 Load(2)
Distance of the route: 1170m
Load of the route: 2

Route for vehicle 45:
 0 Load(0) ->  8 Load(1) ->  0 Load(1)
Distance of the route: 829m
Load of the route: 1

Route for vehicle 46:
 0 Load(0) ->  12 Load(0) ->  0 Load(0)
Distance of the route: 489m
Load of the route: 0

Route for vehicle 47:
 0 Load(0) ->  1 Load(0) ->  0 Load(0)
Distance of the route: 489m
Load of the route: 0

Route for vehicle 48:
 0 Load(0) ->  18 Load(19) ->  0 Load(19)
Distance of the route: 490m
Load of the route: 19

Route for vehicle 49:
 0 Load(0) ->  3 Load(3) ->  0 Load(3)
Distance of the route: 0m
Load of the route: 3

Total distance of all routes: 48025m
Total load of all routes: 88
Total vehicles need: 19 from total vehicles: 50

ps: next time please provide a working sample with import etc...

3 replies

glazaridis Dec 31, 2020
Author

@Mizux Hi Mizux, thanks for your prompt and kind reply. I'm sorry for the code snippet -might have Ctrl+Z'd something during copy pasting from my computer as I was executing the code with different parameters.

All your callbacks must return value of type int i.e. fix your demand callback or update your data...

Thanks for pointing that out; I'm reading the documentation in parallel with coding, so I definitely missed it.

Try to allow nodes to be dropped to see what's happen
ref: https://developers.google.com/optimization/routing/penalties#overview

Should I try that even if I definitely want to visit all the nodes?

you have demand of 23 for node 19, with a vehicle capacity of 22 without allowing node to be dropped -> your problem is infeasible...

Isn't is possible to somehow solve this issue by visiting this node twice with a vehicle of capacity 22?

since I use int() to round your demand you have demand of 0 so your counter of active vehicle didn't work so I replace it by route_distance since your start/end node is the same location i.e. 0
your vehicle capacity list contains 100 values while you specified 50 vehicles... -> data ill formed

Thanks for pointing this out as well.

Extra questions:

If the demand > vehicle capacity, isn't it possible to allocate an extra vehicle?
Will there be any actual difference between i) adding an extra node and increasing the maximum locations per vehicle to 2 so as each vehicle to follow [Depot -> Node 1 -> Node 2 -> Depot] and ii) Leaving the problem as is and adding the distance from Node1 -> Node2 in the distance matrix?

Mizux Jan 1, 2021
Maintainer

Each node can only be visited once, if you want this, you must split yourself the node by duplicating it and adapt distance matrix etc...

glazaridis Jan 1, 2021
Author

To which of my questions does this answer apply?

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

No solution is found for simple CVRP problem #2306

{{title}}

{{editor}}'s edit

{{editor}}'s edit

Replies: 1 comment 3 replies

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

Select a reply

No solution is found for simple CVRP problem #2306

glazaridis Dec 31, 2020

Replies: 1 comment · 3 replies

Mizux Dec 31, 2020 Maintainer

glazaridis Dec 31, 2020 Author

Mizux Jan 1, 2021 Maintainer

glazaridis Jan 1, 2021 Author

glazaridis
Dec 31, 2020

Replies: 1 comment 3 replies

Mizux
Dec 31, 2020
Maintainer

glazaridis Dec 31, 2020
Author

Mizux Jan 1, 2021
Maintainer

glazaridis Jan 1, 2021
Author