立方体利用率和装箱

堆放：每辆拖车中的 3D 几何

北美标准托盘是48 英寸 x 40 英寸（GMA 托盘）。这是物流几何的基本单位。

立方体利用率衡量填充空间的效率：实际产品体积除以可用体积。按重量装满但体积半空的拖车立方体利用率差。装至天花板的拖车立方体利用率优异。

纵堆：每层相同，盒子直接堆放在彼此上方。结构脆弱但空间利用效率高。

交错（风车）堆放：交替层旋转 90 度。稳定性更强但在边缘产生空隙，浪费 5-15% 的托盘面积。

装箱是真正的几何挑战：将各种尺寸的矩形盒子装入 40 英尺集装箱（内部尺寸约 39'5" x 7'8" x 7'10"）。这是3D 装箱：计算机科学中经典的 NP 困难问题之一。没有算法能在合理时间内保证大规模实例的最优解。

实际上，物流公司使用启发式方法：最大的物品优先、先填充楼面积再堆高、按目的地分组以便卸货效率。

托盘装载效率

您需要将尺寸为 12 英寸长、10 英寸宽、8 英寸高的盒子装到标准 48" x 40" 托盘上。最大堆放高度为 48 英寸。

为什么路线优化变得困难

旅行商问题 (TSP)

假设您必须访问 10 个客户并返回您的仓库。最短路线是什么？这是旅行商问题：数学和计算机科学中研究最多的问题之一。

困难是组合爆炸。对于 N 个停靠点，有 (N-1)!/2 条唯一路线（除以 2 是因为顺时针和逆时针的距离相同）。

- 5 个停靠点：12 条路线：在毫秒内检查所有路线

- 10 个停靠点：181,440 条路线：对计算机仍可管理

- 15 个停靠点：436 亿条路线：需要数小时

- 20 个停靠点：60.8 千万亿条路线：需要数个世纪

- 50 个停靠点：路线数超过可观测宇宙中的原子数

TSP 是 NP 困难的：没有已知的算法能在多项式时间内解决它。当 N 增长时，精确解变得不可能，我们必须使用启发式方法：快速找到良好（但不保证最优）解的算法。

常见启发式方法：

- 最近邻：从当前位置，始终去最近的未访问停靠点。快速但通常产生带有丑陋十字交叉的路线。

- 凸包插入：从最外层停靠点开始（凸包：几何边界）。然后逐个插入内部停靠点，使其增加的距离最少。

- 2-opt 改进：采用已完成的路线并尝试交换边对。如果移除两条边并以不同方式重新连接使路线更短，则保留交换。重复直到找不到改进。

启发式方法与精确解

一家配送公司今天有 12 个停靠点。他们的司机使用最近邻启发式方法：在每个点，驾驶到最近的未访问停靠点。

区域、密度和车辆路线问题

最后一公里配送：几何与经济学相遇的地方

最后一公里：从配送中心到客户门口：占总运费的 40-50%。这是供应链中几何约束最大的部分。

从仓库的辐射路线：配送车从中央配送中心扇形分散。每辆车的路线应覆盖一个紧凑的地理区域：没有两辆车应该互相穿过彼此的领地。

配送密度决定一切。在密集的城市地区，一辆车在 8 小时班次内可能进行 150 次配送。在农村地区，同一辆车可能管理 20-30 次。几何原因：城市停靠点靠近（停靠点之间的短驾驶），而农村停靠点距离远。

基于区域的路线将服务区域划分为地理群。每个区域分配给一辆车。好的区域是紧凑的（大致圆形或正方形）& 连续的（无间隙或孤立的口袋）。目标：最小化总距离，同时保持每条路线在时间/容量限制内。

车辆路线问题 (VRP) 将 TSP 推广到多辆车。给定仓库、N 个客户 & K 辆车（每辆都有容量和时间限制），将客户分配给车并排序每辆车的路线以最小化总距离。VRP 也是 NP 困难的。

设计良好的区域地图创建路线，其中每个司机的路径形成紧凑的几何形状：从仓库延伸的粗圆形或叶片形。如果您看到一条自己穿过或与另一个司机区域重叠的路线，路线设计效率低下。

区域设计

一家配送公司从城市中心的仓库运营。他们有 4 名司机和 200 次配送分散在一个大致圆形的服务区域，半径为 10 英里。