下载掌阅APP，畅读海量书库
立即打开
国外对配送车辆优化调度问题作了大量而深入的研究。早在1983年Bodin、Golden等人在他们的综述文章中就列举了700余篇有关文献。在Christofides（1985）、Golden和Assad（1988）编辑的论文集中，以及Altinkemer和Gavish（1991）、Laporte（1992）、Salhi（1993）等的综述文章中都对该领域的研究成果进行了详尽的阐述。该研究领域的代表人物主要有Bodin、Christofides、Golden、Assad、Ball、Laporte、Rinnooy Kan、Lenstra、Desrosiers和Desrochers等。
国内也有一些对配送车辆优化调度问题的研究。李大卫等以TSP的最近距离启发式算法为基础，通过设置评价函数来处理时间窗约束，求解了简单的VSP。张震针对单车场满载问题，提出了考虑运输行程约束的优化方法。蔡延光等应用并行禁忌搜索算法和模拟退火算法对满载问题进行了求解。刘浩等用模拟退火算法求解了两车型随机需求的VRP。张涛等用禁忌搜索算法和遗传算法的混合策略求解了VRP。王莉用启发式算法求解了有时限的VRP。袁健等用神经网络法求解了VRP。姜大立、李大卫分别用遗传算法求解了无时限和有时限的配送车辆优化调度问题。近年来，郭耀煌、李军、谢秉磊等对配送车辆优化调度问题进行了较为深入的研究，提出了多种求解算法。周双贵对配送车辆优化调度问题的模型和求解方法也进行了较为深入的研究。
配送车辆优化调度问题提出后，不少专家、学者对其计算复杂性进行了研究，这是确定其求解算法研究方向的基础。Lenstra和Rinnooy Kan对VSP的计算复杂性进行了综述和分析；Dantzig和Fuikerson（1954）证明了有确定开始时间的配送车辆优化调度问题的复杂性为O（n 3 ）；Savelsbergh（1985）和Solomon（1986）提出有时限的配送车辆优化调度问题比一般的配送车辆优化调度问题更复杂；Savelsbergh（1985）提出有时限的配送车辆优化调度问题不仅问题本身是NP难题，甚至在车队大小固定时，找一个可行解也是NP难题；Lenstra和Rinnoopy Kan还证明了几乎所有类型的配送车辆优化调度问题均为NP难题。
配送车辆优化调度问题作为一个NP难题，随着客户数量的增加，可选的配送路径方案数量将以指数速度急剧增长，即出现组合爆炸现象。据计算，对于一个有20个顶点的TSP（Traveling Salesman Problem，旅行商问题），其可能的路径总数为20！/（2×20）≈6.08×10 16 ，即使用每秒一亿次的计算机按穷举搜索法求解，也需要计算350年。配送车辆优化调度问题作为一个约束性多路旅行商问题，与TSP相比，不仅约束条件更为复杂，而且存在多条配送路径，因此，其计算量会比TSP大得多。一般地，只有在客户数量较少、运输网络较简单时，才能求得配送车辆优化调度问题的精确最优解。
求解配送车辆优化调度问题的方法很多，究其实质，可以分为精确算法和启发式算法两大类。精确算法是指可求出其最优解的算法，主要有：分枝定界法、割平面法、网络流算法、动态规划法等。由于精确算法的计算量一般随问题规模的增大呈指数增长，在实际中其应用范围很有限。为此，专家们把精力主要用在构造高质量的启发式算法上。下面对配送车辆优化调度问题的一些常用求解方法进行简单评述。
Dantzig和Ramser提出配送车辆优化调度问题后，将该问题作为旅行商问题的推广问题进行求解。
旅行商问题，也称为货郎担问题、巡回销售员问题。该问题是一个典型的组合优化问题，可以简单地描述为：设有N个城市并已知各城市间的旅行费用，找一条走遍所有城市且费用最低的旅行路线。
配送车辆优化调度问题可以说是对旅行商问题加以一定的限制而形成的，这些限制包括：客户有一定的货物需求（或供应）数量且要求货物在一定的时间范围内送到（或取走），配送车辆的装载量限制及一次配送的最大行驶距离限制等，即配送车辆优化调度问题是一个多约束的旅行商问题。同时，配送车辆优化调度问题还可以归结为在每一个配送路线中的旅行商问题。
如果把从一个配送中心用一台配送车辆向L个客户送货的配送车辆优化调度问题考虑为（L+1）个点的旅行商问题，则它的解是：从配送中心出发，对所有的客户巡回一次，再回到配送中心的距离为最短的路线。在配送车辆优化调度问题中，可以把全部配送路线划分为几条大的配送路径，每台配送车辆只沿一条配送路径送货，即只访问配送中心一次。因此，除了实际的配送中心外，还可以再虚设几个配送中心，这样，配送车辆优化调度问题就可以转化为有几个封闭循环线路的旅行商问题，即多路旅行商问题。可见，配送车辆优化调度问题是一个约束性的多路旅行商问题。将配送车辆优化调度问题转化为旅行商问题后，就可以利用求解旅行商问题的方法加以求解。目前求解旅行商问题的算法主要有：近邻法、贪婪法、分枝定界法、最近插入法、最远插入法、双极小生成树法、剥脱法、空间填空曲线法、Karp法、Litke法、Christofides法、2-交叉法、k-交叉法、Lin-Kernighan法、神经网络法、禁忌搜索法、模拟退火法、遗传算法等。
动态规划是一种常用的运筹学方法，它适于解决这样的问题：某个大问题可以划分为几个阶段，每个阶段形成一个子问题，各个阶段是相互联系的，每个阶段都要做出决策，并且某个阶段的决策，常影响下一阶段的决策，从而影响整体决策。在动态规划求解过程中，作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，对其决策所形成的状态而言，余下的诸决策必须构成最优策略，这是动态规划的最优化原理。利用这个原理可以把多阶段决策的求解过程看成是一个连续的递推过程，由后向前逐步推算。在求解时，各状态前面的状态和决策，对其后面的子问题而言，只不过相当于其初始条件而已，并不影响后面过程的最优策略。动态规划求解问题的一个突出弱点是：当问题中的变量个数太多时，将会由于计算机存储器容量和计算速度的限制而无法求解。
用动态规划法求解配送车辆优化调度问题的思路如下。
用0表示配送中心，i表示客户（i=1，2，…，L）；设S={1，2，…，L}表示所有客户的集合；若用S
1
，S
2
，…，S
K
分别表示第1，2，…，K条配送路线上的客户的集合，K为所需的配送车辆数，则有：S=S
1
∪S
2
∪S
3
∪…∪S
K
，S
j
∩S
k
=φ，j≠k，j、k=1，2，…，K。设从0出发，用最合适的配送路线向S
j
（j=1，2，…，K）送货，再回到0的配送距离为D（S
j
），则配送车辆优化调度问题的目标是使总配送距离
最小。用f
k
（U）表示使用第k辆车，对部分客户的集合U配送时的最小配送距离。由最优化原理可得下面的递推公式：
上式中，最合适的部分集合U*是使总配送距离为最小的S的最合适部分S 1 、S 2 、…S K 。
从理论上讲，利用动态规划法可以求得配送车辆优化调度问题的精确最优解。该方法的缺点是：①由于动态规划方法本质上是一种枚举法，当配送车辆优化调度问题较复杂时，式（1.1）将变得十分复杂，求解也会十分复杂，甚至会因为计算机存储量的限制和计算速度的限制而根本无法求解；②使用动态规划法求解配送车辆优化调度问题时，很难考虑到实际配送过程中的一些具体要求（如按客户指定的时间窗送货或取货等）。
节约法是由Clarke和Wright于1964年提出的。该方法提出了从多条可供选择的配送路径中，选出最佳配送路径的方法。
如图1.1所示，由配送中心P向两个客户A、B 送货，P至A、B 的最短距离分别为l 1 和l 2 ，A、B间的最短距离为l 3 ，客户A、B的货物需求量分别为q 1 和q 2 。
图1.1 节约法原理分析图
对上述问题，最简单的配送方法是用两台车辆分别对A、B两个客户运送所需货物，然后各自返回配送中心。使用该种配送路径方案时配送车辆的走行总里程为：
如果改为由一台车辆向A、B 两个客户巡回送货（设q 1 +q 2 ≤ 配送车辆的载重量），则配送车辆的走行总里程为：
后一种配送方案比前一种配送方案节约的车辆走行里程为：
式（1.4）称为节约量公式，从图形看，它等于三角形的两个邻边之和减去对边的差。
如果在配送中心P的供货范围内还存在着第3、4、5、…、L个客户，在配送车辆载重量允许的情况下，可将它们按节约量的大小依次连入巡回线路，直至车辆满载为止。余下的客户可用同样的方法确定巡回路线，另外派车。
第一步：做出最短距离矩阵，即根据配送网络图中配送中心与客户之间以及客户相互之间的距离，计算出配送中心与各客户之间以及各客户相互之间的最短距离矩阵。求配送网络顶点间的最短距离时可采用求最短路的算法，如Dijkstra算法等。
第二步：编制节约里程表。即根据配送中心与客户间及各客户相互间的最短距离矩阵，利用节约量计算公式（1.4）计算出客户相互间的节约里程。节约里程的计算结果有正有负，当节约里程的计算结果为负数时，无实际意义，取其节约量为0，将节约里程填入节约里程表。
第三步：编制节约里程顺序表。即将节约里程表中的节约里程按由大到小的顺序排列，然后填入节约里程顺序表。
第四步：制定配送路线。即根据节约里程顺序表中节约里程的大小顺序和配送车辆优化调度问题的约束条件，逐渐组成配送路径图。
节约法是一种启发式方法，它属于逐次逼近法的一种，用该方法不一定能求得配送车辆优化调度问题的精确最优解，但可以高效地得到问题的近似最优解。该方法具有计算步骤简单，计算速度快，且易于考虑各种实际问题的优点。该方法的缺点是未组合点零乱、边缘点难以组合以及有时解的质量不高等。
扫描法是由Gillett和Miller于1974年提出的，该方法的基本思路是采用逐次逼近的方法求解配送车辆优化调度问题。利用扫描法求解配送车辆优化调度问题时，配送中心及客户的位置都用极坐标表示，其中配送中心位于坐标原点。
用扫描法求解配送车辆优化调度问题的步骤如下。
（1）对客户进行编号。将所有客户按极坐标角度由小到大的顺序编上序号，若两客户的极坐标角度相同，则将距离配送中心较近的客户给予较小的序号。设客户的序号分别为1、2、…、L。
（2）作初始配送路线。按客户序号由小到大的顺序，依次将客户1、2、…、j 1 纳入初始配送路线1，其中，j 1 为在满足配送车辆优化调度问题的约束条件（主要为车辆装载能力约束和车辆一次配送最大行驶距离约束）的前提下，第一辆车所能到达的最后客户，换句话说，若将客户j 1 +1也纳入路线1，就会违反配送车辆优化调度问题的约束条件。按同样的方法依次将客户j 1 +1、j 1 +2、…、j 2 纳入初始配送路线2；…；最后将客户j K-1 +1、j K-1 +2、…、L纳入初始配送路线K。上述K条初始配送路线即构成初始配送路径方案，该配送路经方案的总配送距离为各配送路线的距离之和。
（3）配送路线的调整。试着将路线k（k=1，2，…，K-1）上的一个客户与路线k+1上的一个或多个客户进行交换，如果交换后能够使总配送距离减少，则实施这种交换，否则放弃交换。选择交换客户时一般遵循以下原则：
① 从路线k上去掉的客户应当是在路线k上所有客户中距坐标原点（即配送中心）距离最近的客户。
② 被考虑用来加在路线k上的客户应当是：在路线k+1上的所有客户中离最后加到路线k上的客户最近的客户p；被考虑加在路线k上的下一个客户是在路线k+1上距离客户p最近的客户。按照此方法对各条配送路线上的客户逐步替换，以使总配送距离逐步减小。最终将得到该客户编号方案下优化的配送路径方案。
（4）通过改变客户编号，寻求其他优化的配送路径方案。改变客户编号的方法主要有以下两种：
① 旋转坐标轴，以改变第一个客户。例如，可通过旋转坐标轴使原来的第二个客户位于x轴上，这样一来，原来的第二个客户就变成第一个客户，相应地，原来的第三个客户变成第二个客户，…，原来的第L个客户变成第L-1个客户，原来的第1个客户变成第L个客户，按照这种编号方法，通过步骤（2）和（3），可求得另外一种优化的配送路径方案。再旋转坐标轴，还可得到更多优化的配送路径方案。
② 将客户按极坐标角度从大到小的顺序依次进行编号，采用这种客户编号方法，也可得到另外的配送路径优化方案。
（5）求得配送车辆优化调度问题的满意解。从上述多个优化的配送路径方案中，选取总配送距离最小的方案作为配送车辆优化调度问题的满意解。
扫描法是一种逐次逼近法，用该方法不一定能求得配送车辆优化调度问题的最优解，但是能够有效地求得问题的满意解。对于某个具体的配送车辆优化调度问题，由于存在多种客户编号方法，当仅选择一种客户编号方案用扫描法求解时，其计算量相对较小，但相应的解的质量可能不会很高；当选用多种客户编号方案用扫描法求解时，一般能得到质量很高的满意解，但相应地，计算量会成倍增加。研究表明，对于配送车辆优化调度问题，当每条路线上的客户数目大体相同且配送路线不太多时，用扫描法求解是非常有效的。
两阶段法是求解配送车辆优化调度问题的一种常用的启发式算法。两阶段法主要有以下两类：一类是先求配送路线，后分段，即先对客户利用旅行商方法求出其最优巡回配送路线（阶段1），然后根据问题的各种约束条件（如车辆装载限制、车辆一次配送的最大行驶距离限制等）对其路线进行分段（阶段2），在每一小段内，车辆按用旅行商方法确定的配送路线行驶；二是先划分区域，再求行车路线，即先根据各种约束条件进行配送区域划分（阶段1），然后在各小区域内利用旅行商方法设计最优配送路线（阶段2）。虽然从表面上看，两类算法仅求解次序不同，但实际上两类算法的计算结果往往大不相同。研究表明，第一类算法不能做到渐进最优。因此，除少数早期启发式算法采用第一类算法外，绝大多数启发式算法均采用第二类算法。由于在第二类算法中，划分配送区域的问题十分关键，因此，也称该类算法为分区配送算法。
对于配送区域划分问题，有关学者提出了许多具有实用价值的算法，如S.Anily 和A.Federgruen 提出的极端分区算法和改进圆形分区算法，Julien Bramel和David Simchi-Levi 提出的基于基地启发式分区（LBH）算法，S.Viswanthan 和Kamlesh Mathur提出的静止嵌套联合补货策略启发式算法等。
（1）根据配送总量（即全部客户需求量的总和Σq i ）和车辆的装载限制（即车辆的最大载重量Q max ），按下面公式（1.5）确定最少配送路线条数m。
式中，「」表示取整操作，即「f」表示取小于f的最大整数。
（2）置未处理客户的集合V为全部客户，置各条配送路线上客户的集合S k （k=1，2，…，m）为空集，置各条配送路线上车辆的装载量Q k 为0，置各条配送路线上车辆的行驶距离D k 为0，置各条配送线路上的客户数L k 为0。
（3）选取m个初始客户，分别加入到m条配送路线中，并分别与配送中心构成配送回路，并根据上述配送路线更改V、S k 、Q k 、D k 、L k 。
研究表明，上述初始客户的选择对于配送车辆优化调度问题的最终解会产生很大影响。Fisher和Jaikumar对此专门进行了研究，并提出了一些选取初始客户的方法，如交互法（即交由配送计划制定者作决定）和自动法（即由计算机程序根据某些规则自动设定）等。
（4）在未处理客户集合V中，依次选取一个客户i，利用最近插值法，计算该客户加入各配送路线后所增加的最小配送距离c ij （称为最小插入费用）。如果某客户加入某条配送路线后，该线路的车辆装载量超过车辆的最大载重量或车辆的行驶距离超过车辆一次配送的最大行驶距离，则说明该客户不能加入到该配送线路，令其加入后配送距离为无穷大。如果该客户加入所有配送路线的费用均为无穷大，则表明配送路线条数（即车辆数）不够。此时，应增加一条新配送路线，即取m=m+1，然后返回步骤（3）重新计算。
（5）对未处理的客户计算其最小插入费用与次小插入费用的差值，并选择差值最大的客户加入到其最小插入费用的路线中去。这种选取方法类似于运筹学中求解运输问题时所用的伏格尔法，它比最小值法更接近最优解。将该客户加入相应的配送路线后，根据上述新的配送路线更改V、S k 、Q k 、D k 、L k 。
（6）当所有的客户处理完毕，即V为空集时，转步骤（7），否则，转步骤（4）。
（7）输出计算结果，包括总配送距离、配送路线条数及各条配送路线上客户的排列顺序等。
由于现实中的配送车辆优化调度问题涉及面很广、影响因素众多，有的因素难以用数学关系描述，这时可以采用对配送路线方案进行综合评定的方法。
用方案评价法制定配送计划主要包括以下步骤：
（1）确定评价项目。在对配送路线方案进行评价时，一般可考虑采用以下评价项目：使用的车辆数、司机的总工作时间、配送总距离、车辆的总油耗、配送总成本、行车的难易程度、配送的准时性、装卸车的难易程度等。
（2）拟定几个配送路线方案，即针对某个具体的配送车辆优化调度问题，根据某项突出或明确的要求，如配送的准时性、司机的行驶习惯等，拟定几个配送路线方案，方案应提出各条配送路线上的使用的车辆类型及车辆经过各客户的顺序等。
（3）对拟定的几个配送路线方案，分别确定其各项评价项目的值。
（4）对配送路线方案进行综合评价。根据各项评价项目的相对重要性以及各配送路线方案中各评价项目的值，可采用层次分析法、模糊综合评判方法等确定各方案的优劣，最终选取最优的方案。
现代优化计算方法包括禁忌搜索算法、模拟退火算法、遗传算法、神经网络法等。这些算法的出现为求解配送车辆优化调度问题提供了新的工具。
禁忌搜索（Tabu Search，TS）算法，也称列表寻优法，是局部搜索算法（爬山算法）的推广。Glover在1986年首次提出这一概念，进而形成一套完整算法。禁忌搜索算法的特点是采用禁忌技术。为了回避局部邻域搜索易陷入局部最优的不足，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。Gendreau、Jiefeng、Barbarosoglu、蔡延光等利用禁忌搜索算法求解配送车辆优化调度问题，取得了一些研究成果。但上述研究多限于对无时限单向配送车辆优化调度问题或满载配送车辆优化调度问题的求解。
模拟退火（Simulated Annealing，SA）算法也是局部搜索算法的扩展，其特点是以一定的概率选择邻域中目标函数值较差的状态。模拟退火算法的思想最早由Metropolis在1953年提出，Kirkpatrick在1983年成功地将其应用在组合优化问题中。近年来，Osman、Alex Van、Teodorovic、蔡延光、刘浩等人利用模拟退火算法求解配送车辆优化调度问题，取得了一些研究成果。但上述研究也多限于对无时限单向配送车辆优化调度问题或满载配送车辆优化调度问题的求解。
人工神经网络方法基于以下基本原理：大脑皮层每一点的活力是由其他点势能释放的综合效能产生。这一势能与下面的因素有关：
① 相关其他点的兴奋次数；
② 兴奋的强度；
③ 与其不相连的其他点所接受的能量。
该原理是构造人工神经网络模型的基本依据。20世纪80年代，Hopfield将人工神经网络算法成功地应用在组合优化问题上。人工神经网络要求发展神经网络型计算系统来替代传统的计算机。因此，只有当人工神经网络硬件系统得到发展，才能使目前的人工神经网络更快、更有效地解决更大的实际问题。袁健等用神经网络法求解了简单的VRP。
遗传算法（Genetic Algorithm，GA）是由美国Michigan大学的J.Holland教授于1975年提出的，该算法是一种从生物进化的规律中得到灵感和启迪的自适应全局随机搜索方法。由于遗传算法的整体搜索策略和优化计算时不依赖于梯度信息的特点，所以它的应用范围非常广泛，尤其适合于处理传统搜索方法难以解决的高度复杂的非线性问题。有专家断言，遗传算法具有用来解决NP难题的趋势。Berthold，Malmborg，Ochi和Luiz都曾利用遗传算法对配送车辆优化调度问题进行求解，但仍处于尝试阶段，还有待于进一步的研究。在国内，姜大立、李大卫、李军、谢秉磊、张涛等人都曾利用遗传算法求解配送车辆优化调度问题，并取得了一些研究成果。
上述几种现代优化计算方法中，神经网络方法在前几年比较热，但现在已经明显降温，因为它只用一个反传算法，从中很难更深入地开发思想和信息。而禁忌搜索算法、模拟退火算法、遗传算法在求解配送车辆优化调度问题中的应用则刚刚开始，虽然已有一些研究成果，其潜力还有待于进一步挖掘。因此，本书主要研究用禁忌搜索算法、模拟退火算法和遗传算法求解配送车辆优化调度问题。