时间窗分配策略下多方协同配送的物流网络设计

doi:10.3778/j.issn.1002-8331.2305-0339

摘要/Abstract

摘要： 多方物流企业依托信息平台实施协同配送模式能够显著降本增效，但随着合作规模扩大，顾客预期时间愈发难以满足。有研究采取了时间窗分配策略，但大多策略从成本角度出发，忽视了顾客满意度的重要性。提出了一个多目标时间窗分配策略下多方协同车辆路径问题（multi-owner collaborative vehicle routing problem with time window assignment，MOCVRPTWA），可以优化成本且保障顾客满意度。由于MOCVRPTWA模型属于NP-hard问题，为降低计算复杂度保证求解质量，设计了一种由K-means聚类算法与改进的NSGA-II算法组成的混合启发式算法来优化MOCVRPTWA模型。提出了一种改进Shapley值法来寻找稳定协同配送联盟的最优利润分配方案和最优联盟序列。实验结果表明，提出的算法在数据验证上表现出了较高的准确率和鲁棒性，MOCVRPTWA模型同时优化了配送成本和顾客满意度，表明协同配送机制和时间窗分配策略可以提高资源利用率和配送效率，有助于城市物流网络的高效运行和可持续发展。

关键词: 协同配送, 时间窗分配, 利润分配, 多目标优化

Abstract: Collaborative delivery models, implemented by multiple logistics companies via information platforms, can significantly cut costs and boost efficiency. Yet, as cooperation scales up, fulfilling customer’s expected delivery times proves challenging. Existing time-window allocation strategies often neglect customer satisfaction in favor of cost. In response, this paper explores a multi?owner collaborative vehicle routing problem with time window assignment (MOCVRPTWA), aiming to optimize costs while ensuring customer satisfaction. Because MOCVRPTWA model belongs to NP-hard problem, to reduce the computational complexity to ensure the quality of solution, this paper introduces a hybrid heuristic algorithm using K-means and improved NSGA-II to tackle the complex MOCVRPTWA. This paper also proposes an improved Shapley value method for optimal profit distribution in stable delivery alliances. Experimental Results demonstrate high accuracy and robustness, highlighting the potential of collaborative delivery and time-window allocation to improve resource usage, delivery efficiency, and urban logistics sustainability.

Key words: collaborative delivery, time window assignment, profit distribution, multi-objective optimization

柯建超, 孟燕萍. 时间窗分配策略下多方协同配送的物流网络设计[J]. 计算机工程与应用, 2024, 60(18): 324-336.

KE Jianchao, MENG Yanping. Design of Multi-Owner Collaborative Distribution Logistics Network Under Time Window Assignment Strategy[J]. Computer Engineering and Applications, 2024, 60(18): 324-336.

参考文献

[1] 王文. 1月份中国快递发展指数报告发布[N]. 现代物流报, 2023-02-08(001).
WANG W. Release of China express development index report in January[N]. Modern Logistics News, 2023-02-08(001).
[2] CLEOPHAS C, COTTRILL C, EHMKE J F, et al. Collaborative urban transportation: recent advances in theory and practice[J]. European Journal of Operational Research, 2019, 273(3): 801-816.
[3] 国务院办公厅关于印发“十四五”现代物流发展规划的通知[J]. 中华人民共和国国务院公报, 2023(1): 47-60.
Notice of the General Office of the State Council on issuing the “14th Five Year Plan” for the development of modern logistics[J]. The Bulletin of the State Council of the People’s Republic of China, 2023(1): 47-60.
[4] BALDACCI R, MINGOZZI A, ROBERTI R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J]. European Journal of Operational Research, 2012, 218(1): 1-6.
[5] MARINAKIS Y, MARINAKI M, MIGDALAS A. A multi-adaptive particle swarm optimization for the vehicle routing problem with time windows[J]. Information Sciences, 2019, 481: 311-329.
[6] SPLIET R, GABOR A F. The time window assignment vehicle routing problem[J]. Transportation Science, 2015, 49(4): 721-731.
[7] SPLIET R, DESAULNIERS G. The discrete time window assignment vehicle routing problem[J]. European Journal of Operational Research, 2015, 244(2): 379-391.
[8] 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.
[9] WANG Y, ZHANG S L, GUAN X Y, et al. Collaborative multi-depot logistics network design with time window assignment[J]. Expert Systems with Applications, 2020, 140: 112910.
[10] WANG Y, WANG X W, GUAN X Y, 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.
[11]WANG Y, WANG X W, FAN J X, et al. Emergency logistics network optimization with time window assignment[J]. Expert Systems with Applications, 2023, 214: 119145.
[12] 饶卫振, 苗晓河, 刘露. 考虑企业配送能力约束的协作配送模型及成本分摊影响研究[J]. 中国管理科学, 2024, 32(7): 106-116.
RAO W Z, MIAO X H, LIU L. Research on collaborative distribution model considering distribution capabilit. constraints of enterprises and its influence on cost allocation[J]. Chinese Journal of Management Science, 2024, 32(7): 106-116.
[13] 饶卫振, 朱庆华, 金淳, 等. 协作车辆路径成本分摊问题的B-T Shapley方法[J]. 管理科学学报, 2019, 22(1): 107-126.
RAO W Z, ZHU Q H, JIN C, et al. A binary tree Shapely method for cost sharing of the collaborative vehiclerouting problem[J]. Journal of Management Sciences in China, 2019, 22(1): 107-126.
[14] 饶卫振, 苗晓河, 朱庆华, 等. 考虑企业服务质量差异的协作配送问题及成本分摊方法研究[J]. 系统工程理论与实践, 2022, 42(10): 2721-2739.
RAO W Z, MIAO X H, ZHU Q H, et al. Research on collaborative distribution problems and costallocation methods considering differences in service quality of logistics enterprises[J]. Systems Engineering-Theory & Practice, 2022, 42(10): 2721-2739.
[15] MAHMOUDI M, ZHOU X S. Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: a dynamic programming approach based on state-space-time network representations[J]. Transportation Research Part B-Methodological, 2016, 89: 19-42.
[16] CELEBI M E, KINGRAVI H A, VELA P A. A comparative study of efficient initialization methods for the k-means clustering algorithm[J]. Expert Systems with Applications, 2013, 40(1): 200-210.
[17] SRINIVAS N, DEB K. Multiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation, 1994, 2(3): 221-248.
[18] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[19] SHAPLEY L S. A value for n-person games[J]. Contributions to the Theory of Games, 1953, 28: 307-317.
[20] CAI P L, WANG Y P, LU G Q, et al. A spatiotemporal correlative k-nearest neighbor model for short-term traffic multistep forecasting[J]. Transportation Research Part C-Emerging Technologies, 2016, 62: 21-34.