基于贪婪算法的跨境物流系统的设计与实现

李业 王世华 胡传华 吴思莹

（1.深圳市格布领客信息科技有限公司 广东省深圳市 518000）

（2.广东石油化工学院理学院 广东省茂名市 525000）

1 引言

随着全球经济不断朝着一体化方向发展和“一带一路”倡议的深入推进，我国对外贸易发展迅猛，跨境物流的发展在跨境交易中起着重要的纽带作用。根据国家邮政局2021年5月邮政行业运行情况显示：国际/港澳台业务达1.86 亿件，同比增长26.9%。我国跨境运输物品不断增多，而我国跨境物流服务体系不完善、数字化和智能化程度低，导致我国物流行业的发展相对落后。物流成本高成为跨境物流行业发展的痛点之一。跨境的品类增多，重量大、体积大的物品也越来越多，各类物品打包成本也大大增加。优化物流服务模式，加快搭建信息系统化平台，能够更好地促进我国跨境物流服务的转型与发展。如何优化包裹，降低物流成本成为了亟需解决的问题。

由于跨境运输中存在商品种类局限性大、物流时效慢、运输成本高等问题，而现有的跨境物流企业服务中出现服务效率底，服务模式零散，服务功能单一的状况。国内外学者对相关的问题作出了研究。

国外学者主要在物流成本以及物流分拣上的做的研究有：文探讨了受物品数量影响的一体化运输成本和需求呈下降趋势的价格策略，同时构造了一个能够确定最佳物品数量和物流最优价格的决策模型。文认为配送中心的布局对物流系统的设计产生重要影响，因此提出了一个综合上述因素的模型和方法。国外在物流方面物品的分拣早在20 世纪60年代开始，国外就已经开始着手研究检测，分拣系统模型等。20 世纪80年代后，国外将分拣系统与不同的输送带有机结合起来，形成了一个高效的分拣系统。国外对于跨境物流网络环境的优化以及相关信息平台技术的研究搭建主要在路径优化、基础设施的搭建、货物存储转运的设计。文通过建立更加符合现实需求的跨境物流网络，将本土物流网络与跨境物流网络整合起来，使得境内物流管理与跨境物流更好的复合在一起。将自适应权重遗传算法作为该文研究问题的主解决方法。探讨了海运、内陆等不同网络物流背景下的进出口货物的组织优化问题。文作者通过分析第四方物流、海外仓储和物流联盟三种不同的跨境物流模式的优缺点等，设计提出了新的跨境企业物流模式的选择原则。文作者认为为了实现跨境电商物流模式的转型与发展，采用跨境电商物流枢纽园区模式和保税区、保税区物流综合服务模式这两种模式是较为有效的。文作者从社会、政策角度上，提倡政府和相关的跨境物流企业出台相关的现实物流问题应对策略，双管齐下以挑战目前跨境物流的短板和突破物流瓶颈，提出可以从建立各国家之间的商业战略联盟以降低物流成本，加强对跨境物流信息系统的构建以及加大对物流行业人才的培养等。文对于跨境物流信息平台的研究主要在平台的搭建、路线的优化、政策的颁布等方面，对于跨境物流平台中包裹优化，跨语种，跨技术技术标准等方面处于空白。

国内学者主要从宏观经济管理方面对降低物流成本提出对应之策。文通过定量分析、模拟物流系统等方式得出减低物流成本的决策方案。文从整合企业内部物流资源和选用优秀的第三方物流供应商这两方面进行解析；文分析B2C 电子商务企业可从合理选择物流模式、加强电子商务供应链整合、缔结电商企业与物流地产联盟等几方面入手降低物流成本。文研究了一个考虑成组分拣的双层分拣设备目的地指派问题，设计了一种高效的变邻域禁忌搜索算法，采用“成组分拣”方法与考虑目的地指派问题可有效提高分拣设备的分拣效率。文提出通过政府出台专项政策减少物流成本中的制度成本、构建第四方联盟、为顾客制定专属的跨境物流服务从而提高其竞争力等三个方式降低相应的物流成本。文为我们表明了运输成本是物流成本中比重高的项目，但是我们不能忽略存储和存货等成本，减低物流成本既要改革物流成本管理制度也要提高为客户服务的质量，同时现代企业也应创新改革，提高竞争力。文运用Flexsim 三维系统仿真软件, 展现物流分拣过程、利弊以及瓶颈问题，根据数据分析相应的问题，在设备资源、人力资源、资金资源的利用率上进行调整，进而提高整体效益。我国对于物品分拣的研究，是简单的对于货物进行取出、分类、集中打包等操作，有人工分拣系统、半自动化分拣系统、自动分拣系统等，对于分拣系统方面的优化，其主要目的在于减少物品搬运次数、搬运距离，从而提高劳动效率，降低作业成本。设计智能识别物品信息系统，依靠机械装送带对运往相同地点的物品进行分类，降低作业人员的劳动强度，降低人工操作时挑选的错误率，节省作业空间等。尚未未从单独物流成本方面考虑，如何更好的将物品合理分拣打包的问题。

国内外的学者都比较关注目前跨境物流的发展现状并针对相关问题进行分析并提出见解，鼓励相关的跨境物流企业加大创新力度，融合时代背景需求，对跨境物流企业模式进行改革。国内外对于跨境物流研究趋向不同点是在：国外学者更加注重跨境物流领域相关技术的研发。智能算法、数据挖掘技术、人工智能等流行的工具被熟练的运用到跨境物流平台的搭建中。国外主要从理工科的领域方面研究问题。国内学者更加热衷于对跨境物流相关理论政策方面提出建议，对物流模式情况分析，特别是从“一带一路”倡议提出以来，针对于“一带一路”的跨境物流研究文献也越来越多。但是国外学者对于这方面的研究较少。

包装标准化能够提高物品的保管效率，降低运输费用，减少运输过程中的破损率，减少货物的损耗费用。加快完成物流标准化和包装标准化，是物流行业的发展趋势。国内外降低跨境物流的方法主要为优化运输途径、企业结构调整、业务流程优化等，对于物流包裹主要是对快递包裹外观设计、包裹材质的研究。而本文通过利用贪婪算法原理得到物品分拣打包最优方案，降低物流费用，以提高整体效益，推动物流行业的发展。

2 跨境物流贪婪算法

贪婪算法也叫贪心算法，它是通过优化局部解得到局部最优解，进而得到近似的全局最优解。对所有局部解做贪婪选择，将大问题分割为若干个小问题求最优解，当经过多次贪婪选择后最终求得整体的最优解。贪婪算法具有自顶向下的处理问题方式，采取分而治之的思想通过局部最优解，是一种启发式算法。贪婪算法容易理解也易于实现，同时也极大的提高了运行效率并节省了时间，常以当前情况为基础根据某个优化测度做出最优选择。在实际问题中，运用贪婪算法解决问题时，主要有三个中心点，第一点是根据不同的问题实际情况，设置初始条件，该初始条件应该具有合理性，是求得局部最优解的基础。第二点是通过设定一个优化函数，优化每一次的局部解，通过贪婪算法迭代，得到局部最优解。第三点是判断该算法的终止条件。

2.1 分类打包问题的本质与特性

在物品分类打包过程中涉及到了各类因素，包括：物品种类、物品重量、物品数量、物品体积、包裹数量、运输路线等。各类因素对于物流费用的影响因子不同，综合多方面因素，本文对于分类打包问题研究的本质是要合理、合规、安全将物品送达，优化打包方案，同时得到物流费用相对较低。打包方案的最基本特征是多样性。不同的打包方式，可能得到的是相同物流费用。因此无法明确的规定那个方案最优，通过贪婪算法的计算后，得到的是一个相对最优解。

通过对物品分来挑拣打包问题的研究，分类打包问题包括以下五个特性：

（1）多样性：分类打包的方案有多重多样，且每个方案在不同的条件下都可能得到相对最低的物流费用。不同的打包方式可能出现相同的物流费用。

（2）约束性：在物品打包过程中，受到了包裹体积大小的约束，运输方式的约束、特殊的物品种类的约束、物品性质的约束等等。

（3）复杂性：物品打包方式不唯一，无法套用固定的打包方案，物品的数量、性质、大小等多变，导致打包方案千变万化。

（4）目标性：物品打包组合最优的原则是在同一条件下以物流费用达到相对最低为目标，为寄件人提供一个费用相对较低的方案。

（5）灵活性：分类打包能够适用于许多不同特性的物品分类组合。

2.2 分类打包准则

物品组合优化打包问题是一个基于物品属性、运输路线和运输时间等多维属性的组合优化问题。在符合寄件人所提出的寄件需求的情况下，综合考虑各类因素限制，通过设计合理的打包方案，降低物流公司整体的物流费用。在物品打包过程中需遵守的基本原则如下：

（1）保证打包过程中货物的安全性：易碎物品打包所需要的软性缓冲包装材料，防水包装等包装材料。

（2）进行环保打包、合理打包：使用环保纸箱、环保编织袋等节能环保材料。

（3）特殊物品仅能被归类特殊物流通道：比如食品类物品必须走食品专用航线，带电物品或敏感类物品需要从特殊的运输航线进行运输等。

2.3 物品包裹优化模型的可行性研究

综合考虑跨境物流运输中存在商品种类局限性大、物流时效慢和运输成本高等问题，本文重点研究如何对物品进行优化打包，在满足物流运输要求下，能够有效的解决跨境物流中存在的运输成本高的问题。同时，由于物流费用的降低，符合大众的心理预期，能够较好的被人们所接受。因此系统在未来跨境物流发展中有较大的市场前景。

2.4 基于贪婪算法的物品包裹优化模型

2.4.1 物品类型和包裹类型

物品包裹优化首先需要明确物品的类型、物品重量、包裹大小以及运输的航线都关乎打包方案的设计。不同物品类型的组合也会引起打包方案的变化从而产生不同的物流费用。通过移动物品组合，运用贪婪算法对包裹进行不断的组合优化，进而得到一个相对满意的包裹组合。

如表1 所示，根据运输航线对物品的要求，物品类型可分为普通型、带电型、敏感型、液体型和食品型五种类型，分别标记为I,I,I,I,I。五种物品类型的优先等级I<

表1 ：物品类型和优先等级

用P,P,…,P表示某个顾客所邮寄的最小拆分物品，共计n 个，其重量分别用M,M,…,M表示。用B、B、B、B和B分别表示五类包裹，其中包裹B可以存放打包I类型物品，B可以存放打包I和I两种类型物品，B可以存放打包I、I和I三种类型物品，B可以存放打包I、I、I和I四种类型物品，B可以存放打包I、I、I、I和I五种类型物品。

以上是对邮寄物品的类型、物品重量、物品类型的优先级别以及包裹类型进行了描述。接下来讨论讨论物品组合优化的贪婪算法的步骤及系统设计。

2.4.2 包裹优化贪婪算法的步骤和流程

2.4.2.1 包裹优化贪婪算法的基本步骤

步骤1：初始化包裹。包裹B仅存放I物品，包裹B仅存放I物品，包裹B仅存放I物品，包裹B仅存放I物品，包裹B仅存放I物品，当没有该类型的物品，则包裹为空；

步骤2：构造物品组合。在初始化包裹后，根据算法的数据结构定义，将所有的物品分组。例如：将P，P，P这三个物品分组，物品组合有：单个物品组合P、P和P，两物品组合PP、PP和PP，三物品组合PPP；

步骤3：迭代。计算所有物品组合移动引起的费用变化（移动前减移动后），并将费用变化最大且大于0 的物品进行移动，改变包裹间物品的重新组合；

终止条件：若所有物品组合移动引起运费变化都小于等于0，则算法终止。并返回一个相对最优的打包方案。

2.4.2.2 包裹优化算法的流程图包裹优化算法的流程图如图1 所示。先初始化包裹，判断是否满足终止条件，若是则输出最优打包方案。否则将按照物品组合优先级向后寻求合并包裹，计算物品合并前后所产生的运费差，若运费差小于或等于零，即包裹合并后方案的运费大于合并前的或者合并前后运费没有变，这种情况将继续重新合并求运费差，直到运费差大于0，即合并后的运费比合并前低，将更新包裹，再次判断是否满足终止条件，若是则返回最优解，否则重新进行包裹合并、贪婪迭代操作。

图1 ：分类打包算法流程图

3 系统设计与实现

3.1 系统设计

针对用户的需求，在用户模块设计包含寄送物品类型选择和物品重量输入等信息输入模块，待所有物品相关数据输入完成，通过后台运算可以得出最优费用的包裹打包组合方案，反馈给用户参考，用户模块使用流程图如图2 所示。系统编码设计上利用MATLAB 可以简洁处理非常复杂的数学计算问题和Java 具有多变的应用场景（如Web 开发），将两者充分结合起来，采用MATLAB 编写核心算法并将其打包成jar 包供Java 程序调用。

图2 ：用户模块使用流程图

3.2 系统实现

系统前端界面采用HTML 页面实现，结合Element 框架进行开发，开发过程中代码简洁，界面实现效果简洁且易操作，能兼容市面上绝大部分的浏览器进行访问。在运费计算模块，用户将物品信息输入界面，可定义添加删除物品数量，可通过点击或输入即可实现数据的输入。最后通过点击立即提交按钮，系统将运算获取最优打打包方案，最终将最优打打包方案显示在用户界面，如图3 所示。

图3 ：最优打打包方案显示界面

4 结语

本文利用贪婪算法在跨境物流包裹优化中应用解决了包裹组合优化NP 难题，得到了一组较优化的满意解。在保障运输物品完整完好的同时，减少物流成本，同时方便从事跨境物品挑件打包工作人员对于物品的分类打包，在未来的发展中具有广泛的应用前景。通过对信息技术的灵活运用，加快促进跨境物流服务的个性化发展！