考虑时间窗指派的多中心开闭混合式车辆路径问题

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

摘要/Abstract

摘要：

针对带时间窗的多中心车辆路径问题在客户服务时间窗违反规避和运输资源共享相结合方面存在的不足，提出时间窗指派和运输资源共享策略，研究了考虑时间窗指派的多中心开闭混合式车辆路径问题。首先，构建了包含配送成本、运输成本、惩罚成本和时间窗指派成本等物流运营总成本最小化和配送车辆使用数最少化的双目标数学模型。其次，提出了基于K-means聚类的改进多目标粒子群混合算法求解模型，该混合算法结合扫描算法提高了初始可行解的质量，应用外部存档更新机制增强了算法的鲁棒性，并集成时间窗指派策略和运输资源共享策略提高了算法的收敛速度。然后，将所提出算法与CPLEX求解器、非支配排序遗传算法-Ⅱ、多目标蚁群算法和多目标模拟退火算法进行对比分析，验证了所提模型和算法的有效性。最后，结合实例数据对考虑时间窗指派的多中心开闭混合式车辆路径问题进行了实证研究，并探讨了算法参数选择，以及时间窗指派、运输资源共享与多中心开闭混合式车辆路径设计不同组合模式下物流运营总成本和配送车辆使用数等相关指标的变化情况。研究结果表明，时间窗指派策略有利于减少违反客户时间窗的现象，运输资源共享策略有助于实现物流配送资源的合理化配置，进而能够有效降低企业物流运营总成本和提高多中心物流配送网络资源配置效率。本研究有助于城市物流多中心共同配送体系的构建，进而可为多层次多中心物流配送网络优化问题提供理论支持和方法借鉴。

关键词: 多中心开闭混合式车辆路径, 时间窗指派, 运输资源共享, 改进多目标粒子群算法, 外部存档更新机制

Abstract:

With the rapid development of the information technology and e-commerce industry， online shopping has become an important and indispensable part of residents’ daily lives. The full-time sale characteristic of online shopping platforms makes the logistics demand show a blowout growth， which leads to the prominent contradiction between limited logistics resources and the growing logistics demands， and puts forward higher requirements for the resource coordination and time urgency of the urban logistics system. Given the shortcomings of the multi-center vehicle routing problem with time windows in combining resource sharing and customer service time window violation avoidance， a transportation resource sharing strategy and a time window assignment strategy are proposed， and a multi-center closeopen mixed vehicle routing problem with time window assignment is studied. First， combining the time window assignment strategy and the design of open-closed mixed vehicle routes， a bi-objective optimization model is established to minimize the total operating cost and the number of delivery vehicles. The total operating cost is composed of centralized transportation cost， vehicle maintenance cost， delivery cost， penalty cost for violating time windows， time window assignment cost， and incentive subsidy for distribution center collaboration. Second， an improved multi-objective particle swarm hybrid algorithm based on K-means clustering is proposed. The proposed hybrid algorithm divides the service periods according to the customer time window characteristics， and combines the scanning algorithm to improve the quality of the initial feasible solution. The external archive update mechanism is applied to enhance the robustness of the proposed algorithm， and the time window assignment strategy and transportation resource sharing strategy are integrated to improve the convergence speed of the proposed algorithm. Third， the proposed algorithm is compared with CPLEX solver， the non-dominated sorting genetic algorithm-Ⅱ， the multi-objective ant colony algorithm， and the multi-objective simulated annealing algorithm to verify the effectiveness of the proposed model and algorithm. Finally， combined with a multi-center logistics network in Chongqing City， China， a case study is explored on the multi-center closeopen mixed vehicle routing problem with time window assignment， furthermore， the selection of relevant parameter values for the proposed algorithm is analyzed and discussed. The changes in related indicators such as delivery cost， transportation cost， total operating cost， and number of delivery vehicles are discussed under different combination modes of time window assignment， transportation resource sharing， and multi-center closeopen mixed vehicle routing design. The research results show that the time window assignment strategy is conducive to reducing customer time window violations. For example， in the case study， the application of the time window assignment strategy resulted in a 47.5% reduction in the penalty cost and a 10.8% reduction in the total logistics operating cost， and the number of delivery vehicles decreased by 2.The transportation resource sharing strategy and open-closed mixed vehicle routing design help to achieve the reasonable allocation of logistics distribution resources， thereby effectively reducing the logistics operating cost of logistics enterprise and improving the resource allocation efficiency of multi-center logistics distribution networks. Therefore， the research is conducive to constructing a multi-center joint distribution system for urban logistics and can provide theoretical support and method reference for the research on multi-level multi-center logistics distribution network optimization problems.

Key words: multi-center close-open mixed vehicle routing problem, time window assignment, transportation resource sharing, improved multi-objective particle swarm algorithm, external archive update mechanism

中图分类号:

U116

王勇,史亭亭,苟梦圆, 等. 考虑时间窗指派的多中心开闭混合式车辆路径问题[J]. 中国管理科学, 2026, 34(7): 189-205.

Yong Wang,Tingting Shi,Mengyuan Gou, et al. Multi-center CloseOpen Mixed Vehicle Routing Problem with Time Window Assignment[J]. Chinese Journal of Management Science, 2026, 34(7): 189-205.

图/表 17

图1

表1

表2

相关符号和变量定义"

符号	定义
集合
$O$	配送中心集合， $o ∈ O$
$C$	客户点集合， $c ∈ C$
$R$	配送服务时间段集合，主要是根据客户服务时间窗分布特征，划分的服务时间段集合， $r ∈ R$
$E$	运输车辆集合， $e ∈ E$
$H$	配送车辆集合， $h ∈ H$
$F$	不可指派时间窗的客户点集合， $F ⊂ C$
$A$	可指派时间窗的客户点集合， $A ⊂ C$
$E r$	第r时间段内，用于服务配送中心的运输车辆集合， $r ∈ R$
$H r$	第r时间段内，用于服务客户点的配送车辆集合， $r ∈ R$
$K h r$	第r时间段内，配送车辆h的配送线路集合， $r ∈ R, h ∈ H, k ∈ K h r$
$C h k r$	第r时间段内，配送车辆h在第k条配送线路中服务的客户点集合， $r ∈ R, h ∈ H, k ∈ K h r$
参数
$M e$	运输车辆e的最大装载量， $e ∈ E$
$M h$	配送车辆h的最大装载量， $h ∈ H$
$v e$	运输车辆e单位距离的运输成本， $e ∈ E$
$v h$	配送车辆h单位距离的配送成本， $h ∈ H$
$m c r$	第r时间段内，客户点c的需求量， $c ∈ C, r ∈ R$
$d o r$	第r时间段内，配送中心o的最大配送量， $o ∈ O, r ∈ R$
$D o o'$	配送中心o到o´的距离， $o, o' ∈ O$
$d i j$	节点i到节点j的距离， $i ∈ O ⋃ C, j ∈ O ⋃ C$
$W e$	运输车辆e的年度维护成本， $e ∈ E$
$W h$	配送车辆h的年度维护成本， $h ∈ H$
$E r$	第r时间段内使用的运输车辆数量， $r ∈ R$
$H r$	第r时间段内使用的配送车辆数量， $r ∈ R$
$K h r$	第r时间段内，配送车辆h的配送线路总数， $h ∈ H, r ∈ R$
$R$	配送中心所划分时间段的总数量， $r ∈ R$
$C h k r$	第r时间段内，配送车辆h在第k条配送线路中服务的客户点的数量， $h ∈ H, r ∈ R, k ∈ K h r, C h k r ⊆ C$
$[E o r, L o r]$	第r时间段内，配送中心o的服务时间窗， $o ∈ O, r ∈ R$
$[a c, b c]$	不可指派时间窗的客户点c的服务时间窗， $c ∈ F$
$[l c, r c]$	可指派时间窗的客户点c的服务时间窗， $c ∈ A$
$[α c, β c]$	指派给客户点c的服务时间窗， $c ∈ A$
$G T o h k r$	第r时间段内，配送车辆h在第k条配送线路上从配送中心o出发的时间， $o ∈ O, r ∈ R, h ∈ H, k ∈ K h r$
$F T o e r$	第r时间段内，运输车辆e到达配送中心o的时间， $e ∈ E, o ∈ O, r ∈ R$
$t i j h k r$	第r时间段内，配送车辆h在第k条配送线路上从节点i到j的行驶时间， $i ∈ O ⋃ C, j ∈ O ⋃ C, h ∈ H, r ∈ R, k ∈ K h r$
$a t i h k r$	第r时间段内，配送车辆h在第k条配送线路上到达节点i的时间， $i ∈ O ⋃ C, h ∈ H, r ∈ R, k ∈ K h r$
$ε e$	运输车辆e提前到达配送中心的单位时间惩罚成本， $e ∈ E$
$η e$	运输车辆e晚到配送中心的单位时间惩罚成本， $e ∈ E$
$ε h$	配送车辆h提前到达客户点的单位时间惩罚成本， $h ∈ H$
$η h$	配送车辆h晚到客户点的单位时间惩罚成本， $h ∈ H$
$σ$	时间窗指派的单位时间成本系数
$B o$	配送中心o加入联盟时的政府补贴， $o ∈ O$
$P$	一个正无穷大的数
$Q$	一年内工作周期的数量
决策变量
$x i j h k r$	第r时间段内，如果配送车辆h通过第k条线路从节点i行驶到节点j， $x i j h k r = 1$ ，否则 $x i j h k r = 0$ ， $i ∈ O ⋃ C, j ∈ O ⋃ C, h ∈ H, r ∈ R, k ∈ K h r$
$y o o' e r$	第r时间段内，如果运输车辆e从配送中心o到o´， $y o o' e r = 1$ ，否则 $y o o' e r = 0$ ， $o, o' ∈ O, o ≠ o', e ∈ E, r ∈ R$
$z o c h r$	第r时间段内，如果配送车辆h从配送中心o出发服务客户点c， $z o c h r = 1$ ，否则 $z o c h r = 0$ ， $o ∈ O, c ∈ C, h ∈ H, r ∈ R$
$λ h r$	第r时间段内，配送车辆h被用于服务客户， $λ h r = 1$ ，否则 $λ h r = 0$ ， $h ∈ H, r ∈ R$
$δ o c o' r$	第r时间段内，如果属于o的客户点c被指派给o´服务， $δ o c o' r = 1$ ，否则 $δ o c o' r = 0$ ， $o, o' ∈ O, o ≠ o', c ∈ C, r ∈ R$
$T A c$	如果客户c被指派时间窗， $T A c = 1$ ，否则 $T A c = 0$ ， $c ∈ A$
$α o$	如果配送中心o参与合作， $α o = 1$ ，否则 $α o = 0$ ， $o ∈ O$

表2

图2

图3

图4

表3

图5

图6

表4

图7

表5

表6

表7

考虑时间窗指派的多中心开闭混合式车辆路径优化方案"

配送车辆	时间段	起点	终点	优化后配送路径
V1	$[480,720]$	DC1	DC1	DC1→C20→C37→C44→C34→C24→C25→C127→C19→C4→DC1
V1	$[720,1080]$	DC1	DC1	DC1→C5→C16→C8→C12→C3→C9→C7→C17*→DC1
V2	$[480,720]$	DC1	DC1	DC1→C6→C92→C101→C93→C111→C85→C10*→C11→DC1
V2	$[720,1080]$	DC1	DC3	DC1→C18→C21→C23→C58→C22→C126→C73→C61→C38→DC3
V3	$[480,720]$	DC1	DC2	DC1→C1→C97→C15→C2→C45→C40→C42→DC2
V3	$[720,1080]$	DC2	DC2	DC2→C60→C54→C41→C32→C28→C26→C29→C49→C74→C53→C30→C27→C33→DC2
V4	$[480,720]$	DC2	DC2	DC2→C31→C39→C51→C36→C46→C59→C43*→DC2
V4	$[720,1080]$	DC2	DC3	DC2→C50→C57→C48→C122→C71→C83→C80→C56→C47*→DC3
V5	$[480,720]$	DC3	DC3	DC3→C76→C84→C66→C75→C72→C123→C89→C125→C81*→C35→C82→C55→DC3
V5	$[720,1080]$	DC3	DC3	DC3→C52→C68→C65→C90→C69→C67→C70→C88→C86→DC3
V6	$[480,720]$	DC3	DC4	DC3→C62→C63→C64→C77→C116→C113→C114→C79*→DC4
V6	$[720,1080]$	DC4	DC4	DC4→C105→C112→C118→C98→C120→C119→C109→C117→C108→C78→C96*→DC4
V7	$[480,720]$	DC4	DC4	DC4→C102→C110→C106→C128→C124→C100→C103→C121→C115→C91→C13→C14→C104→DC4
V7	$[720,1080]$	DC4	DC1	DC4→C87→C95→C94*→C107→C99→DC1

表7

图8

表8

图9

参考文献 28

[1]	徐小峰，姜明月，邓忆瑞. 整合逆向物流协同配送动态路径优化问题研究［J］. 管理科学学报， 2021， 24（10）： 106-126.
	Xu X F， Jiang M Y， Deng Y R. Dynamic vehicle routing problem with simultaneous pickup and delivery in collaborative distribution under demand concurrent［J］. Journal of Management Sciences in China， 2021， 24（10）： 106-126.
[2]	Côté J F， Mansini R， Raffaele A. Multi-period time window assignment for attended home delivery［J］. European Journal of Operational Research， 2024， 316（1）： 295-309.
[3]	Li Y， Soleimani H， Zohal M. An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives［J］. Journal of Cleaner Production， 2019， 227： 1161-1172.
[4]	Zhen L， Ma C， Wang K， et al. Multi-depot multi-trip vehicle routing problem with time windows and release dates［J］. Transportation Research Part E： Logistics and Transportation Review， 2020， 135： 101866.
[5]	饶卫振，高召珣，朱庆华. 依托平台农超对接运营模式及物流协作机制研究［J］. 中国管理科学，2026， 34（5）： 242-255.
	Rao W Z， Gao Z X， Zhu Q H. Research on the operation mode and logistics cooperation mechanism based on the platform agriculture-supermarket docking［J］. Chinese Journal of Management Science， 2026， 34（5）： 242-255.
[6]	Brandão J. A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem［J］. European Journal of Operational Research， 2020， 284（2）： 559-571.
[7]	范厚明，杨成，张跃光，等. 混合时间窗下多中心混合车队车辆路径优化［J］. 计算机集成制造系统， 2023， 29（10）： 3529-3546.
	Fan H M， Yang C， Zhang Y G， et al. Multi-depot mixed fleet vehicle routing problem with mixed time windows［J］. Computer Integrated Manufacturing Systems， 2023， 29（10）： 3529-3546.
[8]	Subramanyam A， Wang A， Gounaris C E. A scenario decomposition algorithm for strategic time window assignment vehicle routing problems［J］. Transportation Research Part B： Methodological，2018， 117： 296-317.
[9]	Baradaran V， Shafaei A， Hosseinian A H. Stochastic vehicle routing problem with heterogeneous vehicles and multiple prioritized time windows： Mathematical modeling and solution approach［J］. Computers & Industrial Engineering， 2019， 131： 187-199.
[10]	Martins S， Ostermeier M， Amorim P， et al. Product-oriented time window assignment for a multi-compartment vehicle routing problem［J］. European Journal of Operational Research， 2019， 276（3）： 893-909.
[11]	Jalilvand M， Bashiri M， Nikzad E. An effective Progressive Hedging algorithm for the two-layers time window assignment vehicle routing problem in a stochastic environment［J］. Expert Systems with Applications， 2021， 165： 113877.
[12]	Hoogeboom M， Adulyasak Y， Dullaert W， et al. The robust vehicle routing problem with time window assignments［J］. Transportation Science， 2021， 55（2）： 395-413.
[13]	Liu G， Hu J， Yang Y， et al. Vehicle routing problem in cold Chain logistics： A joint distribution model with carbon trading mechanisms［J］. Resources， Conservation and Recycling， 2020， 156： 104715.
[14]	Mancini S， Gansterer M， Hartl R F. The collaborative consistent vehicle routing problem with workload balance［J］. European Journal of Operational Research， 2021， 293（3）： 955-965.
[15]	Dumez D， Lehuédé F， Péton O. A large neighborhood search approach to the vehicle routing problem with delivery options［J］. Transportation Research Part B： Methodological， 2021， 144： 103-132.
[16]	Zhang Q， Wang Z， Huang M， et al. Heterogeneous multi-depot collaborative vehicle routing problem［J］. Transportation Research Part B：Methodological， 2022， 160： 1-20.
[17]	王勇，魏远晗，蒋琼，等. 三维装载约束下基于运输资源共享的车辆路径问题［J］. 计算机集成制造系统， 2023， 29（9）： 3153-3170.
	Wang Y， Wei Y H， Jiang Q， et al. Vehicle routing problem based on transportation resource sharing under three-dimensional loading constraints［J］. Computer Integrated Manufacturing Systems， 2023， 29（9）： 3153-3170.
[18]	Asgharieh Ahari S， Bakir I， Roodbergen K J. A new perspective on carrier collaboration： Collaborative vehicle utilization［J］. Transportation Research Part C： Emerging Technologies， 2024， 163： 104647.
[19]	Wang Y， Wang X， Guan X， et al. A combined intelligent and game theoretical methodology for collaborative multicenter pickup and delivery problems with time window assignment［J］. Applied Soft Computing， 2021， 113： 107875.
[20]	Wang Y， Sun Y Y， Guan X， et al. Two-echelon multi-period location routing problem with shared transportation resource［J］. Knowledge-Based Systems， 2021， 226： 107168.
[21]	Ikotun A M， Ezugwu A E， Abualigah L， et al. K-means clustering algorithms： A comprehensive review， variants analysis， and advances in the era of big data［J］. Information Sciences， 2023， 622： 178-210.
[22]	Daneshgadeh Çakmakçı S， Kemmerich T， Ahmed T， et al. Online DDoS attack detection using Mahalanobis distance and Kernel-based learning algorithm［J］. Journal of Network and Computer Applications， 2020， 168： 102756.
[23]	Patel S P， Upadhyay S H. Euclidean distance based feature ranking and subset selection for bearing fault diagnosis［J］. Expert Systems with Applications， 2020， 154： 113400.
[24]	周鲜成，蒋涛营，贺彩虹，等. 冷链物流配送的绿色车辆路径模型及其求解算法［J］. 中国管理科学， 2023， 31（12）： 203-214.
	Zhou X C， Jiang T Y， He C H， et al. Green vehicle routing model and its solution algorithm in cold-chain logistics distribution［J］. Chinese Journal of Management Science， 2023， 31（12）： 203-214.
[25]	Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints［J］. Operations Research， 1987， 35（2）： 254-265.
[26]	徐小峰，林姿汝，周鹏. 多油品供给受限下多油库被动配送车辆路径问题研究［J］. 中国管理科学， 2021， 29（5）： 157-165.
	Xu X F， Lin Z R， Zhou P. Research on vehicle routing problem of multiple oil depot passive distribution under multi oil supply constraints［J］. Chinese Journal of Management Science， 2021， 29（5）： 157-165.
[27]	Lu Y， Yang J， Yang C. A humanitarian vehicle routing problem synchronized with drones in time-varying weather conditions［J］. Computers & Industrial Engineering， 2023， 184： 109563.
[28]	陈婉茹，徐光明，张得志，等. 碳交易机制下多中心混合车队配送路径和速度优化研究［J］. 系统工程理论与实践， 2023， 43（11）： 3320-3335.
	Chen W R， Xu G M， Zhang D Z， et al. Multi-depot mixed fleet routing and speed optimization under a carbon trading mechanism［J］. Systems Engineering-Theory & Practice， 2023， 43（11）： 3320-3335.

场景	配送成本/元	惩罚成本/元	时间窗指派成本/元	维护成本/元	运输车辆数/辆	运输成本/元	闭合式路径/条	开放式路径/条	配送车辆使用数/辆	物流运营总成本/元
优化前	1020	825	—	700	—	—	7	—	7	2545
优化后	720	50	90	600	1	420	4	3	4	1580

算例	客户数量	CPLEX求解器			IMOPSO			成本差值/%
算例	客户数量	物流运营总成本/元	配送车辆使用数/辆	计算时长/秒	物流运营总成本/元	配送车辆使用数/辆	计算时长/秒	成本差值/%
1	20	985	4	702	985	4	20	0
2	20	816	4	639	816	4	18	0
3	20	742	3	641	742	3	17	0
4	20	853	4	712	853	4	22	0
5	20	769	3	705	769	3	21	0
6	40	1839	6	2780	1839	6	43	0
7	40	2371	7	3052	2371	7	56	0
8	40	1948	6	2693	1964	6	39	0.82
9	40	2534	7	3149	2563	7	62	1.14
10	40	2019	6	2804	2019	6	47	0
平均值	30	1487.6	5	1787.7	1492.1	5	34.5	0.2

算例	IMOPSO		MOACO		NSGA-Ⅱ		MOSA
算例	物流运营总成本/元	配送车辆使用数/辆	物流运营总成本/元	配送车辆使用数/辆	物流运营总成本/元	配送车辆使用数/辆	物流运营总成本/元	配送车辆使用数/辆
1	5658	10	12980	14	8792	12	9264	12
2	5810	11	11897	13	8431	13	8937	13
3	6867	9	11513	12	10141	11	11356	12
4	6589	10	12158	13	10463	12	9458	13
5	5488	10	8706	14	6344	13	8729	12
6	4897	11	7979	13	6682	13	7915	12
7	6180	10	8274	13	7739	12	9352	12
8	5788	11	8174	14	7469	11	10973	13
9	3830	11	8639	13	6400	13	9301	13
10	3764	10	8464	12	6330	12	8604	11
11	11915	20	20751	27	16582	21	15704	22
12	21866	19	38746	28	22324	20	23109	20
13	25868	20	39657	29	26485	22	31902	22
14	25230	19	33946	28	25443	20	27516	21
15	28888	21	32519	30	30596	23	28934	23
16	10482	20	17428	28	11333	21	18063	23
17	8620	19	15534	29	10068	20	14073	21
18	10356	21	16665	28	10667	22	12971	22
19	8496	19	14661	26	9216	20	10537	21
20	14909	20	23710	29	17167	22	21754	23
平均值	11075.05	15	17620.05	21	12933.6	17	14922.6	17
t检验			-7.99	-8.30	-6.66	-10.51	-9.12	-13.78
p值			1.72E-07	9.58E-08	2.26E-06	2.33E-09	2.27E-08	2.41E-11

场景	w₁			w₂
场景	参数值	物流运营总成本/元	标准方差	参数值	物流运营总成本/元	标准方差
1	0.1	4027.6	10.5	0.1	3928.5	9.5
2	0.2	3675.3	8.3	0.2	4011.3	8.7
3	0.3	3326.5	9.2	0.3	3548.6	7.6
4	0.4	3238.9	8.4	0.4	3110.9	6.2
5	0.5	3135.2	7.6	0.5	3451.7	6.9
6	0.6	3210.7	8.7	0.6	3371.2	7.3
7	0.7	3379.8	6.5	0.7	3256.8	7.1
8	0.8	3125.4	6.3	0.8	3467.2	7.6
9	0.9	3099.5	5.6	0.9	3510.9	8.5
10	1	3209.6	6.8	1	3686.3	8.8

场景	时间窗指派成本/元	惩罚成本/元	配送成本/元	运输成本/元	维护成本/元	物流运营总成本/元	配送车辆使用数/辆
优化前	0	2610.23	3040.82	0	390	6041.06	13
优化后	296.67	666.45	2769.86	306.51	260	3099.50	7