Path Planning

Plan efficient pick paths through warehouse aisles using various routing strategies.

Installation

pip install numpy networkx

Quick Start

# Pick locations in aisle-position format
pick_list = [
    {'sku': 'A001', 'aisle': 1, 'position': 10},
    {'sku': 'B002', 'aisle': 3, 'position': 25},
    {'sku': 'C003', 'aisle': 1, 'position': 30},
    {'sku': 'D004', 'aisle': 2, 'position': 15}
]

# Apply S-shape routing
route = s_shape_routing(pick_list, num_aisles=5, aisle_length=50)

Routing Strategies

S-Shape (Serpentine) Routing

def s_shape_routing(pick_list, aisle_length):
    """
    S-shape routing: traverse entire aisle if it contains picks.
    Simple but not always optimal.
    """
    # Group picks by aisle
    aisles = {}
    for pick in pick_list:
        aisle = pick['aisle']
        if aisle not in aisles:
            aisles[aisle] = []
        aisles[aisle].append(pick)

    # Sort aisles
    sorted_aisles = sorted(aisles.keys())

    route = []
    current_end = 'front'  # Start at front of warehouse

    for i, aisle in enumerate(sorted_aisles):
        picks = sorted(aisles[aisle], key=lambda p: p['position'])

        if current_end == 'front':
            # Enter from front, exit at back
            route.extend(picks)
            current_end = 'back'
        else:
            # Enter from back, exit at front
            route.extend(reversed(picks))
            current_end = 'front'

    return route

Return Routing

def return_routing(pick_list, aisle_length):
    """
    Return routing: enter and exit each aisle from the same end.
    Picker returns to front after visiting each aisle.
    """
    aisles = {}
    for pick in pick_list:
        aisle = pick['aisle']
        if aisle not in aisles:
            aisles[aisle] = []
        aisles[aisle].append(pick)

    route = []
    for aisle in sorted(aisles.keys()):
        picks = sorted(aisles[aisle], key=lambda p: p['position'])
        # Go to furthest pick and return
        route.extend(picks)

    return route

def return_routing_distance(pick_list, aisle_length, aisle_width):
    """Calculate total distance for return routing."""
    aisles = {}
    for pick in pick_list:
        aisle = pick['aisle']
        if aisle not in aisles:
            aisles[aisle] = []
        aisles[aisle].append(pick['position'])

    total_distance = 0
    sorted_aisles = sorted(aisles.keys())

    for i, aisle in enumerate(sorted_aisles):
        # Travel to aisle
        if i > 0:
            total_distance += aisle_width * (aisle - sorted_aisles[i-1])

        # Travel to furthest pick and back
        max_position = max(aisles[aisle])
        total_distance += 2 * max_position

    return total_distance

Largest Gap Routing

def largest_gap_routing(pick_list, aisle_length):
    """
    Largest gap: enter/exit from end closest to picks,
    but traverse entire aisle if gap is smaller than returning.
    """
    aisles = {}
    for pick in pick_list:
        aisle = pick['aisle']
        if aisle not in aisles:
            aisles[aisle] = []
        aisles[aisle].append(pick)

    route = []
    current_end = 'front'

    for aisle in sorted(aisles.keys()):
        picks = sorted(aisles[aisle], key=lambda p: p['position'])
        positions = [p['position'] for p in picks]

        # Calculate gaps
        front_gap = positions[0]  # Gap from front to first pick
        back_gap = aisle_length - positions[-1]  # Gap from last pick to back

        # Find largest internal gap
        max_internal_gap = 0
        gap_position = -1
        for i in range(len(positions) - 1):
            gap = positions[i + 1] - positions[i]
            if gap > max_internal_gap:
                max_internal_gap = gap
                gap_position = i

        largest_gap = max(front_gap, back_gap, max_internal_gap)

        if largest_gap == front_gap:
            # Enter from back
            route.extend(reversed(picks))
            current_end = 'front'
        elif largest_gap == back_gap:
            # Enter from front
            route.extend(picks)
            current_end = 'back'
        else:
            # Split at largest internal gap
            if current_end == 'front':
                route.extend(picks[:gap_position + 1])
            else:
                route.extend(reversed(picks[gap_position + 1:]))

    return route

Midpoint Routing

def midpoint_routing(pick_list, aisle_length):
    """
    Midpoint: divide each aisle at midpoint, serve each half from nearest end.
    """
    midpoint = aisle_length / 2

    aisles = {}
    for pick in pick_list:
        aisle = pick['aisle']
        if aisle not in aisles:
            aisles[aisle] = {'front': [], 'back': []}

        if pick['position'] <= midpoint:
            aisles[aisle]['front'].append(pick)
        else:
            aisles[aisle]['back'].append(pick)

    route = []

    # First pass: front half of all aisles
    for aisle in sorted(aisles.keys()):
        picks = sorted(aisles[aisle]['front'], key=lambda p: p['position'])
        route.extend(picks)

    # Second pass: back half of all aisles (in reverse order)
    for aisle in sorted(aisles.keys(), reverse=True):
        picks = sorted(aisles[aisle]['back'], key=lambda p: -p['position'])
        route.extend(picks)

    return route

Optimal Routing (Dynamic Programming)

def optimal_aisle_routing(picks_in_aisle, aisle_length, entry_end):
    """
    Optimal routing within a single aisle using DP.
    Returns best route and ending position.
    """
    if not picks_in_aisle:
        return [], entry_end, 0

    positions = sorted([p['position'] for p in picks_in_aisle])
    picks_map = {p['position']: p for p in picks_in_aisle}

    if entry_end == 'front':
        entry_pos = 0
    else:
        entry_pos = aisle_length

    # Option 1: Enter, collect all, exit same side
    dist_return = 2 * (max(positions) if entry_end == 'front'
                       else aisle_length - min(positions))

    # Option 2: Enter, collect all, exit other side
    dist_through = aisle_length

    if dist_return <= dist_through:
        if entry_end == 'front':
            route = [picks_map[p] for p in positions]
        else:
            route = [picks_map[p] for p in reversed(positions)]
        return route, entry_end, dist_return
    else:
        if entry_end == 'front':
            route = [picks_map[p] for p in positions]
            return route, 'back', dist_through
        else:
            route = [picks_map[p] for p in reversed(positions)]
            return route, 'front', dist_through

Route Evaluation

def calculate_route_metrics(route, aisle_width, depot_position=(0, 0)):
    """Calculate metrics for a picking route."""
    total_distance = 0
    current_aisle = 0
    current_position = 0

    # Distance from depot to first pick
    first = route[0]
    total_distance += aisle_width * first['aisle'] + first['position']

    for i in range(1, len(route)):
        prev = route[i - 1]
        curr = route[i]

        if prev['aisle'] == curr['aisle']:
            total_distance += abs(curr['position'] - prev['position'])
        else:
            total_distance += aisle_width * abs(curr['aisle'] - prev['aisle'])
            total_distance += abs(curr['position'] - prev['position'])

    # Return to depot
    last = route[-1]
    total_distance += aisle_width * last['aisle'] + last['position']

    return {
        'total_distance': total_distance,
        'num_picks': len(route),
        'aisles_visited': len(set(p['aisle'] for p in route)),
        'distance_per_pick': total_distance / len(route)
    }