CN107169689B - 一种基于粒子群算法的货物采购及拼船/车运输方法 - Google Patents

Abstract

本发明涉及一种基于粒子群算法的货物采购及拼船/车运输方法，包括如下步骤：S1：获取货物采购及运输需求相关数据；S2：设定粒子群中个体的货物采购及运输的染色体编码方案，设定染色体基因信息；S3：配置粒子群算法参数；S4：随机生成初始粒子群，包括位置群与速度群；S5：解读粒子群中所有个体的染色体基因信息，生成采购‑拼船/车运输配送方案，并计算粒子群中个体的适应值；S6：记录个体历史最优方案与群体历史最优方案，更新群中各粒子个体的速度与位置；S7：判断是否满足终止条件，如果不满足则返回S5，如此循环直至满足终止条件，如果满足则优化结束输出最优方案。

Description

一种基于粒子群算法的货物采购及拼船/车运输方法

技术领域

本发明涉及优化与智能计算技术领域，具体涉及一种基于粒子群算法的货物采购及拼船/车运输方法。

背景技术

对于集团化经营的公司，各分公司的资源采购需求往往较为分散，各自进行资源采购并运输需要花费较高的物流成本。将各分公司的采购需求汇总，并由总部通过优化方法制定联盟采购和拼装运输计划往往可获得较高的经济效益。

大型船舶(车辆)的单位货物运输成本一般远低于小型船舶。对于供应地相近，需求地相近，而中途运输距离较长的多批次零散货物而言，将不同批次的零散货物拼装成大船(车)进行运输和配送可以有效提高经济效益。

拼船运输一般由货物收集、长途运输与货物分送三个过程组成。具体是指：大型船泊/车辆依次经过不同的产地并将各产地的零散货物收集起来，经长途运输抵达销售地区后再依次经过不同的销地并在销地卸载相应批次的零散货物。

优化采购及拼船/车运输的目的是在相关条件的限制下寻找最优采购及运输方案，使所有参与运输计划的船舶的总运费最低。总运费包含航行费用、装港滞期费、卸港滞期费和靠港费用。

优化采购及拼船运输优化的限制条件包括以下几类：(1)供需平衡限制，对于任意批次的货物需求，其实际供货量与预定供货量之间的误差应控制在±5％以内；(2)单船额定载重限制，每船的货物运载量都要小于等于该船的额定载重；(3)装货日期限制，对于无装期限定的货物，船舶可以自选装期抵达装港，对于有装期限定的货物，船舶必须在规定的装期之前抵达；(4)到货日期限制，船舶必须在自身装载各批次货物规定的卸期之内抵达并装载货物；(5)定向运输限制，某些批次的货物可以和其他批次的货物拼船运输，但最后必须卸载到指定港口。(6)港口水深限制，所选型号的船舶装满货物后的吃水深度必须小于港口水深限定。(7)单向运输限制，某些国家环保法律禁止已装载部分高硫油品的船舶进港拼装。

拼船运输优化属于NP难问题(Non-deterministic Polynomial的问题，多项式复杂程度的非确定性问题)，本发明采用粒子群算法予以求解。

发明内容

要解决的技术问题如何提高货物采购及拼船/车运输方案的寻优效率。

针对现有技术中的缺陷，本发明提供了一种基于粒子群算法的货物采购及拼船/车运输方法，包括如下步骤：

S1：获取货物采购及运输需求相关数据；

S2：设定粒子群中个体的货物采购及运输的染色体编码方案，设定染色体基因信息；

S3：配置粒子群算法参数；

S4：随机生成初始粒子群，包括位置群与速度群；

S5：解读粒子群中所有个体的染色体基因信息，生成采购-拼船/车运输配送方案，并计算粒子群中个体的适应值；

S6：记录个体历史最优方案与群体历史最优方案，更新群中各粒子个体的速度与位置；

S7：判断是否满足终止条件，如果不满足则返回S5，如此循环直至满足终止条件，如果满足则优化结束输出最优方案。

可选地，所述设定粒子群中任一个体的货物采购及运输的染色体编码方案的步骤具体包括：

将货物采购-运输过程的货物收集方案、装货时间、货物分送方案和参与运输的运输工具分解的为供应染色体、需求染色体、运输工具染色体和装期染色体。

可选地，所述计算粒子群中个体的适应值的步骤具体包括：

按照供应染色体和运输工具染色体基因顺序和基因对应的附加属性对货物运载工具装载及生成采购-装载方案；

按需求染色体基因顺序对应的附加属性对货物分运载工具配送；

按供应染色体和需求染色体的基因及基因附加属性定位货物供应地和货物卸载地的位置；

根据参与运输的运输工具和货物编号对应的货物供应地和货物卸载地的位置确定运输工具运输线路，并根据路线计算运输费；

按装期染色体、供应染色体和需求染色体的基因信息反推标注自选装货期的货物的装货期，而后计算到货期；

根据装货期和到货期计算运载工具在装货地和卸货地的滞期，并根据滞期计算滞期费；

根据供应染色体和需求染色体与运输工具染色体的港口与船型信息，计算运输工具的靠港费用。

将所有运输工具运输费、滞期费和靠港费加和，获得粒子群中相应个体的适应值。

可选地，所述根据滞期计算滞期费的步骤还包括：

两个以上运载工具同时抵达时，其中之一需等待，等待时间为滞期，计算滞期费。

可选地，所述对货物运载工具装载及生成采购方案步骤具体包括：

S51：从运输工具染色体起始点开始读取运输工具染色体基因所代表的运输工具的编号，并由基因属性获取该运输工具的剩余载重；

S52:从供应染色体起始点开始读取供应染色体体基因所代表的货物编码，并由基因属性获取该批次货物的剩余数量；

S53:判断是否结束生成装载方案；若供应染色体起始点位置大于供应染色体长度或运输工具的剩余载重将为零，则停止生成采购方案；否则，进入步骤S54；

S54:令运输工具装载货物，生成购买与装载方案。

可选地，所述按装期染色体、供应染色体和需求染色体的基因信息反推标注自选装货期的货物的装货期，而后计算到货期的具体步骤为：

从前至后读取编号为i的运输工具中装载的供应染色体的基因所代表的采购货物；

若编号为i的运输工具中装载的供应染色体基因所代表的某批次采购货物装期并非自选，则以此货物装期为基准，根据装港间的航程，向前反推前面编号为i的运输工具中装载的供应染色体的基因所代表的货物的装期，而后向后正推后面编号为i的运输工具中装载的供应染色体的基因所代表的货物的装期；

若编号为i的运输工具中装载的供应染色体所有基因所代表的采购货物装期属性都为自选，则根据编号为i的运输工具中装载的需求染色体第一个基因所代表的货物的卸载期限和装期染色体中的相应装期基因计算第一卸期，而后根据第一卸期反推前面编号为i的运输工具中装载的供应染色体的基因所代表的货物的装期；

其中i为常数。

可选地，所述设定染色体基因信息的步骤具体包括：

对需要运输的各批次货物编号；

标记各货物供应地/卸载地，数量、类型、装货期/卸货期限，并相应编号；

对运输工具编号并标记各运载工具的额定运载量；

将供/需货物批次编号、运输工具编号及装货期编号作为相应染色体基因；

将货物供应地编号、货物卸载地编号、供应货物类型、需求货物类型、供应货物数量、需求货物数量、货物装期、参与运输的运载工具载重作为基因属性附着于相应染色体的基因上。

可选地，所述粒子群算法参数包括惯性权重、个体历史最优权重、群体历史最优权重及位置更新约束因子、计算总迭代次数和粒子群的数量。

可选地，更新群中各个体的速度与位置是按以下公式执行的：

速度更新公式为：

位置更新公式为：

其中，

指第k次迭代粒子i飞行速度矢量的第d维分量；

指第k次迭代粒子i位置矢量的第d维分量；

指粒子i搜索到的自身历史最优矢量的第d维分量；

指所有粒子所搜索到的全局历史最优矢量的第d维分量；

ω指保持原来速度的系数，也叫做惯性权重；

c₁指粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识；

c₂指粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识；

ξ，η指[0,1]区间内均匀分布的随机数,用于增加搜索的随机性；

r指位置更新约束因子。

由上述技术方案可知，本发明提供的基于粒子群算法的优化采购及拼船/车运输方法，将采购-拼船/车运输过程分解为采购染色体、装货期染色体、需求染色体与运输工具染色体进行耦合编码，并利用粒子群算法予以求解。通过需求匹配编码、配送定向解码及装期限定解码等方法，避免无解假象并有效提高算法的寻优效率，节约了大量的计算时间，实现了货物采购及拼装运输方案的优化，降低了分散货物采购-运输过程的物流成本，提高了集团化公司的联盟经营效益。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单的介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明一个实施例中基于粒子群算法的货物采购及拼船/车运输方法流程示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

如图1所示，一种基于粒子群算法的优化采购及拼船/车运输方法，包括如下步骤：S1：获取货物采购及运输需求相关数据；S2：设定粒子群中任一个体的货物采购及运输的染色体编码方案，设定染色体基因信息；S3：配置惯性权重、个体历史最优权重、群体历史最优权重及位置更新约束因子等粒子群算法参数；S4：随机生成初始粒子群，包括位置群与速度群；S5：解读粒子群中所有个体的染色体基因信息，生成采购-拼船/车运输配送方案，并计算适应值；S6：记录个体历史最优方案与群体历史最优方案，根据公式更新群中各粒子个体的速度与位置；S7：判断是否满足终止条件，如果不满足则返回S5，如此循环直至满足终止条件，如果满足则优化结束输出最优方案。

下面以采购并拼船运输不同港口的原油为优选例对本发明展开详细的说明。

第一，介绍获取货物运输需求数据的步骤。

一般货物运输的需求数据包括货物的卸载地、货物的需求数量、需求货物的类型、到货时间期限等。

第二，介绍确定货物运输的四染色体编码方案，设定染色体基因信息的步骤。

在本发明的一个实施例中，确定货物采购-运输的四染色体编码方案的步骤具体包括：将货物采购-运输过程的货物收集方案、装货时间、货物分送方案和参与运输的运输工具分解表示为供应染色体X、装期染色体D、需求染色体Y和运输工具染色体Z。

首先，将需要购买并收集的货物按批次编号，并用XVol表示各批次供应货物的数量，用XPort表示各批次供应货物所在的港口编号，用XType表示各批次供应货物的类型编号；用XDate表示各批次供应货物所在的装货日期。其次，将所需配送的货物按批次编号，并用YVol表示各批次需求货物的数量，用YPort表示各批次需求货物所在的港口编号，用YType表示各批次需求货物的类型编号；用YDate1表示各批次需求货物的最早到货日期；用YDate2表示各批次需求货物的最晚到货日期。再次，将参与运输的船舶编号，并用ZVol表示各船的额定载重。最后，将各船的装货期编号，并用Date表示装货期选值。

下面以采购并拼船运输不同类型的原油为例，对确定四染色体编码方案做具体说明。

如表1所示，假设生产共需采购并运输7个批次的原油(X)，各批次采购原油依次编号1-7，各批次采购原油需采购的数量分别为20、10、13、9、14.5、19与18万吨，各批次采购原油分别位于1、2、3、4、5、6、7号出口港,各批次采购原油类型分别为1、2、3、4、5、6、7，各批次采购原油装货期分别为10-1、自选、10-4、自选、自选、自选、自选。销售地区共需进口7个批次的原油(Y)，各批次进口原油依次编号1-7，各批次进口原油需求数量分别为20、10、13、9、14.5、19与18万吨，各批次进口原油分别位于1、2、3、4、5、6、7号进口港。可能参与运输的船舶有5只，依次编号1、2、3、4、5，其额定载重都为26万吨。将各船的装货期编号(D)1、2、3、4、5，并用假设进化过程中某代某一个体的装货期选值为0.12、0.23、0.48、0.89、0.64。

表1基因附加属性表

按货物供需类型匹配要求的限定，(X)1号采购原油只能对应供应(Y)1号进口原油。依次类推，其余2、3、4、5、6、7号采购原油也只能分别供应类型相匹配的2、3、4、5、6、7号进口原油。

为了体现每种原油的供需平衡运输限制，(一般实际供货量与预定供货量之间的误差应控制在±5％以内算满足精度要求)，1号原油的实际采购量可以在20×0.95＝19万吨至20×1.05＝21万吨之间浮动。

第三，介绍配置粒子群算法相关参数的步骤。

为了提高方案寻优计算的效率，需要对粒子群算法参数做详细的配置，具体地，需要设置惯性权重、个体历史最优权重、群体历史最优权重及位置更新约束因子、计算总迭代次数和粒子群的数量等。

第四，介绍所述从四染色体编码解读拼船采购-运输方案的步骤。

按预先设置的种群数量，随机生成包含初始供应染色体X、需求染色体Y、运输工具染色体Z和装期染色体D的位置群和速度群。其中X染色体的长度等于货物供应批次数目，Y染色体的长度等于货物需求批次数目，Z染色体的长度等于参与运输货物的船舶数目，D染色体长度与Z相同。

介绍解读种群各个体所对应的采购-拼船运输方法。

假设迭代过程中某代种群中个体染色体组如表2所示：

表2某代种群中某个体染色体组编码

X	1	2	3	4	7	6	5
								Y	3	1	2	4	6	7	5
Z	2	4	3	1	5
								D	0.12	0.23	0.48	0.89	0.64

首先，令船舶对采购原油进行装载，生成采购-拼装方案。

船舶Z起始点为2号船，其剩余载重为26万吨，令2号船对采购货物X进行装载，X起始点为1号采购原油，其剩余数量为20万吨。由于1号采购原油剩余数量小于2号船舶的剩余载重，因此船舶将其完全装载。装载后，2号船剩余载重为26-20＝6万吨，1号原油剩余数量为0；

令Z起始点保持不变，仍为2号船，X起始点后移一位，指向2号原油。令2号船继续装载2号原油，由于2号船剩余载重6万吨，小于2号原油剩余数量10万吨，因而2号船只装载6万吨2号原油，其剩余载重为0，2号原油剩余数量为10-6＝4万吨。

此时2号船满载，共计装载20万吨1号采购原油和6万吨2号采购原油。

令Z起始点后移一位，指向4号船，其剩余载重为26万吨，令X起始点保持不变，仍然指向2号原油，其剩余数量为4万吨，由于4号船舶剩余载重大于2号原油剩余数量，因此船舶将其完全装载。装载后，4号船剩余载重为26-4＝22万吨，2号原油剩余数量为0。

Z起始点保持不变，仍为4号船，X起始点后移一位，指向3号原油。令4号船继续装载3号原油，由于4号船剩余载重22万吨，大于3号原油剩余数量13万吨，因此船舶将其完全装载。装载后，4号船剩余载重为22-13＝9万吨，3号原油剩余数量为0。

Z起始点保持不变，仍为4号船，X起始点后移一位，指向4号原油。令4号船继续装载4号原油，由于4号船剩余载重9万吨，等于4号原油剩余数量9万吨，因此船舶将其完全装载。装载后，4号船剩余载重为0，4号原油剩余数量为0。

此时4号船满载，共计装载4万吨2号采购原油和13万吨3号采购原油和9万吨4号采购原油。

令Z起始点后移一位，指向3号船，其剩余载重为26万吨；令X起始点后移一位，指向7号原油，其剩余数量18万吨。由于7号采购原油剩余数量小于3号船舶的剩余载重，因此船舶将其完全装载，装载后，3号船剩余载重为26-18＝8万吨，7号原油剩余数量为0；

令Z起始点保持不变，仍为3号船，令X起始点后移一位，指向6号原油。令3号船继续装载6号原油，由于3号船剩余载重8万吨，小于6号原油剩余数量19万吨，因而3号船只装载8万吨6号原油，其剩余载重为0，6号原油剩余数量为19-8＝11万吨。

此时3号船满载，共计装载18万吨7号采购原油和8万吨6号采购原油。

令Z起始点后移一位，指向1号船，其剩余载重为26万吨，令X起始点保持不变，仍然指向6号原油，其剩余数量为11万吨，由于1号船舶剩余载重大于6号原油剩余数量，因此船舶将其完全装载。装载后，1号船剩余载重为26-11＝15万吨，6号原油剩余数量为0。

令Z起始点保持不变，仍为1号船，令X起始点后移一位，指向5号原油。令1号船继续装载5号原油，由于1号船剩余载重15万吨，大于5号原油剩余数量14.5万吨，因而船舶将其完全装载，装载后，1号船剩余载重为15-14.5＝0.5万吨，5号原油剩余数量为0。

此时，1号船共计装载11万吨6号采购原油和14.5万吨5号采购原油。由于采购原油X已被完全拆分装载，因此，装船过程结束，Z中5号船不再参与运输。

其次，令载油船舶根据需求进行分配卸载，生成配送方案。

船舶Z起始点为2号船，共计装载20万吨1号采购原油和6万吨2号采购原油。令Y起始点指向第一个剩余需求数量不为0的需求油品，当前为3号需求原油，剩余需求数量13万吨，需求类型为3，2号船中无相关类型油品，不对其配送。

令Y起始点指向下一个剩余需求数量不为0的需求油品，指向1号需求原油，剩余需求数量20万吨，需求类型为1，令2号船对1号需求原油进行配卸20万吨1号采购原油，则1号需求原油剩余需求数量为0，2号船1号采购原油剩余装载量为0。

令Y起始点指向下一个剩余需求数量不为0的需求油品，也即2号需求原油，剩余需求数量10万吨，需求类型为2。令2号船对2号需求原油进行配卸6万吨2号采购原油，则2号需求原油剩余需求数量为10-6＝4万吨，有待继续配卸。2号船2号采购原油剩余装载量为0。

至此，2号船所装载的采购原油完全配送完毕。根据2号船的装油方案和卸油方案，并参照各油品所在的装、卸港，即可得到2号船的行船路线：

XPort1(1,20/20)→XPort2(2,6/10)→YPort1(1,20/20)→YPort2(2,6/10)。

令Z起始点后移一位，指向4号船，共计装载4万吨2号采购原油和13万吨3号采购原油和9万吨4号采购原油。令Y起始点指向第一个剩余需求数量不为0的需求油品，也即3号需求原油，剩余需求数量13万吨，需求类型为3。令4号船对3号需求原油进行配卸13万吨3号采购原油，则3号需求原油剩余需求数量为0,4号船中3号采购原油剩余装载量为0。

令Y起始点指向下一个剩余需求数量不为0的需求油品，也即2号需求原油，剩余需求数量4万吨，需求类型为2。令4号船对2号需求原油进行配卸4万吨2号采购原油，则2号需求原油剩余需求数量为0，4号船中2号采购原油剩余装载量为0。

令Y起始点指向下一个剩余需求数量不为0的需求油品，也即4号需求原油，剩余需求数量9万吨，需求类型为4。令4号船对4号需求原油进行配卸9万吨4号采购原油，则4号需求原油剩余需求数量为0，4号船中4号采购原油剩余装载量为0。

至此，4号船所装载的采购原油完全配送完毕。根据4号船的装油方案和卸油方案，并参照各油品所在的装、卸港，即可得到4号船的行船路线：

XPort2(1,4/10)→XPort3(3,13/13)→XPort4(3,9/9)→YPort3(3,13/13)→YPort2(2,4/10)→YPort4(4,9/9)。

以此类推，令3号船和1号船按从前之后的顺序对Y中剩余需求数量不为0的需求原油进行配送，分别可得各自的行船路线。

3号船：

XPort7(7,18/18)→XPort6(6,8/19)→YPort6(6,8/19)→YPort7(7,18/18)。

1号船：

XPort6(6,11/19)→XPort5(5,14.5/14.5)→YPort6(6,11/19)→Y Port5(5,14.5/14.5)。

再次，为各船装货期标记为“自选”的原油选择装期。

计算到货期的具体步骤为：从前至后读取编号为i的运输工具中装载的供应染色体的基因所代表的采购货物；若编号为i的运输工具中装载的供应染色体基因所代表的某批次采购货物装期并非自选，则以此货物装期为基准，根据装港间的航程，向前反推前面编号为i的运输工具中装载的供应染色体的基因所代表的货物的装期，而后向后正推后面编号为i的运输工具中装载的供应染色体的基因所代表的货物的装期；若编号为i的运输工具中装载的供应染色体所有基因所代表的采购货物装期属性都为自选，则根据编号为i的运输工具中装载的需求染色体第一个基因所代表的货物的卸载期限和装期染色体第i号基因计算第一卸期，而后根据第一卸期反推前面编号为i的运输工具中供应染色体的基因所代表的货物的装期；其中i为常数。

分别选取2号船和3号船为例说明选装货期的方法。

对于2号船，装载20万吨1号采购原油和6万吨2号采购原油，配送给1号需求原油20万吨和2号需求原油6万吨。从前至后检查2号船是否装载有固定装期的采购原油。由于2号船装载的1号采购原油装期固定为10-1，因此D染色体不起作用，对于2号船装载的各批次原油装货期选取以1号采购原油为准，其具体计算方式为：2号原油的装货期＝1号采购原油的装货期+1号采购原油数量÷1号装港的装货时间+1号装港拖船时间+1号装港与2号装港间的航程÷2号船的航速。

对于3号船，装载有18万吨7号采购原油和8万吨6号采购原油，配送给6号需求原油8万吨和7号需求原油18万吨。从前至后检查3号船是否装载有固定装期的采购原油。由于3号船所装载的所有批次的采购原油都为“自选”装期，因此D染色体起作用。对于2号船装载的各批次原油装货期选取可根据6号需求原油的6YDate1和6YDate2求得，具体步骤为：(a)计算3号船的“第一卸期”＝6YDate1+(6YDate2-6YDate1)×3D(0.48)＝11月16日；(b)由”第一卸期”反推3号船中6号采购原油的装货期＝“第一卸期”-6号卸港与6号装港间的航程÷3号船的航速-6号采购原油的船载数量÷6号装港的装货时间-6号装港的拖船时间；(c)由6号采购原油的装货期反推7号采购原油的装货期＝6号采购原油的装货期-6号装港与7号装港间的航程÷3号船的航速-7号采购原油的船载数量÷7号装港的装货时间-7号装港的拖船时间。

最后，介绍根据以上过程生成优化采购方案的方法。

所述对货物运载工具装载及生成采购方案步骤具体包括：S51：从运输工具染色体起始点开始读取运输工具染色体基因所代表的运输工具的编号，并由基因属性获取该运输工具的剩余载重；S52:从供应染色体起始点开始读取供应染色体体基因所代表的货物编码，并由基因属性获取该批次货物的剩余数量；S53:判断是否结束生成方案；若供应染色体起始点位置大于供应染色体长度或运输工具的剩余载重将为零，则停止生成采购方案；否则，进入步骤S54；S54:令运输工具装载货物，生成购买与拼装方案。

根据装船过程，2号采购原油被2号船分载6万吨，被4号船分载4万吨，因此，2号采购原油分两批次采购和运输，采购时各批次的装货期申报也由2号船和4号船的具体运输过程确定，参见上文所述装期选择办法。同理，6号采购原油被3号船分载8万吨，被1号船分载11万吨，因此，6号采购原油分两批次采购和运输，采购时各批次的装货期申报也由3号船和1号船的具体运输过程确定，参见上文所述装期选择办法。

对于1号船，最终货物装载量为25.5万吨，可按5％的误差需求，增加装载采购原油的数量至26万吨，以提高船舶运输的经济效益。具体方法为：(1)校核计划采购增量是否满足5％的误差需求，具体为(26-25.5)÷(第6号油品的需求总量19+第5号油品的需求总量14.5)＝1.5％，满足误差精度要求；(2)对船载采购原油按需求总量分配采购增量，具体为6号油品采购增量＝第6号油品的需求总量19÷(第6号油品的需求总量19+第5号油品的需求总量14.5)×总采购增量0.5＝0.28万吨，5号油品采购增量＝第5号油品的需求总量14.5÷(第6号油品的需求总量19+第5号油品的需求总量14.5)×总采购增量0.5＝0.22万吨。

第五，介绍四染色体编码粒子所对应的采购-拼船/车运输方案的适应值计算步骤。

对实数编码的四染色体分别排序，得到整数编码的四染色体。按上文所述方法从整数编码的四染色体中解读粒子所代表的采购拼船-运输方案。

将船舶运行费用作为适应值，船舶运行费用包含地理航程费用、装/卸港滞期费用及靠港费用三部分。航程费用可根据上述行船路线计算；滞期费用可根据船舶在装港及卸港的非正常停靠时间计算；靠港费可根据该船沿途所停靠港口的征费标准计算。

其中装港滞期费用主要分两种情况，第一种是船舶过早抵达装港，等待装货期期间需向船东缴纳的费用，第二种是船舶过晚抵达装港，装期已过，需向港口管理方缴纳的费用。

写港滞期费用也分两种情况，第一种是船舶抵达卸港后，卸港内有其他船舶占用卸油泊位，等待泊位期间须向船东缴纳的费用；第二种是第一种是船舶抵达卸港时间超出需求油品的到货期要求范围，须向油品需求方缴纳的费用。

对于装卸原油而言，一般不允许超出时间期限，因此，第二种装港滞期费和第二种卸港滞期费都要设为无穷大，以控制算法的方案搜索方向。

第六：介绍群中粒子速度与位置更新操作。

按上文介绍的采购-拼船/车运输的适应值计算方法，计算群中各粒子的适应值，记录各粒子所搜索到的自身历史最优值，记录所有粒子所搜索到的全局历史最优值。根据下述公式更新各粒子的速度与位置。

(1)速度更新公式为：

(2)位置更新公式为：

上述两式中：

指第k次迭代粒子i飞行速度矢量的第d维分量；

指第k次迭代粒子i位置矢量的第d维分量；

指粒子i搜索到的自身历史最优矢量的第d维分量；

指所有粒子所搜索到的全局历史最优矢量的第d维分量；

ω指保持原来速度的系数，也叫做惯性权重。

c₁指粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识。

c₂指粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识。

ξ，η指[0,1]区间内均匀分布的随机数,用于增加搜索的随机性。

r指位置更新约束因子。

最后，介绍判断是否满足终止条件，如果不满足则返回步骤S5，如此循环直至满足终止条件，如果满足则结束计算并输出最优方案。

在本实施例中，程序终止条件是预先设定的迭代次数(例如，迭代1000次程序终止)。如果不满足则返回S5继续迭代，如此循环直至满足终止条件。如果满足则结束计算并输出最优方案。

本发明提供的基于粒子群算法的优化采购及拼船/车运输方法，将采购-拼船/车运输过程分解为采购染色体X、装货期染色体D、需求染色体Y与运输工具染色体Z进行耦合编码，并利用粒子群算法予以求解。通过需求匹配编码、配送定向解码及装期限定解码等方法，避免无解假象并有效提高算法的寻优效率，节约了大量的计算时间，实现了货物采购及拼装运输方案的优化，降低了分散货物采购-运输过程的物流成本，提高了集团化公司的联盟经营效益。该方法不仅可以应用于原油的优化采购及远洋船运，也可以应用于其他货物的优化采购及陆地车运，在此不再赘述。

本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

最后，还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。术语“上”、“下”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。

本发明的说明书中，说明了大量具体细节。然而能够理解的是，本发明的实施例可以在没有这些具体细节的情况下实践。在一些实例中，并未详细示出公知的方法、结构和技术，以便不模糊对本说明书的理解。类似地，应当理解，为了精简本发明公开并帮助理解各个发明方面中的一个或多个，在上面对本发明的示例性实施例的描述中，本发明的各个特征有时被一起分组到单个实施例、图、或者对其的描述中。然而，并不应将该公开的方法解释呈反映如下意图：即所要求保护的本发明要求比在每个权利要求中所明确记载的特征更多的特征。更确切地说，如权利要求书所反映的那样，发明方面在于少于前面公开的单个实施例的所有特征。因此，遵循具体实施方式的权利要求书由此明确地并入该具体实施方式，其中每个权利要求本身都作为本发明的单独实施例。

以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围，其均应涵盖在本发明的权利要求和说明书的范围当中。

Claims (5)

1.一种基于粒子群算法的货物采购及拼船/车运输方法，其应用场景包括：大型船泊/车辆依次经过不同的产地并将各产地的零散货物收集起来，经长途运输抵达销售地区后再依次经过不同的销地并在销地卸载相应批次的零散货物；其特征在于，包括如下步骤：

S1：获取货物采购及运输需求相关数据；

S2：设定粒子群中个体的货物采购及运输的染色体编码方案，设定染色体基因信息；

S3：配置粒子群算法参数；

S4：随机生成初始粒子群，包括位置群与速度群；

S5：解读粒子群中所有个体的染色体基因信息，生成采购-拼船/车运输配送方案，并计算粒子群中个体的适应值；

S6：记录个体历史最优方案与群体历史最优方案，更新群中各粒子个体的速度与位置；

S7：判断是否满足终止条件，如果不满足则返回S5，如此循环直至满足终止条件，如果满足则优化结束输出最优方案；

其中，所述设定粒子群中任一个体的货物采购及运输的染色体编码方案的步骤具体包括：

将货物采购-运输过程的货物收集方案、装货时间、货物分送方案和参与运输的运输工具分解的为供应染色体、需求染色体、运输工具染色体和装期染色体；

其中，所述计算粒子群中个体的适应值的步骤具体包括：

按照供应染色体和运输工具染色体基因顺序和基因对应的附加属性对货物运载工具装载及生成采购-装载方案；

按需求染色体基因顺序对应的附加属性对货物分运载工具配送；

按供应染色体和需求染色体的基因及基因附加属性定位货物供应地和货物卸载地的位置；

根据参与运输的运输工具和货物编号对应的货物供应地和货物卸载地的位置确定运输工具运输线路，并根据路线计算运输费；

按装期染色体、供应染色体和需求染色体的基因信息反推标注自选装货期的货物的装货期，而后计算到货期；

根据装货期和到货期计算运载工具在装货地和卸货地的滞期，并根据滞期计算滞期费；

根据供应染色体和需求染色体与运输工具染色体的港口与船型信息，计算运输工具的靠港费用；

将所有运输工具运输费、滞期费和靠港费加和，获得粒子群中相应个体的适应值；

其中，所述根据滞期计算滞期费的步骤还包括：

两个以上运载工具同时抵达时，其中之一需等待，等待时间为滞期，计算滞期费。

可选地，所述对货物运载工具装载及生成采购方案步骤具体包括：

S51：从运输工具染色体起始点开始读取运输工具染色体基因所代表的运输工具的编号，并由基因属性获取该运输工具的剩余载重；

S52:从供应染色体起始点开始读取供应染色体基因所代表的货物编码，并由基因属性获取该批次货物的剩余数量；

S53:判断是否结束生成装载方案；若供应染色体起始点位置大于供应染色体长度或运输工具的剩余载重将为零，则停止生成采购方案；

否则，进入步骤S54；

S54:令运输工具装载货物，生成购买与装载方案。

2.根据权利要求1所述的货物采购及拼船/车运输方法，其特征在于，所述按装期染色体、供应染色体和需求染色体的基因信息反推标注自选装货期的货物的装货期，而后计算到货期的具体步骤为：

从前至后读取编号为i的运输工具中装载的供应染色体的基因所代表的采购货物；

若编号为i的运输工具中装载的供应染色体基因所代表的某批次采购货物装期并非自选，则以此货物装期为基准，根据装港间的航程，向前反推前面编号为i的运输工具中装载的供应染色体的基因所代表的货物的装期，而后向后正推后面编号为i的运输工具中装载的供应染色体的基因所代表的货物的装期；

若编号为i的运输工具中装载的供应染色体所有基因所代表的采购货物装期属性都为自选，则根据编号为i的运输工具中装载的需求染色体第一个基因所代表的货物的卸载期限和装期染色体中的相应装期基因计算第一卸期，而后根据第一卸期反推前面编号为i的运输工具中装载的供应染色体的基因所代表的货物的装期；

其中i为常数。

3.根据权利要求1所述的货物采购及拼船/车运输方法，其特征在于，所述设定染色体基因信息的步骤具体包括：

对需要运输的各批次货物编号；

标记各货物供应地/卸载地，数量、类型、装货期/卸货期限，并相应编号；

对运输工具编号并标记各运载工具的额定运载量；

将供/需货物批次编号、运输工具编号及装货期编号作为相应染色体基因；

将货物供应地编号、货物卸载地编号、供应货物类型、需求货物类型、供应货物数量、需求货物数量、货物装期、参与运输的运载工具载重作为基因属性附着于相应染色体的基因上。

4.根据权利要求1所述的货物采购及拼船/车运输方法，其特征在于，所述粒子群算法参数包括惯性权重、个体历史最优权重、群体历史最优权重及位置更新约束因子、计算总迭代次数和粒子群的数量。

5.根据权利要求1所述的货物采购及拼船/车运输方法，其特征在于，更新群中各个体的速度与位置是按以下公式执行的：

速度更新公式为：

位置更新公式为：

其中，

指第k次迭代粒子i飞行速度矢量的第d维分量；

指第k次迭代粒子i位置矢量的第d维分量；

指粒子i搜索到的自身历史最优矢量的第d维分量；

指所有粒子所搜索到的全局历史最优矢量的第d维分量；

ω指保持原来速度的系数，也叫做惯性权重；

c₁指粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识；

c₂指粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识；

ξ，η指[0,1]区间内均匀分布的随机数,用于增加搜索的随机性；

r指位置更新约束因子。

Images