route optimization with precedences between pairs of nodes

Question

For my routing application I have multiple pairs of nodes which must be visited. The order the nodes in each pair is not important, but both nodes in each pair must be visited after each other. Also, I have a max_travel_distance constraint per vehicle and it is not required to visit all nodes if no optimal solution exist. Meaning that if one node in a pair needs to be dropped, both nodes in the pair must be dropped.

For instance I have three pairs: [A,B], [C,D], [E,F], two valid solutions for two vehicles could be:

(if all node pair can be covered)
1) 0->A->B->C->D->0
2) 0->F->E->0

or

(if only [A,B] is within max_travel_distance)
1) 0->A->B->0
2) 0->0

From the pickup and deliveries example I see how I can make sure that both nodes in a pair always is included in the solution. The problem is that I dont see how I can enforce a constraint so that the two nodes from the same pair always is visited directly after each other, and that the order does not matter (A->B and B->A are both ok)

import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

def calc_dmat(pairs, depot = [0,0]):
    # Distance matrix
    ncol = len(pairs)*2
    nodes = [depot] + [p for pair in Pairs for p in pair]
    dmat  = [[math.dist(c,r) for c in nodes] for r in nodes]
    return dmat

# Nodes and pairs
A = [1,1] # Coordinate
B = [1,5]
C = [3,1]
D = [3,8]
E = [6,3]
F = [6,19]

Pairs = [
    [A,B],
    [C,D],
    [E,F]
]

data = {}
data["distance_matrix"] = calc_dmat(Pairs)
data["depot"] = 0
data["num_vehicles"]=2
data["pickups_deliveries"] = [
    [1,2],
    [3,4],
    [5,6]
]

def print_solution(data, manager, routing, solution):
    if solution is None:
        print("No solution")
        return
    print(f'Objective: {solution.ObjectiveValue()}')
    # 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 += ' {}'.format(manager.IndexToNode(node))
    print(dropped_nodes)

    max_route_distance = 0
    max_route_time     = 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_time     = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(manager.IndexToNode(index))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        plan_output += '{}\n'.format(manager.IndexToNode(index))
        plan_output += 'Distance of the route: {}m\n'.format(route_distance)
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
        max_route_time = max(route_time, max_route_time)
    print('Maximum of the route distances: {}m'.format(max_route_distance))
    print('Maximum of the route time: {}m'.format(max_route_time))    

manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])
routing = pywrapcp.RoutingModel(manager)

def distance_callback(from_index, to_index):
    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,
    18,
    True,
    dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)

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

# Omit some nodes
for node in range(1,len(data["distance_matrix"])):
    routing.AddDisjunction([manager.NodeToIndex(node)], 13)

# Setting first solution heuristic.
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.
print_solution(data, manager, routing, solution)

Output:

*Objective: 25
Dropped nodes:
Route for vehicle 0:
 0 ->  3 ->  1 ->  2 ->  4 -> 0
Distance of the route: 9m

Route for vehicle 1:
 0 ->  5 ->  6 -> 0
Distance of the route: 16m

Maximum of the route distances: 16m
Maximum of the route time: 0m*

I don't see how I can add a constraint making sure both nodes from the same node is picked successively and independently of the order. A solution to this would be highly appreciated.

Answer 1

Here is another approach.

Create 2 fake nodes 'a->b' and 'b->a', do not create the nodes a and b.

Distance from any node c to 'a->b' is distance c to a. Distance from 'a->b' to any node d is distance from b to d.

Same thing for b->a.

Add 'a->b' and 'b->a' in a disjunction.

And solve.

Answer 2

Set a dimension representing rank (transit is always 1)

Link the vehicle variables of the two nodes in a pair to be equal

Add each one in a disjunction of size 1 (maybe both in a unique disjunction of size 2)

Add a precedence on the cumul variables of the 2 elements of a pair