基于改进模拟退火算法的配送路径优化研究

钱叶霞 陈子敬

摘 要：“互联网+”时代背景下，越来越多的企业纷纷入驻生鲜电商行业，生鲜电商的企业盈利和竞争压力随之增大，这就要求生鲜企业做好精细化的成本控制策略，实现物流系统的高效运作。在生鲜配送过程中，配送路径优化是极为重要的一环，所以生鲜电商企业必须做好物流配送路径的合理规划，降低配送环节的成本，增加物流总收益。本文以生鲜农产品为研究对象，建立以最短路径为目标函数的数学模型，利用改进模拟退火算法进行研究，并通过PyCharm软件进行求解。求解结果表明：本文所建立的车辆路径优化模型能有效缩短配送线路的总距离，降低配送运输的整體运营成本，进一步验证了车辆路径优化模型和改进算法的有效性和实用性。

关键词：生鲜农产品；配送路线优化；改进模拟退火算法；建模分析

本文索引：钱叶霞，陈子敬.<变量 2>[J].中国商论，2023（08）：-089.

中图分类号：F572 文献标识码：A 文章编号：2096-0298（2023）04（b）--04

随着我国经济水平的提升，人民群众对食品的消费观念已经不再是“民以食为天”，而是逐步转变成“民以鲜为天”。收入水平的不断提升和经济社会的进一步发展，使人们从原来“吃得饱”的需求转变为“吃得好”，同时在食品质量和安全问题上投入更多的关注，尤其是对配送要求较高的生鲜食品。

2020年6月，国家发改委发布《关于进一步优化发展环境促进生鲜农产品流通的实施意见》，旨在统筹推进生鲜运输市场和疫情防控，规范市场。2020年6月，农业农村部发布《关于进一步加强农产品仓储保险冷链设施建设工作的通知》，细化农产品生鲜运输，落实建设生鲜农产品信息平台。2022年4月，交通运输部发布《关于加快推进冷链物流运输高质量发展的实施意见》，旨在通过促进冷链运输发展来解决现有的生鲜运输问题。2020年发布的中央一号红头文件《关于抓好“三农”领域重点工作确保如期实现全面小康的意见》明确指出“要推进农产品保鲜冷藏冷冻物流基础设施建设，增强生鲜农产品的冷藏冷冻物流统一规划，提升制定标准和布局分类”。由此看来，本文通过优化路径解决生鲜运输和配送问题具有一定的现实意义。

如图1所示，2020年新冠疫情推动生鲜电商加速发展，生鲜电商市场规模不断扩大。

2021年上半年，中国生鲜电商交易规模约2362.1亿元；2021年底，生鲜电商交易规模约达4658.1亿元，同比增长27.92%。如图2所示，随着生鲜电商的发展及模式的成熟、用户网购生鲜习惯的养成，生鲜电商行业渗透率逐渐提高，越来越多的企业纷纷进入生鲜电商行业，生鲜电商企业盈利和竞争压力随之增大，这就要求生鲜企业做好精细化的成本控制策略，实现物流系统的高效运作。在生鲜配送过程中，配送路径优化是极为重要的一环，本文聚焦生鲜配送路径优化问题进行研究。

1 生鲜农产品配送路径模型建立

1.1 生鲜农产品配送路径优化问题概述

生鲜农产品配送问题可描述为：某个地区存在若干个生鲜农产品需求点，通过规划和设计运输路线，使得该若干个需求点的生鲜农产品需求被满足，并实现包括运输、库存、时间等成本在内的总成本最小。

与传统路径优化问题不同的是，生鲜农产品运输车辆路径优化问题的运输货物类型极易腐烂。一方面，这一因素使其必须利用冷链运输，以保证生鲜农产品在抵达目的地时没有出现损坏。另一方面，运输所使用的时间必须在客户需求的时间窗内，最好是在客户期望的软时间窗口内，进而满足客户要求。

1.2 构建路径优化模型

本文所研究车辆路径优化问题是考虑在单个配送中心的情况下，采用一辆运输车辆进行配送。配送车辆以配送中心为起点，在由多个前置仓组成的区域内进行配送，每个前置仓的位置和订单信息都是已知的，配送车辆同时向所有的前置仓提供服务，同时假定配送车辆在所需要的配送订单内具有完全的载货能力，提出以下假设：

（1）单一的配送中心，配送由一辆车完成，假定该车具有完全载货能力；

（2）车辆从配送中心出发需要重新回到配送中心；

（3）每个前置仓只需要经过一次；

（4）无视时间窗的配送约束条件；

（5）配送中心、前置仓和订单需求量为已知条件；

（6）不考虑道路条件和恶劣气候条件，车辆在道路上始终保持匀速状态行驶；

（7）在配送的过程中，冷链车的车厢内温度始终保持恒定温度；

（8）假定问题中的路线是对称的，一座前置仓到另一前置仓的往返距离是一样的，即dij=dji。

1.3 参数说明

本文对模型中出现的一些参数与符号在表1中做解释说明。

1.4 建立优化模型

对于上述求解Rmin的问题，本文设立如下模型：

即目标函数为：

式（1）的含义，即将一条旅行商回路中所有前置仓的长度进行比较，在其中选择最小路径后，可得到所求问题的最优化解。式（2）和式（3），代表所求的目标函数为该路径的最优化方案。

约束条件为：

式（4）表示在所求问题中，路程的成本最小。式（5）、式（6）表示，在所求问题中，每一个前置仓都被服务过且仅被服务过一次。

1.5 模拟退火算法原理

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，在常温时达到基态，内能减为最小。以一定的概率接受新状态所产生的最优问题解，这是算法的核心内容，借此跳出模型中的局部极值点，继续计算得到模型中的其他解，进而得到全局最优问题解（见图3）。

2 算例分析

本文以D公司为例进行分析，D公司主要经营范围包括水果蔬菜、肉禽蛋奶、粮油调味、酒水饮料、休闲食品等，需要每天把生鲜农产品运往各个门店前置仓，以保证每日门店前置仓生鲜农产品的质量和数量。目前，D公司的门店前置仓主要分布在嘉兴市的南湖区和秀洲区，各个门店前置仓的位置比较分散。为了保证生鲜农产品的质量、数量和时效性及降低配送成本，D公司需要合理规划从配送中心到各个门店前置仓的配送路线。D公司为节约成本，只有一辆冷链运输车，目前对门店的需求订单是由信息系统和员工共同分发的，每天由调度员通知司机需要分发的门店。然后，在获得所需运输商店的分布信息后，司机往往根据自己的经验在运输环节以“由近到远”的方式进行运输。对于装卸搬运大多使用手推车、地牛等较为依靠人力的设备，效率较低。目前D公司的配送类型有以下两种：（1）直接配送，即冷链仓根据日常运营数据估算生鲜农产品日需求量，与配送中心形成订单关系， 配送中心每天定量向门店提供生鲜农产品；（2）供应商配送，即冷链仓直接接收客户下单，将生鲜农产品配送至门店，再由客户去提货。

3 改进模拟退火算法优化配送路线过程

3.1 获取基本数据

在本模型中，以A表示分配中心，以B到Q表示每个门店前置仓节点。本文从百度地图获取的各个门店前置仓的位置，通过技术的手段，对地图进行简化，所有红色标记即为门店、前置仓各节点的位置，经Python软件简化位置如图4所示。

对坐标简化进行一定的处理，在图中建立坐标系，并且得到门店前置仓坐标点的坐标，得到简化坐标图5。

经处理后得到的各个门店前置仓坐标点的坐标如表2所示。

同时，利用在平面直角坐标系中两点间距离公式，可以计算各个门店前置仓坐标点之间的距離，如表3所示。

3.2 将基础数据带入算法模型，求得最优解

根据以上参数和变量，对所设计的配送路经进行模拟退火算法（SA）利用Python在Jupyter notebook中进行了设计和编程。算法求解优化前初始种群随机路径轨迹如图6所示，此时初始种群中的一个路径方案为：A-D-M-P-H-E-C-N-L-Q-B-I-F-G-O-J-K-A，总距离为158km，此时路线十分复杂，并不是最优解，存在优化空间。因此，引入模拟退火算法，求解最短路径。

优化后的路径如图7所示，优化后总路线长60km，优化路线为A-Q-P-O-N-M-L-I-H-K-J-G-F-E-D-C-B-A，较原配送路线长度158km共节约里程98km，节约的里程非常直观，生成的路径方案可为D公司的物流配送路径选择提供依据。

4 结语

首先，本文对目前生鲜市场的不断扩大做了总结和归纳。其次，对模拟退火算法（SA）和生鲜的相关概念进行探讨，并讨论了模拟退火算法在生鲜配送路径优化上使用的可行性，为配送路径优化提供理论上的依据。以D公司为例，通过探讨D公司目前存在的配送问题，确立D公司配送的各个门店前置仓的位置，建立了D公司生鲜配送模型。最后，根据D公司的经营状况，将实际数据带入建立的优化模型，并使用Python进行优化运算，得出优化的结果。

参考文献

傅文渊，凌朝东.布朗运动模拟退火算法[J].计算机学报，2014，37（6）：1301-1308.

田昀，梁海龙.基于模拟退火算法的物流配送路径优化问题分析[J].交通科技与经济， 2013，15（5）：85-88.

胡治锋，陈冬方，李庆奎，等.基于模拟退火蚁群算法的拣货路径规划[J].电子设计工程， 2021，29（24）：10-14.

张波，叶家玮，胡郁葱.模拟退火算法在路径优化问题中的应用[J].中国公路学报，2004， 17（1）：3-7.

陈科胜，鲜思东，郭鹏.求解旅行商问题的自适应升温模拟退火算法[J].控制理论与应用， 2021，38（2）：8-13.

李朝迁，裴建朝.新型模拟退火遗传算法在路径优化的应用[J].组合机床与自动化加工技术，2022（3）：22-26.

杨理云.用模拟退火算法求解旅行商问题[J].微电子学与计算机，2007，24（5）：6-12.