지상 계획 최적화
창고 레이아웃: 저장 및 이동성 지오포메트리
창고는 지오포메트리 최적화 문제입니다. 모든 제곱 фут은 저장(제품을 보관하는 레일) 또는 이동성(사람과 포크리프트를 위한 계단형)이거나 이동성입니다. 트레이드오프는 기본적입니다: 더 넓은 계단형은 이동이 쉬워지지만 저장 공간이 줄어듭니다. 더 좁은 계단형은 더 많은 저장 공간이 있지만 특화된(및 비싼) 장비가 필요합니다.
표준 계단형 폭:
- Conventional forklift: 11-13 feet (포크리프트는 패렛을 들고 있는 공간이 필요합니다)
- Reach truck: 8-10 feet (암이 레일로 확장하여 패렛에 도달합니다)
- Very narrow aisle (VNA): 5-6 feet (비싼但저장 공간을 최대로 활용하는 특화된 터렛 트럭)
Pick path strategies: 작업자 who collects items that follow the geometric route:
- S-pattern (serpentine): 모든 계단형에 들어가, 그 전체 길이로 이동, 다른 쪽 끝에서 나감. 간단하지만 필요한 아이템이 있는 계단형을 모두 방문합니다.
- Largest gap: 필요한 아이템을 수거하는 데만 들어가는 계단형. 계단형 내에서 picks 사이의 가장 큰 간격에서 돌아서 전체 길이로 이동하지 않습니다.
- Cross-dock: 수거에서 배송으로 직행하는 아이템에 대해: 저장을 완전히 피합니다. 크로스도크 레이아웃은 수거 및 배송 도크가 서로 대각선으로 위치하며, 그 사이에 명확한 경로가 있습니다.
저장 밀도 계산
창고는 200피트 폭과 400피트 길이(전체 80,000제곱피트)입니다. 현재 레이아웃은 12피트 계단형의 전통적인 포크리프트를 사용합니다. 레일은 각 계단형의 양쪽에 4피트 깊이(단일 패렛 깊이)로 있습니다. 레이아웃은 레일, 계단형, 레일, 계단형으로 번갈아 가며 있습니다.
각 rack-aisle-rack 단위는: 4(레일) + 12(계단형) + 4(레일) = 20피트입니다.
큐브 활용도와 빈 패킹
스택킹: 트레일러의 모든 곳에 존재하는 3D 기하학
북아메리카의 표준 파렛은 48인치 x 40인치 (GMA 파렛)입니다. 이 것이 로지스틱스 기하학의 기본 단위입니다.
큐브 활용도는 공간을 얼마나 효율적으로 채우는지를 측정합니다: 실제 제품 부피를 이용 가능 부피로 나눕니다. 무게로 채운 트레일러지만 반은 비어 있는 경우 큐브 활용도가 낮습니다. 천장까지 채운 트레일러는 최적의 큐브 활용도를 가집니다.
열기 스택킹: 각 레이어가 동일하며, 상위에 상자를 직접 쌓습니다. 구조적으로 약하지만 공간을 효율적으로 사용합니다.
교차 연결(핀휠) 스택킹: 대체로 계층이 90도 회전합니다. 더 안정적이지만 가장자리에서 공간을 낭비하므로 파렛 풋프린트의 5-15%를 잃습니다.
컨테이너 로딩은 실제로 다양한 크기의 직사각형 상자들을 40피트 컨테이너(내부 크기 약 39'5" x 7'8" x 7'10")에 맞춰 넣는 것이 기하학적 도전입니다. 이것이 컴퓨터 과학의 클래식한 NP-하드 문제 중 하나: 3D 빈 패킹입니다. 최적의 해를 합리적인 시간 내에 큰 인스턴스에 대해 보장할 수 있는 알고리즘은 없습니다.
실제로 로지스틱스 회사들은 근사치를 사용합니다: 가장 큰 물품부터 시작, 바닥 면적을 먼저 채우고 높이로 스택킹, 목적지 효율성을 위해 물품을 그룹화합니다.
파렛 로딩 효율성
12인치 길이, 10인치 폭, 8인치 높이의 상자를 표준 48" x 40" 파렛에 적재해야 합니다. 최대 스택 높이는 48인치입니다.
경로 최적화의 어려운 이유
여행 판매인 문제(TSP)
10명의 고객을 방문해야 하며 기지로 돌아가야 합니다. 가장 짧은 경로는 무엇인가요? 이것이 여행 판매인 문제입니다: 수학 및 컴퓨터 과학에서 가장 연구된 문제 중 하나입니다.
어려움은 계산적 폭발입니다. N개의 정류장일 때, (N-1)!/2개의 고유 경로가 있습니다(2로 나눠지는 것은 시계 방향과 반시계 방향이 같은 거리를 이동하기 때문).
- 5개 정류장: 12개 경로: 밀리초 내에 모두 확인 가능
- 10개 정류장: 181,440개 경로: 컴퓨터로 관리 가능
- 15개 정류장: 43.6억 개의 경로: 몇 시간 소요
- 20개 정류장: 60.8조 개의 경로: 수세기 소요
- 50개 정류장: 관측 가능한 우주에서 원자보다 더 많은 경로
TSP는 NP-완전 문제입니다: 알려진 알고리즘으로는 이 문제를 다항 시간 내에 해결할 수 없습니다. N이 증가할수록 정확한 해결책이 불가능해지며, 우리는 히루리즘을 사용해야 합니다: 빠르게 좋은(하지만 최적화된 결과가 보장되지 않는) 해결책을 찾는 알고리즘.
주요 히루리즘:
- 가장 가까운 이웃: 현재 위치에서 방문하지 않은 정류장 중 가장 가까운 곳으로 이동합니다. 빠르지만 일반적으로 불순한 교차가 포함된 경로를 생성합니다.
- convex hull insertion: 외부 정류장(Convex hull: 기하학적 경계)을 시작으로 정렬한 후, 내부 정류장을 한 번에 추가하여 최소 거리가 추가되는 곳에서 삽입합니다.
- 2-opt improvement: 완료된 경로를 취해 두 개의 엣지를 바꿔보고 경로가 더 짧아지는지 확인합니다. 두 개의 엣지를 제거하고 다시 연결하는 것이 더 짧은 경로를 만드는 경우, 변경 사항을 유지합니다. 더 이상 개선이 없는 경우 반복을 중지합니다.
히루리즘 vs 정확한 해결책
배달 회사에는 오늘 12개의 정류장이 있습니다. 운전사는 근접 이웃 휴리스틱을 사용합니다: 각 점에서 방문하지 않은 가장 가까운 정류장으로 이동합니다.
존, 밀도 및 배달 경로 문제
마일 끝 배달: 지오메트리와 경제가 만나는 곳
배달 센터에서 고객의 집까지의 마일 끝 배달: 총 배송 비용의 40-50%를 차지합니다. 공급 사슬의 가장 지오메트리적으로 제약된 부분입니다.
편도 경로로부터 분포 센터: 배달 트럭은 중앙 분포 센터에서 방사형으로 출발합니다. 각 트럭의 경로는紧凑的地理区域覆盖:两个트럭不应该相互交叉的领土。
배달 밀도는 모든 것을 결정합니다. 밀도 높은 도시 지역에서는 트럭이 한 번의 8시간 시프트 내에 150개의 배달을 수행할 수 있습니다. 반면, 농촌 지역에서는 같은 트럭이 20-30개의 배달을 수행할 수 있습니다. 지오메트리적 이유: 도시 정류장은 가까워져서 정류장 사이의 주행 거리가 짧은 반면, 농촌 정류장은 멀어져서 정류장 사이의 주행 거리가 멀어집니다.
존 기반 경로는 서비스 영역을 지오메트리 클러스터로 나눕니다. 각 존은 하나의 차량에 할당됩니다. 좋은 존은 밀집 (주로 원형 또는 사각형) 및 연속 (격자 또는 고립된 포켓이 없는)입니다. 목표: 총 거리를 최소화하면서 각 경로가 시간/용량 제한 내에 있도록 합니다.
차량 경로 문제 (VRP)는 TSP을 여러 차량으로 일반화합니다. 기지, N명의 고객, 및 K대의 트럭(각각의 용량 및 시간 제한)을 주어, 고객을 트럭에 할당하고 각 트럭의 순서를 결정하여 총 거리를 최소화합니다. VRP는 또한 NP-hard입니다.
효율적으로 설계된 영역 지도는 각 운전자 경로가 기지에서 연장되는 밀집 기하학적 형태를 만듭니다: 원이나 돌출부의 형태를 가진 약한 원형. 만약 당신이 다른 운전자 영역과 겹치는 것을 포함하여 경로가 자기 자신을 번갈아 가며 이동한다면, 라우팅은 비효율적입니다.
영역 디자인
도시 중심에 기지에서 운영되는 배송 회사があり, 4명의 운전자와 200개의 배송이 약 10마일 반지름의 원형 서비스 영역에 분포하고 있습니다.