基于模糊时间窗的多目标冷链配送优化

doi:10.3778/j.issn.1002-8331.2106-0530

摘要/Abstract

摘要：

随着生鲜冷链行业竞争逐渐白热化，成本高、时效性强、新鲜度难以保持等问题已成为制约冷链物流配送的瓶颈。为提高生鲜配送效率，考虑客户满意度，以货损成本、惩罚成本等综合配送成本最低为目标函数，构建了一个多目标配送路径优化模型。设计带精英策略的非支配排序遗传算法（Elitist Non-dominated Sorting Genetic Algorithm，NSGA-II）求解该问题，利用Solomon标准数据集进行仿真模拟实验。实验结果对比分析表明，考虑满意度时冷链物流配送所需车辆更少，总路径长度更短，设计的算法可以在较短的时间内获取到帕累托最优解集，能够有效地解决模糊时间窗下的配送路径优化问题。

关键词: 带时间窗的车辆路径问题（VRPTW）, 冷链物流, 带精英策略的非支配排序遗传算法（NSGA-II）, 多目标优化

Abstract:

With the increasingly fierce competition in the fresh cold chain industry, the problems such as high cost, strong timeliness and difficult to maintain freshness have become the bottleneck restricting the distribution of cold chain logistics. In order to improve the efficiency of fresh distribution, a multi-objective distribution path optimization model is established in this paper, which considers the customer satisfaction and takes the cargo damage cost, penalty cost and other comprehensive distribution costs as the lowest objective function. The Elitist Non-dominated Sorting Genetic Algorithm （NSGA-II） is designed to solve this problems, and the simulation experiment is carried out by using the Solomon standard data set. The comparative analysis of the experimental results shows that considering the satisfaction, the cold chain logistics distribution needs fewer vehicles and the total path length is shorter, and the designed algorithm can obtain the Pareto optimal solution set in a short time. It can effectively solve the distribution route optimization problem under the fuzzy time window.

Key words: Vehicle Routing Problem with Time Windows（VRPTW）, cold-chain logistics, Elitist Non-dominated Sorting Genetic Algorithm（NSGA-II）, multi-objective optimization

李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.

LI Qian, JIANG Li, LIANG Changyong. Multi-objective Cold Chain Distribution Optimization Based on Fuzzy Time Window[J]. Computer Engineering and Applications, 2021, 57(23): 255-262.

参考文献

[1] HUANG Z H，HUANG W L，GUO F.Integrated sustainable planning of self-pickup and door-to-door delivery service with multi-type stations[J].Computers & Industrial Engineering，2019，135：412-425.
[2] 郭放，黄志红，黄卫来.考虑前置仓选址与服务策略的同时取送货车辆路径问题研究[J].系统工程理论与实践，2021，41（4）：962-978.
GUO F，HUANG Z H，HUANG W L.Integrated sustainable planning of fast-pick area network and vehicle routing with simultaneous delivery and pick-up[J].Systems Engineering-Theory & Practice，2021，41（4）：962-978.
[3] 徐小峰，林姿汝，周鹏.多油品供给受限下多油库被动配送车辆路径问题研究[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.
[4] 王新，王征，徐伟.面向多个无人机站点的车辆与无人机联合配送路径问题研究[J].运筹与管理，2021，30（5）：31-37.
WANG X，WANG Z，XU W.Vehicle and drone joint disribution routing prolem with multiple drone hubs[J].Operations Research and Management Science，2021，30（5）：31-37.
[5] XIAO Y Y，KONAK A.The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion[J].Transportation Research Part E：Logs and Transportation Review，2016，88：146-166.
[6] HSIAO Y H，CHEN M C，CHIN C L.Distribution planning for perishable foods in cold chains with quality concerns：formulation and solution procedure[J].Trends in Food Science & Technology，2017，61：80-93.
[7] BELHAIZA S.A game theoretic approach for the real-life multiple-criterion vehicle routing problem with multiple time windows[J].IEEE Systems Journal，2018，12（2）：1251-1262.
[8] LI Y，LIM M K，TSENG M L.A green vehicle routing model based on modified particle swarm optimization for cold chain logistics[J].Industrial Management & Data Systems，2019，119（3）：473-494.
[9] DING Q L，HU X P，SUN L J，et al.An improved ant colony optimization and its application to vehicle routing problem with time windows[J].Neurocomputing，2012，98：101-107.
[10] ZHANG L Y，TSENG M L，WANG C H.Low-carbon cold chain logistics using ribonucleic acid-ant colony optimization algorithm[J].Journal of Cleaner Production，2019，233：169-180.
[11] 王淑云，孙虹.随机需求下冷链品多温共配路径优化研究[J].工业工程与管理，2016，21（2）：49-58.
WANG S Y，SUN H.Optimization of multi-temperature joint distribution with stochastic demands[J].Industrial Engineering and Management，2016，21（2）：49-58.
[12] 马向国，刘同娟，杨平哲，等.基于随机需求的冷链物流车辆路径优化模型[J].系统仿真学报，2016（8）：1824-1832.
MA X G，LIU T J，YANG P Z，et al.Vehicle routing optimization model of cold chain logistics based on stochastic demand[J].Journal of System Simulation，2016（8）：1824-1832.
[13] 鲍春玲，张世斌.考虑碳排放的冷链物流联合配送路径优化[J].工业工程与管理，2018，23（5）：95-100.
BAO C L，ZHANG S B.Route optimization of cold chain logistics in joint distribution：with consideration of carbon emission[J].Industrial Engineering and Management，2018，23（5）：95-100.
[14] 方文婷，艾时钟，王晴，等.基于混合蚁群算法的冷链物流配送路径优化研究[J].中国管理科学，2019，27（11）：107-115.
FANG W T，AI S Z，WANG Q，et al.Research on cold chain logistics distribution path optimization based on hybrid ant colony algorithm[J].Chinese Journal of Management Science，2019，27（11）：107-115.
[15] 于江霞，杜红亚，罗太波.基于客户分类的即时配送路径优化研究[J].交通运输系统工程与信息，2020，20（4）：202-208.
YU J X，DU H Y，LUO T B.Real-time delivery routing optimization based on customer classification[J].Journal of Transportation Systems Engineering and Information Technology，2020，20（4）：202-208.
[16] 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.
[17] SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research，1987，35（2）：254-265.
[18] 易云飞，蔡永乐，董文永，等.求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J].电子学报，2015，43（10）：2053-2061.
YI Y F，CAI Y L，DONG W Y，et al.Improved ITO algorithm for multiobjective real-time vehicle routing problem with customers’ satisfaction[J].Acta Electronica Sinica，2015，43（10）：2053-2061.
[19] 罗梓瑄，杨杰庆，刘学文.基于NSGA-II的考虑客户满意度的多目标车辆径问题研究[J].重庆师范大学学报（自然科学版），2020，37（6）：13-17.
LUO Z X，YANG J Q，LIU X W.Research on multi-objective vehicle routing problem considering customer satisfaction based on NSGA-II[J].Journal of Chongqing Normal University（Natural Science），2020，37（6）：13-17.