整车物流调度系统

【摘 要】随着我国经济突飞猛进的发展，物流成为社会分工中重要的环节。物流系统的优劣也影响了业务流程的运行效率及其成本。国内某家物流公司的主要业务是从分布在全国的M个主机厂，将N种品牌商品小汽车调运到全国多个城市的4S店。文章应用0-1规划的思想解决了整车物流调度的优化问题。

【关键词】遗传算法；0-1[2]规划；Floyd算法

1.模型建立

我们假设货车运达所有订单后，停留在最终的目的地且不返回，因此不产生回途所需要的空载费用以及小汽车运载的业务费。

1.1相应的一系列费用陈述如下

①货车P从订单点i到订单点j的空载费用=货车运输途中因部分车位空闲而产生的空载运输成本为0.2元/（公里·车位）*空载车位数量*订单点i，j之间的距离，即为：0.2×T×d。

②小汽车订单点i到订单点j的业务费用=运输商品小汽车的业务费为0.7元/（公里·辆）*从订单点i卸下订单后的小汽车数量（也即为货车可运载小汽车总车位数量-空车位数量）*订单点i，j之间的距离，即为：0.7×（Bp-Tij）×dij。

③货车P从订单点i到订单点j的油耗费=油耗动力成本为0.5元/公里*订单点i，j之间的距离，即为：0.5×d。

④货车P从订单点i到订单点j的过路费=过路费成本为0.4元/公里*订单点i，j之间的距离，即为：0.4×d。

⑤以上费用为货车P从运单点i到j的总体费用，进行求和得到编号为P的货车在两订单点之间的运营成本：W=

0.2×T+0.7×

（B

-T）+0.9×d。

⑥一辆货车在订单点i，j之间产生的总体费用，因问题一中92个订单点的总体费用只需将其针对i、j求和即可，但考虑到货车P不一定经过每一个订单点，因此我们在此引入一个0-1变量Xijp，定义。

X=1 编号为P的货车从订单点i行驶到j

0 编号为P的货车不从订单点i行驶到j

由此即可得到编号为P的货车在两订单点之间的总运输费，记为 W2：

W2=0.2

×T+0.7×

（B

-T）+0.9×d×X

⑦而从某个主机厂调度货车来完成运输订单，保证在完成运输任务的基础上得到总体运输成本为：W3=0.2

×T+0.7×

（B

-T）+0.9×d×X。

由题意有，需要我们把握在完成运输任务的基础上使得运费最少，再结合上述的费用称述，因此我们得到目标函数为：

min=W3=0.2

×T+0.7×

（B

-T）+0.9×d×X。

1.2约束条件，在此，我们主要考虑以下因素

①每一辆货车所能装载的小汽车数量有限（也即车位有限）：D×Y≤B。

②一个运力货车运单的目的地城市的数量不超过3个：Y≤3。

③允许将不同订单用同一货车运输，但是不允许将同一订单拆分用不同货车运输：X×Y=1。

由上述可得，模型建立如下：

min=W3=0.2

×T+0.7×

（B

-T）+0.9×d×X。

s.t

D

×Y≤

B

Y≤3

X×

Y=1

Y=0，1

X=0，1

2.模型求解

文章解决的是一个典型的规划问题，我们采用遗传算法进行问题的求解。

遗传算法[1]基本原理：长度为L的n个二进制串bi（i=1，2，…，n）组成遗传算法的初解群，在每个串中，每个二进制位就是个体染色体的基因。

遗传算法的步骤和意义：

（1）初始化：选择一个群体集合bi，i=1，2，...n，这个初始的群体即问题假设解的集合。一般取n=30-160。

（2）选择：根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。给出目标函数f，则f（bi）称为个体bi的适应度。为选中bi为下一代个体的次数。显然：

1）适应度较高的个体，繁殖下一代的数目较多。

2）适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

如此产生对环境适应能力较强的后代。即选择出和最优解较接近的中间解。

（3）交叉：对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。例如有个体：S1=100101、S2=010111，选择它们的左边3位进行交叉操作，则有：S1=010101、S2=100111，一般而言，取值为0.25—0.75。

（4）变异：根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。例如有个体S=101011。对其的第1，4位置的基因进行变异，则有S'=001111。

（5）全局最优收敛：最优个体的适应度达到给定的阈值，或者最优个体适应度和群体适应度不再上升时，则算法迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步继续循环。

对原始数据进行了预处理之后利用遗传算法，应用C语言得到结果如下：

图一 求解结果地图呈现

3.结果分析

根据本文求解，我们可以应用到各种物流的具（下转第215页）（上接第186页）体分配工作方面，可以在理论上帮助降低成本，给出较优的规划方案。 [科]

【参考文献】

[1]王赟，李仁旺，倪夏静，陈昆昌，莫灿林.基于遗传算法的服装配送路径优化策略[J].浙江理工大学学报，杭州：2013.03.

[2]殷铭，张兴华，戴先忠.基于MATLAB的遗传算法.南京东南大学自动控制系（210096）.计算机应用.