I searched for many similar questions and couldn't find the solution to my situation. I would be really grateful if any of you could give me some tips.

This is my situation

A vehicle load some new machines at the depot then visits a number of locations. As the vehicle deliver new machines to each node, they also collect broken machines from each node.

Meanwhile, the vehicle has a capacity constraint.

Also, I need to duplicate the depot to allow multi trips: the vehicle needs to go back to the depot to unload the broken machines and load new machines and travel again until all the deliveries and pickups are fulfilled.

The main idea is similar to this example: https://github.com/google/or-tools/blob/master/ortools/constraint_solver/samples/cvrp_reload.py, but for now I don't consider the time constraint.

What I did

The main idea is that:

• uncomment the time window constraint.
• use deliveries dimension to track the deliveries of new machines
• use pickups dimension to track the pickups of broken machines
• add a constraint that at each node, CumulVar(pickups) + CumulVar(deliveries) <=capacity

Ask for help

The example task is like this:

The problem is:

If I set the vehicle capacity as 10, the problem could be solved. But when I set 7, then "No solution found"!

But obviously, the vehicle could travel at least 4 times to get all the job done:

round1: load 5 new machines at the depot, go to node 1, unload them, and pick up 4 broken machines go back to the depot

round2: load 5 new machines at the depot, go to node 2, unload them, and pick up 6 broken machines go back to the depot

round3: load 2 new machines at the depot, go to node 3, unload them, and pick up 7 broken machines go back to the depot

round4: load 3 new machines at the depot, go to node 4, unload them, and pick up 3 broken machines go back to the depot

I can understand why the solver didn't find this solution. Because the deliveries dimension reset to _capacity each time the vehicle departs from the duplicate depot node. When _capacity is 7, the vehicle could fulfill the demand of node 1 and node 4. (At node 1, it unloads 5 new machines and loads 4 broken machines. At node 4, it unloads 3 broken machines and loads 3 new machines. )

But at node 2 and node 3, the pickups/deliveries are +6/-5 and +7/-2. When the vehicle departs from the duplicate depot node, its capacity is 7, both node 2 and node 3 would break the capacity constraint. (+6-5>0, +7-2>0)

So the root cause of this problem is: the duplicate depot node should not set the deliveries dimension value as a fixed value(_capacity), but a value between [0, _capacity].

But the max_slack is a positive number and I have no idea about how to make the deliveries dimension has a value between [0, _capacity].

Could anyone help me? Thank you so much.

Below is my code.

from functools import partial
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
from itertools import repeat

###########################
# Problem Data Definition #
###########################
def create_data_model():
    """Stores the data for the problem"""
    data = {}
    _capacity = 10  # 7 doesn't work
    _duplicate_depot_num = 5
    # Locations in block unit
    _locations = [
        (4, 4),  # depot
        (2, 0), (8, 0),  # 1, 2
        (0, 1), (1, 1)]  # 3, 4
    _locations[1:1] = tuple(repeat(_locations[0], _duplicate_depot_num))

    data['locations'] = _locations
    data['num_locations'] = len(data['locations'])
    data['pickups'] = [0,  # depot
                       4, 6,  # 1, 2
                       7, 3]  # 3, 4
    data['pickups'][1:1] = tuple(repeat(-_capacity, _duplicate_depot_num))

    data['deliveries'] = [0,  # depot
                          -5, -5,  # 1, 2
                          -2, -3]  # 3, 4
    data['deliveries'][1:1] = tuple(repeat(_capacity, _duplicate_depot_num))

    data['vehicle_max_distance'] = 1000
    data['vehicle_capacity'] = _capacity
    data['num_vehicles'] = 1
    data['depot'] = 0
    data['dup_depot_num'] = _duplicate_depot_num
    return data


#######################
# Problem Constraints #
#######################
def manhattan_distance(position_1, position_2):
    """Computes the Manhattan distance between two points"""
    return (abs(position_1[0] - position_2[0]) +
            abs(position_1[1] - position_2[1]))


def create_distance_evaluator(data):
    """Creates callback to return distance between points."""
    _distances = {}
    # precompute distance between location to have distance callback in O(1)
    for from_node in range(data['num_locations']):
        _distances[from_node] = {}
        for to_node in range(data['num_locations']):
            if from_node == to_node:
                _distances[from_node][to_node] = 0
            # Forbid start/end/reload node to be consecutive.
            elif from_node in range(data['dup_depot_num']+1) and to_node in range(data['dup_depot_num']+1):
                _distances[from_node][to_node] = data['vehicle_max_distance']
            else:
                _distances[from_node][to_node] = (manhattan_distance(
                    data['locations'][from_node], data['locations'][to_node]))

    def distance_evaluator(manager, from_node, to_node):
        """Returns the manhattan distance between the two nodes"""
        return _distances[manager.IndexToNode(from_node)][manager.IndexToNode(
            to_node)]

    return distance_evaluator


def add_distance_dimension(routing, manager, data, distance_evaluator_index):
    """Add Global Span constraint"""
    distance = 'Distance'
    routing.AddDimension(
        distance_evaluator_index,
        0,  # null slack
        data['vehicle_max_distance'],  # maximum distance per vehicle
        True,  # start cumul to zero
        distance)
    # distance_dimension = routing.GetDimensionOrDie(distance)
    # Try to minimize the max distance among vehicles.
    # /!\ It doesn't mean the standard deviation is minimized
    # distance_dimension.SetGlobalSpanCostCoefficient(100)


def create_demand_evaluator(data):
    """Creates callback to get demands at each location."""
    _demands = data['pickups']

    def demand_evaluator(manager, from_node):
        """Returns the demand of the current node"""
        return _demands[manager.IndexToNode(from_node)]

    return demand_evaluator


def add_pickups_constraints(routing, manager, data, pickups_evaluator_index):
    """Adds capacity constraint"""
    vehicle_capacity = data['vehicle_capacity']
    capacity = 'pickups'
    routing.AddDimension(
        pickups_evaluator_index,
        vehicle_capacity,
        vehicle_capacity,
        True,  # since this is pickups, so start cumul should be zero
        capacity)


def create_deliveries_evaluator(data):
    """Creates callback to get demands at each location."""
    _deliveries = data['deliveries']

    def deliveries_evaluator(manager, from_node):
        """Returns the demand of the current node"""
        return _deliveries[manager.IndexToNode(from_node)]

    return deliveries_evaluator


def add_deliveries_constraints(routing, manager, data, deliveries_evaluator_index):
    """Adds capacity constraint"""
    vehicle_capacity = data['vehicle_capacity']
    capacity = 'deliveries'
    routing.AddDimension(
        deliveries_evaluator_index,
        vehicle_capacity,
        vehicle_capacity,
        False,  # there is a initial capacity to be delivered
        capacity)

###########
# Printer #
###########
def print_solution(data, manager, routing, assignment):  # pylint:disable=too-many-locals
    """Prints assignment on console"""
    print(f'Objective: {assignment.ObjectiveValue()}')
    total_distance = 0
    total_pickups = 0
    # total_time = 0
    total_deliveries = 0
    pickups_dimension = routing.GetDimensionOrDie('pickups')
    # time_dimension = routing.GetDimensionOrDie('Time')
    deliveries_dimension = routing.GetDimensionOrDie('deliveries')
    dropped = []
    for order in range(6, routing.nodes()):
        index = manager.NodeToIndex(order)
        if assignment.Value(routing.NextVar(index)) == index:
            dropped.append(order)
    print(f'dropped orders: {dropped}')
    for reload in range(1, 6):
        index = manager.NodeToIndex(reload)
        if assignment.Value(routing.NextVar(index)) == index:
            dropped.append(reload)
    print(f'dropped reload stations: {dropped}')

    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = f'Route for vehicle {vehicle_id}:\n'
        distance = 0
        while not routing.IsEnd(index):
            pickups_var = pickups_dimension.CumulVar(index)
            deliveries_var = deliveries_dimension.CumulVar(index)
            # time_var = time_dimension.CumulVar(index)
            plan_output += ' {0} Pickups({1}) Deliveries({2})->'.format(
                manager.IndexToNode(index),
                assignment.Value(pickups_var),
                assignment.Value(deliveries_var)
                # assignment.Min(time_var), assignment.Max(time_var)
            )
            previous_index = index
            index = assignment.Value(routing.NextVar(index))
            distance += routing.GetArcCostForVehicle(previous_index, index,
                                                     vehicle_id)
        pickups_var = pickups_dimension.CumulVar(index)
        deliveries_var = deliveries_dimension.CumulVar(index)
        # time_var = time_dimension.CumulVar(index)
        plan_output += ' {0} Pickups({1}) Deliveries({2})\n'.format(
            manager.IndexToNode(index),
            assignment.Value(pickups_var),
            assignment.Value(deliveries_var)
            # assignment.Min(time_var), assignment.Max(time_var)
        )
        plan_output += f'Distance of the route: {distance}m\n'
        plan_output += f'Pickups of the route: {assignment.Value(pickups_var)}\n'
        plan_output += f'Deliveries of the route: {assignment.Value(deliveries_var)}\n'
        # plan_output += f'Time of the route: {assignment.Value(time_var)}min\n'
        print(plan_output)
        total_distance += distance
        total_pickups += assignment.Value(pickups_var)
        total_deliveries += assignment.Value(deliveries_var)
        # total_time += assignment.Value(time_var)
    print('Total Distance of all routes: {}m'.format(total_distance))
    print('Total Pickups of all routes: {}'.format(total_pickups))
    print('Total Deliveries of all routes: {}'.format(total_deliveries))
    # print('Total Time of all routes: {}min'.format(total_time))


########
# Main #
########
def main():
    """Entry point of the program"""
    # Instantiate the data problem.
    data = create_data_model()

    print(data['locations'])

    # Create the routing index manager
    manager = pywrapcp.RoutingIndexManager(data['num_locations'],
                                           data['num_vehicles'], data['depot'])

    # Create Routing Model
    routing = pywrapcp.RoutingModel(manager)

    # Define weight of each edge
    distance_evaluator_index = routing.RegisterTransitCallback(
        partial(create_distance_evaluator(data), manager))
    routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator_index)

    # Add Distance constraint to minimize the longuest route
    add_distance_dimension(routing, manager, data, distance_evaluator_index)

    # Add Demand constraint
    demand_evaluator_index = routing.RegisterUnaryTransitCallback(partial(create_demand_evaluator(data), manager))
    add_pickups_constraints(routing, manager, data, demand_evaluator_index)

    # Add deliveries constraint
    deliveries_evaluator_index = routing.RegisterUnaryTransitCallback(
        partial(create_deliveries_evaluator(data), manager))
    add_deliveries_constraints(routing, manager, data, deliveries_evaluator_index)

    # # Add Slack for reseting to zero unload depot nodes.
    # e.g. vehicle with load 10/15 arrives at node 1 (depot unload)
    # so we have CumulVar = 10(current load) + -15(unload) + 5(slack) = 0.
    pickups_dimension = routing.GetDimensionOrDie("pickups")
    deliveries_dimension = routing.GetDimensionOrDie('deliveries')

    # Allow to drop reloading nodes with zero cost.
    for node in range(1, data['dup_depot_num']+1):
        node_index = manager.NodeToIndex(node)
        routing.AddDisjunction([node_index], 0)

    for node in range(data['dup_depot_num']+1, len(data['pickups'])):
        node_index = manager.NodeToIndex(node)
        pickups_dimension.SlackVar(node_index).SetValue(0)
        deliveries_dimension.SlackVar(node_index).SetValue(0)  # ordinary node don't allow slack
        # routing.AddDisjunction([node_index], 100_000)  # Allow to drop regular node with a cost.

    # Add Constraint: Pick + Deliveries <= max_capacity
    for node in range(len(data['pickups'])):
        index = manager.NodeToIndex(node)
        routing.solver().Add(
            pickups_dimension.CumulVar(index) + deliveries_dimension.CumulVar(index) <= data["vehicle_capacity"])


    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )  # pylint: disable=no-member

    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.FromSeconds(3)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("No solution found !")


if __name__ == '__main__':
    main()