Go And Back trip, solver didn't return solution

[stephaneleroi]

I try to modelize a 2 pickup and delivery trip.
The first Pickup/Delivery (location1 -> location 2) is the first trip.
The second Pickup/Delivery (location2 -> location 1) is the second trip and is a back trip.

Due to the fact the location can only be visited once, I have duplicated the node.

data = {}
_location_depot = [(4, 4)]
_location_pickup_and_delivery = [
(2, 0), #1
(7, 2), #2
(2, 0), # 3
(7, 2), # 4
]
data['pickups_deliveries'] = [
[1, 2],
[4, 3],
]

I want the go trip to be done before the retrun trip.
So I Tryed to had this constraint :
routing.solver().Add(distance_dimension.CumulVar(2) <= distance_dimension.CumulVar(4))

But the solver didn't find any solution....
I can not figure out why....

I tried also to model with a dimension counting the first pickup and delivery.
And saying you back pickup/delivery can't be done until all the first pickup/delivery are done.
But it didn't work either....
Any Help would be greatly appreciated..

def nb_node_go_visited_callback(from_index):
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
if (from_node in [1,2]):
return 1
else:
return 0

nb_node_go_visited_callback_index = routing.RegisterUnaryTransitCallback(
nb_node_go_visited_callback)
routing.AddDimensionWithVehicleCapacity(
nb_node_aller_visited_callback_index,
0, # null capacity slack
[2], # vehicle maximum capacities
True, # start cumul to zero
'NBNodeGo')

nb_node_visited_go_dimension = routing.GetDimensionOrDie('NBNodeGo')
nb_node_go = 2 # [1,2]
for node_go in [1,2]:
node_aller_index = manager.NodeToIndex(node_go)
all_node_go_visited = nb_node_visited_go_dimension.CumulVar(node_go) == nb_node_go # nb max allé
for node_back in [4,3]:
node_back_index = manager.NodeToIndex(node_back)
next_node_condition = routing.NextVar(node_go_index) == node_back_index
expression = routing.solver().ConditionalExpression(next_node_condition, all_node_go_visited, 1)
routing.solver().AddConstraint(expression >= 1)

My code (first attempt):

"""Simple Pickup Delivery Problem (PDP)."""
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import numpy as np

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    _location_depot = [(4, 4)]
    _location_pickup_and_delivery = [
        (2, 0),  #1
        (7, 2),  #2
        (2, 0),  # 3
        (7, 2),  # 4
    ]

    data['pickups_deliveries'] = [
        [1, 2],
        [4, 3],
    ]

    data["locations"] = _location_depot + _location_pickup_and_delivery
    data["num_locations"] = len(_location_depot + _location_pickup_and_delivery)

    data['num_vehicles'] = 1
    data['depot'] = 0

    def create_demande():
        liste_demande = [0]
        for i in range(1, len(data["locations"])):
            demande = -1
            for j in range(len(data['pickups_deliveries'])):
                if (i == data['pickups_deliveries'][j][0]):
                    demande = 1
                liste_demande.append(demande)
        return liste_demande

    def create_distance_matrix():
        distance_matrix = np.zeros(
            (len(data["locations"]), len(data["locations"])), dtype=int)
        for i in range(len(data["locations"])):
            for j in range(len(data["locations"])):
                if i == j:
                    distance_matrix[i][j] = 0
                else:
                    distance_matrix[i][j] = manhattan_distance(
                        data["locations"][i], data["locations"][j])
                dist_matrix = distance_matrix.tolist()
        return dist_matrix

    def manhattan_distance(position_1, position_2):
        return int(
            abs(position_1[0] - position_2[0]) +
            abs(position_1[1] - position_2[1]))

    data["distance_matrix"] = create_distance_matrix()
    data['demands'] = create_demande()
    return data


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    total_distance = 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
        while not routing.IsEnd(index):
            node = manager.IndexToNode(index)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            distance = routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
            route_distance += distance
            plan_output += f' {node} --{distance}--> '
        plan_output += f'{manager.IndexToNode(index)}\n'
        plan_output += f'Distance of the route: {route_distance}m\n'
        print(plan_output)
        total_distance += route_distance
    print('Total Distance of all routes: {}m'.format(total_distance))


def main():
    """Entry point of the program."""
    # 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)

    # Define cost of each arc.
    def distance_callback(from_index, to_index):
        """Returns the manhattan 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)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

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

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

    idx2 = manager.NodeToIndex(2)
    idx4 = manager.NodeToIndex(4)
    routing.solver().Add(
            distance_dimension.CumulVar(idx2) <=
            distance_dimension.CumulVar(idx4))

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)

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

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("solution not found!")


if __name__ == '__main__':
    main()

à or-tools-discuss

I tried also to model with a dimension counting the first pickup and delivery.
And saying you back pickup/delivery can't be done until all the first pickup/delivery are done.
But it didn't work either....
Any Help would be greatly appreciated..

def nb_node_go_visited_callback(from_index):
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
if (from_node in [1,2]):
return 1
else:
return 0

nb_node_go_visited_callback_index = routing.RegisterUnaryTransitCallback(
nb_node_go_visited_callback)
routing.AddDimensionWithVehicleCapacity(
nb_node_aller_visited_callback_index,
0, # null capacity slack
[2], # vehicle maximum capacities
True, # start cumul to zero
'NBNodeGo')


nb_node_visited_go_dimension = routing.GetDimensionOrDie('NBNodeGo')
nb_node_go = 2 # [1,2]
for node_go in [1,2]:
node_aller_index = manager.NodeToIndex(node_go)
all_node_go_visited = nb_node_visited_go_dimension.CumulVar(node_go) == nb_node_go # nb max allé
for node_back in [4,3]:
node_back_index = manager.NodeToIndex(node_back)
next_node_condition = routing.NextVar(node_go_index) == node_back_index
expression = routing.solver().ConditionalExpression(next_node_condition, all_node_go_visited, 1)
routing.solver().AddConstraint(expres
sion >= 1)

[lperron]

This is not an issue. I moved this to discussion.
Note that these have limited audience. I recommend closing this and using the mailing list.

[Mizux]

your code is not properly indented we can't even copy paste and test it locally -_-
EDIT: I'll edit your question to fix it...DONE

[Mizux]

Fixed using

    # Create counter dimension
    def counter_callback(from_index):
        return 1

    counter_callback_index = routing.RegisterUnaryTransitCallback(counter_callback)
    # Add Counter constraint.
    name = 'Counter'
    routing.AddDimension(
        counter_callback_index,
        0,  # no slack
        10,  # vehicle maximum travel distance
        True,  # start cumul to zero
        name)
    counter_dimension = routing.GetDimensionOrDie(name)

    idx2 = manager.NodeToIndex(2)
    idx4 = manager.NodeToIndex(4)
    routing.solver().Add(
            counter_dimension.CumulVar(idx2) <=
            counter_dimension.CumulVar(idx4))

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
        #routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)

You had two issues:

• PARALLEL_CHEAPEST_INSERTION didn't manage to find a solution so replace it by PATH_CHEAPEST_ARC
  side note: So as a remember when you didn't get any first solution try few other first strategy heuristics...
• Since node 2 and 4 are at the same location distance(2, 4) == 0 so solver keep putting 4 before 2 and still respect
  routing.solver().Add(distance_dimension.CumulVar(idx2) <= distance_dimension.CumulVar(idx4)), the trick here is to use a counter dimension or whatever so each time you visit a node the cumulVar strictly increase (here +1) so now solver is "forced" to place visit of 2 before 4...