APS排程：车辆路径规划优化算法

编辑导语： 车辆路径规划算法在高级排程系统（APS）中，用于计算、优化发货配送计划。车辆路径规划问题（Vehicle Routing Problem，VRP）一般指的是：对一系列发货点和收货点，组织调用…

车辆路径规划算法在高级排程系统（APS）中，用于计算、优化发货配送计划。

车辆路径规划问题（Vehicle Routing Problem，VRP）一般指的是：对一系列发货点和收货点，组织调用一定的车辆，安排适当的行车路线，使车辆有序地通过它们，在满足指定的约束条件下（例如：货物的需求量与发货量、交发货时间、车辆容量限制、行驶里程限制、行驶时间限制等），力争实现一定的目标（如车辆空驶总里程最短、运输总费用最低、车辆按一定时间到达、使用的车辆数最小等）。

车辆路径规划问题还与企业的配送模式存在紧密联系，比如常规模式、取货送货模式、多车型、多仓库、多行程等。

车辆路径规划求解器引擎，需要解决带容量限制的VRP(Capacitated VRP)，多场站VRP(VRP with Multiple Depots)，带时间窗的VRP(VRP with Time Windows)，带回程的VRP(VRP with Backhauls)，多车型VRP(VRP with Heterogeneous Fleet)，取送货VRP(VRP with Pickups and Deliveries),时间依赖型VRP(Time-dependent VRP)，旅行商问题(Traveling Salesman Problem)，Dial-a-Ride问题(Dial-a-Ride Problem)，支持的复杂约束条件如上图所示。

APS智能排产系统，实现路径规划与排产计划联动，同时考虑静态的路径约束与动态的交货期约束，实现基于路径规划的生产计划模拟排程，以及基于计划执行结果的路径规划重排与调整，实现计划与路径规划的闭环滚动。

车辆路径规划算法，有非常多的算法，比如实时启发式搜索算法、基于分层路网的搜索算法、神经网络、遗传算法及模糊理论等。大多数算法应用于求解车辆路径规划问题时都会存在一定的缺陷，所以目前的研究侧重于利用多种算法融合来构造混合算法。

1、Dijkstra 算法

Dijkstra（迪杰斯特拉）算法是最短路算法的经典算法之一。该算法适于计算道路权值均为非负的最短路径问题，可以给出图中某一节点到其他所有节点的最短路径。

2、Lee 算法

Lee 算法最早用于印刷电路和集成电路的路径追踪，与 Dijkstra 算法相比更适合用于数据随时变化的道路路径规划。只要最佳路径存在，该算法就能够找到最佳优化路径。

3、Floyd 算法

Floyd 算法是是一种计算图中任意两点间的最短距离的算法。可以正确处理有向图或负权的最短路径问题，

4、启发式搜索算法—— A* 算法

启发式搜索有很多的算法，如 : 局部择优搜索法、最好优先搜索法、A* 算法等。其中 A* 算法通过引入估价函数，加快了搜索速度，提高了局部择优算法搜索的精度，是当前较为流行的最短路算法。

5、双向搜索算法

双向搜索算法在从起点开始寻找最短路径的同时也从终点开始向前进行路径搜索，最佳效果是二者在中间点汇合。

6、蚁群算法

蚁群算法是一种随机搜索算法 , 是在对大自然中蚁群集体行为的研究基础上总结归纳出的一种优化算法，而且易于与其他方法相结合。

最近更新于 2022-05-14，由 猿小六 于 2021-10-16 发布，已阅 2311 次。