中南大学 数学建模 lingo matlab 优化建模论文 货运公司的运输问题

摘要合理安排车辆的运载方案，能够大大节省货运公司的运输费用，以便能得到更大的利润。本文通过构建数学模型，寻求车辆配置的最优方法，从而为运输公司提供明确的车辆的运载方案。问题一为不调头情况下的线性目标规划问题。模型一使用了图论里的矩阵，再使用目标规划模型建立目标函数与约束条件求出最少运输费用。模型二采取分批次设置分界线两侧运输的方法，在考虑运载原料不能拆分，小件在上大件在下、运输途中不允许掉头、空车运载费用小于重载费用等约束条件的情况下，建立出车次-运费的资源配置多目标规划模型。通过逐步搜索的方法，在三种材料能卸便卸的情况下选择出每一次出车的最优方案，并且对材料A、B、C进行重要性分析，将C材料看作是附加产品搭载在A、B材料上一起运输来满足各公司对三种材料的需求，最后得到了一共出车28次，耗时为42小时，费用为4905.4元的最优方案。问题二为可掉头情况下的线性目标规划问题。我们仍然采用了类似于问题一的思路进行解决的方式，为达到运输费用小、运输时间短的要求，我们修改了每次的出车方案使得货车卸完货之后都原路返回，这样就减少了货车空载情况下所跑路程、时间与费用。由此得到了出车28次，耗时为27.93小时，费用为4572.8元的最优方案。问题三考虑到部分公司有道路相通，在没有出现负权的情况下，可以采用Dijkstra算法来解决这类最短路问题。对于有8个公司的规划问题，可以将其进行区域化，求出各部分局部最优解，从而得到最优运输方案。本题目的难点为车辆、货物、公司三者之间相互关系中得到最小调度费用的问题，所以首先得确定货车的载货情况，在各辆车均满载的情况下，试图满足各公司的材料需求量，在某些公司无法满足时，考虑某些车次不满载或只装载某一类货物。在模型的推广部分，加入了跨越分界线的运输方式，这样可以相当程度上减少不满载情况下的出车次数，并解决单一材料的运输问题，虽未能减少了出车次数，但节约了行车费用。关键字：目标规划模型逐步搜索Dijkstra算法问题重述1.1基本情况某地区有8个公司（如图一编号①至⑧），某天某货运公司要派车将各公司所需的三种原材料A，B，C从某港口（编号⑨）分别运往各个公司。路线是唯一的双向道路（如图一）。货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次（车辆每出动一次为一车次）。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时（不考虑塞车现象），每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A，B，C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，1.2有关信息附录中给出了该货运公司所掌握的一些数据资料：附件1：各公司当天的需求量表；附件2：唯一的运输路线图及相关里程数；问题提出请根据题中所给的这些数据资料，利用数学建模的方法，解决如下问题：（1）货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小；（2）每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？（3）选做（任选一问）：（01）如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？（02）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法（可结合实际情况深入分析）。二、问题分析合理安排车辆的运载方案，能够大大节省货运公司的运输费用，以便能得到更大的利润。纵观全题，通过剖析题意可得：负重运输载重量越少，负载里程越短，运载费用就越少，因此需要货车能卸货就卸；此外派车次数越少，越能减少出车费用，因此需使货车每次载重相对最大化。另外由于出车方向不定，假设以顺时针货运方向上，货车最远到达④点；同样的在逆时针货运方向上，货车最远到达⑤点，由于负载费用远大于空载，所以定④⑤为分界线，两侧运输为货运不超过分界限的运输方式。通过在相关原则下建立车次-运费的资源配置多目标规划模型来解决问题一。在问题一中，它的最短空载里程为两侧运输在各个公司卸载完毕后，不掉头按原来行驶方向驶向⑨的里程。而在问题二中，由于运输途中可随时掉头，只需在问题一所建模型的基础上，将其中的最短空载路程确定为：若超过分界线卸载完毕，就继续前行至⑨；未超过分界线而卸载完毕，则按原路返回至⑨。对于问题三，当各个公司间都有或者部分有道路直接相通时，原来确定的运输最小路径已发生改变，各公司和港口已形成一个网状结构，在综合考虑各方面约束的条件下可运用Dijkstra算法来解决此类最短路问题。三、模型假设(1)假设每辆车装载时尽量发挥其最大装载能力；(2)假设运输车在行驶过程中不考虑塞车抛锚现象，以保证每辆车每天可以达到最大的工作时间；(3)假设运输车不会因天气状况，而影响其行驶速度，和装载、卸载时间;四、符号说明m—出车一次的费用(已知10元/次)k—派车一次的费用（已知20元/次）—第i次出车时载重的费用—第i次出车时空载的费用S—总运费方案a:A+2C方案b:A方案c:2B方案d:5C方案e：A+C方案f：B+3C方案g：B+2C方案h：B+C方案i：B五、模型的建立与求解问题1：模型一：符号说明：：第i次出车在公司j所卸A材料单位数：第i次出车在公司j所卸B材料单位数：第i次出车在公司j所卸C材料单位数：港口9顺时针到各个公司的距离：第i次出车在公司j将所有的材料卸完：第j个公司对第k种材料的当日需求量模型的建立：根据三种材料的装卸情况，可以分别得到关于材料A、B、C装卸情况的三个矩阵X、Y、Z：建立港口⑨顺时针方向与各个公司之间距离的矩阵M：矩阵N为0-1矩阵，当第i次出车在第j个城市正好将所有的材料都卸完，记作，其他情况下记作。建立每日各公司对各材料需求量的矩阵A：最小运输费用的目标函数：由相关的约束条件得到以下式子：本模型的缺点是没有办法将逆时针方向运输材料的情况，用0-1型整数规划模型融合到该模型中来，得到的解不是最少运输费用的运载方案，所以我们采用了模型二对问题一进行进一步求解。模型二：对于问题一，在货运里程为固定的60公里的情况下，我们希望货车能尽可能早的将货物从车上卸下，以减少负载行驶过程中产生的费用。首先将A种材料看作是重要物资首先进行运输，而将C种材料看作是附加物资与A种材料一起装车；在满足各公司A种产品的要求之后，同样的，再将B种材料看作是重要的物资进行运输，将C种材料与B种材料一起装车；最后对于所剩B类材料未能满足的公司，我们将继续以货车能卸货就卸、货车每次载重相对最大化的原则只装载B种材料进行运输。在考虑运载原料不能拆分，小件在上大件在下、运输途中不允许掉头、空车运载费用小于重载费用等约束条件以及在货车能卸货就卸货、货车每次载重相对最大化总原则下，建立出车次-运费的资源配置多目标规划模型。为了达到费用最小的目标，给出一个运输原则：尽可能的满载，运送时以满足各个公司的需求中A的优先级最高，其次是B，最后是C；若顺时针运送，尽量在到达公司5之前把货物卸完，若逆时针运输，则尽量在到达公司4之前把货物卸完。若没有满足这两个条件中的任何一个，都可以考虑反向运输。费用模型如下：模型的求解步骤：派出装载方案a（1单位A，2单位C）的货车顺时针送货或者逆时针送货，在行车途中所经过的公司能卸货便将车上的可卸货物放下，顺时针送货的货车必须在公司4之前将货卸完，逆时针送货的货车必须在公司5之前将货卸完，若派出的货车无法将6吨货物卸完便不再派发方案a的货车；二、若有某一公司以及它之前的公司只需要1单位C材料，则派出装载方案e（1单位A，1单位C）的货车进行运输；三、若有某一公司以及它之前的公司不需要C材料，则派出装载方案b（1单位A）的货车就近运输；四、若A材料已满足各公司的需求，则派出装载方案f（1单位B，3单位C）的货车顺时针或者逆时针送货，卸货原则同步骤一，五、若有某一公司以及它之前的公司只需要2单位C材料，则派出装载方案g（1单位B，2单位C）的货车进行运输；六、若有某一公司以及它之前的公司只需要2单位C材料，则派出装载方案h（1单位B，1单位C）的货车进行运输；七、若有某一公司以及它之前的公司不需要C材料，则派出装载方案c（2单位B）的货车就近运输，能卸货便卸货；八、若最后只有公司4或公司5各需要1单位B，则派出装载方案i（1单位B）的货车就近运输，并不能跨越分界线。得出最佳出车情况具体如下：出车方案卸货方案xiyixi+yi1a9→1（1，0，2）86.420.8107.22a9→1（1，0，2）86.420.8107.23a9→8（0，0，1）→7（1，0，1）10819.6127.64a9→8→7（1，0，2）118.819.6138.45a9→1（0，0，1）→2（1，0，1）149.418167.46a9→8→7（0，0，2）→6→5（1，0，0)205.214.82207a9→1→2(0，0，1)→3(1，0，1)24314.4257.48a9→1→2→3(1，0，2)259.214.4273.69a9→1→2→3(0，0，1)→4(1，0，1)31512.4327.410a9→8→7→6(0，0，2)→5→4(1，0，1)277.211.6288.811a9→8→7→6(0，0，1)→5(0，0，1)→4(1，0，0)291.611.6303.212b9→8(1，0，0)3622.458.413b9→8(1，0，0)3622.458.414b9→8(1，0，0)3622.458.415b9→8(1，0，0)3622.458.416b9→8(1，0，0)3622.458.417b9→1(1，0，0)57.620.878.418b9→1(1，0，0)57.620.878.419c9→8(0，2，0)54227620c9→8(0，1，0)→7(0，1，0)86.419.610621c9→1(0，1，0）→2（0，1，0）124.218142.222c9→8→7(0，1，0)→6(0，1，0)140.418158.423c9→8→7→6(0，2，0)1621818024c9→1→2（0，2，0）1621818025c9→1→2（0，2，0）1621818026c9→8→7→6（0，1，0）→5（0，1，0）205.214.822027c9→8→7→6→5（0，1，0）→4（0，1，0)291.611.6303.228d9→8→7→6→5(0，0，3)→4(0，0，1)18011.6191.6合计4003.2501.24504.4方案a:A+2C方案b:A方案c:2B方案d:5C用上述模型进行计算：总费用:又因为28次的出车中共停车卸货42次，装货28次，若不卸货的出车一次需1个小时，故总时间为三部分时间的加和:总时间问题2：在第一问的基础上，假定载货方案及卸载方案不变的情况下，运费的变动只取决于空载的距离，如果掉头的空载距离短就掉头行驶，如果不掉头的空载距离短就按原方向行驶。即：当车辆沿顺时针方向跨过4公司还没有卸完或者沿逆时针方向到达公司5还没有卸完的的话，就不掉头，按原来方向继续前进；当车辆沿顺时针方向到达5公司之前或者沿逆时针方向到达4公司之前就能卸完的情况下，就掉头行驶；得出最佳出车情况具体如下：出车装载方案卸货方案xiyixi+yi1a9→1（1，0，2）→掉头86.43.289.62a9→1（1，0，2）→掉头86.43.289.63a9→8（0，0，1）→7（1，0，1）→掉头1084.4112.44a9→8→7（1，0，2）→掉头118.84.4123.25a9→1（0，0，1）→2（1，0，1）→掉头149.46155.46a9→8→7（0，0，2）→6→5（1，0，0)→掉头205.29.2214.47a9→1→2(0，0，1)→3(1，0，1)→掉头2439.6252.68a9→1→2→3(1，0，2)→掉头259.29.6268.89a9→1→2→3(0，0，1)→4(1，0，1)→掉头31511.6326.610a9→8→7→6(0，0，2)→5→4(1，0，1)277.211.6288.811a9→8→7→6(0，0，1)→5(0，0，1)→4(1，0，0)291.611.6303.212b9→8(1，0，0)→掉头3623813b9→8(1，0，0)→掉头3623814b9→8(1，0，0)→掉头3623815b9→8(1，0，0)→掉头3623816b9→8(1，0，0)→掉头3623817b9→1(1，0，0)→掉头57.63.260.818b9→1(1，0，0)→掉头57.63.260.819c9→8(0，2，0)→掉头5425620c9→8(0，1，0)→7(0，1，0)→掉头86.44.490.821c9→1(0，1，0）→2（0，1，0）→掉头124.26130.222c9→8→7(0，1，0)→6(0，1，0)→掉头140.46146.423c9→8→7→6(0，2，0)→掉头162616824c9→1→2（0，2，0）→掉头162616825c9→1→2（0，2，0）→掉头162616826c9→8→7→6（0，1，0）→5（0，1，0）→掉头205.29.2214.427c9→8→7→6→5（0，1，0）→4（0，1，0)291.611.6303.228d9→8→7→6→5(0，0，3)→4(0，0，1)18011.6191.6合计4003.2169.64172.8总费用总时间为六、模型评价与推广约束条件重新确定后的推广模型本文依据题目分析运输问题，做出分批次运输与两侧运输的判断，以及第三问题的区域化求局部最优解，得出了我们自己认为比较理想的结果。我们的模型对于题目的完整性解答有些不足，在第一问与第二问中，我们笼统的将货运地点按分界线分成两个部分来进行求解，无法考虑到在跨越分界线运输情况下的最优解，而且我们没有能够建立通用的计算模型而是采取的手工计算。因此在取消跨界约束的情况下，我们对问题二的模型做了改进，重新构建了数学模型，所得最佳运载方案结果如下表优化改进方案出车装载方案卸货方案xiyixi+yi1a9→1（1，0，2）→空载掉头86.43.289.62a9→1（1，0，2）→空载掉头86.43.289.63a9→8（0，0，1）→7（1，0，1）→空载掉头1084.4112.44a9→8→7（1，0，2）→空载掉头118.84.4123.25a9→1（0，0，1）→2（1，0，1）→空载掉头149.46155.46a9→8→7(0，0，2)→6(0，0，2)→空载掉头93.6699.67a9→8→7→6(0，0，1)→5(1，0，1)→空载掉头2349.2243.28a9→1→2(0，0，1)→3(1，0，1)→空载掉头2439.6252.69a9→1→2→3(1，0，2)→空载掉头259.29.6268.810a9→1→2→3(0，0，1)→4(1，0，1)→空载掉头304.211.6315.811b9→8→7→6→5(0，0，2)→4(1，0，0)30611.6317.612b9→8→7→6→5(0，0，1)→4(1，0，1)320.411.633213b9→8(1，0，0)→空载掉头3623814b9→8(1，0，0)→空载掉头3623815b9→8(1，0，0)→空载掉头3623816b9→8(1，0，0)→空载掉头3623817b9→8(1，0，0)→空载掉头3623818b9→1(1，0，0)→空载掉头57.63.260.819b9→1(1，0，0)→空载掉头57.63.260.820c9→8(0，2，0)→空载掉头5425621c9→8(0，1，0)→7(0，1，0)→空载掉头86.44.490.822c9