Multiroute delivery pickup problem with multiple stops at same customer

[Steffen Spliethoff]

Hello together,

I am currently working on a delivery and pickup problem where I would like to minimize the total cost (variable cost of km driven + fixed costs of vehicles used). I would like to plan for a 7 day time horizon and therefore it may happen that a customer is delivered multiple times on different days. However, on which day the customer is delivered is not really fixed but should be flexible decided by the solver. I have time windows telling the opening hours of a customer e.g. every day in the morning. 

I have created an example but the solver gives me a solution where if I have for example 3 visits at a customer per week, it delivers 3 times immediatly after each other to customer C:

--- Vehicle 1 ---
- Main Depot: arrival time 0 (travel 0)
- Customer C (Pickup): arrival time 4 (travel 4)
- Customer C (Pickup): arrival time 4 (travel 0)
- Customer C (Pickup): arrival time 4 (travel 0)
- Customer B (Pickup): arrival time 16 (travel 12)
- Customer A (Pickup): arrival time 22 (travel 6)
- Reload Point 2: arrival time 28 (travel 6)
- Reload Point 1: arrival time 28 (travel 0)
- Customer A (Delivery): arrival time 31 (travel 3)
- Customer B (Delivery): arrival time 33 (travel 2)
- Customer C (Delivery): arrival time 38 (travel 5)
- Customer C (Delivery): arrival time 38 (travel 0)
- Customer C (Delivery): arrival time 38 (travel 0)
- Main Depot: return at 40

#!/usr/bin/env python3

# -*- coding: utf-8 -*-

from ortools.constraint_solver import pywrapcp, routing_enums_pb2

# ==== DATA MODEL ====

def create_data_model(x_hours, num_reloads):

    data = {}

    # Base node: main depot

    depot = {'name': 'Main Depot', 'coord': (4, 4)}

    # Reload points (copies of the depot)

    reloads = [

        {'name': f'Reload Point {i+1}', 'coord': depot['coord']}

        for i in range(num_reloads)

    ]

    # Existing customers with pickup and delivery coordinates

    customers = [

        ('Customer A', (2, 0), (5, 2)),

        ('Customer B', (8, 0), (7, 2)),

        ('Customer C', (3, 7), (3, 3)),

        ('Customer C', (3, 7), (3, 3)),

        ('Customer C', (3, 7), (3, 3)),

    ]

    # Build node list: depot, reloads, then for each customer a pickup & delivery node

    nodes = [depot] + reloads

    for name, pu_coord, de_coord in customers:

        nodes.append({'name': f'{name} (Pickup)', 'coord': pu_coord})

        nodes.append({'name': f'{name} (Delivery)', 'coord': de_coord})

    # Store in data model

    data['nodes'] = nodes

    data['num_nodes'] = len(nodes)

    data['depot_index'] = 0

    data['num_vehicles'] = 3

    # Time limit per trip (in same units as distance)

    data['time_limit'] = x_hours * 60

    # Pickup-delivery pairs (index pairs)

    pd_pairs = []

    start_idx = 1 + num_reloads

    for i in range(len(customers)):

        pu = start_idx + 2 * i

        de = pu + 1

        pd_pairs.append((pu, de))

    data['pd_pairs'] = pd_pairs

    return data

# ==== HELPER FUNCTION ====

def manhattan(a, b):

    """Calculates Manhattan distance between two coordinates."""

    return abs(a[0] - b[0]) + abs(a[1] - b[1])

# ==== MAIN FUNCTION ====

def main():

    # Configuration

    x_hours = 5

    num_reloads = 2

    fixed_costs = [500, 700, 900]

    # Build data

    data = create_data_model(x_hours, num_reloads)

    nodes = data['nodes']

    # Index manager and routing model

    manager = pywrapcp.RoutingIndexManager(

        data['num_nodes'], data['num_vehicles'], data['depot_index']

    )

    routing = pywrapcp.RoutingModel(manager)

    # Transit callback for travel time (using Manhattan distance)

    def time_callback(from_idx, to_idx):

        i = manager.IndexToNode(from_idx)

        j = manager.IndexToNode(to_idx)

        return manhattan(nodes[i]['coord'], nodes[j]['coord'])

    transit_cb_index = routing.RegisterTransitCallback(time_callback)

    # Add time dimension

    routing.AddDimension(

        transit_cb_index,

        0,

        data['time_limit'],

        True,

        'Time'

    )

    time_dim = routing.GetDimensionOrDie('Time')

    # Make reload points optional, resetting time when visited

    for i in range(1, 1 + num_reloads):

        idx = manager.NodeToIndex(i)

        routing.AddDisjunction([idx], 0)

    # Set fixed cost for each vehicle

    for vid, cost in enumerate(fixed_costs):

        routing.SetFixedCostOfVehicle(cost, vid)

    # Add pickup & delivery constraints

    solver = routing.solver()

    for pu, de in data['pd_pairs']:

        pu_idx = manager.NodeToIndex(pu)

        de_idx = manager.NodeToIndex(de)

        routing.AddPickupAndDelivery(pu_idx, de_idx)

        solver.Add(routing.VehicleVar(pu_idx) == routing.VehicleVar(de_idx))

        solver.Add(time_dim.CumulVar(pu_idx) <= time_dim.CumulVar(de_idx))

    # Search parameters

    search_params = pywrapcp.DefaultRoutingSearchParameters()

    search_params.first_solution_strategy = (

        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC

    )

    search_params.time_limit.seconds = 10

    # Solve

    solution = routing.SolveWithParameters(search_params)

    if not solution:

        print('No solution found!')

        return

    # Output results

    print('\n=== Solution Overview ===')

    total_time = 0

    total_cost = 0

    for vid in range(data['num_vehicles']):

        if not routing.IsVehicleUsed(solution, vid):

            continue

        print(f"\n--- Vehicle {vid+1} ---")

        index = routing.Start(vid)

        route_desc = []

        last_time = 0

        while not routing.IsEnd(index):

            node = manager.IndexToNode(index)

            name = nodes[node]['name']

            cum_time = solution.Value(time_dim.CumulVar(index))

            travel = cum_time - last_time

            route_desc.append(

                f"- {name}: arrival time {cum_time} (travel {travel})"

            )

            last_time = cum_time

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

        # End depot

        end_node = manager.IndexToNode(index)

        name = nodes[end_node]['name']

        cum_time = solution.Value(time_dim.CumulVar(index))

        route_desc.append(f"- {name}: return at {cum_time}")

        # Calculate costs

        route_time = cum_time

        cost_v = route_time + fixed_costs[vid]

        # Print detailed route

        print('\n'.join(route_desc))

        print(

            f"-> Total travel time: {route_time}, "

            f"Fixed cost: {fixed_costs[vid]}, Total cost: {cost_v}"

        )

        total_time += route_time

        total_cost += cost_v

    print(f"\n=== Overall Total Travel Time: {total_time}")

    print(f"=== Overall Total Cost: {total_cost}\n")

if __name__ == '__main__':

    main()

I would like to add a constraint that only allows a delivery of a customer once per shift (in other words, has return to the depot before deliver to the customer again). Has anyone faced something similar and/or can help me?

Really appreciate you help!

Best,

Steffen