《货运列车编组运输问题-数学建模【整理版】.docx》由会员分享，可在线阅读，更多相关《货运列车编组运输问题-数学建模【整理版】.docx（53页珍藏版）》请在金锄头文库上搜索。
1、西南财经大学数学建模竞赛货运列车编组运输问题货运列车编组运输问题摘要本次问题编程的目的是，在不同问题设定下，制定货运列车的最佳编组方案。对于问题一：问题一是以运输货物数量最多、运输总重量最小为目标函数的双目标优化问题。参考公司投资组合问题中为解决利润最大、风险最小而采用的有效前沿的方法，我们用MATLAB编程得到可行的装运方案，做出各方案的运输总重量和运输数量决定的散点图，得到类似的有效前沿，具体方案见4.2表二：对于问题二：问题二是下料问题，因此需要先确定可行的下料方式，即两种车厢可行的货物装载方式。以每种装载方式的使用次数为决策变量，总使用次数最少为目标函数，建立整数线性规划模型求解。用M
2、ATLAB解得：要将货物运输完毕，B,C,E分别为68、50、41件时使用的最少车厢数量为25，B,C,E分别为48,42,52件时使用的最少车厢数量为21，具体方案见5.2表三、表四。对于问题三：由于上午、下午需要运输的集装箱数量是随机的，导致铁路部门的利润也是随机的，因此我们以铁路部门的平均日利润最大为目标函数，对上午、下午进行独立分析，构建概率模型，并用MATLAB求解，得到最佳编组方案:上午发的列车带41节型车厢、下午发的列车带38节型车厢。对于问题四：我们参考图论模型中的dijkstra算法，将模型中的权重新定义为到各站点的收益，利用matlab软件找到收益最大的路线，尽可能满足这条
3、路线上的需求量，然后去掉路线中除去起点和终点的点，再次运用程序计算利润最大的路线，重复以上过程到只剩下起点和终点。得到最佳编组运输方案为：路线A-B1-C2-D2-E3-F运输3次分别带40、40、29节车厢；路线A-B2-C2-D1-E1-F满载运输1次；路线A-B2-C4-D3-E3-F运输2次分别带40、2节车厢；路线A-B1-C1-D1-E2-F运输1次带27节车厢；路线A-B2-C3-D2-E2-F运输1次分别带29节车厢，此时铁路部门利润为449050元。对于问题五：模仿第四题的思路，在其基础上，考虑各个站点之间集装箱运输的需求量，得到最佳编组运输方案见8.2.4表五。关键词：双目
4、标优化 有效前沿 下料问题 概率模型 dijkstra算法1.问题重述货运列车编组调度的科学性和合理性直接影响货物运输的效率。在不同的问题设定下，进行分析得到货运列车的最佳编组方案。具体设定及需要解决的问题如下：1.1问题一1) 甲地到乙地每天有5种货物需要运输，其包装箱相关参数确定（附录一表1）。2) 每天有一列货运列车从甲地发往乙地，由1节型车厢（单层平板车）和2节型车厢（双层箱式货车）编组（具体规格见附录一表2）。3) 货物在车厢中必须按占用车厢长度最小的方式放置，且不允许重叠；型箱式车厢下层装载货物后剩余长度小于等于0.2米，才能在上层放置货物。 试设计运输货物数量最多的条件下，运输总
5、重量最小的装运方案。1.2问题二1) 在编组中型车厢的数量多于型车厢数量。2) 型箱式车厢下层装载货物后剩余长度小于等于5米，才能在上层放置货物。3) 货物装车其它规则同问题1。 如果现有B,C,E三种类型的货物各68、50、41件，试设计一个使用车厢数量最少的编组方案将货物运输完毕。 若B,C,E三种类型的货物各有48,42,52件，请重新编组。1.3问题三1) 从甲地到乙地每天上午和下午各发送一列由型车厢编组的货运列车。2) 每列火车开行的固定成本为30000元，加挂一节车厢的可变成本为1500元。3) 铁路部门拟将货物放置到长、宽、高分别为4米，3米及1.99米的集装箱中运输，每个集装箱
6、的总重量不超过18吨，集装箱的运费为1000元/个。4) 每天需要运输的集装箱数量是随机的（过去最近100天数据见附录一表3）。5) 上午的需求如果不能由上午开行列车运输，铁路部门要支付50元/个的库存费用；下午列车开行后如果还有剩余集装箱，铁路部门将支付200元/个的赔偿，转而利用其它运输方式运输。 试制定两列火车的最佳编组方案。1.4问题四1) 每天铁路部门将以A站为起点F站为终点，沿不同的路线开行若干趟全部用型车厢编组的货运列车，每列火车最大编组量为40节车厢。2) 每列火车列车开行的固定成本为15000元，每节车厢开行的可变成本为1元/公里，每个集装箱的运费为2元/公里（按两车站间的最
7、短铁路距离计费）。3) 铁路网线情况见附录一表4，从A站到其它站点的潜在集装箱运输需求量见附录一表5，集装箱规格同第三问（铁路部门没有义务把集装箱全运输完毕）。 请为铁路部门设计一个编组运输方案。1.5问题五1) 铁路部门每天从A站用型车厢编组开行到F站的若干趟货运列车。2) 每天各个车站之间潜在的集装箱运输量见附录一表6。3) 铁路网线及费用设定同问题4。 请为铁路部门设计一个编组运输方案。2. 基本假设与符号说明2.1基本假设1) 货物不能重叠放置，且不能直立放置；2) 上午运不完的集装箱，归到下午需要运的集装箱的范畴；3) 出于利润最大化的考虑，发出的列车车厢数达到最大编组量且每个车厢中
8、装满三个集装箱；4) 超过需求量的集装箱，铁路部门收不到相应的运费；5) 从A出发时，为中途站点所有要装上的集装箱留下位置，即同一车厢位置不考虑装卸集装箱后的重复使用；6) 每一条路线可以重复运输。2.2符号说明=1,2,3,4,5分别对应货物类型A,B,C,D,Ei型货物占用车厢长度i型货物重量、型车厢的长度、型车厢的载重量单个车厢某装载方式中i型货物的装载量只考虑B,C,E的型车厢第j种装载方式的使用次数只考虑B,C,E的型车厢第j种装载方式的使用次数i型货物现有数量 r1 r2上午、下午需要运的集装箱的数量s1 s2上午、下午发出的货运列车的车厢数R1 R2上午、下午铁路部门的利润3.
9、问题分析针对问题一，我们首先明确了问题一是以运输货物数量最多、运输总重量最小为目标函数的双目标优化问题，借鉴公司投资组合问题中为解决利润最大、风险最小而采用的有效前沿的方法，我们用MATLAB编程得到可行的装运方案，做出各方案的运输总重量和运输数量决定的散点图，得到类似的有效前沿。针对问题二，我们注意到其实质是下料问题，因此需要先考虑可行的下料方式，即两种车厢可行的货物装载方式，以每种装载方式的使用次数作为决策变量，总使用次数最少为目标函数，建立整数线性规划模型求解。针对问题三，由于每天需要运输的集装箱数量是随机的，导致铁路部门每天的利润也是随机的，不能作为优化模型的目标函数，因此我们以铁路部
10、门的平均日利润最大为目标函数，以上午、下午发出的货运列车的车厢数为决策变量，构建概率模型，并用MATLAB求解。针对问题四，我们参考图论模型中的dijkstra算法，将模型中的权重新定义为到各站点的收益，利用matlab软件找到收益最大的路线，尽可能满足这条路线上的需求量，然后去掉路线中除去起点和终点的点，再次运用程序计算利润最大的路线，重复以上过程，直到只剩下起点和终点，得到最佳编组运输方案。针对问题五，模仿第四题的思路，在其基础上，考虑各个站点之间集装箱运输的需求量，进行求解。4. 问题一的解答4.1模型一的建立4.1.1基本思路确定双目标优化类比投资组合问题的有效前沿确定可行的装运方案计
11、算相应的运输数量和运输总重量做出散点图，得到有效前沿4.1.2对于双目标的处理问题一要求，根据题设，设计运输货物数量最多的条件下，运输总重量最小的装运方案，这是以运输货物数量最多、运输总重量最小为目标函数的双目标优化问题。对于双目标优化问题常见的方法有，分层序列法以及化多为少的方法，如主要目标法、线性加权法、理想点法等，但是这些方法各有局限，且优化的结果并不直观1。联系公司投资组合中利润最大、风险最小的问题2，我们发现问题一与其有相似的情况，如下表。表一：投资组合问题与问题一的比较投资组合问题问题一双目标优化利润最大运输货物数量最大风险最小运输总重量最小方案确定每年每个项目投资多少每车厢每货物
12、装载多少方案选择投资组合方案货物装运方案因此我们决定类比公司投资组合问题中采用的有效前沿的方法,得到问题一的有效前沿。4.1.3确定可行的货物装运方案要得到有效前沿，确定可行的货物装运方案是第一步。1.基本思路由于货物不能重叠放置，我们可以将货物车厢中的装载问题抽象为二维矩形件的排样问题，只是增加了货物总重量的上限约束。如果将一节车厢和两节车厢一起进行分析，情况较为复杂，为减少计算负荷，我们先对两种车厢各自的可行装载方式进行分析，再将其进行组合。2.考虑单个车厢时，满足如下条件：1) 货物占用车厢的高度车厢高度考虑实际情况以及题中所给的例子，我们假设货物不能竖直放置。此时只需考虑货物实际高度与
13、车厢高度的关系，得到型车厢的第二层不能放置A类和B类货物的结论。2) 货物按占用车厢长度最小方式放置对于A,C,D,E类的货物，他们占用车厢的最小长度就是他们的实际长度。对于B类货物，需要进行分类讨论：车厢中B类货物的装载量为偶数时，两两并排放置（如图1左）占用车厢长度最小；车厢中B类货物的装载量为奇数时，在两两并排的基础上，将余下的一件B类货物横着放置（如图1右）占用车厢长度最小。 图1 B类货物放置示意图即3) 货物占用车厢的宽度车厢宽度货物按占用车厢长度最小的方式放置时，恰使得A,C,D,E类货物占用车厢的宽度等于车厢宽度，而对B类货物进行分类讨论时，已经考虑到了车厢宽度的限制，因此这一
14、条件可以不单独列出。4) 货物占用车厢总长度车厢长度5) 货物总重量车厢载重量6) 型车厢下层装载货物后剩余长度小于等于0.2米时，才能在上层放置货物3. 在MATLAB中编程（源程序见附录二表1）得到两种车厢可行的货物装载方式（附录二表2）4.对两种车厢可行的货物装载方式进行组合因为列车由一节、两节编组，在型车厢可行的货物装载方式中选择一种，在型车厢可行的货物装载方式中选择两次（可重复），记录下装载货物不超过数量上限的组合，得到可行的装运方案，计算其运输数量及运输总重。（MATLAB源程序见附录二表3，由于可行的装运方案过多，不在附录中体现，见附件 可行装运方案.xlsx）4.2模型一的求解由得到可行装运方案的数据，在MATLAB中做出散点图及边界曲线，并用MATLAB 自带的基本拟合工具得到拟合曲线y=-0.00074x2+0.34x-14。结果如下：图2：模型一求解出的有效前沿表二：有效前沿上的点所对应的装运方案运输重量122128135143149.5158.5170180.5运输数量1718192021222324型车厢A4444344444322B0000000000000C0000000000244D0000100000000E0000000
