什么是车辆路线问题
车辆路线问题(Vehicle Routing Problem,VRP)是一类问题的总称。它是指一定数量的客户,各自有不同数量的货物需求,配送中心向客户提供货物,由一个车队负责分送货物,组织适当的行车路线,目标是使得客户的需求得到满足,并能在一定的约束下,达到诸如路程最短、成本最小、耗费时间最少等目的。
规划问题
类似VRP这样的问题域,还有很多相似的场景,比如课程表编排,任务分配、车间调度、服务器资源优化等这样在有限资源的情况下提供符合(软/硬)条件的产品或服务。这类问题统称为规划问题(Planning Problem)。
在有限的资源和特定的约束条件下,规划问题有一个最优目标。最优目标可以是任何数量的事情,这被称为约束满足规划(Constraint Satisfaction Programming,是运筹学学科的一部分)。
约束
一个规划问题至少有两种约束:
一定不能打破硬性约束(负向的) 。例如:一个老师不能同时教两门不同的课。
如果它可以避免最好不被打破的软性约束(负向的) 。例如:A老师不喜欢在星期五下午上课。
一些问题也有正向的制约因素:
如果可能的话,应该满足一个积极的软约束(或奖励)。例如:B老师喜欢在星期一早上上课。
这些约束定义了规划问题的得分计算(又称适应度函数)。一个规划问题的每一个解决方案都可以用一个分数来评分。
规划问题的巨量搜索空间
搜索空间:因为目前针对规划问题,只能通过搜索的方式去寻找相对最优解,因为相对一些直接通过算法操作得到的办法而言,规划问题只能将它的解一个一个地对比,逐步收敛逼近的办法来得到相对最优解。所以,你可以认为规划问题的相对最优解是搜索出来的,而且每一步搜索都需要对约束进行运算;从所有经历过的解中,找到相对最优一个。所以规划问题存在一个搜索空间的问题,即有多少种可能的解,就表示搜索空间有多大。例如将3个进程分配到两个机台上,存在多少种可能?大家可以自己去算,其实就是排列组合问题。
而对实际问题时,稍复杂的约束,稍多一点的规划实体,最后得出的可能解的数量都是非常巨大的,很多问题其搜索空间轻易就是一个天文数字。所以,如果对于所有规则问题,都是使用这些暴力枚举的办法,以现有世界上的计算机的算力,很多问题是没办法找到最优解的。
规划问题的规模,即是规划实体及每个实体的规划变量的组合,例如时间、空间,及影响因素,及这些因素的所有情况组合。例如,如果上述所有实体,规划的变量和所有因素,展开后的数量是M,而一个解是对其中的N个变量进行规划,那么有多少个解呢?其实就是M到N的排列P(M->N).当遇到实际问题的,这些组合的数量就是天文数字了。
规划问题的解
可能解:一个规划问题的任意一个解都称为可能解。例如分配工人A,在1月20日晚班,到1号车间;分配工人A在1月20日晚班到2号车间;分别是两个不同的可能解,尽管它们的差别只是分配到不同的车间
可行解:可行解就是那些完全符合硬约束的解。即若存在一个解,它对任何一个硬约束都是符合的,则称这个解为可行解。可行解是可能解的一个子集。可行解是可验证的,只要根据目前所有的硬约束,对解中的每一个规划实体中的每个规划变量,逐一核对,看是否符合所有硬约束,如果符合,那就表示这个解是可行解
相对最优解:上面已经提到,规划问题的搜索空间非常巨量,大多数情况下是不可能计算并比较所有解的值,再取得最佳方案(这个解就是绝对最优解)的。那以在我们固定的时间内找到的最优方案,就是称作相对最优解了。
绝对最优解:同样的上面提到,就是所有可能解中最优的那个解,目前是没有直接确定的算法,通过运算在合理的时间内去找到一个问题的绝对最优解的,所以要得到绝对最优解,只有一个办法,就是将所有可能解都遍历一次才能找到。当问题规模不算大的时候,以目前的CPU速度还是能实现的。但如果问题稍复杂一点,规划实体和规划变量稍多一点,那么可能解的数量就是一个天文数字了,这种情况下是没办法完全遍历的。所以,在我们现实中,我们是无法得到绝对最优解的。其实更贴切地说,我们所得到的相对最优解,我们不知道它是不是绝对最优解。因为现在数学上还没有办法(除了遍历)证明一个相对最优解是否绝对最优。
车辆路线规划
了解了规划问题及规划问题求解的基础后我们重回主题,到底如何解决车辆路线问题。
我们再看一看VRP的定义:车辆路线规划是基于一个或多个仓库的车队必须为地理上分散的城市或客户确定一组路线。VRP的目标是为一组已知需求的客户提供起始和终止于一个仓库的最低成本的车辆路线。
然后我们将VRP套入规划问题的公式,在有限的资源和特定的约束条件下,规划问题有一个最优目标。
资源:车辆、仓库、配送点等
限制:车辆载货量、仓库/配送点时间窗口(允许配送的时间段)、路线配送总需求等
目标:使用最少的车辆在最少的时间/最短路线完成配送
VRP的不同变种
车辆路线规划问题在物流领域和生产领域的应用非常广泛。所以在实际应用中也出现了一些在标准问题的基础上增加了某些变化之后的变型问题。其中较为常见的包括:
Capacitated VRP(CVRP)
CVRP是一种VRP,其中固定容量的固定车辆车队必须以最小的运输成本满足客户对来自公共仓库的单个商品的已知需求。也就是说,CVRP就像VRP,但有一个额外的约束条件,即每个车辆必须具有统一的单一商品容量。
目的
目的是最大程度地减少车辆数量和行驶时间,并且每条路线的商品总需求不得超过为该路线服务的车辆的容量。
可行性
如果分配给每条路线的总数量不超过为该路线服务的车辆的容量,则解决方案是可行的。
Multiple Depot VRP(MDVRP)
公司可能有多个仓库,可以从中为客户提供服务。如果客户聚集在仓库附近,则应将分发问题建模为一组独立的VRP。但是,如果客户和仓库混合在一起,则应该解决多仓库车辆路径问题。
MDVRP要求将客户分配到仓库。每个仓库都有一支车队。每辆车都来自一个仓库,为分配给该仓库的客户提供服务,然后返回同一仓库。
问题的目的是为所有客户提供服务,同时最大程度地减少车辆数量和行驶距离。
目的
目的是最大程度地减少车辆数量和行驶时间,并且必须从几个仓库满足商品的总需求。
可行性
如果每条路线都满足标准VRP约束并且在同一站点开始和结束,则可以采用一种解决方案。
VRP with Backhauls(VRPB)
带回程的车辆路线问题(VRPB)是一种VRP,客户可以在其中请求或退回一些商品。因此,在VRPPD中,需要考虑到客户退回交付车辆的货物必须适合其中。至关重要的假设是,必须在每条路线上进行所有交付,然后才能进行取货。这是由于以下事实:车辆被重新装载,并且在运送点处的轨道上的载荷的重新布置被认为不经济或不可行。待交付和提取的数量是固定的,并且事先已知。VRPB与VRPPD相似,但有一个限制:就VRPB而言,必须在完成任何取货之前完成每个路线的所有交付。
目的
目的是找到这样的一组路线,以使总行驶距离最小。
可行性
该问题的可行解决方案包括一组路线,其中在完成任何取车之前,每个路线的所有交付均已完成,并且分配给该路线的回程或回程点均不会违反车辆的容量。
VRP with Pick-Up and Delivering(VRPPD)
带提货和运送的车辆路径问题(VRPPD)是一种VRP,其中考虑了客户退还某些商品的可能性。因此,在VRPPD中,需要考虑到客户退回交付车辆的货物必须适合其中。这种限制使规划问题更加困难,并可能导致车辆容量利用率低下,行驶距离增加或需要更多车辆。
因此,通常要考虑有限的情况,即所有交付需求都从仓库开始,所有提货需求都应带回仓库,因此客户之间没有商品互换。另一种选择是放宽所有客户必须被精确访问一次的限制。另一个通常的简化是考虑到每辆车必须在提取任何货物之前交付所有商品。
目的
目的是最大程度地减少车辆数量和旅行时间,并限制车辆必须具有足够的能力来运输要运送的商品以及那些要在客户处取回的商品以将其返回仓库。
可行性
如果分配给每条路线的总数量不超过为路线服务的车辆的能力,并且该车辆具有足够的能力在客户处拾取商品,则该解决方案是可行的。
VRP with Time Windows(VRPTW)
VRPTW的问题与VRP相同,其附加限制是客户对货物的送达时间有时间窗口要求。
目的
目的是最大程度地减少车辆数量,以及在所有需要的时间内为所有客户提供所需的行驶时间和等待时间的总和。
可行性
关于VRP,VRPTW具有以下附加限制:
- 如果在其时间窗口的上限之后提供客户,则解决方案将变得不可行。
- 在时间窗下限之前到达的车辆会在路线上增加等待时间。
- 每条路线必须在与该仓库关联的时间窗口内开始和结束。
- 在软时间窗口的情况下,以后的服务不会影响方案的可行性,但是会通过在目标函数上增加一个值而受到负向影响。
以上各类问题之间的关系可以通过下图表示:
求解算法
车辆路径规划问题是典型的NP-hard问题,非常具有挑战性。同时因为其在实际应用的巨大价值,学术界和工业界对此类问题的优化算法的探索已经持续了几十年的时间。已有的经典求解算法可以分为精确解算法和启发式算法两大类。
在精确解算法方面,最基本的方法为分支定界算法,虽然其能够从理论上保证在有限时间内获得最优解,但是在实际计算中存在计算耗时巨大的情况。为了提高求解效率,研究者们先后提出了多种Branch-and-Cut以及Branch-Cut-and-Price方法,大幅降低了算法的求解时间。但是对于实际应用中较大规模的问题而言(例如超过200个点的问题),精确解算法依然无法能够在合理的时间内完成计算。所以还有一大部分研究集中于启发式算法领域。
启发式算法的思想为通过一系列启发式的规则来构造和改变解,从而逐步提升解的质量。对于VRP而言,较为经典的启发式算法为Clarke-Wright算法等。此外,经过不断的探索研究,元启发式算法被证明在求解VRP方面具有很好的效果和效率。一些经过精心设计的元启发式算法,例如模拟退火、禁忌搜索、遗传算法、蚁群算法、变邻域搜索、自适应大规模邻域搜索算法等在求解VRP上有着非常好的表现。
这里罗列了VRP的常用算法及细节。
建模及实现
本文以比较容易理解的精确解算法中的分支定界(Branch-and-Cut)作为标准进行数学建模。
我们用最标准的CVRP为例:
VRP问题可以抽象成一张有向完全图(图中各边都有方向,且每两个顶点之间都有两条方向相反的边连接的图):
$G=(V,A),V=N\cup\{o,d\}$,其中$N$是客户的集合,$\{o,d\}$分别是起点和终点,$A$是弧(路线)的集合。给定一个车队集合$K$,每辆车的型号完全一样且能够装载货物的容量为$q$。$\forall i \in V,q_i$是对应所需要的货物的数量。每个点$i \in V$有配送需求$d_i$,起点和终点的需求为0。目标是:找到一个车辆配送方案,所有客户的货物需求满足,且最小化配送费用。配送费用实际就是车辆经过每条弧所产生的费用$c_a,\forall a \in A$。
假设(约束):
- 图$G$满足三角形两边之和大于第三边
- 每个客户只能被一辆车配送
- 每辆车从仓库出发,经过若干客户,回到仓库后不能再被使用
这个组合优化问题暗含两个决策点:
- 哪辆车配送哪些客户
- 对每辆车而言,以什么顺序配送
所以,我们定义一个决策变量$x_{i,j}^k$: 车辆$k$是否经过弧$(i,j)$,如果经过则为1,否则为0。确定了该决策变量,上述决策也就确定了。下面我们给出整数规划模型:
s.t.
$\delta ^+ (i)$:代表的是所有从点$i$出发的弧;
$\delta ^- (i)$: 代表的是所有进入点$i$的弧;
$\delta ^+(S):\{(i,j) | (i,j) \in A, i \in S, j \notin S\}$($S$是一个点的集合)
公式解释:
公式1:表示所有路线的成本之和的最小值,也就是最终要求的结果
公式2:表示每个客户都必须服务到位
公式3:表示进入某个点的流等于出去的流
公式4和公式5:表示每辆车必须从$o$出发,回到$d$,不能停在客户的点不走了
公式6:表示不能超载
公式7:表示子回路消除。也就是避免出现,一辆车在几个客户之间无限打圈;
公式8:表示整数约束
作者是JAVA背景,所以在github上找到了一个使用Java实现的Demo,有兴趣可以研究一下。当然Python、C++或其他语言也有相关实现,可以自行查找。
应用
车辆路线规划距离类型
空中距离:两点之间的直线距离
道路距离:实际道路网图的测绘局里,在实际计算时又可按照道路距离和驾驶时长来区分
一般在计算车辆路线时使用道路距离,但不要使用最快路线来优化最短行程,要确定好唯一目标,不然很难得出最优解。
实现路径
- 使用地图API或离线路网测绘数据将所有的位置点转化成位置矩阵
- 使用规划算法将原始矩阵转化为最优路线矩阵
- 将矩阵解析成不同路线渲染到地图