遗传算法-物流分析课件

基于遗传算法的物流配送车调度优化算法

信息科学系科技研讨

基于遗传算法的物流配送车调度优化算法

信息科学系科技2电子商务物流配送:是指物流配送企业采用计算机网络技术和现代化的硬件设备、软件系统及先进的管理手段,针对社会需求,按用户的订货要求,进行一系列分类、编配、整理、分工、配货等理货工作,定时、定点、定量地交给没有范围限度的各类用户,满足其对商品的需求.基于遗传算法的物流配送车调度优化算法2电子商务物流配送:基于遗传算法的物流配送车调度优化算法3

电子商务物流配送平台：将物流平台信息中心、网上银行、商家、客户和各个配送网点的通信介质集成在一起。基于遗传算法的物流配送车调度优化算法3电子商务物流配送平台：基于遗传算法的物流配送车调度优4业务流程:(1)客户通过Internet访问物流信息平台的网站,填写送货单;(2)物流信息平台认证客户身份;(3)客户通过输入银行信用卡账号和网上专用密码进行支付;(4)物流信息平台将支付信息提交网上银行;(5)网上银行返回扣款结果,网上交易结束;(6)物流信息平台中心服务器进行订单派送调度;(7)订单配送至相应配送网点,各配送网点安排运输车次与运输路线,配送货物,这是物流配送中的配送车调度问题。基于遗传算法的物流配送车调度优化算法4业务流程:基于遗传算法的物流配送车调度优化算法5车辆调度问题(VehicleRoutingProblem简称VRP)：是对巡回旅行商问题(TSP,TravelingSalesmanProblem)加以一定的限制而形成的,属于约束性的多重TSP问题(CMTSP,ConstrainedMultipleTravelingSalesmanProblem)基于遗传算法的物流配送车调度优化算法5车辆调度问题(VehicleRoutingProble6约束条件：(1)所有车辆路线均起始并终止于配送中心，每一客户点只由一辆车服务，一辆车也可服务多个客户点；(2)每个客户点都有一个非负的额货物需求量，但每辆车负责的客户点的货物需求量总和不超过该车辆的最大装载辆；(3)每辆车的行车路线的总耗时不超过一个事先定下的值，以满足客户对供货时间的要求；(4)对某个客户点，车辆到达时间限制在某一时间段内。如此约束不满足，则引入惩罚函数；基于遗传算法的物流配送车调度优化算法6约束条件：基于遗传算法的物流配送车调度优化算法7根据上述问题描述，对车辆调度问题进行建模。设F为最小成本，则目标函数为:其中，K为所有车辆的集合，K={1,2…,m},k∈KI为所有客户的集合，I={1,2…,n}，i∈I目标函数中的Cij表示从客户i到客户j的费用成本。目标函数中的为P(t)为惩罚函数，当车辆不能按时到达时，引入此函数来增加车辆调度的成本。基于遗传算法的物流配送车调度优化算法7根据上述问题描述，对车辆调度问题进行建模。设F为最小成本8

该函数满足的约束条件为：其中(1)控制n个客户由m辆车来共同完成。(2)控制每一客户只有一辆车来完成。其中：X基于遗传算法的物流配送车调度优化算法8该函数满足的约束条件为：基于遗传算法的物流配送车调度9目标函数中的Pnum(M)为车辆装容量约束，首先扫描每一客户的需求量，若这些需求量均不小于每一车辆的载重量，则所需车辆总数为Int(Sum/avge)+1，其中Sum表示所有客户的需求量总和，avge表示车的载重量。若扫描客户的需求量时，有超过车辆的载重量的，先看客户的需求能装满几辆车，直接从可供选择的车辆中随机挑选几辆车去完成该客户的需求，然后把装不满一辆车的需求量作为该客户的需求量去参与基本遗传算法的运算。基于遗传算法的物流配送车调度优化算法9目标函数中的Pnum(M)为车辆装容量约束，首先扫描每一10

车辆调度问题中遗传算法的设计：1染色体编码（一般采用自然数编码）：设配送中心的序号为0，依次对各配送点编号形成染色体，该染色体表示了车辆调度，路线安排等各种信息。例如。染色体01203450表示一条路线从配送中心出发，经过配送点1，2后回到配送中心；另一条路线从配送中心出发，经过配送点3，4，5回到配送中心。基于遗传算法的物流配送车调度优化算法10车辆调度问题中遗传算法的设计：基于遗传算法的物流配11

车辆调度问题中遗传算法的设计：2生成初始染色体种群：染色体的长度=车辆总数+客户数+13适应度函数：由目标函数fk=Zmin/Zk转化得到:fk是染色体k的适应度函数,Zmin是同代群体中最佳染色体的费用,Zk

是染色体k的费用.适应度最大染色体对应配送成本最低调度方案.基于遗传算法的物流配送车调度优化算法11车辆调度问题中遗传算法的设计：基于遗传算法的物流配12

车辆调度问题中遗传算法的设计：4复制算子:给n条染色体排序;计算适应度fk;计算选择概率w

k=fk/Σfk;计算累积概率uk=Σw

k;产生[0,1]区间均匀分布随机数R,若R≤u1,则复制染色体1,否则复制染色体k,使得uk-1<R≤uk,k=2,⋯,n.重复复制,直到符合群体规模n.为提高算法性能,保留上代群体中最佳染色体.基于遗传算法的物流配送车调度优化算法12车辆调度问题中遗传算法的设计：基于遗传算法的物流配13

车辆调度问题中遗传算法的设计：5交叉算子:按2个一串将双亲“01302450”和“02350140”基因分组,得0|13|02|450和0|23|50|140;双亲1中子串“13”两端都为0,把“13”和所有“0”基因保留,填充到空白染色体相同位置上;删去双亲2基因1和3,把剩余基因按顺序填入空白位置,得后代1“01302540”.同理得后代2“03250140”.若所有子串两端不全为0,则左移或右移“|”,直到存在两端为0子串.基于遗传算法的物流配送车调度优化算法13车辆调度问题中遗传算法的设计：基于遗传算法的物流配14

车辆调度问题中遗传算法的设计：6变异算子:对2交换变异算子,在染色体中任意确定两个非零基因,交换其位置,就得到1条新染色体.以此类推。基于遗传算法的物流配送车调度优化算法14车辆调度问题中遗传算法的设计：基于遗传算法的物流配15

车辆调度问题中遗传算法的设计：6变异算子:遗传算法设