考虑需求可拆分的雇佣和众包车辆协同运输路径规划模型

doi:10.16381/j.cnki.issn1003-207x.2023.1435

摘要/Abstract

摘要：

众包是社会车辆接受偏离自己的路线向其他人递送物品并获得少量补偿的运输模式。当企业雇佣车辆和社会众包车辆共同参与物流配送时，如何协调这两者的运输路线是企业降低运输成本的关键。本文在这一背景下，考虑客户需求被任意拆分的情况，建立了需求可拆分的协同运输路径规划模型。然后，设计关系模型辅助评价的遗传算法求解模型，算法框架包括上下两层，上层采用0-1编码的遗传算法将客户分配给不同类型的车辆，下层针对上层的分配结果采用自然数编码的遗传算法，分别解决雇佣车辆和众包车辆的路径规划子问题。为了加快下层遗传算法的求解效率，利用支持向量机模型学习解对之间的优劣关系辅助下层遗传算法搜索。最后，基于标准算例库设计测试集并进行数值实验，结果表明，所提出的算法具有较好的性能。企业可以采用协同运输模式，同时，优先使用高容量的众包车辆以降低企业运营成本。

关键词: 车辆路径问题, 众包, 协同运输, 需求可拆分, 关系模型, 遗传算法

Abstract:

Crowdsourcing is a mode of transportation in which social vehicles accept to deviate from their own routes to deliver goods to others for a small amount of compensation. With the popularity of the sharing economy， it has become an important means to reduce logistics and transportation costs. However， there is a significant difference in the transport capacity of vehicles in the crowdsourcing model， and customer needs are split to meet when participating in logistics delivery. At the same time， when enterprises employ both their own vehicles and social crowdsourced vehicles for logistics delivery， the key to reducing transportation costs lies in coordinating the routes of these two types of vehicles. In this paper， considering that customer demand can be split， a collaborative transportation routing model with split demands is established. Then， a genetic algorithm for relational model-assisted evaluation is designed. The algorithm framework consists of two layers： the upper layer adopts the genetic algorithm of 0-1 coding to assign customers to different types of vehicles， and the lower layer adopts the genetic algorithm of real number coding for the distribution results of the upper layer to solve the subproblems of routing problems for hired vehicles and crowdsourcing vehicles respectively. In order to speed up the efficiency of the lower genetic algorithm， support vector machine model is used to learn the relationship between the good and bad of the solution pairs for assisting the search of the lower genetic algorithm. Finally， some test instances based on benchmark instances are designed， and numerical experiments are conducted. The results demonstrate that the proposed algorithm performs well. The management enlightenment obtained from the research is as follows：（1） Enterprises can adopt collaborative transportation mode to reduce transportation costs. （2） In the process of reducing enterprise operating costs， crowd-sourced vehicles with larger available capacity should be given priority.

Key words: vehicle routing problem, crowdsourcing, cooperative transportation, split delivery, relational model, genetic algorithm

中图分类号:

O221.4

周煜丰,吴志彬,向传凯, 等. 考虑需求可拆分的雇佣和众包车辆协同运输路径规划模型[J]. 中国管理科学, 2026, 34(2): 133-144.

Yufeng Zhou,Zhibin Wu,Chuankai Xiang, et al. A Collaborative Route Planning Model for Hiring and Crowdsourcing Vehicles with Split Delivery[J]. Chinese Journal of Management Science, 2026, 34(2): 133-144.

图/表 10

图1

表1

图2

表2

SDVRPHOD模型符号和参数"

参数符号	含义
$V 0 = {0}$	仓储中心集合，
$C = {1, …, n}$	客户集合，用 $i ∈ C$ 表示客户索引
$V = {0,1, …, n}$	仓储中心和客户集合
$S = {n + 1, …, n + k o}$	众包车辆起始点集合，用 $s k ∈ S$ 表示众包车辆起始点索引
$D = {n + k o + 1, …, n + 2 k o}$	众包车辆目的地集合，用 $d k ∈ D$ 表示众包车辆目的地索引
$K H = {1, …, k h}$	雇佣车辆集合，用 $k ∈ K H$ 表示雇佣车辆索引
$K O = {1, …, k o}$	众包车辆集合，用 $k ∈ K O$ 表示众包车辆索引
$Q$	雇佣车辆最大载重量，全为同型号车辆
$Q k$	众包车辆最大载重量，不同型号的车辆， $k ∈ K O$
$F$	雇佣车辆的固定成本
$c i j$	节点 $i$ 和节点 $j$ 之间的旅行成本， $i, j ∈ V 0 ⋃ C ⋃ S ⋃ D$
$p$	众包车辆绕路行驶的补偿系数
$c s k d k$	众包车辆 $k$ 起始节点和目的地节点之间的旅行成本， $k ∈ K O$
$d i$	客户 $i$ 的需求量， $i ∈ C$
$l i j$	从节点 $i$ 到节点 $j$ 的行驶距离，与 $c i j$ 线性相关
决策变量	含义
$x i j k$	0-1决策变量，为1表示雇佣车辆 $k (k ∈ K H)$ 从节点 $i$ 行驶到节点 $j$
$r i j k$	0-1决策变量，为1表示众包车辆 $k (k ∈ K O)$ 从节点 $i$ 行驶到节点 $j$
$z i$	0-1决策变量，为1表示客户节点 $i (i ∈ C)$ 被众包车辆服务
$y i k$	取货变量，雇佣车辆 $k (k ∈ K H)$ 在客户节点 $i (i ∈ C)$ 的取货量
$o i k$	取货变量，众包车辆 $k (k ∈ K O)$ 在客户节点 $i (i ∈ C)$ 的取货量
$α i j k$	载重变量，车辆 $k (k ∈ K O)$ 经过弧 $(i, j)$ 的载重量

表2

图3

图4

表3

表4

图5

表5

参考文献 27

[1]	潘雯雯，郭海湘，周光勇，等. 基于两阶段算法的需求可拆分多车型车辆路径问题［J］. 中国管理科学， 2016， 24（S1）： 55-61.
	Pan W W， Guo H X， Zhou G Y， et al. Research on split delivery andheterogeneous fleet vehicle routing problem based on two phase algorithm［J］. Chinese Journal of Management Science， 2016， 24（S1）： 55-61.
[2]	Henke T， Speranza M G， Wäscher G. A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes［J］. Annals of Operations Research， 2019， 275（2）： 321-338.
[3]	Miranda-de la Lama G C， Villarroel M， María G A. Livestock transport from the perspective of the pre-slaughter logistic chain： A review［J］. Meat Science， 2014， 98（1）： 9-20.
[4]	Polat O， Topaloğlu D. Collection of different types of milk with multi-tank tankers under uncertainty： A real case study［J］. TOP， 2022， 30（1）： 1-33.
[5]	Guo F， Huang Z， Huang W. Heuristic approaches for a vehicle routing problem with an incompatible loading constraint and splitting deliveries by order［J］. Computers & Operations Research， 2021， 134： 105379.
[6]	Dror M， Trudeau P. Split delivery routing［J］. Naval Research Logistics （NRL）， 1990， 37（3）： 383-402.
[7]	Claudia Archetti M W P S. Worst-case analysis for split delivery vehicle routing problems［J］. Transportation Science， 2006， 40（2）： 226-234.
[8]	Ho S C， Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries［J］. Computers & Operations Research， 2004， 31（12）： 1947-1964.
[9]	Mitra S. A parallel clustering technique for the vehicle routing problem with split deliveries and pickups［J］. Journal of the Operational Research Society， 2008， 59（11）： 1532-1546.
[10]	Chen P， Golden B， Wang X， et al. A novel approach to solve the split delivery vehicle routing problem［J］. International Transactions in Operational Research， 2017， 24（1-2）： 27-41.
[11]	He P， Hao J K. General edge assembly crossover-driven memetic search for split delivery vehicle routing［J］. Transportation Science， 2023， 57（2）： 482-511.
[12]	范厚明，张轩，任晓雪，等. 多中心开放且需求可拆分的VRPSDP问题优化［J］. 系统工程理论与实践， 2021， 41（6）： 1521-1534.
	Fan H M， Zhang X， Ren X X， et al. Optimization of multi-depot open split delivery vehicle routing problem with simultaneous delivery and pick-up［J］. Systems Engineering-Theory & Practice， 2021， 41（6）： 1521-1534.
[13]	Desaulniers G. Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows［J］.Operations Research， 2010，58（1）： 179-192.
[14]	Bianchessi N， Drexl M， Irnich S. The split delivery vehicle routing problem with time windows and customer inconvenience constraints［J］. Transportation Science， 2019， 53（4）： 1067-1084.
[15]	揭婉晨，侍颖，杨，等. 需求可拆分电动汽车车辆路径问题及其改进分支定价算法研究［J］. 管理学报， 2020， 17（12）： 1873-1880.
	Jie W C， Shi Y， Y， et al. Split delivery routing problem of electric vehicles and its modified branch-and-price algorithm［J］. Chinese Journal of Management， 2020， 17（12）： 1873-1880.
[16]	Archetti C， Savelsbergh M， Speranza M G. The vehicle routing problem with occasional drivers［J］. European Journal of Operational Research， 2016， 254（2）： 472-480.
[17]	Devari A， Nikolaev A G， He Q. Crowdsourcing the last mile delivery of online orders by exploiting the social networks of retail store customers［J］. Transportation Research Part E： Logistics and Transportation Review， 2017， 105： 105-122.
[18]	Macrina G， Di Puglia Pugliese L， Guerriero F， et al. Crowd-shipping with time windows and transshipment nodes［J］. Computers & Operations Research， 2020， 113： 104806.
[19]	Kafle N， Zou B， Lin J. Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery［J］. Transportation Research Part B： Methodological， 2017， 99： 62-82.
[20]	Behrend M， Meisel F， Fagerholt K， et al. An exact solution method for the capacitated item-sharing and crowdshipping problem［J］. European Journal of Operational Research， 2019， 279（2）： 589-604.
[21]	Boysen N， Emde S， Schwerdfeger S. Crowdshipping by employees of distribution centers： Optimization approaches for matching supply and demand［J］. European Journal of Operational Research， 2022， 296（2）： 539-556.
[22]	Macrina G， Di Puglia Pugliese L， Guerriero F， et al. The vehicle routing problem with occasional drivers and time windows［C］//Proceedings of Optimization and Decision Science： Methodologies and Applications， Cham， November 5， Springer， 2017： 577-587.
[23]	Wu S H， Zhan Z H， Zhang J. SAFE： Scale-adaptive fitness evaluation method for expensive optimization problems［J］. IEEE Transactions on Evolutionary Computation， 2021， 25（3）： 478-491.
[24]	Baller A C， Dabia S， Dullaert W E H， et al. The vehicle routing problem with partial outsourcing［J］. Transportation Science， 2020， 54（4）： 1034-1052.
[25]	Vidal T， Crainic T G， Gendreau M， et al. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows［J］. Computers & Operations Research， 2013， 40（1）： 475-489.
[26]	Hao H， Zhou A， Qian H， et al. Expensive multiobjective optimization by relation learning and prediction［J］. IEEE Transactions on Evolutionary Computation， 2022， 26（5）： 1157-1170.
[27]	Jin Y， Wang H， Chugh T， et al. Data-driven evolutionary optimization： An overview and case studies［J］. IEEE Transactions on Evolutionary Computation， 2019， 23（3）： 442-458.

参考文献	需求拆分方式			车辆类型		众包配送模式			求解方法
参考文献	任意拆分	部分拆分	不拆分	单车型	多车型	一对一	一对多	多对一	精确算法	启发式算法
He和Hao^[11]	√			√						√
揭婉晨等^[15]	√			√					√
Archetti等^[16]			√	√		√				√
Boysen等^[21]			√		√	√	√		√
Wu等^[23]			√	√		√				√
Baller等^[24]		√			√	√	√		√
本文	√				√	√	√	√		√

算例类型	算例编号	众包车辆编号
A	A-n32-k5、A-n39-k6、A-n48-k7、A-n80-k10	A-n80-k10
B	B-n31-k5、B-n45-k5、B-n56-k7、B-n67-k10	B-n78-k10
P	P-n40-k5、P-n50-k10、P-n60-k10、P-n101-k14	P-n101-k4

测试问题	GA-Greedy				GA2-TNS				RSGA-TNS
测试问题	Best	Avg	Gap/%	Time/s	Best	Avg	Gap/%	Time/s	Best	Avg	Gap/%	Time/s
A-n32-k5	2395.72	2484.92	-10.29	1.32	2149.13	2244.47	-0.00	368.23	2209.59	2262.92	-2.74	689.30
A-n39-k6	3044.99	3137.29	-12.80	1.72	2655.26	2760.29	-0.00	641.08	2692.62	2798.49	-1.39	834.00
A-n48-k7	3866.59	4046.58	-15.55	2.06	3331.52	3408.51	-1.98	1193.85	3265.50	3356.16	0.00	1013.16
A-n80-k10	6279.28	6482.63	-16.15	2.09	5529.02	5589.61	-4.77	1549.46	5265.34	5302.11	0.00	1368.71
B-n31-k5	1634.42	1670.23	-0.00	1.40	1811.34	1828.66	-9.77	715.98	1776.61	1818.42	-8.00	867.18
B-n45-k5	2697.91	2829.36	-13.43	1.97	2539.15	2565.57	-8.02	906.28	2335.46	2373.80	0.00	902.93
B-n56-k7	3723.42	3887.75	-17.74	1.47	3473.26	3602.10	-11.82	958.91	3062.76	3135.36	0.00	902.86
B-n67-k10	6320.59	6593.33	-22.51	1.84	5913.64	5967.69	-17.18	1082.05	4897.94	5221.66	0.00	1344.32
P-n40-k5	2218.86	2329.80	-4.49	1.51	2252.37	2299.39	-5.91	557.62	2119.29	2198.33	0.00	707.90
P-n50-k10	4240.81	4366.81	-1.50	2.25	4444.81	4492.93	-6.02	729.44	4177.08	4279.94	0.00	911.69
P-n60-k10	4699.79	4866.13	-10.64	1.67	4481.92	4511.40	-6.30	694.84	4199.69	4366.41	0.00	659.14
P-n101-k4	3578.19	3935.77	-18.76	2.46	3609.40	3774.09	-19.46	873.44	2906.83	3083.17	0.00	873.56

序号 A-n32-k5	SDVRP-HV			SDVRP-OD			VRPHOD			SDVRPHOD
序号 A-n32-k5	L(L_HV )	K_HV	T	L(L_OD )	K_OD	T	L(L_HV /L_OD )	K_HV/K_OD	T	L(L_HV /L_OD )	K_HV /K_OD	T
1	991.28	5	991.28	632.94	33	632.94	241.78/249.02	1/19	490.80	390.61/231.07	2/20	621.68
2	972.73	5	972.73	716.43	35	716.43	264.73/165.54	1/18	430.27	328.55/269.86	2/20	598.41
3	1012.85	5	1012.85	590.80	30	590.80	309.41/152.26	1/19	461.67	255.43/360.15	1/23	615.68
4	987.68	5	987.68	578.95	33	578.95	271.42/234.43	1/20	505.84	318.99/301.71	1/21	620.70
5	997.93	5	997.93	724.58	30	724.58	269.99/149.48	1/21	419.47	337.62/258.52	1/22	596.14
6	979.68	5	979.68	762.38	32	762.38	329.81/257.85	1/21	587.67	251.82/380.04	1/24	631.86
7	993.72	5	993.72	647.33	28	647.33	298.89/139.91	1/19	438.80	381.57/254.96	2/18	636.54
8	975.10	5	975.10	733.09	32	733.09	288.07/175.13	1/19	463.20	318.46/260.21	2/19	578.67
9	1020.15	5	1020.15	748.82	30	748.82	264.51/146.67	1/19	411.18	507.26/156.32	2/17	663.58
10	992.33	5	992.33	679.60	30	679.60	286.31/125.98	1/19	412.29	343.35/292.33	2/20	635.68
平均值	992.35	5	992.35	681.49	31.3	681.49	282.49/179.63	1/19.4	462.12	343.37/276.52	1.6/20.4	619.88
最优解	972.73	5	972.73	578.95	28	578.95	241.78/125.98	1/18	411.18	251.82/156.32	1/17	578.67
最劣解	1020.15	5	1020.15	762.38	35	762.38	329.81/257.85	1/21	587.67	507.26/380.04	2/24	663.58
改进%			37.53			9.04			-34.14