基于供需匹配优化的多货品可拆分车辆路径问题

摘" 要：针对供应链上下游企业原料生产运输问题，提出了供需匹配优化策略，并将部分客户对不同原料的需求分批次配送，可以确保满足客户需求并降低车辆空载率、提高运输效率，建立了以车辆固定成本和行驶成本之和最小为目标的取送货车辆路径优化模型。采用遗传算法进行求解，设计了供需匹配对编码策略和车辆路径调整策略，可以增强全局搜索能力，更有可能获得最优解。通过算例分析得出最小总成本和最优车辆路径，并验证了文章匹配策略和需求拆分策略的有效性，研究成果对生产运输企业的实际运营具有一定的参考价值。

关键词：供需匹配优化；多货品可拆分；车辆路径；遗传算法

中图分类号：F253" " 文献标志码：A" " DOI：10.13714/j.cnki.1002-3100.2025.03.005

Abstract： Aiming at the production and transportation problem of raw materials for upstream and downstream enterprises in the supply chain， the optimization strategy of supply and demand matching was proposed， and some customers' demand for different raw materials was distributed in batches， which could ensure that customer demand could be met， vehicle empty load rate could be reduced， and transportation efficiency could be improved. A pickup and delivery vehicle routing optimization model aiming at the minimum sum of fixed cost and running cost of vehicles was established. Genetic algorithm is used to solve this problem. The supply and demand matching pair coding strategy and vehicle routing adjustment strategy are designed， which can enhance the global search ability and more likely to obtain the optimal solution. The minimum total cost and the optimal vehicle routing are obtained through experiments and the effectiveness of the matching strategy and demand splitting strategy is verified. The research results have certain reference value for the actual operation of production and transportation enterprises.

Key words： supply and demand matching optimization; multi-commodity split; vehicle routing; genetic algorithm

0" 引" 言

我国现代经济的发展带动了以生产和运输为经营链条的供应链上下游企业走向规模化、立体化，客户的需求也不断增长。例如在原油生产运输企业中，石油需要通过多种类型的原油生产得到，而有些客户只能生产一部分类型的原油，需要别的客户提供所需原油，同时也能为其他客户提供自身生产的原油，同时取送货车辆路径问题SPDVRP（Simultaneous Pickup and Delivery Vehicle Routing Problem）随之开始出现。Min[1]于1989年首次提出同时取送货车辆路径问题。

企业实际生产运输中存在客户之间自行调拨原料的情况，导致配送过程经常出现多批次、少批量运输，造成车辆空载率较高，因此就需要建立物流管控中心，从全局角度协调上下游客户之间的原料调拨，对客户的供应和需求关系进行匹配，以满足客户个性化需求，提高运输效率。于是基于供需匹配优化的取送货车辆路径问题BSDMOPDVRP（Based on Supply and Demand Matching Optimization Pickup and Delivery Vehicle Routing Problem）开始被重视。徐倩等[2]基于外卖配送问题建立了成对出现的取送餐节点，设计了自适应大邻域搜索算法，为实际调度优化提供了理论支持；Dominik[3]设计了取送货地点一一对应的车辆运输策略，采用了禁忌搜索算法研究该策略下电动汽车配送的优势；任腾等[4]将电子商务和取送货问题结合，设计了个人和电商客户在同城订单中的一对一配送策略，来降低车辆空载率；Chemla et al.[5]针对共享单车系统中供需匹配关系未知的问题，建立了调节系统对各站点自行车进行供需分配，确保实时满足客户需求；敬鹏程[6]基于众包外卖配送问题设计了配送员抢单的策略来进行供需匹配，在保证提成和客户满意度的情况下优化配送路径。

此外，由于企业的规模逐渐增大，多种原料的调拨问题开始出现，普通的供需匹配方式显然无法满足客户的实际需求，很多客户需要车辆分批次配送，由此对基于供需匹配优化的多货品可拆分取送货车辆路径问题BSDMOMCSPDVRP（Based on Supply and Demand Matching Optimization Multi-Commodity Split Pickup and Delivery Vehicle Routing Problem）的研究也开始进入学者们的视野。Chen et al.[7]针对多商品取送货问题，设计了对顶点处物料需求进行拆分并由多个车辆分批次配送的策略，最大程度降低总成本；张颖钰等[8]研究了需求可拆分的车辆路径问题，设计了客户点能被多次访问的运输策略，采用大变异邻域遗传算法求解；徐东洋等[9]基于烟草公司卷烟生产和原料调拨问题研究了供需匹配关系不确定的取送货问题，建立了客户对多种货品的需求可任意拆分满足的优化模型；Hernandez et al.[10]引入多次访问客户点的策略来提高车辆的装载率，并采用变邻域搜索算法求解最小成本；高振迪等[11]研究了对不同商品可分批次取送货的车辆路径问题，设计了可多次服务客户点的配送策略，并考虑了配送失败时从仓库补货，采用改进的遗传禁忌算法求解。

综上所述，虽然学术界对MCSVRPBSDMO问题的各个方面都有一定涉及，但详细考虑多货品的供需匹配策略、需求拆分策略的研究相对较少，且鲜有将生产运输与调度配送问题相结合的研究。本文针对车辆空载率较高问题提出了基于客户点间距的供需匹配策略，针对多种原料的运输问题提出了拆分策略和车辆路径调整策略，并以生产运输问题为背景进行算例分析，研究成果可以为企业实际运营提供参考。

1" 基于供需匹配优化的多货品可拆分车辆路径问题模型

1.1" 问题描述

车辆路径问题的供需匹配策略主要有一对一订单匹配、司机（骑手）抢单匹配等，本文设计了基于客户点间距的供需匹配策略，即在众多匹配方案中选择总间距较小的，得到较优的匹配策略。而多货品问题的需求拆分策略主要有遍历拆分、据货品种类或数量拆分等，本文采取的是部分拆分策略，即将同时具有取送货需求的部分客户点进行需求拆分，从而更有可能在满足客户需求的情况下得到较优的车辆路径。具体需求拆分策略如图1所示，假设有两种原料分别用正方形和圆表示，拆分节点的原料用梯形表示，节点1和节点3分别为客户1和客户3的拆分节点，“+”表示送货需求，“-”表示取货需求，箭头表示车辆行驶路线。图1中客户1至客户4均为具有取送货需求的客户点，车辆从配送中心出发后访问客户1和客户3时只能满足其取货需求，因此就需要将其送货需求拆分，在访问客户2和客户4之后再去满足客户1和客户3的送货需求，最终返回配送中心。

本文研究的是基于供需匹配优化的多货品可拆分车辆路径问题，假设有一个配送中心来统一调度车辆运输路径，一个客户可能对多种原料有取货或送货需求，并且可以由车辆分批次配送。遵循尽可能减少车辆调拨次数和行驶距离的原则进行原料配送方案的规划，最终基于供需匹配策略来建立以车辆固定成本和行驶距离成本之和最小为目标的优化模型。

1.2" 模型假设

（1）道路交通顺畅，天气晴朗，车辆的行驶速度恒定；

（2）客户对同一原料的取货或送货需求应当一次性满足，对不同原料的取送货需求可以由车辆通过多次访问来满足；

（3）所有车辆的载重量是恒定且相同的；

（4）每种原料的总需求量不能多于其总供应量。

1.3" 符号说明

A：车辆集合，A=1，2，…，k；V：配送中心和所有客户点集合，V=0，1，…，i；F：所有客户点集合，F=1，2，…，i；F：所有客户节点和拆分节点集合，F=1，2，…，im；E：供需匹配对集合，E=1，2，…，g；N：原料种类集合，N=1，2，…，h；W：访问次数集合，W=1，2，…，m；v：车辆行驶速度；Q：车辆的最大装载量；T：车辆最大工作时间；b：客户i和j之间的距离；c：车辆固定使用成本；c：单位距离的行驶成本；d：客户i对原料h的送货需求量；p：客户i对原料h的取货需求量；

t：车辆k在供需匹配对g的取货节点im开始服务的时间；t：车辆k在供需匹配对g的送货节点jn开始服务的时间；y：0～1变量，如果供需匹配对g由车辆k配送，则其值为1，否则为0；x：0～1变量，如果车辆k第m次访问客户点i后直接行驶到客户点j（第n次访问），则其值为1，否则为0；L：车辆k第m次离开客户i后直接行驶到客户j（第n次访问）时装载原料h数量；q：车辆k在第m次访问客户i时投放原料h的数量；r：车辆k在第m次访问客户i时取出原料h的数量。

1.4" 模型建立

minZ=cx+cbx， m∈W， n∈W" " " " " " " " " " " " " " "（1）

s.t. x=x=1， k∈A， m∈W， n∈W" " " " " " " " " nbsp; " " " " " " " "（2）

x-x=0， j∈V， k∈A， m∈W， n∈W" " " " " " " " " " " " " " " （3）

x≤1， j∈F， m∈W， n∈W" " " " " " " " " " " " " " " " " " " "（4）

Lx≤Q， j∈V， h∈N， m∈W， n∈W" " " " " " " " " " " " " " "（5）

L-q+r-L-Qx≥-Q， j∈F， k∈A， h∈N， m，n∈W" " " " "（6）

L-q+r-L+Qx≤-Q， j∈F， k∈A， h∈N， m，n∈W" " " " "（7）

q=d， i∈F， h∈N， m∈W" " " " " " " " " " " " " " " " " " " " " "（8）

r=p， i∈F， h∈N， m∈W" " " " " " " " " " " " " " " " " " " " " "（9）

y=1， g∈E" " " " " " " " " " " " " " " " " " " " " " " " " " " " （10）

t≤t， k∈A， im∈F， jn∈F， g∈E" " " " " " " " " " " " " " " " " " "（11）

x≤T， k∈A， h∈N， m∈W， n∈W" " " " " " " " " " " " " " "（12）

L=0， i∈V， j∈V， k∈A， h∈N， m∈W， n∈W" " " " " " " " " " " " " "（13）

L=0， i∈V， j∈V， k∈A， h∈N， m∈W， n∈W" " " " " " " " " " " " " "（14）

x≤S-1， k∈A， S？奂V， m∈W， n∈W" " " " " " " " " " " " " "（15）

x∈0，1， y∈0，1， i∈V， j∈V， k∈A， m∈W， n∈W， g∈E" " " " " " "（16）

L≥0， i∈V， j∈V， k∈A， h∈N， m∈W， n∈W" " " " " " " " " " " " " （17）

q，r≥0， i∈F， k∈A， h∈N， m∈W" " " " " " " nbsp; " " " " " " " " " " （18）

式（1）是目标函数，表示车辆的固定使用成本和单位距离的行驶成本之和最小；式（2）表示车辆k的起点和终点都是配送中心；式（3）表示车辆进出平衡约束，即车辆访问了某个客户点之后必须离开；式（4）表示每个拆分节点只能被访问一次；式（5）表示车辆k在运输过程中任意节点的载重量都不能超过车辆的最大载重；式（6）和式（7）表示装载平衡约束，即车辆k在第n次离开客户点j时的装载原料h的数量等于第n次到达客户点j时装载原料h的数量减去在客户点j投放原料h的数量并加上在客户点j取走原料h的数量（若没有需求记为0）；式（8）和式（9）表示要保证满足客户所有的取送货需求；式（10）表示同一供需匹配关系中的取送货需求节点及其拆分出的需求节点必须由同一车辆进行访问；式（11）表示同一供需匹配关系中到达取货需求节点的时间必须早于到达送货需求节点的时间；式（12）表示车辆k的行驶时间不能超过最大工作时间；式（13）和式（14）表示车辆从配送中心空车出发，完成配送后空车返回；式（15）表示消除子回路约束；式（16）表示0～1决策变量约束；式（17）和式（18）表示非负的连续变量约束。

2" 算法设计

求解MCSVRPBSDMO问题需分析如何在保证满足供需匹配策略的情况下制定成本较小的车辆路径，此问题较为复杂。本文首先基于需求拆分策略和供需匹配策略构造初始解，然后采用遗传算法优化配送路径。同时引入了车辆路径调整策略，在满足供需匹配策略的基础上，通过扩大解空间增加产生最优解的可能性，算法流程如图2所示。本文的适应度函数[12]根据式（1）的目标函数变形得到；精英种群选择采用二元锦标赛选择策略[13]；交叉采用OX交叉策略[14]；变异采用两点基因互换的策略[15]。

2.1" 编" 码

本文采用整数编码方式对包含多个供需匹配对的解进行编码，每个供需匹配对包含多个节点。以10个客户点（编号为1～10）、两种原料为例，可以构造如表1所示编码。

其中客户1至客户6表示具有取送货需求的客户点，按照图1的需求拆分策略选取了客户1、客户3、客户5的需求进行拆分，拆分节点依次编码为11、12、13。而客户7、客户9表示对两种原料都只有取货需求的客户点，客户8、客户10表示只有送货需求的客户点。因此可以形成1，2，11、7，8等供需匹配对。

2.2" 初始解的形成

本文根据客户点之间的供需匹配策略构建初始解，将对不同原料都只有一种需求和具有取送货需求的客户点及其拆分出的需求节点分别进行供需匹配，生成初始供需匹配对后储存到新的解空间中并根据客户点间距择优保留。然后打乱供需匹配对应关系，根据总成本最小的优化目标生成一定规模的高质量初始解。

2.3" 车辆路径调整策略

本文不同于普通取送货问题的操作都是在确保符合配送约束的情况下进行，为了能够产生较优解，本文首先不在取送货的约束范围内进行迭代，而是先在较大的解空间中不断优化，最后再根据供需匹配策略对车辆运输路径进行调整，从而满足配送约束。以表1中的10个客户点为例：

（1）根据载重进行分车后可能会出现同一供需匹配关系中的取送货需求节点及其拆分出的需求节点不在同一路径中。

调整前：1-2-7-5-6-（12）-13-（10），3-4-9-（8）-（11）；调整后：1-2-7-5-6-（11）-13-（8），3-4-9-（10）-（12）。

上述例子中，调整前供需匹配对1，2，11、3，4，12、7，8、9，10均出现了取送货需求节点不在同一路径中的情况，因此需要将客户节点11、12互换，将客户8、10互换，以满足配送约束。

（2）交叉、变异后，可能会出现同一供需匹配关系中到达取货需求节点的时间晚于到达送货需求节点的时间。

调整前：3-7-4-8-1-（11）-5-（10）-12-（2）-（9）-6-13；调整后：3-7-4-8-1-（2）-5-（9）-12-（11）-（10）-6-13。

上述例子中，调整前供需匹配对1，2，11、9，10均出现了到达取货需求节点的时间晚于到达送货需求节点的时间的情况，因此需要将客户节点2、11互换，将客户9、10互换，以满足配送约束。

3" 算例分析

3.1" 算例描述

本文采用的数据以Solomon数据集中的RC101为基础，将其修改为针对多货品的可拆分取送货需求数据，据此构建了基于供应链上下游企业的生产配送算例。企业设有一个配送中心，同一型号的配送车辆3台，已知需要服务的客户有20个，需要配送的原料有两种，车辆固定成本为50元/辆，燃油消耗成本为1元/单位里程，供需匹配成本为1元/单位里程。

3.2" 参数分析

本文利用Python编写程序对算例进行模拟，采用遗传算法求解，其参数设置如表2所示。

3.3" 算例结果

求解结果：车辆固定成本100元（两辆车），行驶成本530.736 6元，总成本630.736 6元。最优车辆路径如表3所示（其中0～19为客户节点，20～24为拆分出的需求节点），最优车辆路径图如图3所示，三角形代表客户点，横纵坐标代表客户点所在位置。最优车辆路径对应的供需匹配成本为573.874 08，供需匹配结果如表4所示，供需匹配结果图如图4所示，正方形代表客户点，横纵坐标代表客户点所在位置。

结合表2、表3和图3、图4可以得到车辆最优配送路径中各客户点都尽可能和离自己较近的客户点进行路径连接，而不一定完全按照供需匹配顺序配送。同时供需匹配结果中各客户点也都尽可能以就近原则进行供需匹配，因此能得到较优的供需匹配结果，而本文采用了2.3的车辆路径调整策略，将较优的配送路径据此供需匹配结果进行调整，则能够在确保满足配送约束的前提下获得最优车辆运输路径。

3.4" 供需匹配有效性验证

为验证本文供需匹配策略的有效性，分别采用一对一订单匹配策略（策略1）、司机（骑手）抢单匹配策略（策略2）和本文的匹配策略（策略3，见表1）进行配送，将车辆总成本之和最小作为优化目标。按照参数分析所得结果设置实验，每组运行10次，结果如表5（最优值、最差值、平均值均代表总成本）和表6（最优值、最差值、平均值均代表匹配成本）所示。

结合表5和表6可以得到采用策略3的供需匹配策略进行路径优化结果要优于策略1和策略2，虽然策略1的总成本和供需匹配成本都比较稳定，但解空间偏小，很难有大幅度的优化，会出现行驶距离较长的情况；而策略2虽然最优值和策略3接近，行驶距离都相对较短，但其稳定性较差并且求解效率难以保证。因此，策略3是相对较好的选择，其更有可能得到较优的供需匹配结果和车辆运输路径。

3.5" 可拆分的多货品有效性验证

为验证本文需求拆分策略的有效性，分别采用遍历需求拆分策略（策略1）、本文需求拆分策略（策略2，见图1）进行配送，将车辆的总成本最小作为优化目标。按照参数分析所得结果设置实验，每组运行10次，结果如表7（最优值、最差值、平均值均代表总成本）所示。

从表7中可以得到采用策略2的需求拆分策略进行路径优化结果要优于优于策略1，策略1虽然可以确保满足取送货约束条件，同时能更灵活的调整配送路线，但也会导致拆分的需求节点过多，造成车辆访问次数较多，降低稳定性，增加问题复杂性和运输成本。因此策略2更有可能得到高质量的解，更加适用于多种原料的取送货车辆路径问题。

4" 结" 论

本文将生产运输与调度配送问题相结合，建立了以车辆固定成本和行驶成本之和最小为目标的MCSVRPBSDMO模型，并提出了车辆路径调整策略，采用遗传算法进行求解。通过改进的Solomon数据集进行算例分析，得出了较优的参数取值并进行实验，最终得到了最优车辆路径和最小总成本，同时也验证了本文供需匹配策略和多货品需求拆分策略的有效性，表明其在求解质量和效率上都具有明显优势，可以帮助企业节约配送成本，对理论研究和企业实际运营提供了很好的借鉴意义。由于企业在实际生产过程中可能会出现意外情况，影响供需匹配对应关系，因此未来在模型上可以考虑加入供应量不确定的问题，求解上也可以结合禁忌搜索算法、模拟退火等算法进行进一步优化。

参考文献：

[1]" MIN H. The multiple vehicle routing problem with simultaneous delivery and pick-up points[J]. Transportation Research Part A General， 1989，23（5）：377-386.

[2] 徐倩，熊俊，杨珍花，等. 基于自适应大邻域搜索算法的外卖配送车辆路径优化[J]. 工业工程与管理，2021，26（3）：115-122.

[3]" DOMINIK G. Granular tabu search for the pickup and delivery problem with time windows and electric vehicles[J]. European Journal of Operational Research， 2019，278（3）：821-836.

[4] 任腾，罗天羽，谷智华，等. 考虑同时取送货的城市物流共同配送路径优化[J]. 计算机集成制造系统，2022，28（11）：3523-3534.

[5]" CHEMLA D， MEUNIER F， WOLFLER CALVO R. Bike sharing systems： Solveing the static rebalancing problem[J]. Discrete Optimization， 2013，10（2）：120-146.

[6] 敬鹏程. 基于城市路网众包抢单外卖配送动态路径优化研究[D]. 重庆：重庆交通大学，2021.

[7]" CHEN Q F， LI K P， LIU Z X. Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads[J]. Transportation Research Part E： Logistics amp; Transportation Review， 2014，69（3）：218-235.

[8] 张颖钰，吴立云. 多中心半开放式送取需求可拆分的车辆路径研究[J]. 计算机应用研究，2022，39（8）：2312-2316.

[9] 徐东洋，李昆鹏，郑飘，等. 多车场多车型多品类供需未匹配与可任意拆分取送货车辆路径问题优化[J]. 管理学报，2020，17（7）：1086-1095.

[10]" HERNANDEZ-PEREZ H， et al. Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem[J]. Computers amp; Operations Research， 2018（97）：1-17.

[11] 高振迪，计明军，孔灵睿，等. 多商品分批次取送货的模糊需求车辆路径问题[J]. 运筹与管理，2022，31（11）：59-64.

[12] 孙青伟，张杨. 带同时取送货的选址—多车型路径问题研究[J]. 交通运输工程与信息学报，2017，15（2）：100-104，118.

[13] 张琛，詹志辉. 遗传算法选择策略比较[J]. 计算机工程与设计，2009，30（23）：5471-5474，5478.

[14] 郭庆腾，董学士，李清顺. 基于自适应大邻域搜索的遗传算法求解VRPTW研究[J]. 青岛大学学报（工程技术版），2023，38（2）：1-9.

[15] 田帅辉，欧丽英. 基于改进遗传算法的带时间窗城市配送路径多目标优化[J]. 物流科技，2021，44（11）：7-12，17.

收稿日期：2024-01-23

作者简介：史" 铭（1998—），男，山西长治人，太原科技大学经济与管理学院硕士研究生，研究方向：路径优化；莫思敏（1977—），本文通信作者，女，山西太原人，太原科技大学经济与管理学院，教授，博士，研究方向：智能优化、机器学习。

引文格式：史铭，莫思敏. 基于供需匹配优化的多货品可拆分车辆路径问题[J]. 物流科技，2025，48（3）：21-25.