乘用车物流运输计划模型及融合启发式的智能算法求解-2015研究生数学建模竞赛二等奖.docxVIP

参赛密码 （由组委会填写） 全 第十一届华为杯全国研究生数学建模竞赛 学 校 参赛队号 队员姓名 30 - 第十一届华为杯全国研究生数学建模竞赛 题 目 乘用车物流运输计划模型及融合启发式的智能算法求解 摘 要 本文对乘用车物流运输计划问题进行了研究，建立了问题的整数线性规划模型，并利用CPLEX求解器实现了模型求解。考虑到问题具有NP-hard特性，设计了融合启发式的智能算法来提高求解效率。 对问题1-3，首先将问题归纳为乘用车运输任务的轿运车选择和轿运车的装载两个子问题。建立了通用的整数线性规划模型，该模型通过CPLEX求解器可得到问题的最优解。设计了一种融合启发式规则和离散人工蜂群算法的智能算法，分别对两个层面的子问题进行求解。 对于轿运车选择这个子问题，通过离散人工蜂群算法进行求解；对于轿运车装载这个子问题，通过两种启发式规则来解决。第一种启发式规则以装箱问题的FFD方法为基础，通过加入整车优先机制改进而成；第二种启发式方法基于保证局部最优的思想设计而成，通过建立每种轿运车的装载方案优先级列表，按照优先级顺序依次选择装载组合。 最后，对于原题的三个问题，通过CPLEX和离散人工蜂群算法均获得了最优解， 1-1型和1-2型轿运车的配比方案依次为（16:2）、（12:1）、（25:5）。同时，对于随机生成的10组运输任务，离散人工蜂群算法均获得了和CPLEX相同的最优解，验证了算法和启发式规则的有效性和普适性。 对问题4，建立问题的整数线性规划模型，该模型可通过CPLEX求解器得到问题的最优解及相应装载方案。设计了一种融合启发式的邻域有哪些信誉好的足球投注网站算法进行求解，其中通过设计的“长途稍货”启发式规则得到初始解，再利用邻域有哪些信誉好的足球投注网站调整不同目的地的1-1型、1-2型轿运车配比，对初始解进行局部调整，以提高解的性能。 求解方面，CPLEX和邻域有哪些信誉好的足球投注网站算法均求得了问题的最优解，1-1型和1-2型轿运车的配比方案为（21:4），运输距离（成本）为6404。实验表明，该算法能在较短时间内获得问题的最优解或近优解。 对问题5，设计了一个三层结构的整数线性规划模型，在第一层首先确定针对当前任务所需的最少轿运车数量；第二层以第一层的结果为输入，以最短路径为目标函数，将轿运车分给不同的目的地；第三层最终确定轿运车的装载方案。第一层模型已通过CPLEX解得任务所需的总轿运车数量为102。同时，通过聚类分析和约束满足的方法，将问题进行简化，尝试设计一个启发式规则进行求解。 关键词：乘用车物流 整数线性规划 智能算法 启发式规则 问题描述 整车物流指的是按照客户订单对整车快速配送的全过程。乘用车生产厂家根据全国客户的购车订单，向物流公司下达运输乘用车到全国各地的任务，物流公司则根据下达的任务制定运输计划并配送该批乘用车。 本问题中考虑使用三种双层轿运车：上下层各装载1列型（1-1型）、下上层分别装载1、2列型（1-2型）、上下层各装载2列型（2-2型），在一定的约束条件下，对下列五次运输任务制定相应计划，确定所需各类轿运车的数量、每辆轿运车上乘用车的装载方案和具体行车路线，使运输成本最低。 五次运输任务如下： 1、物流公司要运输Ⅰ车型的乘用车100辆及Ⅱ车型的乘用车68辆； 2、物流公司要运输Ⅱ车型的乘用车72辆及Ⅲ车型的乘用车52辆； 3、物流公司要运输Ⅰ车型的乘用车156辆、Ⅱ车型的乘用车102辆及Ⅲ车型的乘用车39辆； 4、物流公司要运输166辆Ⅰ车型的乘用车（其中目的地是A、B、C、D的 分别为42、50、33、41辆）和78辆Ⅱ车型的乘用车（其中目的地是A、C的，分别为31、47辆），具体路线见图4，各段长度：OD=160，DC=76，DA=200，DB=120，BE=104，AE=60； 5、附件的表1给出了物流公司需要运输的乘用车类型（含序号)、尺寸大小、数量和目的地，附件的表2给出可以调用的轿运车类型（含序号)、数量和装载区域大小（表里数据是下层装载区域的长和宽, 1-1型及2-2型轿运车上、下层装载区域相同；1-2型轿运车上、下层装载区域长度相同，但上层比下层宽0.8米。此外2-2型轿运车因为层高较低，上、下层均不能装载高度超过1.7米的乘用车。 模型假设 1、题中所给数据可靠无误； 2、运输过程不受非可控因素影响； 3、轿运车的装载区域和乘用车均简化为长方体，不考虑实际几何形状影响； 4、各类型轿运车运输过程中，行驶单位路程的费用认为相同，卸车成本忽略不计； 5、轿运车在运输过程中不可折返。 问题1-3建模与求解 本节根据1-3的问题特点建立了通用的整数线性规划模型，并通过CPLEX线性求