VRP问题的建模及算法研究

作者：孔阳 李世伟 孔晓丹

来源：《科技经济市场》2015年第07期

        摘 要：近年来随着社会智能交通的兴起，电子商务不断发展，中国现代物流业进入了高速发展时期。车辆配送作为物流业中一个核心功能，被作为重要的研究对象。本文以车辆路径问题为出发点，研究了车辆路径问题多目标优化算法，利用建模做出了算法优化方案，对现实操作中具有现实意义。

        关键词：车辆路径；数学模型；多目标优化

        0 引言

        近年来，随着电子商务和社会智能交通的不断发展，人们生活的方方面面都有物流的支撑， 配送作为物流系统中一项重要的活动，其作用已经越来越重要，从运输、仓储、配送等过程中，将产品或信息传送到指定的顾客位置，是配送的主要功能和属性。对VRP问题进行研究能够提高物流企业的配送水平，对公司而言显得尤其突出和重要。

        1 车辆路径问题

        1959年Dantzig提出了车辆路径问题（VRP）[1]。车辆路径问题（VRP）问题中的旅行商问题（TSP）被学者Gaery[2]在其论文中证明旅行商问题是一个NP难题，故VRP问题也是一个NP难题。NP难题不光在理论研究上有很大意义，在现实生活中的意义也十分显著，在车辆路径优化问题上就得到印证。车辆路径问题主要是指在某一区域内存在需要货物的客户要从配送中心得到货物补充，客户的货物由配送中心统一配送，由车队进行配送负责货物，通过合理的安排车辆路径线路，以保证在一定的约束条件下，做到诸如成本小，时间耗费少和路程短等目的完整路线规划问题，见图1所示。

        车辆进行配送过程中，是以车辆的载重为计算衡量，其成本计算为载重量乘以路线距离。常见的优化目标就是总路线长度的最短，节约物流公司和客户的时间，节省大量成本，尽可能地降低车辆成本是保证物流公司提高运营效率，尽量地使总成本最低，以保证运营的正常运作。

        2 车辆路径问题的算法

        当客户量少的时候，我们可以选取一些精确算法进行求解。精确算法是指最优解可以通过推理和数学计算得到答案的一种求解算法[3]。当客户数量的庞大，物流配送网络也就越大，我们需要选择人工智能算法来解决此类问题。以下为几个比较常见的人工智能算法[4]。

        （1）Clarke-Wright算法、

        该算法的核心思想是：依次将路线中的两个闭合线路整合成一个线路，合并结果是大幅度减少了线路的总运输距离，最后当满足车辆载重情况后，再进行下一辆车的类似的优化。但到的解往往不是最优解，需要与其他算法结合使用。

        （2）Sweep算法。

        该算法的核心思想是：首先要计算出需要遍历客户点的极坐标，随后对极坐标的大小进行排序。在满足可行约束条件下，把不同的角度大小和子路经归并在一起，再通过VRP的优化算法对得到的子路径进行处理优化。

        （3）遗传算法

        该算法的核心思想是：从需要优化的一组可行解中开始，照达尔文进化论的优胜劣汰原则，对选择出的一组可行解进行进化以便产生越来越好的一个解。通过不断进化，得到的解更可以接近于最优解分布。

        3 车辆路径问题建模

        针对车辆路径优化目标，本文主要从保证多个配送中心（DC）服务多个客户（DS）时，确定最小车辆数目m，并确定最短路径长度，以便于满足总的配送成本最低。目标函数如下：

        minC=■■c■D■x■ （1）

        其中，c表示客户点之间距离运输成本；D■表示的是从客户点i到客户点j的距离；x■是0-1变量，含义为，当车辆从i到j时，x■=1。否则，x■=0；下标集K=1，2，…，k为第k个DC，I=1，2，…，i和J=1，2，…，j分别为第i和j个DS，而且R=I+J。约束条件如下：

        N≤n （2）

        ■x■=■x■，i∈R，j∈R，且i≠j （3）

        ■x■=■x■，k∈K （4）

        ■x■w■-d■≥0 （5）

        w■表示访问客户之前载重，d■是指客户点j的货物量；

        ■x■w■-d■=■x■w■，k∈K（6）

        ■D■≤D■ （7）

        xij∈0，1 （8）

        以上的数学建模的各个含义为：约束（2）表示运行车辆数目不能大于车辆数目的总和；约束（3）表示访问配送中心的车是同一辆；约束（4）表示访问客户点的车是同一辆；约束（5）表示车辆不可空载；约束（6）表示客户得到满足；约束（7）表示车辆的最远驾驶距离不能超过规定距离 ；约束（8）表示一个0-1变量。

        4 模型的优化算法

        本文使用上面介绍的遗传算法进行模型优化。下面我们给出遗传算法的步骤：

        （1）选取初始种群规模：确定合适的种群规模是我们使用遗传算法首要问题。种群规模越大，反而不容易陷入局部最优解，其结果是搜索时间会加长。为了确定初始种群规模，通过穷举法来求取最优解的区间。

        （2）为得到适应度函数，使用自然编码法。首先运用自然数编码法，产生初始可行解。

        （3）更新种群。更新种群是从上步可行解中，选择适应度大，条件好的个体进行交叉、变异，产生新的解的过程。第一，交叉的核心意义在于，继承父代的优良基因，来提高个体的适应度。第二，我们采用随机多次对换的方式，依据一定的变异概率来决定生成的两个个体是否需要进行变异。

        （4）操作完成之后，我们将得到的种群进行适应度的排列，保证了下一次算法进化的实现。

        5 结论

        本本文是针对车辆路径的问题研究。第一分析了车辆路径问题的定义，第二针对有关算法进行描述，最后进行建模和算法优化。近年来随着社会智能交通的兴起，电子商务不断发展，中国现代物流业进入了高速发展时期，要求我们不断对VRP模型和算法要做进一步的研究。

        参考文献：

        [1]祝崇俊，刘民，吴澄.供应链中车辆路径问题的研究进展及前景.计算机集成制造系统CIMS[J].2001，7（11）：1-6.

        [2]姜大立等.车辆路径问题的遗传算法研究[J].系统工程理论与实践，1999（6）：40-45.

        [3]郎茂祥-物流配送车辆调度问题的模型和算法研究[D].北方交通大学博士论文，2002.