物流网络优化算法如何提升包裹运输效率

某中心运输服务的中间里程团队开发路由解决方案，以最高效的方式将客户订单从其供应商和履约中心移动到分拣中心、航空设施和配送站网络。

过去五年中，该团队在帮助实现日益雄心勃勃的目标方面发挥了关键作用——从Prime会员的两日和一日送达，到Prime Now等服务的一小时送达窗口。近期，国际运筹学与分析专业协会授予某中心2021年INFORMS奖，以表彰这些成就。

极其复杂的问题

考虑到确定最优路由决策涉及的大量变量，复杂性是中间里程团队的常态。

对于每个客户订单，路由算法必须确定通过网络移动产品的最佳路径，在供应商、履约中心、分拣设施和配送站之间快速、安全且经济高效地送达客户。

算法必须评估每种运输方式（陆运、铁路、空运或海运）的优势，并确定最有效的路线。算法还确定将订单发送到可分拣并移交配送的设施的最优或接近最优路线。最后，所有时间表必须以优化安全性并符合政府规定（如休息时间、服务时间和其他要求）的方式设计。

“我们的卡车网络单独就呈现了超过10^88种可能的路由解决方案，”中间里程研究与优化总监Tim Jacobs表示，“考虑到可见宇宙中的原子数量为10^82，这是一个特别大的数字。”

而这仅仅是卡车网络。

2016年，Mauricio Resende是中间里程团队中仅有的几位科学家之一——此后这一数字已显著增长。

“2016年，某中心的陆运路由决策使用基本的本地搜索算法，”Resende说，“负载是预先分配的。该过程基本上是迭代的，我们每周对算法进行小幅改进。”

关键的是，为了自动化路由决策，算法和系统需要考虑对路由决策产生深远影响的不同约束和输入，例如各国监管机构的细微差别。

系统还需要通过考虑运营时间或是否需要停车位等因素来了解每个设施的存储和吞吐量约束。因此，团队努力建模并消除这些系统盲点。

“在设计路由时间表时，我们开发了更高级的数据结构和算法技术来解释这些约束，”Resende说。

Resende提供了某中心中间里程研究团队设计的序列评估器示例。该评估器旨在帮助为预定目标函数（如成本或空载行程数）找到最有效的路由解决方案。

评估器计算所呈现路线的成本。它持续处理对路线的可能更改，直到找到接近最优的路线。然后扰动该解决方案——故意消除路线并将新交付输入算法。然后重复该任务。通过这种方式，算法逐步朝着迭代更好的解决方案前进。

通过此类方法，Resende及其同事研究人员显著降低了陆运成本。

“当处理如此大的可能性宇宙时，必须极其高效地表述问题，”Resende说，“然后必须高效地设计算法来解决该问题的表述。”

Nilay Noyan于2019年9月加入公司担任首席研究科学家。

“广义上讲，航空路由问题与陆运网络类似，”Noyan说，“然而，航空公司存在完全不同的约束。”

这些包括监管约束、采购飞机的交付时间、燃料价格波动的影响以及管理航空公司合同所需的资源。航班时间表设计还需要确保有足够的时间进行例行线路维护、飞机加油以及包裹装卸。

到达和离开时间必须与可用容量和资源对齐，以确保包裹按时处理。更复杂的是，航空公司时间表必须与陆运网络的时间表对齐，以便有卡车在地面等待将包裹运送到下一个目的地。

过去四年中，中间里程规划研究与优化科学团队开发并实施了十多个优化和机器学习模型来构建和运营航空运输网络。这些工具帮助团队在航班时间表设计、燃料管理、包裹流规划、维护计划和中断恢复等领域做出最优决策。

Noyan表示机器学习在帮助中间里程团队解决本质上随机或不可预测的问题方面也发挥着重要作用。

“在因天气、计划外维护和机组相关延误导致意外中断事件的情况下，执行计划的偏差是不可避免的，”Noyan说，“基于机器学习的预测方法帮助我们应对这些意外情况，并快速适应，以便能够履行对客户的交付承诺。”

除了帮助适应不可预测的事件外，Jacobs认为机器学习在帮助更有效地统一陆运、空运、铁路和海运网络世界方面发挥着越来越重要的作用，无论是网络设计还是运营当日。

“我们以客户为中心进行反向工作，”他说，“我们不单独考虑每种运输模式，这在行业中很常见。相反，我们不断努力有效地结合这些领域，以便规划网络和运营网络的方式保持一致。”