新加坡留学项目SM2面试指导汇总

下午8时5分1/23来源于生物界的蚁群算法在车辆路径问题（VRP）中的应用学号：姓名：指导教师：下午8时5分2/231…VRP的问题来源和研究现状论文要点：2…蚁群算法及其在VRP中的具体应用3…VRP程序设计和求解分析来源于生物界的蚁群算法在车辆路径问题（VRP）中的应用下午8时5分3/231…VRP的问题来源和研究现状物流（Logistics）1…物资的流通：来源于二战时期军队的后勤保障系统2…现代企业的第三利润来源：营运成本与价格竞争力的强弱3…电子商务全面改变经济活动：物流管理成为经济发展的重要课题下午8时5分4/23通常意义下的VRP的提法为：已知一批客户，每个客户点的位置和货物需求已知，车辆的负载能力一定，每辆车都从起点(depot)出发，完成若干客户点的运送任务后再回到起点.假设每个客户被而且只被访问一次，每辆车所访问的城市的需求总和不能超过车辆的负载能力.问题是使所有客户需求都得到满足，且总旅行成本最小.1…VRP的问题来源和研究现状车辆路径问题（VehicleRoutingProblem，简记VRP）是物流配送优化中关键的一环1.提高物流经济效益、实现物流科学化2.是管理科学的一个重要研究课题3.其优化技术是现代物流配送的一项关键技术.下午8时5分5/23VRP已经被证明是NP—hard问题目前提出的求解算法很多下午8时5分6/231…VRP的问题来源和研究现状求解方法（Solution）精确算法（ExactAlgorithm）1.动态规划方法;2.割平面法;3.网络流算法;4.分支定界法构造启发式算法（StructuralHeuristicAlgorithm）1.扫描法;2.节约算法;3.最邻近法;4.最近插入法智能启发式算法（IntelligentHeuristicsAlgorithm）1.遗传算法;2.模拟退火法;3.禁忌搜索算法;4.蚁群算法;5.微粒群算法;6.神经网络算法下午8时5分7/232…蚁群算法及其在VRP中的具体应用蚁群算法与VRP蚁群觅食，会选择一条从蚁穴到食物源的最短路径.下午8时5分8/232…蚁群算法及其在VRP中的具体应用蚂蚁选择最短路径的原理：信息素信息素浓度越高蚂蚁越容易选择经过时间越长信息素挥发越多蚂蚁选择较短路径ijijmijijijinf(m)sub(m)Prand(m)inf(m)sub(m)下午8时5分9/232…蚁群算法及其在VRP中的具体应用ijijmijijijinf(m)sub(m)Prand(m)inf(m)sub(m)代表路径上的信息素浓度对选择概率的影响，信息素浓度越高，选择该路径的机率就越大.故实际上就是蚁群的正反馈机制.ijinf(m)吃午饭了，去一食堂还是二食堂呢？大家都去一食堂吃饭，我也去一食堂吧！代表路径上的启发因子，，为路径间的距离，即距离越小选择该路径的机率就越大.故启发因子实际代表蚂蚁的能见度.ijsub(m)ijij1sub(m)tijt要吃午饭了，去一食堂还是二食堂呢？二食堂比较近，去二食堂吧。rand(m)为随机因子，即在选择路径时给与蚂蚁适当扰动.要吃午饭了，今天到底是去一食堂还是二食堂呢？随便选一个吧。下午8时5分10/232…蚁群算法及其在VRP中的具体应用ijijmijijijinf(m)sub(m)Prand(m)inf(m)sub(m)对于蚁群算法中的等相关参数α、β、γ的选择，目前还没有成熟的理论可供参考，一般只能通过实验进行选择.信息素挥发：本文中，信息素更新策略采用最大-最小蚂蚁系统MMAS算法，因为经大量学者实验验证，这种更新机制有较好的效果.下午8时5分11/233…VRP程序设计和求解分析本文求解VRP主要采取蚁群优化2阶段构造算法（AntConstructiveAlgorithm）即：第1阶段，根据蚁群优化准则，每次将一个不在线路上的点增加进线路，直到所有的点都被安排进线路为止；第2阶段，将得到的可行解进行2-OPT变换优化。下午8时5分12/233…VRP程序设计和求解分析第1阶段，根据蚁群优化准则，每次将一个不在线路上的点增加进线路，直到所有的点都被安排进线路为止；下午8时5分13/233…VRP程序设计和求解分析从当前点出发，根据选择概率选择下一个点即在选择时，计算当前点到所有可选点的选择概率，加以比较，并选择概率最大的点。下午8时5分14/233…VRP程序设计和求解分析第2阶段，将得到的可行解进行2-OPT变换优化。2-opt原理下午8时5分15/233…VRP程序设计和求解分析以上为程序设计原理，具体程序流程如下：BEGINDO{FOR(i=0;i最大蚂蚁组数;i++){FOR(j=0,reach=1;reach最大节点数;j++)//j为蚂蚁数{初始化一只蚂蚁，即将一只蚂蚁放到起点;WHILE(蚂蚁没有达到最大载重量且仍然有节点未经访问){蚂蚁按照选择概率公式（1）选择下一节点;reach++；//reach代表已经访问的节点数}reach--;}ant_n[i]=j;将这组蚂蚁的蚂蚁数记录下来nextant;转到下一组蚂蚁}FOR(i=0;i最大蚂蚁组数;i++)FOR(j=0;j本组蚂蚁数;j++)对每一只蚂蚁进行2-opt交换；比较得到的解选择本次循环得到的最好蚂蚁，将其与全局最好解进行比较.按照全局最优解根据公式（2）更新信息素nc++;}WHILE(ncNC);迭代结束，输出最优解下午8时5分16/233…VRP程序设计和求解分析程序流程图BEGINEND蚂蚁按照选择概率公式选择下一节点2-OPT优化信息素更新下午8时5分17/233…VRP程序设计和求解分析为了检验算法的结果，求解实例全部采用osiris.tuwien.ac.at网络公布的CVRP测试问题，下载网址为：~wgarn/VehicleRouting/neo/Problem%20Instances/CVRPinstances.html各实例验证结果如下：VRP实例已知最优解本文程序运行结果偏离程度总行程（COST）车辆数总行程（COST）车辆数A-n33-k56615700.14855.92%A-n38-k57305796.59859.12%A-n54-k7116771268.3378.68%B-n34-k57885834.60355.91%A-n37-k694961104.39616.37%B-n50-k77417895.556720.85%下午8时5分18/233…VRP程序设计和求解分析实例：A-n33-k50.75实验时，取迭代次数为20次，选择概率权重为信息素挥发1.755迭代次数12345路径长度792.5831.036813.547730.671795.566与最优解的差131.5170.036152.54769.671134.566迭代次数678910路径长度778.556738.302732.822720.824714.067与最优解的差117.55677.30271.82259.82453.067迭代次数1112131415路径长度738.302738.302738.148750.682780.854与最优解的差77.30277.30277.14889.682119.854迭代次数1617181920路径长度761.337721.642738.302700.148745.092与最优解的差100.33760.64277.30239.14884.092下午8时5分19/233…VRP程序设计和求解分析将表格数据画图得：下午8时5分20/233…VRP程序设计和求解分析得到的A-n33-k5具体运输路线下午8时5分21/23谢谢观赏结束下午8时5分22/23下午8时5分23/23◆分支定界法（BranchandBoundApproach）[6]分支定界法是一种应用范围很广的搜索算法，它的基本思想是把给定问题分解为若干个较小的子问题，每个子问题又可继续分解，直到子问题不能再分解或不能产生最优解.根据问题的特点和不同的策略，把问题分解为子问题的过程称之为分支.分支定界法求解VRP问题的基本思想是，以相应的不含整数约束的VRP问题(B)的最优解为出发点，若此解是整数解，那么这个解就是原VRP问题(A)的最优解，否则以B的非整数解的相邻整数作附加条件，形成2个分支，即2个子问题，进行求解.若对上面2个子问题求出最优解是整数解，则停止该子问题的分支，否则继续分支求解.这种方法只能适用于求解小型VRP问题.Kolenatal曾利用此方法求解含时间窗约束的车辆巡回问题，发现当节点数扩大至12时，计算机有内存不足的现象产生.下午8时5分24/23•◆割平面法（CuttingPlanesApproach）[6]•割平面法求解VRP问题(A)的基本思想是，在求解相应的不含整数约束的VRP问题(B)上，增加线性约束条件(几何术语称为割平面)，以将B的可行域切割掉一部分，使其切割掉的部分只包含非整数解，没有切割掉任何整数可行解，直到切割后得到的可行域有一个整数坐标的极点恰好是A的最优解为止.由于割平面法求解时间过长，故不适用于大规模问题.下午8时5分25/23•◆网络流算法（NetworkFlowApproach）[6]•网络流算法求解VRP问题的基本思想是，首先构建VRP问题的网络模型，找到网络中需调量最大的弧，然后通过调节弧流量或弧两端节点上的位势，来减少弧上的需调量，直至所有弧的需调量都等于零.由于网络模型的顶点数目和边的数目会显著影响网络流算法时间效率，所以这种算法只适用于小规模的VRP问题.下午8时5分26/23•◆动态规划方法（DynamicProgrammingApproach）[6]•动态规划法求解VRP问题的基本思路是，将VRP问题视为一个阶段的决策问题，进而将其转化为依次求解具有递推关系的单阶段的决策问题，从而简化计算过程.用这种方法可求得VRP的最优解，但仅适用于较小规模的寻优问题.•此外，Fisher(1985)、Jomstern(1986)、Madsen(1990)、Halse(1992)等人分别用不同的拉格朗日分解法求解VRP问题.Desrochers等人在1992年利用列生成方法求解VRP问题.Fisher(1994)又提出利用K-树方法求解VRP问题.下午8时5分27/23下午8时5分28/23下午8时5分29/23下午8时5分30/23下午8时5分31/23下午8时5分32/23