基于动态规划改进求解VRP问题节约法的DSM模型及其拓展分析

2010年第1期物流工程与管理第32卷总第187期LOGISTICSENGINEERINGANDMANAGEMENT【收稿日期】2009-12-15【作者简介】张艳（1972－），女，汉族，辽宁大连人，大连职业技术学院管理工程系物流管理专业教师，讲师，大连海事大学交通工程与物流学院硕士研究生，研究方向：物流优化技术，物流信息系统与管理，供应链管理。经济与管理Doi:10.3969/j.issn.1674-4993.2010.01.043VRPDSM【摘要】【关键词】【中图分类号】U111【文献标识码】B【文章编号】1674-4993（2010）01-0120-02□ZHANGYan（FacultyofManagementEngineering,DalianVocationalTechnicalCollege,Dalian116035，China）【Abstract】Inthispaper,anewalgorithmnamedDSM(DynamicprogrammingSavingMethod)issubmittedwhichimprovingtheSavingMethodofVRP.DSMcombinestheSavingMethodstandinginforheuristicapproachanddynamicprogrammingstandinginforprecisealgorithmic,andtosetupadynamicprogrammingmathematicalmodelinwhichthesavingvalueincreasedcontinually,soastofindtheglobaloptimalsolution.DSMmodelacceptsincreasedconstrainteasily;itcanaddmorefiltrateconditionswhichmakethecomputationalprocedureconvergingsmoothly.【Keywords】transportation;VRP;savingmethod;dynamicprogramming;DSM车辆路径问题（VRP）是组合优化领域中著名的NP难题。节约法作为解决VRP问题的一种有效的启发式算法，其优化过程是一个多阶段决策过程，具备动态规划问题的基本特性。通过应用动态规划思想，改进求解VRP问题的节约法，建立不断增加节约量的动态规划数学模型，使其能够得到全局最优解。该算法计算量较小，平稳收敛，且对增加约束条件的情况更易接受。1问题的提出节约法求VRP问题不能保证得到最优解。例如1个配送中心，7个用户的问题，表1给出了配送中心与用户的距离、用户之间的距离以及客户的需求量qi（单位：t），现有7台4t的车，3台6t的车。求运输里程最短的配送车辆路线优化的方案。根据节约量公式，求出用户连接的费用节约值，标注在距离右边，以逗号隔开。优化过程中，首次优化从最大节约量16开始，但次大节约量11有两个，分别对应6、7点和1、7点，在二次优化中选择不同的连接点，最终结果是不一样的：先优化6、7点，节约量43，总里程81公里；先优化1、7点，节约量44，总里程是80公里。[1]表1运输里程表及节约量节约法的优化过程是一个多阶段决策过程，每个阶段所做决策影响未来的可选决策集合，具备动态规划问题的基本特征，因此，应用动态规划改进节约法，将精确算法与启发式算法相结合，能够保证得到全局最优解。第1期张艳：基于动态规划改进求解VRP问题节约法的DSM模型及其拓展分析1212动态规划节约法（DSM）建模应用动态规划思想，将决策过程分为n个阶段，各阶段可选决策集合受模型条件约束，通过过滤，在可选决策集合中以节约量之和最大为指标函数建立动态规划的基本方程。状态转移方程中，对载重超限等不符合约束条件的点，设计为中止重计点，其下一阶段的状态转移：客户序列重起，载重量重计，节约量之和不变（即节约量的阶段指标函数为0）。①创建结点标号()ijkkSPq∑∑，其中ijS∑为节约量累计之和，kP为路线连接的客户，kq∑为客户的送货需求量之和。②阶段：配送中心为m个客户送货，问题划分为k=m-1个阶段。③状态：每个阶段的状态即当前需要送货的客户，有m个客户。但可选决策集合需要满足已连点不再连（即目的地不可包含在本地kP序列中）的条件。④状态转移方程情形一：kq∑未超载时，kP序列增加，ijS∑增加，kq∑增加。情形二：kq∑超载时，kP序列中止重计，ijS∑保持不变，kq∑重计。⑤动态规划基本方程(){}k+1k+1k+1ijkkkkSPqmaxSSSPq∑∑=+∑∑∑建立多阶段决策过程图，求解过程以图上作业法实现，本文中以表格形式表达图上作业法的计算过程，如表2所示。从最后一阶段中我们可以知道最优方案节约量最大值为44[2]。3DSM模型拓展分析城市中某些道路在不同时间段内限制某些车辆通行,为解决这类问题，需要在复杂路网的运输里程表和节约量表中有通行时间限制的路段上附以时间限制条件的标注，但这个限制条件单独不足以形成新的约束。这里需要引入一个新的参数t，这个参数从发车伊始开始跟踪记录，计算车辆到达下个用户点的时间。在这个时间参数t的动态跟踪记录中，需要考虑到不同的道路，在不同的时间段内，其畅通程度不同，需引入不同道路在不同时间段的通行通畅系数。此外，还要考虑送货车辆在用户点卸货发生的等待时间。DSM模型的节点标号新增参数∑tk，如下表示：（∑Sij∣Pk……∣∑qk∣∑tk）该参数以0为初始值，状态转移方程可表示为tk+1=tk+（sij/vkn）+ti,其中tk表示k子阶段累计时间，tk+1表示k+1子阶段累计时间，sij表示连接i,j两点的实际距离,v表示车辆的正常行驶速度，kn表示n时段该道路的畅通系数，ti表示i用户所花费的卸货时间。ti=qi/ai，其中,qi表示i用户的本次送货量,ai表示i用户卸货效率。新增的∑tk参数，使DSM模型的优化过程又增加了一个过滤条件，该条件过滤掉了超出送货时间范围的路线安排，也过滤掉了特定时间不允许通行的道路的路线安排，虽然新增参数限制，增加了每个步骤优化值的计算量，但是从总体上，减少了可能路线的数量，使DSM模型优化过程收敛更快。在DSM模型中，要增加车型使用情况跟踪，需要在用户连接点序列中增加车型跟踪记录，如某点标号（36/51,67,234/5.6），三条路线的载货量分别是5.6，3.9，4.5，增加车型跟踪记录后，表示为（36/51@6,67@4,234@6/5.6），@前面表示某路线上连接的用户点序列，@后面表示使用的车型吨位。在DSM优化过程中，用户点序列依次增加，车辆的使用情况也依次得到监控和适当安排。在DSM中，沿用了SM的优化目标，（下转第152页）表2DSM作业表152物流工程与管理第31卷在教育界，通常认为教学模式成功的一个重要标志是学生个性化学习方法的形成和自主学习能力的发展。教学模式的改变不仅是教学活动或教学手段的转变，而且是教学理念的转变。如何使学生掌握高效的学习方法并养成勤于学习的习惯，则是包括高等教育在内的各阶段教育都必须正视的问题。我们处在知识爆炸的时代。知识爆炸的一个特点是不同学科的相互渗透，人们普遍认为，必须加强课程内容的跨学科性和多学科性和提高教学方法的效果。教学改革的措施都应体现这些新的变化。大学英语教学改革在四年多的时间内完成了根深蒂固的教学方法的转变，取得了巨大成绩，其在教学要求、教学模式、课程设置、教学评估等方面均针对以往教学方式提出新思路。然而，在教学内容方面，改革却并未走得很远。英国教育学家科德提出：外语教学必须以学生为中心。他主张外语教学“不能令学生去适应教师和教材,而应让教师和教材去适应学生”。实际上，让教师去适应学生并不困难，问题是，教师拿什么去适应学生，怎样去适应？这涉及到我们目前的教材是否合理，教材是否能满足学生的语言应用需要。现有的教材不论在内容上还是体例上都是应试教育的产物，文章内容和课后习题在知识性、时代性、引导性等方面都有较大欠缺。教材的改革实际上直接涉及教学方法的改革。要突出写作能力和交流能力，必然要在教材的章节安排上考虑纳入英文写作规范、商务英语、办公口语等内容，而不能一成不变、千篇一律，每一章所要达到的教学目标都是相同的。通过这样设置，大学英语教材既有需要深度分析的范文，也包括介绍写作、会话技巧等的“专业”内容，更具可读性与知识性。大学英语是以英语语言知识与应用技能、学习策略和跨文化交际为主要内容的学科。通过大学英语，学生不仅仅是学习对第二语言的听说读写译方面的综合能力，更应在大量阅读英文资料的基础上，去了解世界文化的多样性与特殊性。然而，就目前来看，尽管在课堂上已经实现了教学互动，但在课后，学生对大学英语的学习仅限于教材或自学软件的范围。这大大限制住了学生的视野。因此，如果能将目前的教学互动改为学生主动，使学生改变课前或课堂抱佛脚的学习习惯，通过课后自己准备大量素材，可以从根本上使大学英语摆脱单纯工具性的尴尬，让学生在学习语言的同时获得更多知识。除了教材内容须进一步改革外，大学英语教学改革还有其他一些未触及的问题。例如，传统的大学英语教学以讲解课文为主，在英语能力培养上仅关注阅读能力的培养，从而使学生的写作能力和翻译能力长期得不到锻炼。这一方面是由于应试教育左右了教学方式，即阅读在考试中所占比重大，而写作通常可以借助万能作文，翻译类的题目则更少出现。另一方面，由于语言学和翻译学研究在中国的起步时间比较晚，相关专业的学习和研究需要长期的积累，很多教师无法在短期内传授给学生实用的写作和翻译技巧。而国外有关写作与翻译的理论目前仍无法应用到实际写作和翻译中。4结语2005年，中国社会调查所在北京、上海等八个城市进行了关于全国英语培训市场的调查研究，其中93.6%的被访者认为,应用英语是今后英语培训的趋势。八成以上的被访者认为，如果企业对员工有英语要求时，会非常看重具有口语交流能力和读写能力的实用性人才。从被访者个人选择英语培训机构的目的来看,多数被访者是为了提高英语运用能力,加强自身竞争力,这与个人的发展有着密切的关系。从企业对人才的需求来说,越来越多的企业更看中人才的英语口语交流能力,而非一纸证书。这反映了“高校本身对市场需求反应比较迟钝”,也反映了大学生对现在的大学英语课程表现出不满。高等教育的规模的扩大及培养目标的转化对高等学校的课程内容和教学方法提出了更高的要求。高校是知识的生产地，没有高校的创新就不会有社会的进步。因此，高校课程的内容和教学方法必须能够及时反映社会的需求。随着中国改革开发的进程加快，在经济全球化的影响下，英语作为一种国际语言越来越显示出它的重要性，然而，对于大多数高校毕业生而言，大学英语教学对其英语能力的提高所发挥的作用有限。尽管存在着局限，但大学英语教学毕竟在高等教育发展的大背景下迈出了第一步改革。随着改革的逐步深入，其必将更好地与高等教育的目标和任务相衔接。（上接第121页）即节约量最大，运输里程最短。如果实际运营中，以成本最低为优化目标，就需要在原模型中，增加成本参数∑Ck，其中Ck=cd+dijfn，Ck表示k阶段运输的变动成本，其中，cd表示司机人工成本，dij表示两点间的运输里程，fn表示第n种车型每公里成本。节点标号（∑Ck∣Pk……∣∑qk），动态转移方程∑Ck+1=Ck+1+∑Ck。当以成本最低为第一目标时，DSM的动态规划基本方程为：∑Ck+1∣Pk+2……∣∑qk+1=min﹛Cij+∑Ck∣（∑Ck∣Pk……∣∑qk）﹜[参考文献][