写点什么

用 OptaPlanner 进行车辆路线优化

  • 2022 年 10 月 09 日
    广东
  • 本文字数:1994 字

    阅读完需:约 7 分钟

用OptaPlanner进行车辆路线优化

您的系统软件是否管理着一批车辆,例如运送现场技术人员的出租车,或运送最后一公里专送包裹的快递车?您可以将车队的总体驾驶时间减少 25%,节省大量费用。提高生产力、减少排放,使用 AI 求解器能够实现自动化、优化您的车辆路线。


1、车辆路线优化视频展示

在这个案例中,我们在一个地区的中间有一个仓库,我们需要查看全国各地的许多仓库位置,就像地图上的这些点。我们想要查看的仓库位置,我们有许多车辆,如紫色、绿色、黄色、蓝色等车辆。我们需要决定每次派哪些车辆去现场勘查,需要考虑这些位置、以及派出勘查的安排顺序。这就是实际上我们可以减少这些车辆的驾驶时间的重要方式。现在这些车辆可以运送现场技术人员,他们可以在这些位置的客户家里安装例如电缆或互联网;同时这些车辆也可能运送物资,如最后一英里的交付,交付客户在网上购买的物品。


2、使用 OptaPlanner 解决车辆规划说明

这个场景中会存在很多的“硬约束”条件。首先可能有约束,比如容量约束。即某辆车在每一次派车过程中,它只能承载一定的重量和体积。考虑到冗余的容量空间,和路线等待时间等因素。我们当然要确保卡车内有足够的空间,来安排下一个到访目的地,所需要运载的物品。例如,这辆车是装甲的,已明确要派出前往这个位置。你需要有一辆装甲车,因为它是一种昂贵物品的运输。同时,如果您有技术人员要一同派出,去现场做技术保障。您可能在该特定位置需要特殊技能,当然只有具有该技能的技术人员才能前往该位置。

另一个重要的因素,是时间窗。尤其是对燃油技师而言,如果您已约好客户,需要在早上 8 点到 10 点之间,或 8 点到 12 点之间与客户一起到达指定地点。你需要确保准时到达那里,不要太早也不要太晚。


除此之外,还有一些“软约束”条件。就像某些车辆连续派出安排需要等待一天一样,当然,其中最大的软约束是您希望减少总驾驶时间,您希望使每一个分段的派出尽可能短、尽可能快,以便您用相同数量的车辆,来满足实际送达更多地点的需求。或者用更少的车辆完成相同的工作要求。让我们在这里的演示中看看它是如何工作的。我将加载比利时的一些地点,我将开始向那里发送一些运输需求。我们将尝试优化它的总行驶时间,如你所见,您可以在右上角看到,我们从 17 小时开始。但是作为 Opta Planner 内部的算法,找到越来越好的解决方案,你得到一个越来越短的实际上越来越快的路线,这通常也是一条更短的路线。因此,它不仅减少了驾驶时间,还减少了燃料消耗量,这对我们当下的环境是有益的。


因此你可以看到它已经优化了,但我能做的好事是我实际上可以做实时计划。什么是实时计划? 当客户打电话时,我们想要实时响应客户需求,并实际调整一些我们的车辆运输路径。根据需要,所以我将在一个位置点击,您会看到我们的自动规划器实时优化此位置,并在我点击更多位置时,进行自动调整。您可以看到它实际上会调整车辆路径,也会带来调整的 其他效果。调整其他路线,以尽最大可能实现优化效果。


当然在更高级的场景下,您无需做任何事情。实际上这是在实时规划,不会扰乱已经在进行规划的路线。当然,您可以中断实时规划,即进行手工规划。实际上您可以中断,并根据最新信息进行规划优化,这更好。

那你怎么实现这个场景?让我来看代码,让我告诉你.


这是在 Java 中,当然,我们可以在 Kotlin 和 Python 中做到这一点。那么它是如何工作的呢?我们定义约束条件之一,是车辆容量约束。我们不想在一辆车上装载太多重量物品, 我们要在这个约束中做的是我们要为每个计划访问说。我们将按车辆对它们进行分组,以便进行所有计划访问。我们乘坐同一辆车访问。我们将对他们进行分组,并对他们的需求求和。例如,第一次访问可能需要运载 10 吨物品,第二次访问可能需要 3 吨,那是 13 吨,这就是总需求量。在车辆上,我们将使用过滤器检查该车辆的容量,如果需求实际上大于该车辆的容量,那么在这种情况下。我们在车辆中投入更多,而车辆实际上可以处理这是一件坏事。所以我们要告诉玩家不要这样做,不要在这辆车上放置那么多运输容量,或者不要在这辆车上放置这种访问组合,我们将对其进行扣分惩罚。我们会说有 1 个硬约束被破坏,我们实际上还要指定多少。这通常很有趣,所以我们会说好的。对于每一吨容量,我们对那辆车的需求太多了。我们将实际分析它,我们会说这是车辆容量限制和非常类似的方式,您可以添加任何约束。你可以想到,通常组织总是有自己的小特殊约束,所以我们可以处理这些,我们可以添加这些,我们可以用传统的 for  循环以更简单的方式编写它。


编程,这种方法的可扩展性很强,这就是为什么它会称为增量计算 Delta。但是最优解是什么?巨大的可扩展性增益,最重要的是,它使用哈希来执行分组或连接等操作,这大大提高了求解速度。


如果你想试试这个 AI 求解器?你要做就是去 OptaPlanner 网站?然后单击 quick starts。同时在 quick starts 快速入门链接上,您只需下载 并自己尝试一下。谢谢你的聆听。

用户头像

寻觅世界最强求解器,找出人生难题最佳答案 2017.12.08 加入

OptaPlanner中文开发指南,开发好用的APS系统~

评论

发布
暂无评论
用OptaPlanner进行车辆路线优化_OptaPlanner中文_InfoQ写作社区