论文部分内容阅读
摘要：随着电子商务的不断发展，互联网订单数量的不断增加，线下物流配送的压力越来越大。如何设计一个效果优良，可靠性强的物流线路选择方法越来越成为人们关注的热点。文章采用模拟退火算法对多节点物流配送路线最短选择问题进行了研究，建立了适用于物流配送路线最短问题的模拟退火算法方法。对于物流配送最短路线的优化计算提供了算法参考。对于其他行业关于多节点遍历路线最短问题同样具有参考意义。
关键词：模拟退火算法；物流配送；线路选择
中图分类号：TP301.6 文献标识码：A 文章编号：1009-3044（2019）04-0270-02
随着电子商务的不断发展，互联网订单数量的不断增加，线下物流配送的压力越来越大。在此背景下，现有诸多电商和物流相关企业都在进行物流配送线路选择的研究和应用，如阿里巴巴，京东等。物流配送研究是为了解决物流线路规划的问题而存在的，其是一个典型的旅行商问题[1]（Travelling Salesman Problem，TSP），它是一个组合优化问题。关于物流线路选择问题，可以将每个城市看成一个AOV有向图的节点，节点与节点之间有的单向连接，有的双向连接，也有的没有连接。如图1所示。
从图1中选择任意一个节点作为开始节点，找出一条路径，路径包含剩余所有节点，并只包含一次，最后返回到开始节点，要求这条路径所花费的代价最少（距离最短），这就是TSP问题。物流线路选择作为一个典型的TSP问题，当城市个数增加时，它可能的配送路线数量是成指数型增长的，是一个NP[2]难题。众所周知，NP难问题是很难精确的求出其最优解，因此，对于物流线路选择问题求出近似解是具有意义的。
1 相关工作
目前，在电商行业和物流行业飞速发展的背景下，关于物流配送的路径规划方面的研究越来越多。刘婷婷等人根据物流配送最短路线规划的现状，利用最小生成树法对现有问题进行分析，通过资料整合、建立实例模型、使用Kruskal算法建立模型、比较权值大小并用canvas画布显示最终路径图形等过程，得出物流配送网络的最佳路径，最后用Java实现整个模型，得出最短路径和最低时耗方案[3]。张倩等人针对 如何更好地确保电商平台生鲜食品冷链物流运作成本和运作效率的问题，提出了一种改进的蚁群算法，优化了生鲜电商冷链物流的配送路径，并通过实例仿真验证了优化方法的可行性[4]。王勇等人采用遗传算法对多节点物流配送路线最短选择问题进行了研究，建立了适用于物流配送路线最短问题的遗传算法方法[5]。
此外，由于物流配送的路径规划本质就是TSP问题的研究，所以关于TSP问题的研究工作是在研究物流配送的路径规划问题时不可避免的。李阳等人为优化TSP，结合禁忌搜索算法（TS）和模拟退火算法（SA）的思想设计了混合退火算法（TSA）。针对模拟退火算法搜索效果不稳定等问题，在初始阶段TSA多次禁忌搜索并筛选初始解，确保算法稳定地收敛到全局最优值，在求解部分设计了快速退火算法，使其快速退火并收敛。与其他算法相比，TSA求解精度高，求解效果稳定鲁棒性强，并且求解时间短[6]。Christine等人提出了一种进化分裂与侵占（EDAC）方法，用于替代遗传算法在硬组合搜索中的应用，该方法可以利用对子问题的良好解决方案的知识来改进问题本身的解决方案。文中使用遗传算法来探索问题细分的空间，而不是解决方案本身的空间，并给出了应用于几何TSP的该方法的一些初步结果[7]。
2 模拟退火算法原理
SA起源于物理学中固体退火原理，固体退火过程包括加温过程、等温过程和冷却过程。固体加温过程中，固体内部粒子随着温度的上升变成了无序状，导致内能增大。固体等温过程中，固体内部粒子渐趋有序，致使在每个温度都达到平衡态。固体冷却过程中，固体内部粒子随着冷却达到基态，内能减小为最小。模拟退火法的一般原理如下：
1）初始温度为[T0]，及初始点[x]，计算该点的函数值[f（x）]；
2）随机产生扰动[?x]，得出新点[x’=x ?x]，计算新点函数值[f（x’）]，和函数值差[?f=fx’=f（x）]；
3）假如[?f≤0]，则接受新点，当做下一次模拟的初始点；
4）假如[?f>0]，则计算新点接受概率：[p?f=exp -?fK?T]，产生[0，1]区间上均匀分布的伪随机数[r]，[r∈0，1]，若[p（?f）≥r]，则接受新点作为下一次模拟的初始点；否则放弃新点，仍取原来的点作为下一次模拟的初始点。
以上的原理过程也称为Metropolis过程。可遵循一定的物理退火原理逐步降低物体温度，重复Metropolis过程，形成模拟退火算法。
3 物流路线选择的模拟退火策略
1）解空间和初始解
5 结束语
本文就物流线路选择问题，提出了模拟退火算法解决该问题的策略。文中详细阐述了问题的解空间、初始解、目标函数、产生新解方式、目标函数差、Metropolis接受准则和详细流程图。最后文中通过两组实验证明了本文提出的策略的可靠性和正确性。
参考文献：
[1] Tao G， Michalewicz Z. Inver-over Operator for the TSP： International Conference on Parallel Problem Solving from Nature[C]， 1998.
[2] Woeginger G J. Exact Algorithms for NP-Hard Problems： A Survey[J]. 2003.
[3] 劉婷婷， 于卫红. 物流配送网络最短路线规划[J]. 电子商务， 2018（12）：9-10.
[4] 张倩， 张悟移， Rattapon Incharroen. 电商环境冷链物流路径优化研究[J]. 特区经济， 2018（11）： 103-105.
[5] 王勇. 遗传算法在物流配送线路选择方面研究[J]. 物流科技， 2018（4）.
[6] 李阳， 李文芳， 马骊， 等. 混合退火算法求解旅行商问题[J]. 计算机应用， 2014，34（S1）： 110-113.
[7] Valenzuela C L， Jones A J. Evolutionary Divide and Conquer（I）： A Novel Genetic Approach to the TSP[M]. MIT Press， 1993.
【通联编辑：张薇】
关键词：模拟退火算法；物流配送；线路选择
中图分类号：TP301.6 文献标识码：A 文章编号：1009-3044（2019）04-0270-02
随着电子商务的不断发展，互联网订单数量的不断增加，线下物流配送的压力越来越大。在此背景下，现有诸多电商和物流相关企业都在进行物流配送线路选择的研究和应用，如阿里巴巴，京东等。物流配送研究是为了解决物流线路规划的问题而存在的，其是一个典型的旅行商问题[1]（Travelling Salesman Problem，TSP），它是一个组合优化问题。关于物流线路选择问题，可以将每个城市看成一个AOV有向图的节点，节点与节点之间有的单向连接，有的双向连接，也有的没有连接。如图1所示。
从图1中选择任意一个节点作为开始节点，找出一条路径，路径包含剩余所有节点，并只包含一次，最后返回到开始节点，要求这条路径所花费的代价最少（距离最短），这就是TSP问题。物流线路选择作为一个典型的TSP问题，当城市个数增加时，它可能的配送路线数量是成指数型增长的，是一个NP[2]难题。众所周知，NP难问题是很难精确的求出其最优解，因此，对于物流线路选择问题求出近似解是具有意义的。
1 相关工作
目前，在电商行业和物流行业飞速发展的背景下，关于物流配送的路径规划方面的研究越来越多。刘婷婷等人根据物流配送最短路线规划的现状，利用最小生成树法对现有问题进行分析，通过资料整合、建立实例模型、使用Kruskal算法建立模型、比较权值大小并用canvas画布显示最终路径图形等过程，得出物流配送网络的最佳路径，最后用Java实现整个模型，得出最短路径和最低时耗方案[3]。张倩等人针对 如何更好地确保电商平台生鲜食品冷链物流运作成本和运作效率的问题，提出了一种改进的蚁群算法，优化了生鲜电商冷链物流的配送路径，并通过实例仿真验证了优化方法的可行性[4]。王勇等人采用遗传算法对多节点物流配送路线最短选择问题进行了研究，建立了适用于物流配送路线最短问题的遗传算法方法[5]。
此外，由于物流配送的路径规划本质就是TSP问题的研究，所以关于TSP问题的研究工作是在研究物流配送的路径规划问题时不可避免的。李阳等人为优化TSP，结合禁忌搜索算法（TS）和模拟退火算法（SA）的思想设计了混合退火算法（TSA）。针对模拟退火算法搜索效果不稳定等问题，在初始阶段TSA多次禁忌搜索并筛选初始解，确保算法稳定地收敛到全局最优值，在求解部分设计了快速退火算法，使其快速退火并收敛。与其他算法相比，TSA求解精度高，求解效果稳定鲁棒性强，并且求解时间短[6]。Christine等人提出了一种进化分裂与侵占（EDAC）方法，用于替代遗传算法在硬组合搜索中的应用，该方法可以利用对子问题的良好解决方案的知识来改进问题本身的解决方案。文中使用遗传算法来探索问题细分的空间，而不是解决方案本身的空间，并给出了应用于几何TSP的该方法的一些初步结果[7]。
2 模拟退火算法原理
SA起源于物理学中固体退火原理，固体退火过程包括加温过程、等温过程和冷却过程。固体加温过程中，固体内部粒子随着温度的上升变成了无序状，导致内能增大。固体等温过程中，固体内部粒子渐趋有序，致使在每个温度都达到平衡态。固体冷却过程中，固体内部粒子随着冷却达到基态，内能减小为最小。模拟退火法的一般原理如下：
1）初始温度为[T0]，及初始点[x]，计算该点的函数值[f（x）]；
2）随机产生扰动[?x]，得出新点[x’=x ?x]，计算新点函数值[f（x’）]，和函数值差[?f=fx’=f（x）]；
3）假如[?f≤0]，则接受新点，当做下一次模拟的初始点；
4）假如[?f>0]，则计算新点接受概率：[p?f=exp -?fK?T]，产生[0，1]区间上均匀分布的伪随机数[r]，[r∈0，1]，若[p（?f）≥r]，则接受新点作为下一次模拟的初始点；否则放弃新点，仍取原来的点作为下一次模拟的初始点。
以上的原理过程也称为Metropolis过程。可遵循一定的物理退火原理逐步降低物体温度，重复Metropolis过程，形成模拟退火算法。
3 物流路线选择的模拟退火策略
1）解空间和初始解
5 结束语
本文就物流线路选择问题，提出了模拟退火算法解决该问题的策略。文中详细阐述了问题的解空间、初始解、目标函数、产生新解方式、目标函数差、Metropolis接受准则和详细流程图。最后文中通过两组实验证明了本文提出的策略的可靠性和正确性。
参考文献：
[1] Tao G， Michalewicz Z. Inver-over Operator for the TSP： International Conference on Parallel Problem Solving from Nature[C]， 1998.
[2] Woeginger G J. Exact Algorithms for NP-Hard Problems： A Survey[J]. 2003.
[3] 劉婷婷， 于卫红. 物流配送网络最短路线规划[J]. 电子商务， 2018（12）：9-10.
[4] 张倩， 张悟移， Rattapon Incharroen. 电商环境冷链物流路径优化研究[J]. 特区经济， 2018（11）： 103-105.
[5] 王勇. 遗传算法在物流配送线路选择方面研究[J]. 物流科技， 2018（4）.
[6] 李阳， 李文芳， 马骊， 等. 混合退火算法求解旅行商问题[J]. 计算机应用， 2014，34（S1）： 110-113.
[7] Valenzuela C L， Jones A J. Evolutionary Divide and Conquer（I）： A Novel Genetic Approach to the TSP[M]. MIT Press， 1993.
【通联编辑：张薇】