遗传算法-物流分析课件.ppt

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

2、物流平台信息中心、网上银行、商家、客户和各个配送网点的通信商家、客户和各个配送网点的通信介质集成在一起。介质集成在一起。4v业务流程业务流程: v( 1) 客户通过客户通过Internet 访问物流信息平台的网站访问物流信息平台的网站, 填写送货单填写送货单; v( 2) 物流信息平台认证客户身份物流信息平台认证客户身份; v( 3) 客户通过输入银行信用卡账号和网上专用密客户通过输入银行信用卡账号和网上专用密码进行支付码进行支付; v( 4) 物流信息平台将支付信息提交网上银行物流信息平台将支付信息提交网上银行; v( 5) 网上银行返回扣款结果网上银行返回扣款结果, 网上交易结束网上交易结

3、束;v( 6) 物流信息平台中心服务器进行订单派送调度物流信息平台中心服务器进行订单派送调度;v( 7) 订单配送至相应配送网点订单配送至相应配送网点, 各配送网点安排运各配送网点安排运输车次与运输路线输车次与运输路线, 配送货物配送货物, 这是物流配送中的这是物流配送中的配送车调度问题。配送车调度问题。5v车辆调度问题车辆调度问题(Vehicle Routing Problem 简称简称VRP) ：v是对巡回旅行商问题是对巡回旅行商问题( TSP, Traveling Salesman Problem) 加以一定的限制而形成的加以一定的限制而形成的, 属于约属于约束性的多重束性的多重TSP

4、问题问题( CMTSP, Constrained Multiple Traveling Salesman Problem) 6v约束条件：约束条件：v(1)所有车辆路线均起始并终止于配送中心，所有车辆路线均起始并终止于配送中心， 每一每一客户点只由一辆车服务，一辆车也可服务多个客客户点只由一辆车服务，一辆车也可服务多个客户点；户点； v(2)每个客户点都有一个非负的额货物需求量，每个客户点都有一个非负的额货物需求量， 但但每辆车负责的客户点的货物需求量总和不超过该每辆车负责的客户点的货物需求量总和不超过该车辆的最大装载辆；车辆的最大装载辆；v(3) 每辆车的行车路线的总耗时不超过一个事先定每辆

5、车的行车路线的总耗时不超过一个事先定v下的值，以满足客户对供货时间的要求；下的值，以满足客户对供货时间的要求；v(4)对某个客户点，车辆到达时间限制在某一时间对某个客户点，车辆到达时间限制在某一时间段内。如此约束不满足，则引入惩罚函数；段内。如此约束不满足，则引入惩罚函数；7v 根据上述问题描述，对车辆调度问题进行建模。设根据上述问题描述，对车辆调度问题进行建模。设F 为最为最小成本，则目标函数为小成本，则目标函数为: 其中，其中，K 为所有车辆的集合，为所有车辆的集合， K=1,2,m, kK I 为所有客户的集合，为所有客户的集合， I=1,2,n，iIv 目标函数中的目标函数中的Cij表

6、示从客户表示从客户i 到客户到客户j 的费用成本。的费用成本。v 目标函数中的为目标函数中的为P(t)为惩罚函数，为惩罚函数， 当车辆不能按时到达时当车辆不能按时到达时，引入此函数来增加车辆调度的成本。，引入此函数来增加车辆调度的成本。8该函数满足的约束条件为：该函数满足的约束条件为：v其中其中(1)控制控制n 个客户由个客户由m 辆车来共同完成。辆车来共同完成。v (2)控制每一客户只有一辆车来完成。控制每一客户只有一辆车来完成。v其中：其中：X9v 目标函数中的目标函数中的Pnum(M)为车辆装容量约束为车辆装容量约束 ，首先扫描每，首先扫描每一客户的需求量，一客户的需求量， 若这些需求量

7、均不小于每一车辆的载若这些需求量均不小于每一车辆的载重量，则所需车辆总数为重量，则所需车辆总数为Int(Sum/avge)+1，其中，其中Sum 表表示所有客户的需求量总和，示所有客户的需求量总和，avge 表示车的载重量。若扫表示车的载重量。若扫描客户的需求量时，有超过车辆的载重量的，先看客户的描客户的需求量时，有超过车辆的载重量的，先看客户的需求能装满几辆车，需求能装满几辆车， 直接从可供选择的车辆中随机挑直接从可供选择的车辆中随机挑 选几辆车去完成该客户的需求，选几辆车去完成该客户的需求， 然后把装不满一辆车的然后把装不满一辆车的需求量作为该客户的需求量去参与基本遗传算法的运算。需求量作

8、为该客户的需求量去参与基本遗传算法的运算。10车辆调度问题中遗传算法的设计：车辆调度问题中遗传算法的设计：v1 染色体编码（一般采用自然数编码）：染色体编码（一般采用自然数编码）：v设配送中心的序号为设配送中心的序号为0，依次对各配送点编号形，依次对各配送点编号形成染色体，该染色体表示了车辆调度，路线安排成染色体，该染色体表示了车辆调度，路线安排等各种信息。例如。染色体等各种信息。例如。染色体01203450 表示一条表示一条路线从配送中心出发，经过配送点路线从配送中心出发，经过配送点1，2 后回到配后回到配送中心；另一条路线从配送中心出发，送中心；另一条路线从配送中心出发， 经过配送经过配送

9、点点3，4，5 回到配送中心。回到配送中心。11车辆调度问题中遗传算法的设计：车辆调度问题中遗传算法的设计：v2 生成初始染色体种群：生成初始染色体种群：v染色体的长度染色体的长度=车辆总数车辆总数+客户数客户数+1v3 适应度函数：适应度函数：v由目标函数由目标函数 f k = Zm in / Z k转化得到转化得到: f k是染色体是染色体k 的适应度函数的适应度函数, Zm in 是同代群体中最佳染色体的是同代群体中最佳染色体的费用费用, Z k 是染色体是染色体k 的费用的费用. 适应度最大染色体对适应度最大染色体对应配送成本最低调度方案应配送成本最低调度方案.12车辆调度问题中遗传算

10、法的设计：车辆调度问题中遗传算法的设计：v4 复制算子复制算子: v给给n 条染色体排序条染色体排序; 计算适应度计算适应度f k; 计算选择概率计算选择概率w k = f k/f k; 计算累积概率计算累积概率uk = w k; 产生产生 0, 1 区间均匀分布随机数区间均匀分布随机数R , 若若R u1, 则复制染色体则复制染色体1, 否则复制染色体否则复制染色体k , 使得使得uk- 1 R uk , k = 2, , n. 重复复制重复复制, 直到符合群体规模直到符合群体规模n. 为提高算法为提高算法性能性能,保留上代群体中最佳染色体保留上代群体中最佳染色体.13车辆调度问题中遗传算法

11、的设计：车辆调度问题中遗传算法的设计：v5 交叉算子交叉算子: v按按2 个一串将双亲个一串将双亲“01302450”和和“02350140”基因分组基因分组, 得得0| 13 | 02 | 450 和和v0 | 23 | 50 | 140; 双亲双亲1 中子串中子串“13”两端都为两端都为0, 把把“13”和所有和所有“0”基因保留基因保留, 填充到空白染色填充到空白染色v体相同位置上体相同位置上; 删去双亲删去双亲2 基因基因1 和和3, 把剩余基因把剩余基因按顺序填入空白位置按顺序填入空白位置, 得后代得后代1“01302540”. 同同理得后代理得后代2“03250140”. 若所有子

12、串两端不全为若所有子串两端不全为0, 则左移或右移则左移或右移“| ”, 直到存在两端为直到存在两端为0 子串子串.14车辆调度问题中遗传算法的设计：车辆调度问题中遗传算法的设计：v6 变异算子变异算子: v对对2 交换变异算子交换变异算子, 在染色体中任在染色体中任意确定两个非零基因意确定两个非零基因, 交换其位置交换其位置, 就得到就得到1 条新染色体条新染色体.以此类推。以此类推。15车辆调度问题中遗传算法的设计：车辆调度问题中遗传算法的设计：v6 变异算子变异算子: v遗传算法设计最后一步是确定控遗传算法设计最后一步是确定控制参数和算法终止条件制参数和算法终止条件. 推荐控制推荐控制参数取值范围是群体规模参数取值范围是群体规模n = 20 50, 交叉率交叉率P c = 0.6 1.0, 变异率变异率Pm = 0 0.05. 算法终止条件根据算法终止条件根据v具体情况确定具体情况确定.