입방 이용률 및 빈 패킹

적재: 모든 트레일러의 3D 기하학

북미의 표준 팔레트는 가로 48인치 × 세로 40인치(GMA 팔레트)입니다. 이는 물류 기하학의 기본 단위입니다.

입방 이용률은 공간을 얼마나 효율적으로 채우는지 측정합니다: 실제 제품 부피를 사용 가능한 부피로 나눕니다. 무게로는 가득 찬 트레일러이지만 부피로는 절반이 비어있으면 입방 이용률이 나쁩니다. 천장까지 꽉 찬 트레일러는 우수한 입방 이용률을 가집니다.

열 적재: 각 층이 동일하며 상자가 서로 직접 위에 있습니다. 구조적으로 약하지만 공간을 효율적으로 사용합니다.

인터로킹(핀휠) 적재: 교대로 회전하는 층. 훨씬 더 안정적이지만 팔레트 가장자리에 간격을 만들어 5-15% 낭비합니다.

컨테이너 로딩은 실제 기하학적 과제입니다: 다양한 크기의 직사각형 상자를 40피트 배송 컨테이너(내부 치수 약 39'5" × 7'8" × 7'10")에 맞추기. 이것은 3D 빈 패킹: 컴퓨터 과학의 고전적인 NP-하드 문제 중 하나입니다. 어떤 알고리즘도 대규모 인스턴스에서 합리적인 시간에 최적 솔루션을 보장할 수 없습니다.

실제로 물류 회사는 휴리스틱 접근 방식을 사용합니다: 가장 큰 항목부터 먼저, 높이를 쌓기 전에 바닥 면적 채우기, 배송 효율성을 위해 목적지별로 항목 그룹화.

팔레트 로딩 효율

길이 12인치, 너비 10인치, 높이 8인치인 상자를 표준 48" × 40" 팔레트에 로드해야 합니다. 최대 스택 높이는 48인치입니다.

경로 최적화가 어려워지는 이유

외판원 문제(TSP)

10명의 고객을 방문하고 배송센터로 돌아와야 한다고 가정합니다. 가장 짧은 경로는 무엇일까요? 이것은 외판원 문제: 수학과 컴퓨터 과학에서 가장 많이 연구된 문제 중 하나입니다.

어려움은 조합 폭발입니다. N개의 정류장에 대해 (N-1)!/2개의 고유 경로가 있습니다 (시계 방향과 반시계 방향이 같은 거리이므로 2로 나누기).

- 5개 정류장: 12개 경로: 밀리초 단위로 모두 확인

- 10개 정류장: 181,440개 경로: 컴퓨터에서도 여전히 관리 가능

- 15개 정류장: 43.6억 경로: 몇 시간 소요

- 20개 정류장: 60.8조 경로: 몇 세기 소요

- 50개 정류장: 관찰 가능한 우주의 원자보다 더 많은 경로

TSP는 NP-하드: 다항식 시간에 이를 풀 수 있는 알려진 알고리즘이 없습니다. N이 증가함에 따라 정확한 솔루션은 불가능해지고 휴리스틱을 사용해야 합니다: 좋은(최적이 보장되지는 않음) 솔루션을 빠르게 찾는 알고리즘.

일반적인 휴리스틱:

- 가장 가까운 이웃: 현재 위치에서 항상 가장 가까운 방문하지 않은 정류장으로 이동합니다. 빠르지만 종종 못생긴 교차 경로를 생성합니다.

- 볼록 껍질 삽입: 가장 바깥쪽 정류장(볼록 껍질: 기하학적 경계)으로 시작합니다. 그 다음 내부 정류장을 한 번에 하나씩 삽입하여 가장 적은 거리를 추가하는 곳에 삽입합니다.

- 2-opt 개선: 완성된 경로를 가져와 간선 쌍 교환을 시도합니다. 두 간선을 제거하고 다르게 재연결하면 경로가 더 짧아집니다. 더 이상 개선이 없을 때까지 반복합니다.

휴리스틱 대 정확한 솔루션

배송 회사는 오늘 12개 정류장을 가지고 있습니다. 운전사는 가장 가까운 이웃 휴리스틱을 사용합니다: 각 지점에서 가장 가까운 방문하지 않은 정류장으로 운전합니다.

구역, 밀도, 및 차량 라우팅 문제

라스트마일 배송: 기하학이 경제학과 만나는 곳

라스트마일: 배송센터에서 고객의 문까지: 총 배송 비용의 40-50%를 차지합니다. 이는 공급망에서 가장 기하학적으로 제약된 부분입니다.

배송센터로부터의 방사형 경로: 배송 트럭이 중앙 배송센터에서 방사형으로 퍼집니다. 각 트럭의 경로는 컴팩트한 지리적 구역을 커버해야 합니다: 두 트럭이 서로의 영역을 교차해서는 안 됩니다.

배송 밀도는 모든 것을 결정합니다. 밀도가 높은 도시 지역에서 트럭은 8시간 교대 근무 중에 150개의 배송을 할 수 있습니다. 시골 지역에서는 같은 트럭이 20-30개를 관리할 수 있습니다. 기하학적 이유: 도시 정류장은 서로 가깝고(정류장 사이의 운전이 짧음) 시골 정류장은 멀리 떨어져 있습니다.

구역 기반 라우팅은 서비스 지역을 지리적 클러스터로 나눕니다. 각 구역은 하나의 차량에 할당됩니다. 좋은 구역은 컴팩트하고(대략 원형 또는 사각형) 연속적입니다(간격이나 고립된 주머니 없음). 목표: 각 경로를 시간/용량 제한 내로 유지하면서 총 거리를 최소화하기.

차량 라우팅 문제(VRP)는 TSP를 여러 차량으로 일반화합니다. 배송센터, N개의 고객, & K개의 트럭(각각 용량 & 시간 제약)이 주어지면 고객을 트럭에 할당하고 각 트럭의 경로를 순서대로 배열하여 총 거리를 최소화합니다. VRP도 NP-하드입니다.

잘 설계된 구역 지도는 각 운전사의 경로가 컴팩트한 기하학적 모양을 형성하는 경로를 만듭니다: 배송센터에서 연장되는 대략 원형 또는 엽상 모양. 배송센터에서 자신의 길을 교차하거나 다른 운전사의 구역과 겹치는 경로를 보면 라우팅이 비효율적입니다.

구역 설계

배송 회사는 도시 중심의 배송센터에서 운영합니다. 그들은 4명의 운전사와 10마일 반경의 대략 원형 서비스 지역에 퍼져있는 200개의 배송을 가지고 있습니다.