模糊需求下的多中心冷链配送车辆路径问题

doi:10.3778/j.issn.1002-8331.2208-0143

摘要/Abstract

摘要： 针对多配送中心下冷链配送的车辆路径问题，考虑到低碳冷链运输的时效性以及需求不确定性，以碳排放成本、制冷成本、时间惩罚成本等在内的总配送成本最小和客户满意度最大为总目标，建立基于可信性测度理论的模糊机会约束模型。在需求模糊的情况下，利用改进的遗传-大规模邻域搜索算法得到初始计划路线，再通过随机模拟算法得到实际需求，进行路线调整。通过与其他文献求解结果对比，以及分析算例来验证所建算法的有效性和模型的合理性，同时分析模型相关参数对目标值的影响。实验结果表明，嵌入局部搜索的改进遗传算法避免了局部最优，加快了收敛性。而且在需求不明时，多配送中心的冷链配送模式要优于单配送中心。

关键词: 多中心车辆路径问题, 模糊需求, 冷链, 遗传-大邻域搜索算法, 碳排放

Abstract: Aiming at the cold-chain logistics distribution vehicle routing problem under multi-distribution center, considering the timeliness and low-carbon cold-chain transport demand uncertainty, with the total objective of minimizing carbon cost, refrigeration costs, time penalty cost et al and maximizing the satisfaction of the customers, it sets up the fuzzy chance constrained model based on credibility measure theory. In the case of fuzzy demand, the improved genetic algorithm and large-scale neighborhood search is used to get the initial planned route, and then the actual demand is obtained by random simulation algorithm to adjust the routes. Finally, the effectiveness of the proposed algorithm and the rationality of the model are verified by comparison of other literature algorithms and example analysis, and the related parameters of the model are analyzed. Experimental results show that the improved genetic algorithm embedded with local search avoids local optimization and speeds up convergence. And when the demand is unknown, multi-distribution center cold chain distribution mode is better than single distribution center.

Key words: multi-depot vehicle routing problem, fuzzy demand, cold-chain, genetic-large domain search algorithm, carbon emission

王祺, 肖青. 模糊需求下的多中心冷链配送车辆路径问题[J]. 计算机工程与应用, 2023, 59(23): 341-350.

WANG Qi, XIAO Qing. Multi-Depot Cold Chain Distribution Vehicle Route Problem Under Fuzzy Demand[J]. Computer Engineering and Applications, 2023, 59(23): 341-350.

参考文献

[1] 鲍春玲，张世斌.考虑碳排放的冷链物流联合配送路径优化[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.
[2] SOLOMON M M.Algorithms for the vehicle routing and scheduling problem with time window constraints[J].Operation Research，1987，35（2）：254-265.
[3] 李军涛，路梦梦，李都林，等.模糊时间窗多目标冷链物流路径规划[J].中国农业大学学报，2019，24（12）：128-135.
LI J T，LU M M，LI D L，et al.Research on logistics path planning of fuzzy time window multi-objective cold chain[J].Journal of China Agricultural University，2019，24（12）：128-135.
[4] 李军涛，刘明月，刘朋飞. 生鲜农产品多车型冷链物流车辆路径优化[J].中国农业大学学报，2021，26（7）：115-123.
LI J T，LIU M Y，LIU P F.Route optimization of multi-vehicle cold chain logistics for fresh agricultural products[J].Journal of China Agricultural University，2021，26（7）：115-123.
[5] XU Z T，ELOMRI A，POKHAREL S，et al.A model for capacitated green vehicle routing problem with the time-varying vehicle speed and soft time windows[J].Computer & Industrial Engineering，2019，137：1-14.
[6] 康凯，韩杰，普玮，等. 生鲜农产品冷链物流低碳配送路径优化研究[J].计算机工程与应用，2019，55（2）：259-265.
KANG K，HAN J，PU W，et al.Optimization research on cold chain distribution routes considering carbon emissions for fresh agricultural products[J].Computer Engineering and Applications，2019，55（2）：259-265.
[7] 范厚明，孙秀娜，张跃光，等. 时变路网下带混合时间窗的车辆路径问题[J].计算机工程与应用，2022，58（16）：292-302.
FAN H M，SUN X N，ZHANG Y G，et al.Vehicle routing problem with mixed time windows under time-dependent network[J].Computer Engineering and Applications，2022，58（16）：292-302.
[8] 辜勇，袁源乙，张列，等.带时间窗的多中心半开放式车辆路径问题[J].中国机械工程，2020，31（14）：1733-1740.
GU Y，YUAN Y Y，ZHANG L，et al.Multi-depot half open vehicle routing problem with time windows[J].China Mechanical Engineering，2020，31（14）：1733-1740.
[9] 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：10186.
[10] 范厚明，吴嘉鑫，耿静，等.模糊需求与时间窗的车辆路径问题及混合遗传算法求解[J].系统管理学报，2020，29（1）：107-118.
FAN H M，WU J X，GENG J，et al.Hybrid genetic algorithm for solving fuzzy demand and time windows vehicle routing problem[J]. Journal of Systems & Management，2020，29（1）：107-118.
[11] 王文君.交通流变化下考虑油耗的多车型车辆路径优化研究[D].邯郸：河北工程大学，2017.
WANG W J.Vehicle routing optimization with fuel consumption and multi-types vehicle considered under traffic flow variety[D].Handan：Hebei University of Engineering，2017.
[12] NASAB N G，AHARI S G，GHAZANFARI M.A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands[J].Transactions E：Industrial Engineering，2013，20（3）：919-930.
[13] 曹二保，赖明勇，李董辉.基于混合差分进化算法的模糊需求车辆路径问题[J]. 系统工程理论与实践，2009，29（2）：106-112.
CAO E B，LAI M Y，LI D H.Vehicle routing problem with fuzzy demands based on hybrid differential evolution[J].Systems Engineering-Theory & Practice，2009，29（2）：106-112.
[14] 任俊生，李爱民.蓄冷板冷藏车的特点与制冷量计算[J].专用汽车，2010（8）：47-49.
REN J S，LI A M. Characteristics of cool storage plate refrigerated truck and calculation of cooling capacity[J].Special Purpose Vehicle，2010（8）：47-49.
[15] 张瑾，毕国通，戴二壮.双目标冷链物流车辆路径问题及其遗传蚁群求解[J].科学技术与工程，2020，20（18）：7413-7421.
ZHANG J，BI G T，DAI E Z.Genetic-ant colony algorithm for a two-objective vehicle routing problem of cold chain logistics[J].Science Technology and Engineering，2020，20（18）：7413-7421.
[16] 段征宇，杨东援，王上.时间依赖型车辆路径问题的一种改进蚁群算法[J].控制理论与应用，2010，27（11）：1557-1563.
DUAN Z Y，YANG D Y，WANG S.Improved ant colony optimization algorithm for time-dependent vehicle routing problem[J].Control Theory & Applications，2010，27（11）：1557-1563.
[17] CHENG R，GEN M.Evolution program for resource constrained project scheduling problem[J].Evolutionary Computation，1994，11（3）：274-287.
[18] 王凌.车间调度及其遗传算法[M].北京：清华大学出版社，2003：39-42.
WANG L.Shop scheduling with genetic algorithms[M]. Beijing：Tsinghua University Press，2003：39-42.
[19] 范厚明，杨翔，李荡，等.基于生鲜品多中心联合配送的半开放式车辆路径问题[J].计算机集成制造系统，2019，25（1）：256-266.
FAN H M，YANG X，LI D，et al.Half-open multi-depot vehicle routing problem based on joint distribution mode of fresh food[J].Computer Integrated Manufacturing Systems，2019，25（1）：256-266.
[20] 肖青，赵昊，马悦.多配送中心冷链运输路径优化[J].包装工程，2019，40（17）：116-122.
XIAO Q，ZHAO H，MA Y.Optimization of cold chain transportation route of multi-distribution center[J].Packaging Engineering，2019，40（17）：116-122.
[21] 陈呈频，韩胜军，鲁建厦，等. 多车场与多车型车辆路径问题的多染色体遗传算法[J].中国机械工程，2018，29（2）：218-223.
CHEN C P，HAN S J，LU J X，et al.A multi-chromosome genetic algorithm for multi-depot and multi-type vehicle routing problems[J].China Mechanical Engineering，2018，29（2）：218-223.
[22] 李倩，蒋丽，梁昌勇.基于模糊时间窗的多目标冷链配送优化[J].计算机工程与应用，2021，57（23）：255-262.
LI Q，JIANG L，LIANG C Y.Multi-objective cold chain distribution optimization based on fuzzy time window[J].Computer Engineering and Applications，2021，57（23）：255-262.