为在家患 COVID-19 的患者送餐的本地社区

每天配送 26,000 份餐食?

如此规模的配送物流极具挑战。我们假设我们的志愿者司机每次出车能处理 15 份配给(即 30 份餐食),并为每位司机提供优化后的驾驶路线。即便如此,完成一次配送任务仍需约 1.5 至 2 小时。我们认为,每周 2 到 3 天这样的频率对志愿者来说是可持续的。

对我们而言,26,000 份餐食相当于 13,000 份配给。我们预计这将意味着大约 7,000 个停靠点(每个停靠点约 2 份配给)。假设使用志愿者司机和普通私家车进行配送,这意味着我们需要每天出动 700 名司机;但实际上,考虑到志愿者不会每天都出车,我们大约需要 2,000 名司机。

如果您能控制餐食来源(我们并不制作食物,因此对我们来说难度更大),那么您只需将地址列表按司机进行划分,然后优化每条路线即可。我们的配送量远低于您(我们预计每天 2,000 至 3,000 份餐食,约为您的十分之一),因此我们尚未自动划分地址列表。每个配送地址会被分配到一个社区,我们的调度员会手动按社区划分配送列表(这只是一个简单的电子表格排序)。随后,我们通过运行在 AWS 上的 Web 服务器优化每位司机的路线,并为每位司机提供优化后的驾驶路线(采用简单的旅行商算法)。

我们曾考虑过自动划分完整的地址列表。但目前我们尚不需要这样做,而且资金有限,因此我们希望尽量降低 AWS 和 Google Maps API 的使用成本 :slight_smile: 对于通用的多车辆路径规划问题(VRP),存在一些简单的算法解决方案,例如:

不过,鉴于如此庞大的配送量,我推测您覆盖的地理区域非常广阔,因此可能还需要考虑司机的家庭住址,这将使问题超出常规 VRP 的范畴。或许可以通过简单的启发式方法,将司机群体和配送地址划分为若干子问题,确保每个子问题中的配送点和司机都位于同一地理区域内,这样您便可以再次使用现成的 VRP 解决方案。

顺便提一下,我们使用 Google 地图的行驶时长作为点对点距离的衡量标准。

5 个赞