基于遗传算法的物流货物与运力撮合算法研究

陈德军，王 盼，隋建龙

(武汉理工大学 信息工程学院，湖北 武汉 430070)



基于遗传算法的物流货物与运力撮合算法研究

陈德军，王 盼，隋建龙

(武汉理工大学 信息工程学院，湖北 武汉 430070)

首先，分析了物流园区货物与运力资源优化配置的需求；然后提出了一种基于改进遗传算法的物流货物与运力资源优化配置的方法，实现了货物与运力信息的优化组合；最后对改进算法的效果进行了详细讨论，并运用Matlab对改进前后的算法进行仿真对比，验证了改进算法的有效性。

改进遗传算法；物流园区；撮合算法

物流园区是为满足货物转运需求而建立的，对物流组织管理节点进行集中建设与发展，具有经济开发性质的功能区域，是物流作业集中的地区，可以依托区位交通优势，降低物流成本，提高物流运作效率，实现物流资源的优化配置。

国外学者较早对物流园区的规模、选址和运营模式等问题进行了研究。如SHEU[1]提出了一种基于动态客户群的物流资源配置方法，TANIGUCHI等[2]采用双层规划模型来确定物流园区的规模和选址。在国内，罗文文等[3]建立了灰色马尔可夫预测模型用于物流园区物流量的预测，发现其精度较高。对于货运量预测还可以使用神经网络模型[4]等定量分析预测模型。秦进等[5]设计了通用型的双层模拟退火算法来研究物流设施的选址问题。姚峰等[6]采用知识型遗传算法求解双层CARP优化问题。对物流园区运作模式的研究，我国还鲜有关于此类的研究，多是借鉴国外的研究成果[7]。

在物流园区内，货物与运力资源的优化配置是其最重要也是最基本的需求。一般来说，物流需求方和物流供应方通常在园区物流信息管理平台发布各自的需求信息，物流需求方发布的信息内容主要包括货物类型、货物质量、货物体积、货物目的地及具体的收货人或收货公司的信息，而物流供应方发布的信息通常包括闲置运力吨位数、闲置运力载积、车辆数量、运输单位价格等信息。为此，需要设计一种撮合算法，针对大批量的货物运单，算法可以组合适当物流公司的闲置运力去共同承运这批货物；针对小批量的运单，算法也可以组合发往同一目的地的运单，并根据各物流公司的闲置运力情况交由一家或几家托运，从而提高物流效率，实现物流资源的优化配置。针对当前物流园区物流资源优化配置与利用的问题，笔者提出了一种基于改进遗传算法的物流资源优化配置方法。

1 基于遗传算法的物流货物与运力撮合算法

1.1 撮合算法设计

遗传算法[8-9]的计算过程是一个反复迭代的过程，不妨将第t代种群记作P(t)，这样经过一代的遗传和进化后，可以得到t+1代种群，其也是由多个个体组成的集合，记作P(t+1)，这样经过不断的遗传和进化操作，每次都在当代种群中选择适应度较高的个体遗传到下一代，淘汰适应度较低的个体，迭代一定的代数后，最终将会得到一个优良个体，其表现型将接近或者达到问题的最优解，从而解决问题。

图1 基于遗传算法的物流货物与运力撮合算法流程

由于大型货物运单匹配多家物流公司闲置运力和物流公司闲置运力匹配多个小型货物运单的本质是相同的，所以笔者以后者为例对算法的设计过程进行说明，算法的设计流程如图1所示。首先取出园区物流管理平台上各企业发布的尚未撮合的所有货物信息和闲置运力信息，对货物信息按目的地进行分组，取出第一个分组，从闲置运力信息中选出业务范围包含目的地区的物流公司集合，通过遗传算法对货物信息和物流信息进行撮合，撮合完成后删除已撮合信息，重复上述过程直到所有货物信息均已撮合为止。不难看出，算法的核心部分是基于遗传算法的货物与运力撮合过程。

假设园区物流信息平台上选取发往同一地区Pi的所有货物运单的编号为1，2，…，n，对应的货物质量为W1，W2，…，Wn，货物体积为V1，V2，…，Vn，然后从平台上已发布的闲置运力信息中筛选业务范围包含地区Pi的所有物流公司，将物流公司按照其信用和单位运费价格等因素进行综合评价，得到一个优先配货的序列，即L1，L2，…，Ln，则对应的闲置运力载重分别为WL1，WL2，…，WLn，闲置载积为WV1，WV2，…，WVn，并定义：

(1)

则对于运力信息L1来讲，质量和体积的目标函数分别为：

(2)

(3)

可见上述问题是一个多目标优化问题，需要通过数学方法将多目标融合为单目标，其中最常用的做法为加权法，对每个目标函数分配权重并将其组合成一个目标函数，则融合后的单目标函数为：

(4)

(5)

约束条件为：

(6)

(7)

得到遗传算法的目标函数后，针对式(6)和式(7)的约束条件，需要设计惩罚函数来加快算法收敛速度，让其同时满足式(6)和式(7)的情况下不断进化，最终可以得到最优解或近似最优解。

(8)

(9)

(10)

其中，K1和K2为惩罚系数。惩罚系数的作用体现在计算适应度的时候，目标函数值与对应的惩罚度相乘，如果个体满足所有约束条件，其惩罚度为1，不会影响计算得到的适应度；如果任何一项不满足约束条件，其惩罚度都将变成一个小于1的很小的值，这样便使得该个体的适应度也变得很小，进而面临被淘汰的可能。

确定了目标函数和惩罚函数后，则可按照遗传算法的计算步骤进行计算，整体计算过程如下：

(1)个体编码。将具体问题转化为遗传算法使用的染色体，常用的有二进制编码和浮点数编码方法，由于此处用0或1表示该货物运单被选择与否，所以采用二进制编码。

(2)初始化种群。根据设定的种群规模s，随机生成s个个体，每个个体的染色体长度为当前货物运单的数量n。

(3)计算适应度值。根据式(4)与式(8)，得到初代个体的适应度值：

fitness(t)=F(t)×P(t)

(11)

进而可以得到每个个体被选择的概率：

(4)选择个体。采用常见的轮盘赌选择策略，每次通过Random.next()函数产生一个0～1之间的随机数，从第一个个体开始依次计算个体被选择概率，直到累计概率大于等于该随机数的个体被选择，适应度值较大个体的被选择概率也相对较大，从而实现了优胜劣汰的效果。

(5)交叉运算。通过交叉运算组合父代基因，使个体快速进化，笔者采用两点交叉方法进行交叉运算，即在满足交叉运算概率的前提下，根据染色体长度随机产生两个位置，将这两个位置之间的基因进行交叉互换。

(6)变异运算。可以在种群达到一定稳定状态时，通过改变个体基因座上的基因打破这种相对稳定的状态，从而使种群达到新的平衡，在这一过程中最大适应度可能得到一个新的最大值，从而求出更优的解集，变异概率一般选择0.001～0.010，变异率过大则种群进化速度过慢，变异率过小则耗时较长，笔者选择的变异概率为0.010。

(7)开始迭代过程。根据设置的最大进化代数开始进化，当达到该数值时，算法结束，得到的最优个体的表现型便是所选货物运单的组合。然后对未选中的货物信息与下一个运力信息重新进行撮合，直到所有货物被选中或者没有可用运力信息为止。

1.2 撮合算法仿真

使用Matlab对上述算法进行仿真，输入的货物信息如表1所示。输入闲置运力信息总载重为70 t，载积为6.5 m3，设置种群规模为50，迭代代数为200，染色体长度为当前输入的货物信息数量15，算法通过随机法生成初始种群，种群的迭代过程如图2所示。

由图2可知，初始时的种群个体是随机产生，其适应度值较低，通过不断的进化，适应度值较高的个体被保存了下来，较低的被淘汰，经过1 000代进化后，种群内大部分个体的适应度值都已经变得很高，且稳定在一个较高的数值上，此时目标函数的值0.966就可以看作当前问题的一个最优解，即编号为3、4、10、14的货物信息被选中，从表1可知3号、4号、10号、14号货物总质量为66 t，总体积为6.5 m3，较好地匹配了70 t、6.5 m3的闲置运力信息。

表1 货物信息表

图2 种群迭代过程图

由于算法的运算过程具有随机性，需要多次运行程序记录统计结果，将每次得到的最佳个体的适应度值绘图，如图3所示。由图3可知20次的最佳适应度均值为0.878 0。算法整体上实现了货物与运力信息的撮合，但有时会过早收敛而陷入局部最优解，导致最佳编码值不够理想，如第7、9、10、16次的运行结果。通过增大种群规模和迭代代数可以改善这种状况，但是会增加算法的时间消耗。

图3 运行20次的结果图

2 基于改进遗传算法的物流货物与运力撮合算法

2.1 撮合算法设计

针对撮合过程中遗传算法易早熟、局部搜索能力不强等问题，笔者对遗传算子进行了改进，再引入模拟退火算法来增强其局部搜索能力，以便获得更优的编码结果。模拟退火算法[10]在搜索过程中引入了随机因素，即在一定的概率下可以接受比当前差的解，从而跳出局部最优解，这样便可以加强遗传算法的局部搜索能力，退火过程的概率计算参考了金属冶炼的退火过程，可表示为：

(13)

式中:T为当前温度；K为常数；dE为温度下降所产生的能量差值，则dE<0。式(13)表示在温度为T时，出现能量差为dE的降温的概率，温度越高，P(dE)的值越大，反之就越小，最后趋于稳定。

在遗传算法中引入模拟退火[11]，其具体的运算过程如图4所示。算法的主要改进包括以下4个方面。

图4 基于改进遗传算法的物流货物与运力撮合算法流程

(1)在选择算子中加入保优策略。即选出每代的最优个体直接进入下一代，这种策略可以加快种群的进化速度。

(2)改进交叉算子。①引入自适应的交叉概率，使适应度较高的个体在交叉运算时对应较小的交叉概率，从而保存优良个体；而适应度较低的个体对应较高的交叉概率，促使个体进化，交叉概率的计算公式如式(14)所示。②在原有交叉算子基础上引入模拟退火选择策略：假设个体Q1和Q2通过原有交叉算子产生的子代分别为F1和F2，分别计算其适应度fitness(Qi)和fitness(Fi)，i=1，2。如果fitness(Qi)≥fitness(Fi)，则使用Fi代替Qi，否则以概率exp(-(f(Fi)-f(Qi))/T)接受Fi。

式中：fmax为种群中个体的最大适应度值；favg为适应度均值；f为当前个体的适应度值。

(3)改进变异算子。在原有变异算子基础之上加入模拟退火选择策略，方法与步骤(2)相同。

(4)改进固定的进化代数。即判断每代个体的最大适应度值，如果连续20代无变化，则停止进化，并选出最终的最优个体进行模拟退火运算。这样进化初期充分利用了遗传算法优秀的全局搜索能力，在进化中后期利用模拟退火算法的局部搜索能力进行局部搜索，从而得到更为理想的个体编码。上述的模拟退火运算伪代码描述如下：

While(T

根据当代个体编码Bestcode计算其适应度值fitval1;

Fori=1:L

倒位法产生新个体X;

计算X的适应度fitval(X);

If(fitval1

最佳编码Bestcode=X的编码组合code(X);

Else

接受较差解的概率dp=exp((-fitval(X)-fitval1)/T);

If(dp

最佳编码Bestcode=X的编码组合code(X);

End

T=T×K;

End

End

其中:个体编码Bestcode的初始值是通过遗传算法计算得到的全局较优解;T表示当前温度;Tf表示终止温度;L表示每一个温度T下的状态变化次数，即马尔可夫链的长度，状态产生函数采用倒位法产生新状态，即随机产生两个位置，并将这两个位置之间的编码进行逆序；K表示退温系数，通常取0.95左右，每次迭代通过K来调整温度，从而调整模拟退火操作的接受概率。

2.2 撮合算法仿真

图5 改进算法的种群迭代过程图

在保持原有全局搜索能力基础上，通过对选择、交叉和变异算子的改进，加快了算法的收敛速度，通过并行搜索获得全局较优解后，使用模拟退火对该较优解进行串行搜索，从而加强了算法的局部搜索能力，最终实现了更优的搜索性能。最后使用Matlab对算法迭代过程进行了仿真，如图5所示。从图5可以看出，在进化到10代时群体出现了较优解，其适应度值为0.965 7，且这一最大适应度值持续40代没有变化，这时结束遗传算法的迭代过程，将这个全局较优解作为模拟退火运算的初始状态，并展开局部搜索，最终获得了更为理想的个体编码，001100000001001，其适应度值为1。且与固定进化代数相比，算法迭代代数减少，从而节省了运行时间。

多次运行改进后的算法程序，并记录每次运行得到的最佳编码，如图6所示。20次运行结果的适应度均值为0.971 4，与改进前的均值0.878 0相比获得了明显的提升，且其中4次搜索到了问题的最优解，可见改进后的算法搜索能力更强，效率更高，可以获得更为满意的货物与运力的撮合结果。

图6 改进后算法的20次运行结果图

3 结论

笔者结合物流园区物流资源优化配置的特点，确定了基于遗传算法的货物信息与运力信息匹配方法，并对遗传算法的特点和基本操作进行分析。结果表明算法符合实际要求，达到了资源优化配置的目的，又结合模拟退火算法对遗传算法进行改进，以解决遗传算法易早熟、局部搜索能力不强等问题，Matlab仿真结果显示，改进后的算法搜索能力更强、效率更高，达到了更好的撮合结果。

[1] SHEU J B. A novel dynamic resource allocation model for demand-responsive city logistics distribution operations[J]. Transportation Research Part E Logistics & Transportation Review,2006,42(6):445-472.

[2] TANIGUCHI E, NORITAKE M, YAMADA T, et al. Optimal size and location planning of public logistics terminals[J]. Transportation Research Part E Logistics & Transportation Review,1999,35(3):207-222.

[3] 罗文文,张文会,李德才.物流园区物流量灰色马尔可夫预测模型[J].森林工程,2014，30(5):184-187.

[4] 李晓利,王泽江.基于BP神经网络模型的煤炭物流需求预测研究[J].物流技术,2014,33(1):145-149.

[5] 秦进,史峰.物流设施选址问题的双层模拟退火算法[J].系统工程,2007,25(2):36-40.

[6] 姚锋,邢立宁,李菊芳,等.求解双层CARP优化问题的知识型遗传算法[J].系统工程理论与实践,2014，34(1):239-247.

[7] 张锦惠,陶经辉.国内外物流园区研究评述及展望[J].中国市场,2011(23):14-16.

[8] 周昕,凌兴宏.遗传算法理论及技术研究综述[J].计算机与信息技术,2010(4):37-39.

[9] 欧阳红祥，陈伟伟，李欣.基于间隔率和遗传算法的多资源均衡优化研究[J].武汉理工大学学报(信息与管理工程版)，2014，36(1)：82-85.

[10] 王凌.智能优化算法及其应用[M].北京：清华大学出版社,2001：135-207.

[11] 吕晓峰,张勇亮,马羚.一种求解0-1背包问题的改进遗传算法[J].计算机工程与应用,2011,47(34):44-46.

CHEN Dejun:Prof.; School of Information Engineering, WUT, Wuhan 430070, China.

Research on Matching Algorithm of Logistics Goods and Transport Capacity Based on Genetic Algorithm

CHENDejun，WANGPan，SUIJianlong

This paper analyzes the optimal allocation between goods and transport capacity resources in the logistics park, then a method of the optimal allocation between logistics goods and transport capacity resources based on improved genetic algorithm is proposed, which optimize combination of goods and transport information. MATLAB as a simulation platform ,by discussing the simulation results of improved algorithm in detail，the effectiveness of the algorithm improvement is confirmed.

improved genetic algorithm; logistics park; matching algorithm

2095-3852(2017)02-0208-05

A

2016-10-16.

陈德军(1964-)，男，湖北天门人，武汉理工大学信息工程学院教授，主要研究方向为复杂系统建模、网络控制与管理、智能信息控制与管理系统.

国家自然科学青年基金项目(61303027).

F259.22;U116.5;U125

10.3963/j.issn.2095-3852.2017.02.018