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

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

Abstract

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

CLC Number:

O221.4

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.

Figures/Tables 10

参数符号	含义
$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)$ 的载重量

References 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

A Collaborative Route Planning Model for Hiring and Crowdsourcing Vehicles with Split Delivery

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 27

Related Articles 15

Metrics

Comments

Recommended 0

[1]	Shang Gao, Jing Zhou, Ting Luo. Design and Selection of Incentive Contract for Crowdsourcing Contest Considering Fairness Concern and Altruistic Preference [J]. Chinese Journal of Management Science, 2025, 33(7): 284-293.
[2]	Sha Tao, Jing Jin, Jing Zhou. The Integrated Optimization Project Scheduling and Personnel Assignment Considering Online-Onsite Collaboration [J]. Chinese Journal of Management Science, 2025, 33(6): 85-95.
[3]	Song Xue, Xu Chen, Chao Li, Jingchun Feng. Research on Miniature Multi-Project Scheduling of Service Project Enterprises Considering the Evolution of Human Resources Skills [J]. Chinese Journal of Management Science, 2025, 33(6): 96-104.
[4]	Lili Zhang, Zhengrui Chen, Yang Yang, Shi Dan. One-to-many “Personnel-task” Assignment Method for Maintenance Project of Hazardous Chemicals Production Equipment Considering Complexity [J]. Chinese Journal of Management Science, 2025, 33(4): 175-184.
[5]	Keyi Zhang, Yong Shi, Haixiang Guo, Yongzheng Sun. Optimal Decision-Making for Dispatching Emergency Supplies for Natural Disasters in Mountainous Areas Based on Truck-Drone Collaboration [J]. Chinese Journal of Management Science, 2025, 33(2): 150-160.
[6]	Yuanyuan Jiang, He Luo, Zhiwei Wu, Zhiming Cai, Guoqiang Wang. Research on the Joint Optimization of Procurement Planning and Supplier Selection for the Overseas Base of Manufacturing Enterprises [J]. Chinese Journal of Management Science, 2025, 33(10): 126-137.
[7]	Tieke Li,Yixuan Su,Wenxin Zhang,Bailin Wang. Interval Multi-objective Optimal Scheduling for Steelmaking-continuous Casting with Processing Time Uncertainty [J]. Chinese Journal of Management Science, 2024, 32(8): 95-106.
[8]	Zihao Chu,Zhe Xu,Dongning Liu. Model and Algorithm on Stochastic Scheduling Problem with Activity Overlapping [J]. Chinese Journal of Management Science, 2024, 32(7): 84-94.
[9]	Zhengchi Liu,Bo Liang,Tao Ma. Reward Size, Ability Distribution and Incentive Effects of Crowdsourcing: A Model Analysis on All-Pay Auctions [J]. Chinese Journal of Management Science, 2024, 32(6): 13-21.
[10]	Xingguang Chen,Xinyu Li,Luqiang Cheng. Research on Optimization Strategy of Food Delivery Crowdsourcing Delivery Considering Order Preference [J]. Chinese Journal of Management Science, 2024, 32(6): 86-97.
[11]	Ling Zhang,Pengfei Gao,Lin Zhang. Research on Emergency Evacuation and Material Allocation Based on Deprivation Cost [J]. Chinese Journal of Management Science, 2024, 32(5): 187-195.
[12]	Xiuli Meng,Jing Yang,Bo Liu. Competition Strategy of Crowdsourcing Logistics Service Quality Based on Big Data Technology [J]. Chinese Journal of Management Science, 2024, 32(4): 130-140.
[13]	Zujun Ma, Yiran Wang. Optimal Location and Capacity of Pre-cooling Facilities Considering the First-Mile Loss of Fresh Agri-products [J]. Chinese Journal of Management Science, 2024, 32(2): 315-323.
[14]	Guiqin Xue, Xianlong Ge. Study on Two-stage Dynamic Vehicle Scheduling Optimization Considering the Proactive Category [J]. Chinese Journal of Management Science, 2024, 32(12): 164-172.
[15]	Xinyue Zhang,Peng Jin,Xiaoxuan Hu,Moning Zhu. Research on the Time-dependent Multi-depot Open Vehicle Routing Problem with Time Windows [J]. Chinese Journal of Management Science, 2024, 32(1): 146-157.