遗传算法——物流分析课件.ppt
基于遗传算法的物流配送车调度优化算法,信息科学系科技研讨,2,电子商务物流配送:是指物流配送企业采用计算机网络技术和现代化的硬件设备、软件系统及先进的管理手段,针对社会需求,按用户的订货要求,进行一系列分类、编配、整理、分工、配货等理货工作,定时、定点、定量地交给没有范围限度的各类用户,满足其对商品的需求.,基于遗传算法的物流配送车调度优化算法,3,电子商务物流配送平台：将物流平台信息中心、网上银行、商家、客户和各个配送网点的通信介质集成在一起。,基于遗传算法的物流配送车调度优化算法,4,业务流程:(1)客户通过Internet 访问物流信息平台的网站,填写送货单;(2)物流信息平台认证客户身份;(3)客户通过输入银行信用卡账号和网上专用密码进行支付;(4)物流信息平台将支付信息提交网上银行;(5)网上银行返回扣款结果,网上交易结束;(6)物流信息平台中心服务器进行订单派送调度;(7)订单配送至相应配送网点,各配送网点安排运输车次与运输路线,配送货物,这是物流配送中的配送车调度问题。,基于遗传算法的物流配送车调度优化算法,5,车辆调度问题(Vehicle Routing Problem 简称VRP)：是对巡回旅行商问题(TSP,Traveling Salesman Problem)加以一定的限制而形成的,属于约束性的多重TSP 问题(CMTSP,Constrained Multiple Traveling Salesman Problem),基于遗传算法的物流配送车调度优化算法,6,约束条件：(1)所有车辆路线均起始并终止于配送中心，每一客户点只由一辆车服务，一辆车也可服务多个客户点；(2)每个客户点都有一个非负的额货物需求量，但每辆车负责的客户点的货物需求量总和不超过该车辆的最大装载辆；(3)每辆车的行车路线的总耗时不超过一个事先定下的值，以满足客户对供货时间的要求；(4)对某个客户点，车辆到达时间限制在某一时间段内。如此约束不满足，则引入惩罚函数；,基于遗传算法的物流配送车调度优化算法,7,根据上述问题描述，对车辆调度问题进行建模。设F 为最小成本，则目标函数为:其中，K 为所有车辆的集合，K=1,2,m,kK I 为所有客户的集合，I=1,2,n，iI目标函数中的Cij表示从客户i 到客户j 的费用成本。目标函数中的为P(t)为惩罚函数，当车辆不能按时到达时，引入此函数来增加车辆调度的成本。,基于遗传算法的物流配送车调度优化算法,8,该函数满足的约束条件为：其中(1)控制n 个客户由m 辆车来共同完成。(2)控制每一客户只有一辆车来完成。其中：X,基于遗传算法的物流配送车调度优化算法,9,目标函数中的Pnum(M)为车辆装容量约束，首先扫描每一客户的需求量，若这些需求量均不小于每一车辆的载重量，则所需车辆总数为Int(Sum/avge)+1，其中Sum 表示所有客户的需求量总和，avge 表示车的载重量。若扫描客户的需求量时，有超过车辆的载重量的，先看客户的需求能装满几辆车，直接从可供选择的车辆中随机挑 选几辆车去完成该客户的需求，然后把装不满一辆车的需求量作为该客户的需求量去参与基本遗传算法的运算。,基于遗传算法的物流配送车调度优化算法,10,车辆调度问题中遗传算法的设计：1 染色体编码（一般采用自然数编码）：设配送中心的序号为0，依次对各配送点编号形成染色体，该染色体表示了车辆调度，路线安排等各种信息。例如。染色体01203450 表示一条路线从配送中心出发，经过配送点1，2 后回到配送中心；另一条路线从配送中心出发，经过配送点3，4，5 回到配送中心。,基于遗传算法的物流配送车调度优化算法,11,车辆调度问题中遗传算法的设计：2 生成初始染色体种群：染色体的长度=车辆总数+客户数+13 适应度函数：由目标函数 f k=Zm in/Z k转化得到:f k是染色体k 的适应度函数,Zm in 是同代群体中最佳染色体的费用,Z k 是染色体k 的费用.适应度最大染色体对应配送成本最低调度方案.,基于遗传算法的物流配送车调度优化算法,12,车辆调度问题中遗传算法的设计：4 复制算子:给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,车辆调度问题中遗传算法的设计：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 子串.,基于遗传算法的物流配送车调度优化算法,14,车辆调度问题中遗传算法的设计：6 变异算子:对2 交换变异算子,在染色体中任意确定两个非零基因,交换其位置,就得到1 条新染色体.以此类推。,基于遗传算法的物流配送车调度优化算法,15,车辆调度问题中遗传算法的设计：6 变异算子:遗传算法设计最后一步是确定控制参数和算法终止条件.推荐控制参数取值范围是群体规模n=20 50,交叉率P c=0.6 1.0,变异率Pm=0 0.05.算法终止条件根据具体情况确定.,基于遗传算法的物流配送车调度优化算法,
