成品油配送车辆调度研究范文

《物流科技杂志》2015年第一期

1成品油配送车辆调度数学模型

1.1问题描述在配送网络中，多车型成品油配送VSP可以描述为：配送网络中共有K种成品油配送任务，有N个加油站，其中第n个加油站对k类成油品的需求量为gnkk=1,2,…,K;n=0,1,2,…,,,N配送中心共有S辆不同车型的油罐车可提供配送任务，共有R种车型，某些车型的油罐车可以进行多油品分隔装载，其中车型为r的油罐车油品k的最大载重量为qrkk=1,2,…,K;r=1,2,…,,,R。假设所有进行配送运输任务的油罐车都由配送中心出发，首先到油库完成油品装载，然后完成成品油配送任务，完成所有任务后返回至配送中心，按油罐车行驶过程中的起始节点来划分，可以将运输路线分为以下三类：（1）由配送中心行驶至加油站；（2）由加油站行驶至加油站；（3）由加油站行驶至配送中心。

1.2成品油配送车辆调度模型整个动态配送网络记为Net，由M表示加油站集合，K表示油品型号集合，S表示所有油罐车组成的集合，R表示油罐车车型集合，r∈R的车厢分为多个容量不等的固定舱位，由它们组成的集合记为H,R,；cijk表示由节点i到节点j的品种k的成品油运输成本，其含义可以是距离、费用、时间等；记油罐车空载时的单位距离油耗成本为e1，满载时油耗成本为e2；设油罐车的实载重量为q，则其载重率为pi=q/Qrk（Qrk为车型为r的油罐车油品k的最大载重量），则该车型油罐车的单位油耗成本为：ei''''=e1+pie2-e1,,。则油罐车的油耗成本为运输距离与ei''''的乘积。由此，建立多车型—多油品—多加油站的成品油配送车辆调度VSP数学模型如下：首先给出决策变量：其中，Z表示调度任务的总成本；Frs表示车辆的固定行驶费用，包括人力成本、车辆行驶固定成本、油库内物流附加费等，以及在1.1节中简化的从配送中心至油库的运输成本；N为加油站个数；K为配送区域内油品种类数量；S为可用油罐车个数；R为油罐车车型种类数量；Qrk表示油罐车车型r的油品k最大载重量；L为加油站配送任务个数，即油罐车需要服务的加油站个数；cijk表示两节点间油品k的配送成本；ei''''为油罐车的单位油耗成本；其中编号为0的加油站表示配送中心。在公式（1）中，表示调度总成本最小的优化目标；公式（2）表示车辆s的配送任务中第k种油的配送总量不能超过该油罐车对应舱位的载重量；公式（3）表示每个加油站的每一种油品的配送需求都需要有油罐车对其进行服务；公式（4）、（5）表示两个变量之间的关系，表示节点所有油品配送需求总和间的关系；公式（6）表示车辆由配送中心出发，并且最终回到配送中心；公式（7）表示油罐车所完成的配送油品总数大于配送任务数，即油罐车对加油站的一次配送任务应尽可能完成对多种油品的配送；公式（8）表示从配送中心共发出S辆油罐车；公式（9）、（10）表示变量的0～1约束；公式（11）用于消除配送路径中的回路；公式（12）、（13）为变量的取值范围。

2求解算法

目前，对车辆调度问题的求解算法，国内外相关文献主要分为两类：精确算法和启发式算法，对于简单的小规模车辆调度问题主要采用精确算法，大规模的车辆调度问题，由于车辆调度问题的限制条件较多，大多采用启发式算法求得次优解。成品油配送中的车辆调度路径问题除了具有一般VSP问题求解的复杂性之外，还具有油品配送过程中的复杂性特征，包括多车型、多商品、多舱位、满舱配载要求、运载负荷量平衡等约束条件，由此，本文通过启发式算法寻求可行解。通过对现有文献的总结分析，使用较多的启发式算法为遗传算法。文献[2]、[4-5]建立了车辆调度问题的数学模型并利用遗传算法进行了求解；文献[6]建立车辆调度动态模型，并利用改进的遗传算法对问题进行了求解。本文通过对遗传算法的编码结构、交叉和变异操作方式进行改进来对所建立的数据模型进行求解。

（1）染色体的编码设计。由于成品油车辆调度问题解的特殊结构，本文直接用自然数序列作为染色体的编码。由N个加油站构成的配送网络需要S辆油罐车进行配送的问题，可以用一条长为N+S+1的染色体编码，其中N个自然数从1至N进行全排列，其数值表示加油站序号，在染色体中的位置表示被服务的次序；同时，S+1个0表示S辆车从配送中心出发最后回到配送中心。0,i1,i2…,ie,0,if…,ik,0,ip,…,iq,,0,，其中ij表示第j个加油站，0表示配送中心，其中有三条子路，配送中心首先派出第一辆油罐车按i1,i2,…,ie的顺序对e个加油站进行服务，完成后回到配送中心，形成第一条回路；第二辆油罐车也由配送中心出发，按if,…,ik对加油站完成服务后回到配送中心形成第二条回路；第三条回路也是同理。所设计的染色体具有子路间无序，子路内有序的特点；同时，为了表示每条子路径在完成配送任务时具体使用的车型和舱位，则引入了一个辅助队列用于存储配送油罐车的车型、舱位和载重量，并按染色体中子路径的服务顺序依次存放。这样的编码方式可以很方便的得到某个加油站服务的油罐车具体信息，同时在执行遗传算子时，仅对染色体本身进行遗传操作，其对应的辅助队列只需相应调整即可，能够有效增强算法的收敛性从而缩短求解时间[5]。（2）初始化种群。随机产生N个加油站的序列0,i1,i2,…,ie,,0,，并在首尾插入0，表示油罐车由配送中心出发，最后回到配送中心。如10个加油站的配送网络，,0,3,2,8,5,4,1,6,9,7,10,0,，同时初始化辅助队列，假设配送中心有5种车型，每个车型有h个舱位，以第一个进行配送的3号加油站为例，则在辅助队列中存放如,2,3,,2,3,,,2,3.5,,表示配送中心派出车型为3的2号油罐车用2号舱位2吨，3号舱位3.5吨对3号加油站进行配送。（3）适应度函数。成品油车辆调度问题是一最小化组合优化问题，其目标是运输总成本费用最小，由此，可以直接取目标函数的倒数作为适应度函数。（4）选择操作。利用（3）中的适应度函数计算种群中个体的适应值，根据适应值的大小对其进行排序，则规模为P的种群，记最小适应度值个体为0，最大适应度个体为P-1。在标准正态分布中，99.9%的随机数r分布在≤-3,3≤之间，此时，取r*=r3且-3≤r≤3，则t=r**P-,,1，则选取第t号染色体进入新种群，由此适应度值越靠近0的染色体被选取的概率越大，则选取较优染色体的可能性越高[6]。（5）交叉算子。由于车辆调度问题解的特殊结构，染色体编码具有组间无序、组内有序的特点，如果采用传统的单点交叉、多点交叉等，组内的优良子串都可能被破坏，并且当两个父代个体相同时，无法产生新个体。本文结合油罐车车辆调度问题编码的特殊性，交叉点选择配送中心位置，即编码中0所在位置，以避免破坏优秀子串，同时，在交叉时不是直接复制子串，而是将子串复制到染色体的首位，这样可以最大限度对已生成子串进行保护，同时也避免了在双亲相同时不能产生新个体的问题，具体操作如下：①交叉复制。以概率p随机选择两个染色体A和B，随机在1,m之间产生两个自然数r1和r2（其中m为染色体中的子线路个数），将A中的子路线r1复制到后代B*最前端，同时将B中的子路线r2复制到后代A*最前端，具体过程如图2所示：本文在交叉操作过程中引入了交叉概率自适应性的思想，在迭代求解过程中，不断修正对算法性能起着决定作用的交叉概率,从而克服过早收敛和加快搜索速度。本文采用的自适应交叉概率公式。式（1）中pcmax是最大交叉概率（本文取1.0）；pcmin是最小交叉概率（本文取0.2）；t是遗传代数；T是最大遗传代数。这种自适应的生成方法使得在迭代初期，交叉概率较大并且下降缓慢，能够对染色体产生足够大影响，增强算法的搜索能力，避免算法陷入迟钝状态，加快进化速度；同时在迭代后期，交叉概率较低，并逐步减小，最后为一常量，这种方式避免破坏优良基因，加快收敛速度，能够增加搜索到全局最优解的可能性。②逆转操作。对使用基于路径表示编码的基因进行交叉操作来VSP问题时，如果单纯使用传统的交叉算子，则会使一些较优的基因组合被破坏，使子代难以继承父代的优良基因，导致搜索能力降低。由此，本文采用逆转算子代替交叉操作，即对没有进行交叉复制操作的表示车辆路径的基因串顺序进行逆转操作，以图2中进行交叉复制后的染色体为例，其过程如图3所示。（6）变异操作。以交叉概率随机选择一个染色体，在1,N+S间随机产生两个自然数n1与n2，若n1与n2都对应非0基因，则交换这两个基因，否则重新产生新的自然数。（7）终止条件。设置重复迭代20次种群没有变化，终止迭代过程，若未达到终止条件，转（3），否则转（8）。（8）输出结果。将种群中适应度值最优的个体进行输出，并将其转换为问题的满意解或最优解。

3应用改进遗传算法求解某成品油配送公司车辆调度问题

设某成品油配送公司共有3种油罐车车型，其运力能够满足加油站油品的配送需求，某日配送中心接到13个加油站配送油品配送订单，共有2种不同的成品油类别，13个加油站之间的距离如表1所示（其中0号加油站表示配送中心），油品需求量如表2所示，油罐车油品最大载重量及固定成本如表3所示。表3中，油品种类与仓位在一列中进行表示，即1号仓位装载1号油品，2号仓位装载2号油品，油罐车使用的燃料以7.44元/L的柴油计算，并要求每个加油站只能进行一次配送，应用第3节提出的遗传算法，使用自然数编码，种群大小P设置为100，最大进化代数T设置为120，参数设置如下：pcmax=1.0，pcmin=0.2，以进化代数和适应度为目标进行双重判断，其计算结果如表4所示。从表4运行结果可以看出，方案2，3，7需要的油罐车数量较多，而油罐车固定成本在总成本中占较大比重，因为，直接将该三个方案从备选方案中去除。通过对方案的总成本进行详细分析，如表5所示，以运输总成本为评选指标，方案5为最佳调度方案，该方案具有最低运输成本，同时，行驶总距离最小。

4总结与展望

本文针对成品油配送中车辆调度问题的约束条件进行分析，建立了多车型—多油品—多加油站的成品油配送车辆调度模型，在模型基础上设计改进遗传算法对车辆调度问题进行求解，其中，对算法中的染色体结构，选择操作，交叉操作等进行了改进。最后，通过具体案例验证了模型与算法的有效性。

作者：杨渝华李敏单位：西南交通大学交通运输与物流学院