Same vehicle constraint problem on entire route.

[angelo manzatto]

I found a lot of topics discussing the issue on assigning the same vehicle constraint for an entire route and not finding a single feasible solution like:

route = [1,2,3]

for i in range(len(route)-1):

current_index = manager.NodeToIndex(route[i])

        next_index = manager.NodeToIndex(route[i+1])

        

routing.solver().Add(routing.VehicleVar(current_index) == routing.VehicleVar(next_index))

I am having a hard time trying to figure how to make it work correctly in a way that or all nodes in the route are performed, or all of them need to be dropped.

I made an example with a strange behavior where the solver is not using the other vehicles when the max distance constraint is reached for the the first vehicle. Instead it is dropping the rest of the nodes. Is there an explanation for that ?

"""

Created on Tuesday Sep 14 07:00:42 2021

@author: Angelo Antonio Manzatto

"""

##################################################################################################

# Libraries

##################################################################################################

import time

from ortools.constraint_solver import routing_enums_pb2

from ortools.constraint_solver import pywrapcp

##################################################################################################

# Methods

##################################################################################################

def print_solution(manager, routing, solution):

    

    total_distance = 0

    dropped_vehicles = []

    dash = 120 * '-'

    star = 120 * '*'

    print(star)

    print('VEHICLE ITINERARIES - START')

    print(star)

    dimensions = {}

    dimensions['Distance'] = routing.GetDimensionOrDie('Distance')

    

    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.append(manager.IndexToNode(node))

    """Prints solution on console."""

    for vehicle_id in range(manager.GetNumberOfVehicles()):

        # Check if vehicle is used

        if not routing.IsVehicleUsed(solution, vehicle_id):

            dropped_vehicles.append(vehicle_id)

            continue

        index = routing.Start(vehicle_id)

        print(dash)

        print(f'Route for vehicle: {vehicle_id}')

        print(dash)

        print('{:<4s}{:>15s}{:>15s}{:>20s}'.format(

            'Location', 'Distance', 'Cumul', 'Route'))

        print(dash)

        currt_distance = 0

        

        while not routing.IsEnd(index):

            

            cumul_distance = solution.Value(

                dimensions['Distance'].CumulVar(index))

            currt_distance = cumul_distance - currt_distance

            

            node = manager.IndexToNode(index)

            route = []

            for r in data['routes']:

                if node in r:

                    route = r

                    break

            details = '{:4d}'.format(node)

            details += '{:>15.0f}'.format(currt_distance)

            details += '{:>18.0f}'.format(cumul_distance)

            details += '{:>20}'.format(str(route))

            print(details)

            currt_distance = cumul_distance

            index = solution.Value(routing.NextVar(index))

        node = manager.IndexToNode(index)

        route = []

        for r in data['routes']:

            if node in r:

                route = r

                break

        cumul_distance = solution.Value(dimensions['Distance'].CumulVar(index))

        currt_distance = cumul_distance - currt_distance

        details = '{:4d}'.format(node)

        details += '{:>15.0f}'.format(currt_distance)

        details += '{:>18.0f}'.format(cumul_distance)

        details += '{:>20}'.format('')

        

        total_distance += cumul_distance

        print(details)

        

    print(dash)

    print("dropped nodes : {}".format(dropped_nodes))

    print(dash)

    

    print(dash)

    print("Total cost: {}".format(total_distance))

    print(dash)

    

##################################################################################################

# Data model

##################################################################################################

data = {}

data['distance_matrix'] = [

        [ 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354,468, 776, 662       ],

        [ 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210   ],

        [ 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754  ],

        [ 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358   ],

        [ 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244   ],

        [ 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628,514, 1050, 708      ],

        [ 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856,514, 1278, 480     ],

        [ 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856      ],

        [ 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514     ],

        [ 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468      ],

        [ 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764,730, 388, 1152, 354   ],

        [ 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844    ],

        [ 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730     ],

        [ 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536     ],

        [ 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194   ],

        [ 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 ],

        [ 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0   ],

    ]

data['num_vehicles'] = 4

data['starts'] = [0, 0, 0, 0]

data['ends'] = [0, 0, 0, 0]

data['routes'] = [[1, 2, 3], [4, 5, 6], [7, 8], [9, 10, 11], [12, 13, 14],

                  [15, 16]]

data['drop_penalties'] = [0] + [100000 for _ in range(1, len(data['distance_matrix']))]

############################################

# Create the routing index manager.

############################################

manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),

                                       data['num_vehicles'],

                                       data['starts'],

                                       data['ends'])

# Create Routing Model.

routing = pywrapcp.RoutingModel(manager)

############################################

# Distance Dimension #

############################################

def distance_callback(from_index, to_index):

    from_node = manager.IndexToNode(from_index)

    to_node = manager.IndexToNode(to_index)

    distance = data['distance_matrix'][from_node][to_node]

    return distance

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

# Define cost of each arc.

routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add Distance constraint.

# Change to 3000 to find a feasible solution

dimension_name = 'Distance'

routing.AddDimension(

    transit_callback_index,

    0,  # no slack

    2500,  # vehicle maximum travel distance

    True,  # start cumul to zero

    dimension_name)

distance_dimension = routing.GetDimensionOrDie(dimension_name)

distance_dimension.SetGlobalSpanCostCoefficient(0)

############################################

# Constraint #

############################################

# Same vehicle constraint

for route in data['routes']:

    

    for i in range(len(route) - 1):

    

        current_index = manager.NodeToIndex(route[i])

        next_index = manager.NodeToIndex(route[i+1])

        

        active_var = routing.ActiveVar(current_index) * routing.ActiveVar(next_index) 

        

        routing.solver().Add(

            routing.VehicleVar(current_index) * active_var == 

            routing.VehicleVar(next_index) * active_var

            )

    

for route in data['routes']:

    

    indices = [manager.NodeToIndex(r) for r in route]

    

    routing.AddDisjunction(indices, 1000000, len(route))

    

############################################

# Optimizer parameters #

############################################

# Setting first solution heuristic.

search_parameters = pywrapcp.DefaultRoutingSearchParameters()

search_parameters.first_solution_strategy = (

    routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)

search_parameters.local_search_metaheuristic = (

    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

search_parameters.time_limit.seconds = 10

search_parameters.log_search = True

# Solve the problem.

start = time.time()

solution = routing.SolveWithParameters(search_parameters)

print("Time elapsed:", time.time() - start)

# Print solution on console.

if solution:

    print_solution(manager, routing, solution)

else:

    print('No solution found !')