时间窗和改进算法在冷链物流路径优化中的应用研究

2023-06-04任传荣皇甫世诚黄来望

物流科技 2023年4期

任传荣皇甫世诚黄来望

摘要：文章针对冷链物流运输问题建立了优化模型，使得冷链物流运输过程中的碳成本、时间窗的惩罚成本以及货物的变质成本总和最小，再运用改进蚁群算法，对其信息素浓度做出新的更新规则，避免了求解较慢和陷入局部最優解的问题；文章最后应用模型求解，得到最优路径和最低成本。

关键词：冷链物流；优化模型；时间窗；改进蚁群算法

中图分类号：F259.22；U116文献标志码：ADOI：10.13714/j.cnki.1002-3100.2023.04.041

Abstract： This paper establishes an optimization model for the cold-chain logistics transportation problem to minimize the total cost of carbon cost， penalty cost of time window and deterioration cost of goods in the cold-chain logistics transportation process， and then uses the improved ant colony algorithm to make a new update rule for its pheromone concentration， avoiding the problem of slow solution and falling into local optimal solution. Finally， the model is applied to obtain the optimal path and the lowest cost.

Key words： cold chain logistics; optimization model; time window; improved ant colony algorithm

0 引言

随着网络电子商务的发展，网购日渐成为人们日常购物的首要方式，其中一种购物类别便是对生鲜产品的购买。对于生鲜产品来说，最重要的就是保证生鲜产品送达时的新鲜度，因为其保质期也就几天左右，生鲜产品如果不及时送到，则会导致产品腐坏，为了解决这一问题，物流行业便推出了冷链物流运输新方式。

冷链物流运输在一定程度上保证了产品的新鲜性，但是由于冷链物流运输的特殊性，其消耗成本也较大，其中包括较大的运输成本、变质成本、客户满意度成本[1]（由提前送达的车辆等待成本、合理时间送达的零成本和迟到送达的不满意成本构成），这就需要结合时间窗和蚁群算法[2]优化路径减小冷链运输成本。

传统蚁群算法收敛速度较慢，且由于传统蚁群算法[3]正反馈的特性，为了避免传统蚁群算法的求解结果为局部最优解，本文对蚁群算法继续改进。改进蚁群算法则是在原算法的基础上给予信息素浓度区间，设定一定范围，这样就有效避免了由于某条路线信息素浓度过大而造成蚁群聚集情况，从而大大提高了优化搜索效率。与此同时，必须限制变质成本最低且结合时间窗提高客户满意度。

1 模型建立

由于冷链物流运输造成了大量碳排放，因此减少碳成本就在于减少运输成本，与此同时也为绿色物流贡献了力量。由上所述，本文建立了以碳成本、时间惩罚成本、变质成本最小为目标的优化模型，求得这些成本最低情况下的最短路径情况。

1.1 碳成本模型

2 算法逻辑和模型的求解

2.1 传统蚁群算法

蚁群算法是一种模拟进化算法[5]，可以模拟出蚂蚁的活动意向；其算法凭借鲁棒性优势和正反馈机制被广泛应用于路径优化问题。蚂蚁在寻找食物时，在经过的路径中会分泌信息素，而信息素的浓度[6]会直接影响蚂蚁对路径的选择，即信息素浓度越大，路径选择越多。

算法开始之前，所有目标点、路径上各点的信息素的浓度为0，即T0=Tij（0）；ηij（t）为启发函数，他表示在t蚂蚁从目标点t处选择下一目标点j的期望程度。用Prkij（t）表示在t时刻蚂蚁k从i到j点的概率，计算方法如下。

信息素的浓度则可用上述公式中的τij（t）表示，ij是它的边，α则表示信息素浓度的重要程度，ηij（t）则是相对于Prkij（t）来说的，它表示的则是蚂蚁k从i地到j地的期望概率，β表示的是ηij（t）的重要程度因子。

2.2 改进蚁群算法的信息素更新规则

针对本文问题的多个成本优化，如果选择传统蚁群算法求解则会出现求解较慢且结果是局部最优结果而不是全局最优结果，因此需要对蚁群算法进行改进。经过学习与分析，本文最终对算法中的信息素浓度加以改进，即在信息素浓度的更新过程中给予信息素浓度的上下限，本文将其确定为[τmin，τmax] ，蚁群算法效率就会极大提高，能够较快搜索出全局最优解。信息素浓度的计算具体如下。

其中，迭代次数为t、迭代最优解数量为σ；C（t）则是对应求解的三类成本之和、ρ则是信息素蒸发系数。

改进蚁群算法步骤如下。

步骤1：定义参数，导入客户时间窗数据，将dij定义为客户之间的距离，将Qi定义为客户需求；接着，定义迭代次数，设置开始迭代次数Nc=0，将Ncmax定义为70；然后定义其他参数，将n设置为网点内的客户数量，将m设置为蚂蚁数，最后设置α、β、ρ、参数的值。

步骤2：建立好禁忌表，将所以蚂蚁设定好，准备遍历。

3 模型应用

通过搜集资料，查询冷链相关数据有中心点坐标（80，80）、需求量0t、服务时间0、最佳时间窗为5：30—9：30、可接受时间为5：00—10：00；其他客户点坐标（40，66）、需求量0.33t、服务时间15、最佳时间窗6：00—6：30、可接受时间为5：30—7：00等，客户点共32个。

通过改进蚁群算法在考虑客户满意度、碳排放成本和车辆最大载重量等因素下计算最优配送路径，求得最优配送方案如表1所示。

由表1可知，最优配送方案為调用6辆车分别按以下路径配送，配送路程和成本如表2所示。

由表2可知，改进蚁群算法有效降低了配送总路程、配送总成本，相较传统蚁群算法，改进蚁群算法的总路程缩短0.71%、成本减少17.6%，由此可见，改进蚁群算法较传统蚁群算法提高了配送效率、更加经济性。

由图1可以看出，改进蚁群算法计算求得的路径有效缩短了配送距离，由起初的1 400km不断优化最终达到1 100km到1 150km，通过优化路程减少了33%左右，大大缩短了配送时间，更大程度地满足了客户需求。

由图2可知，通过算法有效降低了配送成本，配送成本从最大峰值6 400元变为5 891元，通过优化成本节省了近8.64%，减轻了配送的经济负担，使得配送中心的配送方案更加经济化，实现合理分配。

4 结语