研究生毕业答辩物流专业PPT学习教案

《研究生毕业答辩物流专业PPT学习教案》由会员分享，可在线阅读，更多相关《研究生毕业答辩物流专业PPT学习教案（50页珍藏版）》请在装配图网上搜索。

1、会计学1研究生毕业答辩物流专业研究生毕业答辩物流专业S食品公司冷链食品公司冷链VRP优化实证研究优化实证研究多配送中心的冷链多配送中心的冷链VRP优化优化满意度约束的单配送中心冷链满意度约束的单配送中心冷链VRP优化优化相关理论基础相关理论基础绪绪 论论第1页/共50页论文重点内容：建立模型时间和品质满意度货损和能源成本模型求解单亲遗传算法局部精英选择策略实证分析满意度约束多配送中心对比实验第2页/共50页S食品公司冷链食品公司冷链VRP优化实证研究优化实证研究多配送中心的冷链多配送中心的冷链VRP优化优化满意度约束的单配送中心冷链满意度约束的单配送中心冷链VRP优化优化相关理论基础相关理论基

2、础绪绪 论论第3页/共50页国外研究国内研究 冷链物流 冷链VRP互联网+政策文件理论意义现实意义模型及算法文献研究法定性与定量理论与实证背景意义研究现状内容方法第4页/共50页S食品公司冷链食品公司冷链VRP优化实证研究优化实证研究多配送中心的冷链多配送中心的冷链VRP优化优化满意度约束的单配送中心冷链满意度约束的单配送中心冷链VRP优化优化相关理论基础相关理论基础绪绪 论论第5页/共50页图2-1 冷链物流适用范围第6页/共50页特特点点全程全程冷链冷链生鲜生鲜易腐易腐经济性经济性时效性时效性时效性时效性高货损高货损比例比例冷链物流公司特点设施设备特点产品特点制冷机组按动力来源分类：独立与

3、非独立制冷机组工作原理：物理循环第7页/共50页2.2 车辆路径问题VRP概念概念：VRP（Vehicle Routing Problem）是指已知配送中心的位置和承运能力及客户需求量，给定车辆配送规则，选择某种指标(距离最短、成本最低等)为优化目标，在满足一定约束条件下(如时间、最少服务数、车辆载重限制等)，合理规划配送车辆数目和行驶路线，使配送方案达到最优。 图2-2 VRP示意图第8页/共50页序号序号分类标准分类标准VRP类型类型1按配送中心数目单配送中心；多配送中心2按配送任务特征纯装货；纯卸货；取送一体化3按车辆载货状况满载型；非满载型4按车辆类型单车型；多车型5按客户对货物取送时

4、间要求无时间窗限制；硬时间窗限制、软时间窗限制、混合时间窗6按客户需求类型需求确定型；随机需求、模糊需求7按需求是否可分可切分的VRP；不可切分的VRP8按优化目标单目标问题；多目标问题9按车辆归属开放型(不必返回其出发配送中心)封闭型(必须返回其出发配送中心)10按两地之间往返距离对称网络；非对称网络VRP的常见分类第9页/共50页图2-3 VRP求解算法第10页/共50页aERTKAe 常用形式为：K反应的速率常数； A 阿伦尼乌斯常数或前因子； Ea反应活化能(J 或kJ )，温度变化不大时为常数； T 绝对温标下的温度(开尔文 )。 R气体常数8.314(kJ/molK)图2-4 阿伦

5、尼乌斯K-T曲线曲线曲线显示，K是T的增函数，且T在e的指数项中，说明反应速率随温度升高而快速增加，并无限接近最大值A。该图显示了反应速率常数与温度之间的关系反应速率常数与温度之间的关系。 推导变质率(2-1)第11页/共50页S食品公司冷链食品公司冷链VRP优化实证研究优化实证研究多配送中心的冷链多配送中心的冷链VRP优化优化满意度约束的单配送中心冷链满意度约束的单配送中心冷链VRP优化优化相关理论基础相关理论基础绪绪 论论单亲遗传算法设计冷链VRP模型建立第12页/共50页目标：综合成本最低、满意度不低于给定水平满意度分析：时间、品质货损成本能源成本运输、调度、时间成本已知：配送中心及车辆

6、、服务时间窗、顾客分布和需求、车速、顾客之间及与配送中心之间的最短距离；约束：每个顾客均被服务一次、车辆返回配送中心等；求解：综合成本最小的车辆路径方案。问题描述：主要内容第13页/共50页图3-2 软时间窗示意图图3-1 硬时间窗示意图图3-3 混合时间窗示意图硬时间窗：配送服务需严格遵循时间窗约定软时间窗：不必严格按时间窗，可早到或晚到混合时间窗：软时间窗和硬时间窗的结合P(t)是关于t的惩罚函数，M为很大的惩罚值 第14页/共50页1111NjjffN10() ()1() ()0iiddiiiiiiiddjiiiddiiiiiiiiiTtEttEtEtEtEttEtfEttLtLttLt

7、LtLttLtTtLtMDVRPTW模中，顾客时间满意度可表示为：图3-4 混合时间窗下的顾客满意度期望接受服务时间最大忍受等待/迟到时间不可接受服务时间(3-1)(3-2)第15页/共50页阿伦尼乌斯方程变质率lqm品质满意度max0100%1 expexp 100%aiiiEQlqmktQRT变换可得：aERTKAe1100%iiitlqme则：maxexp1100%aiiiEktRTlqme令其为令其为(3-3)(3-4)Psi第16页/共50页运输过程(t0t1)卸货过程(t1t2)货损量：1 11(0)1(0)tjjlqmWeW2max2expaEkRT21()21100%jttlq

8、met1秒末：1 11 111( )(0)(0)(0)1(0)(0)jjjtjjtjW tWlqmWWeWeW211 121()( )1(0)jjtttjlqmW teeW211 11 1211 1121()()(0)( )1(0)1(0)1(0)jjjjttttjjtttjlqmWlqmW teWeeWeW总货损量:21211HHjjjNtttjfeN品质满意度:(3-5)开门后处理时间开门前运输和等待时间第17页/共50页211 122112111HHjjjNNtttjjjffffeN综合考虑时间和品质因素对满意度的影响程度对其赋予适当的权值，得到顾客满意度函数f：根据以上推导过程也可得货

9、损成本DC：2111HHjijNtttiiDCpeq第18页/共50页011NKDWei kjjikECcxtt能源成本油耗、设备折旧、其他意外花费运输过程为保持车厢内适宜温度，制冷机组开启，产生能耗成本。卸货过程由冷藏车运输操作规范可知，卸货过程制冷机组需关闭，不计能耗。最终能耗成本可用以下公式表示：第19页/共50页2101001111201111minmax,0max,01+HHjijNNKNKNcijkijfjkiiijkjkiNNNKtttDWiiiei kjjiiikZpx dpxcEttctLtpeqcxtt目标函数：约束条件：1110,0,1,0,1,.,0,1,.,1,1,2

10、,.,1,2,.,NiikiKNijkkjNijkjkiijNijkikjijKikkq yQxKixyjNkxyiNkyiNkK11NKikikyNmax,0,1,2,.,;hjiiiiijttEtttdvi jNij,1,2,.,iiiEttLtiN,1,2,.,DWHijjjtttti jN,f运输、车辆调度、等待、迟到、货损、能源成本之和。载重限制、车辆数限制、前后续节点唯一、每个顾客均被服务且仅一次、时间约束、满意度约束。第20页/共50页GA求解组合优化问题优点：通用的编码技术、简单有效的遗传操作、全局搜索能力。缺点：对复杂问题搜索效率低、易陷入“早熟收敛”、交叉算子对本文染色体具

11、有很强的破环性。PGA优势：突破了双亲繁殖方式，基因个体内部完成自身进化；不再采用交叉算子且初始群体不必具有多样性；避免陷入“早熟收敛”，提高了求解效率；PGA对初始解质量的较低要求降低了其生成难度。简称：遗传算法 (Genetic Algorithm, GA)传统遗传算法 (Traditional Genetic Algorithm, TGA)单亲遗传算法 (Partheno Genetic Algorithm, PGA)第21页/共50页自然数编码配送中心编码为 0 ；顾客编码为 1,2,N ；车辆编码为 1,2,K 。车辆均从配送中心出发，完成任务后返回而形成多条闭合回路。例如，染色体编

12、码：“0-3-5-6-0-1-2-4-0”解码后：路径1 03560 （车辆1）路径2 01240 （车辆2）第22页/共50页车辆初始化路径初始化11NiiqkceilQceil向上取整；表示装卸货物的复杂程度，01，情况越复杂，越小，每辆车装载货物越少，需要的车辆越多。Step 1 随机分配客户访问顺序；Step 2 随机选k-1个点做断点位置；Step 3 按断点位置将编码0插入客户访问顺序，形成各个子路径。例如：顾客顺序断点位置初始化结果1-2-4-3-5-8-62-50-1-2-0-4-3-5-0-8-6-0满足约束：车辆限制、节点唯一性、服务要求(3-5)第23页/共50页mini

13、iZfZ适应度适应度：用以评价路径方案的优劣，代表遗传个体生存能力的大小。适应度越大目标值越小。表示为：满足约束：违背载重约束时，给予Zi 很大的惩罚值；违背时间及满意度约束的个体，在目标函数成本计算时进行适当惩罚，使其在进化过程中被逐渐淘汰。局部精英保留策略局部精英保留策略：1.将种群随机分为若干组，每组八个成员构成一个局部区域；2.精英选择，将局部最优个体直接保留到下一代；3.对每个局部区域的最优个体进行七种不同的单亲遗传操作，产生的子代与父代个体形成下一代种群。这样每代的最优个体均优于上代种群，且种群规模保持不变。步骤第24页/共50页代表子路径的基因段作为遗传操作的基本单位交叉算子变异

14、算子概率融合：优化车辆数染色体：第25页/共50页算算法法流流程程图图1. 染色体编码；2. 初始化种群；3. 解码并计算个体适应度；4. 局部精英选择；5. 单亲遗传操作；6. 判断是否满足终止条件。单亲遗传算法步骤第26页/共50页S食品公司冷链食品公司冷链VRP优化实证研究优化实证研究多配送中心的冷链多配送中心的冷链VRP优化优化满意度约束的单配送中心冷链满意度约束的单配送中心冷链VRP优化优化相关理论基础相关理论基础绪绪 论论对比遗传算法设计MDVRP模型建立第27页/共50页已知：多个配送中心多个配送中心、车辆载重、服务时间窗、顾客分布和需求、车速、顾客之间及与配送中心之间的最短距离

15、；约束：车辆不超载、不共享且不从系统外租赁、满意度约束满意度约束等；目标：综合成本综合成本最小的车辆路径方案。问题描述：模型建立多配送中心转换单亲遗传设计对比算法设计主要内容图4-1 多配送中心VRP示意图第28页/共50页21()1111111112()11111minmax,0max,01+mmmHHiiiKKMN M N MMNNmkmkcijijfN m jiimijkmjkiKNNMNtttmkDWiiiei N miiiimkiZpxdpxcEttctLtpeqcxtt 目标函数：约束条件：运输、车辆调度、等待、迟到、货损、能源成本之和。载重限制、车辆数限制、前后续节点唯一、每个顾

16、客均被服务且仅一次、时间约束、满意度约束。11,1,2,.,;NN MmkiijmijqxQkKm 11,1,2,.,;KNmkijkjkxmiNNNMm111,1,.,;1,2,.,;NNmkmkmijjijjxxiNNM kKm1111,1,2,.,mKMN MmkijmikxjN 1111,1,2,.,mKMN MmkijmjkxiN 1111mKNMN MmkijimjkxN 110,1,.,;1,2,.,;N MN Mmkmkijjii Ni NmxxjNNMkKm1,2,.,iiiEttLtiNDWHijjjttttf第29页/共50页图4-3 几何重心分区法Step 1 绘制散点

17、图，求配送中心的几何重心；Step 2 以重心为起点，过相邻两个配送中心的中点做射线，相邻两条射线围成的区域作为一个分区；Step 3 确定顾客所在分区，分布在射线方程上的客户随机分配到两侧分区。具体步骤：几何重心分区法几何重心分区法在大规模VRP问题中不仅能够有效求解顾客在配送中心的分配方案，而且大大减少了运算量。第30页/共50页模型的解需要体现的要素：客户需求在配送中心的分配车辆调度数车辆路径染色体结构为：配送中心编码+断点位置+依次服务的客户编码+配送中心编码+。如，一条染色体：1 |5 | 2-4-12-5-9-1-6-7-12 | 2 | 3 | 10-8-11-3-14-13，解

18、码后：路径路径出发的配出发的配送中心送中心车辆编号车辆编号服务客户及顺服务客户及顺序序路径路径1112-4-12-5-9路径路径2121-6-7-12路径路径32110-8-11路径路径4223-14-13表4-1 单亲解码结果单亲遗传第31页/共50页模型的解需要体现的要素：客户需求在配送中心的分配车辆调度数车辆路径染色体结构为：虚拟配送中心+实际配送中心+车辆编号+顾客服务次序+虚拟配送中心。如，一条染色体： 0-1-1-2-3-6-9 0-1-2-1-4-8 0-2-1-5-11-7-10-0，解码后：表4-2 自适应解码结果自适应遗传路径路径起点起点实际出实际出发的配发的配送中心送中心

19、车辆编车辆编号号客户及其客户及其服务顺序服务顺序实际返回实际返回的配送中的配送中心心终点终点路径路径10112-3-6-910路径路径20121-4-810路径路径30215-11-7-1020第32页/共50页1.重心分区，确定顾客所属配送中心；2.初始化每个配送中心的车辆数km；3.随机分配顾客访问顺序；4.随机选取km-1个断点位置；5.每个配送中心的顾客访问顺序与km-1个断点位置形成M *km个子路径。单亲遗传并且，子路径顺序与车辆编码相同。11NiiqkceilQ例如：配送中心1顾客顺序断点位置子路径1-2-4-3-5-8-62-51-2,4-3-5,8-6第33页/共50页自适应

20、遗传1.确定虚拟配送中心虚拟配送中心所有配送中心的重心；2.建立极坐标系极坐标系。以虚拟配送中心为极点，以虚拟配送中心与任一客户的连线为极轴；3.利用逆时针扫描法逆时针扫描法进行客户分群客户分群；4.利用C-W节约算法对每个顾客群进行优化优化，形成一条以虚拟配送中心为起点和终点的路径；5.计算每条路径中首末客户与各配送中心的距离，将最近的配送中心配送中心插入插入到首末顾客与虚拟配送中心之间，形成一条完整的路径；6. 将实际配送中心可调度车辆车辆编号插入插入到每条染色体；7.将极轴偏移一个角度，重复步骤(3)-(6)，直至产生产生N/2(设N为种群种群规模)条染色体；8.为保持种群多样性，采用顺

21、时针扫描法对客户进行分群，重复步骤(4)-(6)，直至产生N/2条染色体34670-671。34 刘家利, 马祖军. 存在车辆租赁及共享且有时间窗的多配送中心开环VRPJ. 系统工程理论与实践, 2013(3): 666-675.虚拟配送中心第34页/共50页自适应遗传与第三章类似单亲遗传选择算子参考文献34变异算子交叉算子1.舍弃不满足约束条件的染色体；2.直接保留大于平均适应度的个体 (L条)；3.对所有染色体执行遗传操作，轮盘赌法轮盘赌法选取N-L条染色体，形成L个下代种群。121max1()(),ccavgcavgavgccavgppffpffffppff121max1()(),mma

22、vgmavgavgmmavgppffpffffppff只针对客户编码部分匹配交叉客户编码，如E,B交叉；车辆-车辆 A,F /车辆-配送中心A,E/配送中心-配送中心B,E不交叉，否则增加车辆调拨或行驶成本；车辆-客户A,D /配送中心-客户B,D在客户编码染色体中，交叉点后按最短距离原则插入“0+实际配送中心+车辆编码”。交叉匹配区域对应情形：第35页/共50页S食品公司冷链食品公司冷链VRP优化实证研究优化实证研究多配送中心的冷链多配送中心的冷链VRP优化优化满意度约束的单配送中心冷链满意度约束的单配送中心冷链VRP优化优化相关理论基础相关理论基础绪绪 论论第36页/共50页S公司某日的配

23、送业务中涉及30个客户，有3个配送中心可供调度，分别用D1、D2、D3表示，配送中心及顾客的位置散点图如下：配送中心和顾客详细信息见论文5.1第37页/共50页表5-2 客户信息配送中心配送中心坐标坐标/km拥有冷藏车拥有冷藏车/辆辆发车时间发车时间/时时D1(117.17, 31.52)204D2(106.16, 38.27)164D3(108.19, 22.48)134表5-1 配送中心相关信息客户编号客户编号需求量需求量/t卸货时间卸货时间/min坐标坐标/km时间窗时间窗Et, Lt; Etd,Ltd10.510(119.18,26.05)5,10;6,821.224(103.51,3

24、6.04)7,10;8,930.36(113.14,23.08)7.5,11;8,9表5-2 顾客相关信息模型相关参数：Pf=300元/辆，Q=6t，V=60km/h，Pc=4元/kmh；C1=100元/h，C2=400元/h；Ce=50元/h，P=2 000元/t；T1=-15+273.15，T2=-10+273.15，Kmax =51014/s，Ea=100 kJ/mol，R=8.314 J/molK；=0.6，1= 2=0.5。第38页/共50页配置算法参数：=0.5，初始车辆数为11。pop_size = 400，num_iter = 400，merging_prob = 0.4，超载

25、惩罚系数为 1 000，满意度惩罚系数为10。图5-2 单配送中心冷链VRP结果图从图5-2可以直观地看出，本节算法得出了较为满意的配送路径结果。满意度约束的单配送中心冷链VRP算法总运行时间为278.84s，最优解首次出现代数为180代，平均满意度0.70。第39页/共50页图图5-3显示：显示：本节算法在求解运行过程中收敛速度较快收敛速度较快。图图5-4显示显示：满意度最终并非最优而是趋于较优水平较优水平。意味着物流配送过程中可以牺牲一定一定成本来提高满意度；满意度总体趋势为先升高后降低先升高后降低。表明在优化过程中，前期前期成本的降低伴随着满意度的提高，而后期后期成本的降低则需要牺牲一定

26、的满意度，揭示了企业在实际的冷链运输过程中不能一味不能一味追求低成本而忽略用户满意度追求低成本而忽略用户满意度。图5-4 冷链VRP满意度曲线第40页/共50页图5-5可以看出：运输成本运输成本仍是主要配送成本；货损和能源货损和能源成本占总成本的1/3左右，体现了冷链物流运输品货损大、能耗高的特性特性，同时也表明两者不可忽略不可忽略；货损货损比例高达20%，建议企业采用多配送中心或其他方式降低货损成本。图5-5 成本分布图第41页/共50页重心分区法图5-6 多送中心转换结果图多配送中心转换A区C区B区第42页/共50页Pc1= 0.8, Pc2= 0.4, Pm1= 0.2, Pm2= 0.

27、05图5-10 自适应遗传算法结果图图5-7 多配送中心VRP结果图第43页/共50页多配送中心VRP满意度曲线多配送中心VRP收敛图单亲遗传自适应遗传第44页/共50页最优解最优解/元元运行时运行时间间/s最优解出最优解出现代数现代数平均满意平均满意度度满意度方满意度方差差精英单亲精英单亲遗传遗传15 462.7662.42730.720.037 9自适应遗自适应遗传传16 571.13145.052120.730.040 9表5-9 算法性能对比上图及下表显示上图及下表显示：针对本文模型设计的精英单亲遗传算法得到的成本较优成本较优，运行时间较短运行时间较短，收敛速度较快收敛速度较快，虽然满

28、意度稍低，但结果更加稳定更加稳定。此外，从单配送中心和多配送中心优化结果来看，多配送中心协同配送协同配送的综合成本较低成本较低，建议企业面对大规模配送问题时采用协同配送模式。第45页/共50页图图5-13可以看出可以看出：当问题复杂性相对较低时，两者结果相同或相近，随着问题复杂性的升高，单亲遗传的优点越来越明显。图5-13 成本对比图第46页/共50页1 1建立更加符合冷链物流特性的VRP模型。货损和能源成本、满意度约束、混合时间窗、多配送中心VRP问题。2 2设计精英单亲遗传算法有效求解优化模型。局部精英选择策略和七种单亲遗传操作。3 34 4与自适应遗传算法相比，精英单亲遗传算法在求解本文多配送中心冷链VRP问题上具有一定的优越性。模型和算法结果直观反映了满意度在成本优化过程中的变化趋势。第47页/共50页建立了基于时间和品质满意度约束的冷链物流VRP优化模型。提出了局部精英选择策略的单亲遗传算法。实际配送过程中VRP问题涉及的影响因素众多，本文模型依然具有较较大的局限性大的局限性。本文设计的算法虽然具有可行性、有效性和一定优越性，但并非最为有效的解决方法，在求解大规模VRP时依然体现了一定的不稳定性一定的不稳定性。不足：第48页/共50页The End.Thanks for Your Attention！第49页/共50页