冷链物流配送路径优化_毕业设计论文

表3将我们的CC-ant算法与原蚁群算法和遗传算法[8]在总成本和总路径长度做比较，这是从10次重复实验结果中得到的平均值。可以看出，即使在不同数据集下，我们的CC-ant算法的总成本小于两者的基准。对于R型数据集，成本节约是最明显的，甚至可以达到3.90%，而对于C型和RC型，提升率略低，分别约为0.5%和1%。对于城市节点的聚集分布而言，路径规划中选择的城市对最终结果的影响很小，所以为C型和RC型的改进都比较小，由于RC型的分布具有聚集和随机的城市节点，它的改进略大。因此，总路径长度提升率与总成本的比较是相似的。

五.总结

由于冷链产品的特点，顾客惩罚成本被认为是软时间窗口，它被建模为一个分段函数来反映顾客在交货中的满意度。为了避免局部最优，采用了两种方法来改进原始AC，包括路径选择和信息素更新。数值实验表明，我们的算法在总成本和路径长度都优于现有的算法，计算时间也较短。

摘要—近年来，冷链物流正变得越来越重要，它始终引导着易腐食品或农产品运输到指定地点，以保证其新鲜。它主要由四部分组成：车辆的使用成本、运输成本、客户惩罚成本和损失成本，间接反映了运输的基本运营支出、总路径长度和客户满意度。在这里，只有当产品的交付时间超过给定的时间窗口时，才会产生客户惩罚成本。数值实验表明，与现有的工作相比，我们的路径方法可以提供更少的成本和更少的运行时间。

一.简介

冷链物流配送是将易腐烂的食品、农产品或药品送到不同地点的零售点或超市，并使运输时间最少，成本最低。据报道，从2012年到2015年，冷链运输中缺乏有效路径设计和冷藏的经济损失超过了1000亿元，更不用说其他农产品了[1]。因此，考虑到易腐农产品的新鲜度和总成本，迫切需要优化冷链物流配送车辆的路径规划了。

冷链物流的路径是VRP（车载路径问题）中的一个特殊应用，它与易腐产品的交付时间有关，通常可以用智能算法来解决，包括粒子群优化，遗传算法等等，例如[1]，[2]的作者采用了PSO在冷链物流中寻找最短路径的最优路径。Qian等人在[3]中利用遗传算法对考虑顾客对决策的满意程度的农产品运输中的VRP问题进行了求解。Li等人在[4]中提出一种扫描插入算法，在客户的时间窗口内提供乳制品。Tang等人在[5]采用蚁群算法对农产品运输进行优化。Hsu等人在[6]构建了一个考虑易损食品配送过程随机性的SVRPTW模型，在此基础上严格按照成本约束规划路径，并严格满足客户的时间窗口。事实上，总成本和交货期是冷链VRP中两个最重要的问题，但在现有的工作中没有充分考虑。

然而，设计满足最短长度的路径同时满足顾客送货窗口的时间需求很难。只有在产品交付时间超过给定的时间窗口时，我们才会引入罚款成本。因此，可以将不同的目标转化合并为一个优化目标，将总成本最小化。为了避免局部最优解，在蚁群算法中更新和初始化进程，而不是原来的公式。数值实验表明，与现有工作相比，我们的方法可以提供一个既节省成本、运输时间更少又可行的运输路径。

符号	定义
N	需要服务的顾客总数
K	配送中心的最大车辆数
	每辆车花费的固定成本
	每单位距离花费的运输成本
	每单位冷链货物的价格
	顾客i和顾客j之间的距离，其中i,j∈{ 1, 2，…，n}
	各k车辆的最大负载能力，其中k∈{ 1, 2，…，k}
	顾客i的货运需求
	车辆k对顾客i的到达时间
[]	顾客i期望的时间窗口
[]	顾客i可以接受的时间窗口
	车辆k在时间到达顾客i时的惩罚成本
	配送时间超过或者迟于可接受的时间窗口所造成的惩罚成本
	位于可接受和期望的时间窗口区间的惩罚成本系数
	货物运输和装卸时的损坏率
	从配送中心到顾客i的运输延迟
	顾客i的货物的卸载延迟
	变量0-1表明车辆k是否从顾客i移动到顾客j
	变量0-1表明顾客i的货物由车辆k交付的

二.冷链模型和问题公式化

主要由四部分组成：车辆的固定成本、运输成本、顾客惩罚成本和货物成本。所使用的符号列于表1中。

其中符号

是一个布尔指示符,用来显示车辆k是否计划将货物交付给客户，这可以表示为：

我们考虑使用软窗口进行冷链物流配送，将到达时间划分为五个不同惩罚成本的环节。当车辆到达时间早或晚于客户需要的时间窗口时，惩罚成本更大，所以是否派遣新车辆或支付罚款费用而使用更少的车辆是一个权衡问题。

当车辆在这个时间窗口到达时，它可能造成客户的极大不便，所以在路径设计中应该有更重的惩罚来避免这种情况。

立即送货上门可能会引起客户的不便和投诉，所以应该有一个小的惩罚成本。

按时服务窗口是客户所期望的时间窗口，所以不应该有惩罚成本。

延迟服务时间窗口是比顾客所期望的时间窗口稍后的时间跨度，在这个时间窗口到达时将会产生一个小的惩罚成本。

过晚服务时间窗口是比顾客所期望的时间窗口要晚得多的时间跨度，在这个时间窗口内的货物没有质量保证，甚至导致食物腐烂，所以惩罚成本非常高。

在冷链中，导致新鲜产品损坏的主要因素是指包括旅行时间和到达之后卸载时间在内的运输时间。在到达时间和。运输过程中的损坏的总成本可以表示为：

其中，

，

表示运输和卸载的损失率，

，

表示各自旅行时间和卸载时间。因此，我们可以构想出的问题如下所示：

对于任何位于位置j的客户，应该始终是有一辆车从位置i到它的位置，包括当i = 0时从配送中心出发，如约束（2）所示。类似地，对于任何位置i，它应该总是能在位置j找到下一个服务客户，包括当j = 0时回到分配中心，所以我们有了约束（3）。约束（4）意味着货物的总交付需求不应该超过分配路径的最大负荷。

三.算法设计

蚁群算法是通过模拟在不同地点寻找食物时的蚁群行为来设计的，蚂蚁在行走时总是释放信息素确定食物的特定范围，它们用信息素浓度作为路径选择的判断依据。作为回报, 更多的信息素会通过这个路径释放出来。在我们的路径规划问题中，将蚂蚁比作汽车，目标客户比作食物。表2显示了在我们的算法中将要使用的符号。

符号	定义
N	城市的总数
m	蚂蚁的总数
	城市i和城市j之间的距离，其中i，j∈{1,2，…，N}
	蚂蚁k会从城市i转移到城市j的概率
	在这个循环中路径（i，j）上的信息素总量
	t时刻在路径（i，j）上的可见性
a	信息素启发因子
b	期望值启发因子
	蚂蚁k可以选择的一系列城市
r	信息素蒸发因子
D	经过这一轮搜索路径（i，j）上的信息素总增量
D	蚂蚁k通过路径（i，j）所留下的信息素增量
Q	蚂蚁单周期释放的信息素总量

当蚂蚁k在城市i时，它需要为与信息素密切相关并且浓度和能见度可以步行到达的下一个城市j做选择。蚂蚁k可以从城市i转移到城市j的概率，记为

，通常表示为：

而β表示预期启发式因子，反映了在搜索引导中重新考虑了预期启发式信息的相对重要性。

当所有的蚂蚁完成它们的循环时，每个行走路径（i，j）中的信息素浓度将更新为下列公式：

是指结束这一轮的搜索之后的信息素浓度。它是由蒸发后残留的信息素组成的，并由新经过的蚂蚁增加。D

是指经过这一轮搜索之后，路径（i，j）上的信息素总增量，是由所有蚂蚁经过时留下的信息素增量组成，它可以表示为：

在蚁群框架的基础上，我们提出了一种叫做CC-ant的改进蚁群算法，它可以很好地适应冷链物流配送。

传统的蚁群算法总是能提供局部的最佳解决方案，而不是全局最优解，其缺点如下：

它假设在开始时选择下一次旅行城市的可能性是一样的，所以算法收敛效率低。

信息素的正反馈更新，更多的信息素将积累在某些流行的道路上，使他们更容易在下列搜索中被选择，从而导致局部结果最优。

为了避免陷入局部最优，我们建议联合轮盘赌法的随机概率。为了增加求解空间，我们首先在路径选择中使用随机概率，直到结果不能进一步优化为止。在这种情况下，我们采用轮盘赌方法进行搜索，在更新信息素的同时，寻找比现有路径更优的路径。轮盘赌法的基本思想是给出路径选择的概率，它可以使用随机概率或轮盘赌法生成的数字。

是轮盘赌的概率值，在不同的迭代次数下其对应的不同的值（

），如下所示：

随机概率与轮盘赌法结合的优点是扩大搜索空间，算法后期收敛速度加快。

在路径搜索返回路径中，没有信息素更新，如果在时间限制内没有其他允许访问的城市，蚂蚁会返回原点位置。在返回路径到达所有可能的城市后我们不更新信息素，否则会打破信息素正反馈更新机制，很难依靠信息素浓度寻找更好的解决方案。

在迭代过程中优化求解方案的选择，以避免局部最优，我们基于该解决方案的迭代，包括：在一次迭代中同一蚂蚁重复跑后的最优解选择，并从之前的迭代中选择最优的解决方案。具体规则如下：

可以通过上述两种方法获得当前最优解。之前的解决方案是用一只蚂蚁在约束范围内来旅行所有的城市。在一次迭代中多次重复这个过程，然后选择下一次迭代的最佳的解决方案。后者是从以往所有的迭代中选择最佳的解决方案，而不仅仅不是它迭代的先例。在实践中，我们在每10次迭代中使用前一种方法来运行优化。在其他情况下，我们使用后一种方法来选择当前最优解。利用上述两种方法的信息素反馈机制优于传统蚁群算法，可以有效地避免局部最优，并在实验分析中加以讨论。

四.实验分析

为了进行评价，我们采取常用的Solomon数据集法，这是Solomon[7]最初在VRPTW问题中使用的。这个数据集可分为三种类别：R型、C型和RC型。

注意，我们的冷链VRP考虑的是软时间窗口，所以只有硬时间窗口使用的Solomon数据集应该被调整。我们插入两个时间点b，c进入原来的硬窗口的[a，d]，所以我们的软时间窗口在算术级数中有[ a，b，c，d ]的宽度。