跨境电商越南COD专线快递小包海外仓一件代发

 配送路径优化问题

物流路径优化问题通常可以这样描述：由多辆车将货物从一个或多个配送中心送到多个地理位置散的客户，在满足一定的约束条件（货物的需求量、发送量、交货时间、车辆负载量限制、行驶路程限制、时间限制等）下，如何安排车辆及其行驶路线使得总的配送费用小。这是物流配送的一个核

心问题。

     1 配送路径优化的目标

配送路径合理与否对配送速度、成本、效益影响颇大,因此,采用科学的合理的方法确定配送路线是配送活动中非常重要的一项工作。确定配送路线可以采取各种数学方法和在数学方法基础上发展和演变出来的经验方法。无论采取何种优化方法,我们首先都要明确物流配送路径的优化目标,才能有效地针对目标进行优化。目标的选择根据配送的具体要求、配送中心的水平、实力及客观条件而定,可以有以下多种选择：

（1）效益高：在选择以效益为目标时,通常以企业当前的效益为主要考虑因素,同时兼顾长远的效益。效益是企业整体经营活动的综合体现,可以用利润来表示。因此,在计算时是以利润数值大化为目标值。但由于效益是综合的反映,在拟定数学模型时,很难与配送路线之间建立函数关系,所以一般很少采用这一目标。

（2）成本低：计算成本比较困难,但和以效益为目标相比有所简化,在成本和配送路线之间有密切关系、且成本对终效益起决定作用的情况下,采用以成本低为目标实际上等于选择了以效益为目标,比较实用可行。

      (3) 路程短：如果成本和路程相关性较强,而和其他因素是微相关时,则可以选择路程短为目标,这样可以避免许多不易计算的影响因素,大大简化算。但需要注意的是,有时候路程短并不意味着成本低,如果道路条件、道路收费影响了成本,单以短路程为优解则不合适了。

      (4) 吨公里小：是长途运输中常作为选择目标,在多个发货站、多个收费站、整车发到的情况下,选择吨公里低为目标可以取得满意结果。在配送路线选择中,以吨公里小为目标在一般情况下并不适用,但在采取共同配送方式时,也可以作为目标。

      (5) 准时性高：准时性是配送中重要的服务指标,以准时性为目标确定配送路线就是要将各客户的时间要求和到达各客户点的先后顺序进行协调安排,这样有时难以顾及成本问题,甚至需要牺牲成本来满足准时性要求。但对准时性的要求必须建立在控制成本的基础上。

      (6) 运力利用合理：在运力非常紧张、运力与成本或效益有一定相关的情况下,为了节约运力、充分运用现有运力,而不需外租或新购车辆,也可以运力安排为目标,确定配送路线。针对不同的物流配送问题,要根据具体情况选择优化目标。本文研究的物流配送问题根据帝峰模具公司物流系统的特点,将优化目标设定为路程短、准时性高、运力利用合理。

.2 配送路径优化问题的分类

物流路径优化问题按照各种因素的不同形成了不同的种类，如表2-1。表2-1 不同分类依据下的路径优化问题类型[12] 

 .3 配送路径优化问题的解法分类

针对早期与现今的车辆路径问题模型，已有相当多的文献提出求解方法，可分为以下五大类[13]：

      (1)系统仿真法(Simulation )  

此方法早由Golden 和Skiscim于1986 年提出，主要应用于行车线路与物流配送中心区位的选择。优点在于可直接观察系统安排的效率与效果，但由于问题的实际情况多变且具有不确定性，很难将要实现的配送情形系统逻辑化为仿真程序；

      (2)人机互动法

人机互动法是一种结合使用者的直觉、经验、以及能力，纳入求解过程的一种方法，这种方法可以让决策者在电脑上产生途径的中间阶段。此方法结合人类决策与计算机计算能力，在求解的过程中，通过高度的人机交互模式，结合*的决策信息计算出。该方法的优点是寻优的过程中，决策者可以很清楚地看到各约束条件之间的替代关系以及参数变化可能导致的成本变化；

      (3)精确解法(Exact Procedures )  精确解法一般应用于线性规划(包括经过了专门处理的分枝定界法、割平面法和标号法)和非线性规划等数学规划技术，以便求得问题的优解。在VRP 问题研究的早期，主要是单源点(One-Point)(即配送中心、车场等)派车，研究如何用短路线(或短时间内)对一定数量的需求点(即用户)进行车辆调度，因此主要运用精确算法求出问题的优解。精确式算法一般有以下几种方法：分枝定界法(Branch and Bound Approach )、割平面法(Cutting Planes Approach )、网络流算法(Network FlowApproach)和动态规划方法(Dynamic  Programming Approach)等；

      (4)启发式算法(Heuristics )  

由于上述三种方法的求解效率较差，所以大部分的学者都致力于启发式解法的发展。该方法在解题时可减少搜寻的次数，所以是一种容易且快速求解困难问题的算法。车辆路径问题的启发式解法，包括节约法(Saving method)、邻近法(Nearest neighbor )、插入法(Insertion )及扫描法(Sweeping )等；

（5）智能算法（现代启发式算法）

进入20世纪80年代，一些新颖的优化算法，如人工神经网络算法、遗传算法、模拟退火算法、禁忌算法、混沌等，通过模拟或揭示自然现象或过程得到发展，其思想涉及数学、物理、生物进化、人工智能等各方面，为解决复杂问题提供了新的思路和手段。在优化领域，由于这些算法构造的直观性与自然机理，因而被称为智能优化算法(intelligent optimization algorithms)或现代启发式算法（meta-heuristic algorithms)。就目前的情况来看，智能算法应用于VRP的研究还不深入，一般都只考虑比较简单的约束(容量约束、时间窗约束)，与实际应用还有相当大的距离。但是，用智能优化算法解决VRP问题已经得到了人们的重视，相当多的学者致力于这方面的研究，发展势头很强劲，是进行VRP研究的一个热点方向。相对于传统启发式算法, 现代启发式算法不要求在每次迭代中均沿目标值下降方向, 而允许在算法中适当接受目标值有所上升甚至不可行的解, 其目的是能够跳出局部搜索邻域。

   3 本文配送路径优化方法

在配送路径优化问题的诸多解法当中，本文选择启发式算法当中的三种常被运用到的方法进行方案的优化。多回路运输问题（VRP）是现实中十分普遍的一种调配问题，此类调配的核心问题是如何对车辆进行调度。因此，VRP（Vehicle Routing Problem）模型应运而生，并成为解决多回路问题的一个相当成功的模型。该问题研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在满足一定的约束条件下（如货物需求量、发送量、车辆容量限制，行驶里程限制等），达到一定的优化目标（如里程短，费用小，时间尽量少等）。它涉及了多辆交通工具的服务对象的选择和路径确定两方面问题。

一个典型的VRP模型可以如下表述：

（1）基本条件：现有m辆相同的车辆停在一个共同的源点v0，它需给n个客户提供货物，顾客为v1、v2，…，vn ，两点之间路线为cij[14]。

（2）模型目标：确定所需的车辆数N，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使总费用小。

（3）限制条件：N不大于m；每一个订单都要完成；每辆车完成任务后都要回到源点v0；车辆的容量不能**过一定限制值；配送路线上所有配送点的配送需求量总和不能大于配送车辆的大载重量；从配送中心出发到配送结束并返回配送中心的路程不能大于配送车辆的大行驶距离；每条配送路线必须由一辆配送车辆配送，且要满足路线上所有需求点的要求，特殊问题还需考虑时窗限制、运输规章限制]。近插入法是一种解决旅行商问题的启发式算法,其结合邻近法与节省法的观念，依序将顾插入路径中以构建配送路线[16]。该方法首先以起点近的点作为路线的种子点，再根据邻近点插入法的概念，以插入值小者作为下一个插入点，后再用一般化节省值公式，以其中节省值大者决定插入的位置，重复进行选取与插入的步骤，为了使物流配送的时间少、距离短、费用低，并使合并后的总运输距离节约的里程大，直到达到一辆车的装载限制时，再进行下一条路线的优化]。客点需求：

（1）找到c0i小的节点vi，形成一个子回路，T={v0，vk，v0}；

（2）在剩下的节点中，寻找一个离子回路中某一节点近的节点vk，若此时回路的总货运量未**过车的载重限制，则继续步骤（3），否则，转（1）寻找新的一条回路；

（3）) 路径优化过程对每条路径进行局部搜索，调整路径内或路径间节点访问顺序，改善路径的质量，在子回路中找到一条弧（i，j）,使得cik+ckj-cij小，然后将节点vi插入到节点vi，vj之间，用两条新的弧(i，k)，（k，j）代替原来的弧（i，j），并将节点vk加入到子回路中。若此时该回路的总路程为未**过车辆的行程限制，则继续步骤（4），否则转步骤（1），寻找新的一条回路；

（4）重复步骤（2）和（3），直到每一个节点都被归入某一个子回路中。 2.3.3 扫描法扫描法是用于求解车辆数目不限制的VRP问题的算法，它采用“先分组后路线”的过程，所谓分组就是派给每辆车一组客户点。一种简单的分组方法是将以配送中心为原点的坐标平面划分为多个扇形区域，并初步将每个扇形区域的点分派给一辆车，然后扩充路线，如果在进行了一次“分组-路线”的路线构造后，还存在未分配点，则再进行“分组-路线”程序。如此反复，直到所有的点均已分配为止。

扫描算法的主要步骤：

（1）以起点0点作为较坐标系的原点，并一连通图中的任意一顾客点和原点的连线定义为角度零，建立较坐标系；然后对所有的顾客所在的位置，进行较坐标变换；

（2）从小角度的顾客开始建立一个组，按逆时针方向，将顾客逐个加入到组中，直到顾客的需求总量**出了负载的限制。然后继续建立一个新的组，继续按逆时针方向，将客户加入组中；

（3）重复（2）中的过程，直到所有客户都被分类为止；

（4）对各个组内的单回路进行路径优化。

节约算法是目前用来解决运输车辆数目不确定的VRP模型的**的启发式算法，其思想在于按节约值(较短路径与原路径之差)由大至小排序，在车辆容量限制下，依序将对应的两客户点排入路径中，直至所有客户都被排入路径为止。关键在于当节约值较大的两顾客点被排入路径时，除需考虑车辆容量限制方面采用“量力而为”的策略外，更需要考虑到时间的限制，此方法的优点是提高车辆的利用率[20]。节约算法的核心思想是将运输问题中存在的两个回路（0，…，i，0）和（0，j，…，0）合并成一个回路（0，…，i，j，…，0），在上面的合并操作中，整个运输问题的总运输距离会发生变化，如果变化后总运输距离下降，则称节约了运输距离[21]。其中cio代表从顾客i 至起点的距离，coj代表从起点至顾客j的距离，cji则代表从顾客j 至顾客i 的距离，相应的变化值叫做节约距离QUOTE \* MERGEFORMAT △Cij 。计算两结点i 与j 间的节约值QUOTE \* MERGEFORMAT △Cij 时，应先计算原路径中各往返路径的总和，再与较短路的总路径和相比较。两结点间的节约值的计算公式与意义如式（1）所示。（1）两结点的原路径与较短路的调整过程如图2-1所示。

调整前调整后

图2-1 节约算法的图像描述

节约里程算法主要步骤：

（1）设需求点集NR={1,2,…, n},各点需求量Ri,各点间短距离cij；

（2）确定各车辆配送点集I1，I2，…,Im令Ij={j}, j=1,2,…,n (先采取单点配送)；

（3）计算所有点对的节约度QUOTE \* MERGEFORMAT △Cij ，然后对计算结果进行升序排列。

（4）从升序排列的节约度序列中的上面的值开始，直到节约里程△Cij的队列空为止,重复下列步骤:按照节约里程△Cij队列从大到小的顺序,分析客户i和j之间合并的可能性(是否满足装载限制条件、不在同一路径内以及合并次数不**过2),将i, j连接起来,即可令Ii＇=Ii∪Ij;Ij=∅，如果不是这样,则从节约里程队列中去除当前的节约里程，分析下一个客户对[22]。