遗传算法——物流分析课件

《遗传算法——物流分析课件》由会员分享，可在线阅读，更多相关《遗传算法——物流分析课件（15页珍藏版）》请在装配图网上搜索。

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

2、量地交给没有范围限度的各类用户度的各类用户,满足其对商品的需求满足其对商品的需求.基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法2电子商务物流配送:基于遗传算法的物流配送车调度优化算法3电子商务物流配送平台：电子商务物流配送平台：v将物流平台信息中心、网上银行、将物流平台信息中心、网上银行、商家、客户和各个配送网点的通信商家、客户和各个配送网点的通信介质集成在一起。介质集成在一起。基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算

3、法的物流配送车调度优化算法3电子商务物流配送平台：基于遗传算法的物流配送车调度优4v业务流程业务流程:v(1)客户通过客户通过Internet 访问物流信息平台的网站访问物流信息平台的网站,填写送货单填写送货单;v(2)物流信息平台认证客户身份物流信息平台认证客户身份;v(3)客户通过输入银行信用卡账号和网上专用密客户通过输入银行信用卡账号和网上专用密码进行支付码进行支付;v(4)物流信息平台将支付信息提交网上银行物流信息平台将支付信息提交网上银行;v(5)网上银行返回扣款结果网上银行返回扣款结果,网上交易结束网上交易结束;v(6)物流信息平台中心服务器进行订单派送调度物流信息平台中心服务器进

4、行订单派送调度;v(7)订单配送至相应配送网点订单配送至相应配送网点,各配送网点安排运各配送网点安排运输车次与运输路线输车次与运输路线,配送货物配送货物,这是物流配送中的这是物流配送中的配送车调度问题。配送车调度问题。基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法4业务流程:基于遗传算法的物流配送车调度优化算法5v车辆调度问题车辆调度问题(Vehicle Routing Problem 简称简称VRP)：v是对巡回旅行商问题是对巡回旅行商问题(TSP,Traveling Salesman Prob

5、lem)加以一定的限制而形成的加以一定的限制而形成的,属于约属于约束性的多重束性的多重TSP 问题问题(CMTSP,Constrained Multiple Traveling Salesman Problem)基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法5车辆调度问题(Vehicle Routing Proble6v约束条件：约束条件：v(1)所有车辆路线均起始并终止于配送中心，所有车辆路线均起始并终止于配送中心，每一每一客户点只由一辆车服务，一辆车也可服务多个客客户点只由一辆车服务，一辆车也

6、可服务多个客户点；户点；v(2)每个客户点都有一个非负的额货物需求量，每个客户点都有一个非负的额货物需求量，但但每辆车负责的客户点的货物需求量总和不超过该每辆车负责的客户点的货物需求量总和不超过该车辆的最大装载辆；车辆的最大装载辆；v(3)每辆车的行车路线的总耗时不超过一个事先定每辆车的行车路线的总耗时不超过一个事先定v下的值，以满足客户对供货时间的要求；下的值，以满足客户对供货时间的要求；v(4)对某个客户点，车辆到达时间限制在某一时间对某个客户点，车辆到达时间限制在某一时间段内。如此约束不满足，则引入惩罚函数；段内。如此约束不满足，则引入惩罚函数；基于遗传算法的物流配送车调度优化算法基于遗

7、传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法6约束条件：基于遗传算法的物流配送车调度优化算法7v根据上述问题描述，对车辆调度问题进行建模。设根据上述问题描述，对车辆调度问题进行建模。设F 为最为最小成本，则目标函数为小成本，则目标函数为:其中，其中，K 为所有车辆的集合，为所有车辆的集合，K=1,2,m,kK I 为所有客户的集合，为所有客户的集合，I=1,2,n，iIv目标函数中的目标函数中的Cij表示从客户表示从客户i 到客户到客户j 的费用成本。的费用成本。v目标函数中的为目标函数中的为P(t)为惩罚函数，为惩罚函数，当车辆不能按

8、时到达时，当车辆不能按时到达时，引入此函数来增加车辆调度的成本。引入此函数来增加车辆调度的成本。基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法7根据上述问题描述，对车辆调度问题进行建模。设F 为最小成本8该函数满足的约束条件为：该函数满足的约束条件为：v其中其中(1)控制控制n 个客户由个客户由m 辆车来共同完成。辆车来共同完成。v (2)控制每一客户只有一辆车来完成。控制每一客户只有一辆车来完成。v其中：其中：X 基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算

9、法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法8该函数满足的约束条件为：基于遗传算法的物流配送车调度9v目标函数中的目标函数中的Pnum(M)为车辆装容量约束为车辆装容量约束，首先扫描每，首先扫描每一客户的需求量，一客户的需求量，若这些需求量均不小于每一车辆的载重若这些需求量均不小于每一车辆的载重量，则所需车辆总数为量，则所需车辆总数为Int(Sum/avge)+1，其中，其中Sum 表示表示所有客户的需求量总和，所有客户的需求量总和，avge 表示车的载重量。若扫描表示车的载重量。若扫描客户的需求量时，有超过车辆的载重量的，先看客户的需客户的需求量时，有超过车辆的载重量的，先

10、看客户的需求能装满几辆车，求能装满几辆车，直接从可供选择的车辆中随机挑直接从可供选择的车辆中随机挑 选几辆车去完成该客户的需求，选几辆车去完成该客户的需求，然后把装不满一辆车的需然后把装不满一辆车的需求量作为该客户的需求量去参与基本遗传算法的运算。求量作为该客户的需求量去参与基本遗传算法的运算。基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法9目标函数中的Pnum(M)为车辆装容量约束，首先扫描每一10车辆调度问题中遗传算法的设计：车辆调度问题中遗传算法的设计：v1 染色体编码（一般采用自然数编码）

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

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

13、低调度方案.基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法11车辆调度问题中遗传算法的设计：基于遗传算法的物流配12车辆调度问题中遗传算法的设计：车辆调度问题中遗传算法的设计：v4 复制算子复制算子:v给给n 条染色体排序条染色体排序;计算适应度计算适应度f k;计算选择概率计算选择概率w k=f k/f k;计算累积概率计算累积概率uk=w k;产生产生 0,1 区间均匀分布随机数区间均匀分布随机数R,若若R u1,则复制染色体则复制染色体1,否则复制染色体否则复制染色体k,使得使得uk-1 R

14、 uk,k=2,n.重复复制重复复制,直到符合群体规模直到符合群体规模n.为提高算法为提高算法性能性能,保留上代群体中最佳染色体保留上代群体中最佳染色体.基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法12车辆调度问题中遗传算法的设计：基于遗传算法的物流配13车辆调度问题中遗传算法的设计：车辆调度问题中遗传算法的设计：v5 交叉算子交叉算子:v按按2 个一串将双亲个一串将双亲“01302450”和和“02350140”基因分组基因分组,得得0|13|02|450 和和v0|23|50|140;双亲双

15、亲1 中子串中子串“13”两端都为两端都为0,把把“13”和所有和所有“0”基因保留基因保留,填充到空白染色填充到空白染色v体相同位置上体相同位置上;删去双亲删去双亲2 基因基因1 和和3,把剩余基因把剩余基因按顺序填入空白位置按顺序填入空白位置,得后代得后代1“01302540”.同理同理得后代得后代2“03250140”.若所有子串两端不全为若所有子串两端不全为0,则左移或右移则左移或右移“|”,直到存在两端为直到存在两端为0 子串子串.基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法13车辆调

16、度问题中遗传算法的设计：基于遗传算法的物流配14车辆调度问题中遗传算法的设计：车辆调度问题中遗传算法的设计：v6 变异算子变异算子:v对对2 交换变异算子交换变异算子,在染色体中任在染色体中任意确定两个非零基因意确定两个非零基因,交换其位置交换其位置,就得到就得到1 条新染色体条新染色体.以此类推。以此类推。基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法14车辆调度问题中遗传算法的设计：基于遗传算法的物流配15车辆调度问题中遗传算法的设计：车辆调度问题中遗传算法的设计：v6 变异算子变异算子:v遗传算法设计最后一步是确定控制遗传算法设计最后一步是确定控制参数和算法终止条件参数和算法终止条件.推荐控制参推荐控制参数取值范围是群体规模数取值范围是群体规模n=20 50,交叉率交叉率P c=0.6 1.0,变异率变异率Pm=0 0.05.算法终止条件根据算法终止条件根据v具体情况确定具体情况确定.基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法基于遗传算法的物流配送车调度优化算法15车辆调度问题中遗传算法的设计：基于遗传算法的物流配