vrp-backhauls

name

vrp-backhauls

description

When the user wants to solve VRP with Backhauls (VRPB), optimize routes with both deliveries and pickups, or handle reverse logistics. Also use when the user mentions "VRPB," "backhaul optimization," "linehaul and backhaul," "delivery and pickup routes," "reverse logistics," or "return pickups." Backhauls are pickups that occur AFTER all deliveries on a route. For paired pickup-delivery, see pickup-delivery-problem.

Vehicle Routing Problem with Backhauls (VRPB)

You are an expert in the Vehicle Routing Problem with Backhauls and reverse logistics optimization. Your goal is to help design efficient routes where vehicles make deliveries first (linehauls) and then pick up goods on the return trip (backhauls), maximizing vehicle utilization and minimizing empty miles.

Initial Assessment

Before solving VRPB instances, understand:

1. Backhaul Characteristics

   • Strict sequence (all deliveries before all pickups)?
   • Mixed linehauls and backhauls allowed?
   • Can a customer have both delivery AND pickup?

2. Capacity Considerations

   • Same vehicle capacity for deliveries and pickups?
   • How does capacity work? (delivery reduces load, pickup increases)
   • Can vehicle be fully loaded with pickups after emptying deliveries?

3. Customer Types

   • Linehaul customers (delivery only)
   • Backhaul customers (pickup only)
   • Mixed customers (both delivery and pickup)
   • Number of each type?

4. Business Context

   • Return of empty containers/pallets?
   • Reverse logistics (returns, recycling)?
   • Supply redistribution between locations?
   • Waste collection after deliveries?

5. Problem Scale

   • Small (< 50 customers): Exact methods possible
   • Medium (50-200): Advanced heuristics
   • Large (200+): Metaheuristics required

---

Mathematical Formulation

VRPB with Sequential Constraint

Sets:

• V = {0} ∪ L ∪ B: Nodes (0 = depot, L = linehaul, B = backhaul customers)
• K: Vehicles

Parameters:

• c_{ij}: Cost/distance from i to j
• d_i: Delivery quantity at linehaul customer i ∈ L
• p_j: Pickup quantity at backhaul customer j ∈ B
• Q: Vehicle capacity

Decision Variables:

• x_{ijk} ∈ {0,1}: 1 if vehicle k travels from i to j
• u_{ik} ∈ ℝ: Load on vehicle k after visiting node i

Objective:

Minimize: Σ_{k∈K} Σ_{i∈V} Σ_{j∈V} c_{ij} * x_{ijk}

Constraints:

1. Each customer visited exactly once:
   Σ_{k∈K} Σ_{i∈V, i≠j} x_{ijk} = 1,  ∀j ∈ L ∪ B

2. Flow conservation:
   Σ_{i∈V} x_{ihk} = Σ_{j∈V} x_{hjk},  ∀h ∈ V, ∀k ∈ K

3. Capacity constraint:
   Σ_{i∈L} d_i * Σ_{j∈V} x_{ijk} ≤ Q,  ∀k ∈ K (deliveries)
   Σ_{j∈B} p_j * Σ_{i∈V} x_{ijjk} ≤ Q,  ∀k ∈ K (pickups)

4. Load tracking:
   Delivery phase: u_{jk} = u_{ik} - d_j (load decreases)
   Pickup phase: u_{jk} = u_{ik} + p_j (load increases)

5. Precedence (all linehauls before backhauls):
   If x_{ijk} = 1 and i ∈ L, j ∈ B, then
   all linehaul customers must be visited before j

6. Subtour elimination

7. Binary variables:
   x_{ijk} ∈ {0,1}

---

Classical Heuristics

1. Sequential Cluster-Route for VRPB

import numpy as np

def vrpb_cluster_route(coordinates, linehaul_demands, backhaul_demands,
                      vehicle_capacity, num_vehicles, depot_idx=0):
    """
    Cluster-then-route heuristic for VRPB

    Phase 1: Cluster customers geographically
    Phase 2: Within each cluster, sequence linehauls then backhauls
    Phase 3: Optimize sequences

    Args:
        coordinates: all location coordinates
        linehaul_demands: delivery demands (0 for backhaul-only customers)
        backhaul_demands: pickup demands (0 for linehaul-only customers)
        vehicle_capacity: vehicle capacity
        num_vehicles: number of vehicles
        depot_idx: depot index

    Returns:
        solution dictionary
    """
    n = len(coordinates)
    depot = coordinates[depot_idx]

    # Identify customer types
    linehaul_customers = [i for i in range(n)
                         if i != depot_idx and linehaul_demands[i] > 0]
    backhaul_customers = [i for i in range(n)
                         if i != depot_idx and backhaul_demands[i] > 0]

    print(f"Linehaul customers: {len(linehaul_customers)}")
    print(f"Backhaul customers: {len(backhaul_customers)}")

    # Distance matrix
    dist_matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            dist_matrix[i][j] = np.linalg.norm(coordinates[i] - coordinates[j])

    # Sweep algorithm to create clusters
     math

     ():
        dx = point[] - depot[]
        dy = point[] - depot[]
         math.atan2(dy, dx)

    
    all_customers = linehaul_customers + backhaul_customers
    customer_angles = [(polar_angle(coordinates[c]), c)  c  all_customers]
    customer_angles.sort()

    
    routes = []
    current_route_linehauls = []
    current_route_backhauls = []
    current_linehaul_load = 
    current_backhaul_load = 

     angle, customer  customer_angles:
        is_linehaul = customer  linehaul_customers

         is_linehaul:
            demand = linehaul_demands[customer]

            
             current_linehaul_load + demand <= vehicle_capacity:
                current_route_linehauls.append(customer)
                current_linehaul_load += demand
            :
                
                 current_route_linehauls  current_route_backhauls:
                    routes.append({
                        : current_route_linehauls,
                        : current_route_backhauls
                    })

                current_route_linehauls = [customer]
                current_route_backhauls = []
                current_linehaul_load = demand
                current_backhaul_load = 
        :
            demand = backhaul_demands[customer]

            
             current_backhaul_load + demand <= vehicle_capacity:
                current_route_backhauls.append(customer)
                current_backhaul_load += demand
            :
                
                 current_route_linehauls  current_route_backhauls:
                    routes.append({
                        : current_route_linehauls,
                        : current_route_backhauls
                    })

                current_route_linehauls = []
                current_route_backhauls = [customer]
                current_linehaul_load = 
                current_backhaul_load = demand

    
     current_route_linehauls  current_route_backhauls:
        routes.append({
            : current_route_linehauls,
            : current_route_backhauls
        })

    
    optimized_routes = []

     route  routes:
        
         (route[]) > :
            linehaul_seq = [depot_idx] + route[]
            linehaul_seq = two_opt_segment(linehaul_seq, dist_matrix)
            route[] = linehaul_seq[:]  

        
         (route[]) > :
            backhaul_seq = route[] + [depot_idx]
            backhaul_seq = two_opt_segment(backhaul_seq, dist_matrix)
            route[] = backhaul_seq[:-]  

        optimized_routes.append(route)

    
    full_routes = []
    total_distance = 

     route  optimized_routes:
        full_route = [depot_idx]
        full_route.extend(route[])
        full_route.extend(route[])
        full_route.append(depot_idx)

        full_routes.append(full_route)

        
        route_distance = (dist_matrix[full_route[i]][full_route[i+]]
                            i  ((full_route)-))
        total_distance += route_distance

     {
        : full_routes,
        : optimized_routes,
        : total_distance,
        : (full_routes)
    }


 ():
    
    improved = 
    best = sequence.copy()

     improved:
        improved = 
         i  ((best) - ):
             j  (i + , (best)):
                 j - i == :
                    

                current_cost = (dist_matrix[best[i]][best[i+]] +
                              dist_matrix[best[j-]][best[j]])
                new_cost = (dist_matrix[best[i]][best[j-]] +
                           dist_matrix[best[i+]][best[j]])

                 new_cost < current_cost - :
                    best[i+:j] = (best[i+:j])
                    improved = 
                    

             improved:
                

     best

2. VRPB with OR-Tools

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

def solve_vrpb_ortools(coordinates, linehaul_demands, backhaul_demands,
                      vehicle_capacity, num_vehicles, depot=0,
                      time_limit=60):
    """
    Solve VRPB using OR-Tools

    Enforces that all linehauls are served before backhauls on each route

    Args:
        coordinates: location coordinates
        linehaul_demands: delivery demands (0 if backhaul-only)
        backhaul_demands: pickup demands (0 if linehaul-only)
        vehicle_capacity: vehicle capacity
        num_vehicles: number of vehicles
        depot: depot index
        time_limit: time limit

    Returns:
        solution dictionary
    """
    import math

    n = len(coordinates)

    # Build distance matrix
    dist_matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            dist_matrix[i][j] = math.sqrt(
                (coordinates[i][0] - coordinates[j][0])**2 +
                (coordinates[i][1] - coordinates[j][1])**2
            )

    # Identify customer types
    linehaul_only = [i for i in range(n) if linehaul_demands[i] > 0
                    and backhaul_demands[i] == 0]
    backhaul_only = [i for i in range(n) if backhaul_demands[i] > 0
                     linehaul_demands[i] == ]
    mixed = [i  i  (n)  linehaul_demands[i] > 
             backhaul_demands[i] > ]

    
    manager = pywrapcp.RoutingIndexManager(n, num_vehicles, depot)

    
    routing = pywrapcp.RoutingModel(manager)

    
     ():
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
         (dist_matrix[from_node][to_node] * )

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    

    
     ():
        from_node = manager.IndexToNode(from_index)
         (linehaul_demands[from_node])

    delivery_callback_index = routing.RegisterUnaryTransitCallback(
        delivery_demand_callback)

    routing.AddDimension(
        delivery_callback_index,
        ,  
        (vehicle_capacity),  
        ,  
        )

    
     ():
        from_node = manager.IndexToNode(from_index)
         (backhaul_demands[from_node])

    pickup_callback_index = routing.RegisterUnaryTransitCallback(
        pickup_demand_callback)

    routing.AddDimension(
        pickup_callback_index,
        ,  
        (vehicle_capacity),  
        ,  
        )

    
    
     ():
        from_node = manager.IndexToNode(from_index)
        
         from_node  backhaul_only:
             
         

    counter_callback_index = routing.RegisterUnaryTransitCallback(counter_callback)

    routing.AddDimension(
        counter_callback_index,
        ,  
        ,  
        ,  
        )

    counter_dimension = routing.GetDimensionOrDie()

    
     backhaul_customer  backhaul_only:
        index = manager.NodeToIndex(backhaul_customer)
        counter_dimension.CumulVar(index).SetMin()

    
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.seconds = time_limit

    
    solution = routing.SolveWithParameters(search_parameters)

     solution:
        routes = []
        total_distance = 

         vehicle_id  (num_vehicles):
            index = routing.Start(vehicle_id)
            route = []
            linehaul_customers = []
            backhaul_customers = []

              routing.IsEnd(index):
                node = manager.IndexToNode(index)
                route.append(node)

                 node  linehaul_only:
                    linehaul_customers.append(node)
                 node  backhaul_only:
                    backhaul_customers.append(node)

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

            route.append(manager.IndexToNode(index))

             (route) > :
                routes.append({
                    : route,
                    : linehaul_customers,
                    : backhaul_customers
                })

                
                route_distance = (dist_matrix[route[i]][route[i+]]
                                    i  ((route)-))
                total_distance += route_distance

         {
            : ,
            : routes,
            : total_distance,
            : (routes)
        }
    :
         {
            : ,
            : 
        }



 ():
    
     matplotlib.pyplot  plt

    fig, ax = plt.subplots(figsize=(, ))

    colors = plt.cm.tab10(np.linspace(, , (routes)))

     idx, route_info  (routes):
        route = route_info[]
        linehauls = route_info.get(, [])
        backhauls = route_info.get(, [])

        
        route_coords = [coordinates[i]  i  route]
        xs = [c[]  c  route_coords]
        ys = [c[]  c  route_coords]

        ax.plot(xs, ys, , color=colors[idx], linewidth=, alpha=)

        
         customer  linehauls:
            coord = coordinates[customer]
            ax.plot(coord[], coord[], , color=colors[idx],
                   markersize=, markeredgecolor=, markeredgewidth=)

        
         customer  backhauls:
            coord = coordinates[customer]
            ax.plot(coord[], coord[], , color=colors[idx],
                   markersize=, markeredgecolor=, markeredgewidth=)

    
    depot = coordinates[]
    ax.plot(depot[], depot[], , color=, markersize=,
           label=, markeredgecolor=, markeredgewidth=, zorder=)

    
    ax.plot([], [], , color=, markersize=,
           markeredgecolor=, label=)
    ax.plot([], [], , color=, markersize=,
           markeredgecolor=, label=)

    ax.set_xlabel()
    ax.set_ylabel()
    ax.set_title()
    ax.legend()
    ax.grid(, alpha=)

    plt.tight_layout()

     save_path:
        plt.savefig(save_path, dpi=, bbox_inches=)

    plt.show()



 __name__ == :
     random
    np.random.seed()
    random.seed()

    
    n_linehauls = 
    n_backhauls = 
    n_total = n_linehauls + n_backhauls +   

    coordinates = [(, )]  
    coordinates.extend(np.random.rand(n_linehauls + n_backhauls, ).tolist() * )

    
    linehaul_demands = []  
    linehaul_demands.extend([random.randint(, )  _  (n_linehauls)])
    linehaul_demands.extend([] * n_backhauls)  

    backhaul_demands = []  
    backhaul_demands.extend([] * n_linehauls)  
    backhaul_demands.extend([random.randint(, )  _  (n_backhauls)])

    vehicle_capacity = 
    num_vehicles = 

    ()
    ()
    ()

    ()
    result = solve_vrpb_ortools(coordinates, linehaul_demands, backhaul_demands,
                               vehicle_capacity, num_vehicles, time_limit=)

     result[] == :
        ()
        ()
        ()

        ()
         i, route_info  (result[]):
            route = route_info[]
            linehauls = route_info[]
            backhauls = route_info[]

            total_delivery = (linehaul_demands[c]  c  linehauls)
            total_pickup = (backhaul_demands[c]  c  backhauls)

            ()
            ()
            ()
            ()

        
        visualize_vrpb_solution(coordinates, result[],
                              linehaul_demands, backhaul_demands)
    :
        ()

---

Tools & Libraries

• OR-Tools (Google): Best for VRPB (recommended)
• PuLP/Pyomo: MIP modeling
• Custom heuristics work well for this variant

---

Common Challenges & Solutions

Challenge: Imbalanced Linehauls and Backhauls

Problem:

• Many deliveries, few pickups (or vice versa)
• Vehicles return nearly empty

Solutions:

• Allow mixed linehaul-backhaul at same customer
• Consider dedicated backhaul-only routes
• Relax sequential constraint if possible

Challenge: Strict Sequential Constraint Too Restrictive

Problem:

• Forcing all deliveries before all pickups reduces efficiency
• Could save distance by mixing

Solutions:

• Consider mixed VRPB (allows interleaving)
• See pickup-delivery-problem for more flexible variant
• Use soft penalties instead of hard constraint

Challenge: Capacity Management

Problem:

• Vehicle might be full with pickups before finishing backhauls
• Complex capacity tracking

Solutions:

• Use two-dimensional capacity in OR-Tools
• Carefully check feasibility in heuristics
• Consider vehicle with compartments

---

Output Format

VRPB Solution Report

Problem:

• Linehaul customers: 20 (deliveries)
• Backhaul customers: 15 (pickups)
• Vehicles: 5 (capacity: 100 units)

Solution:

Metric	Value
Total Distance	1,124 km
Vehicles Used	5
Total Deliveries	387 units
Total Pickups	276 units

Route Details:

Vehicle	Linehauls	Deliveries	Backhauls	Pickups	Distance
1	4	78 units	3	54 units	235 km
2	5	95 units	2	38 units	198 km
[...]

---

Questions to Ask

1. Must all deliveries occur before all pickups?
2. Can customers have both delivery and pickup?
3. What's the ratio of linehauls to backhauls?
4. Is this for reverse logistics or redistribution?
5. Are there time constraints?
6. Same vehicle capacity for deliveries and pickups?

---

Related Skills

• vehicle-routing-problem: For general VRP
• pickup-delivery-problem: For paired pickup-delivery
• capacitated-vrp: For capacity-focused routing