数学建模论文-整车物流调度系统的优化设计.doc

2013第十届五一数学建模联赛承 诺 书我们仔细阅读了五一数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其它公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们授权五一数学建模联赛赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号为（从a/b/c中选择一项填写）： c 我们的参赛报名号为： 2013200244 参赛组别（研究生或本科或专科）： 本科 所属学校（请填写完整的全名） 山东科技大学 参赛队员 (打印并签名) ：1. 杨斌 2. 王颖 3. 管雯瑞 日期： 2013 年 5 月 1 日获奖证书邮寄地址：山东省青岛经济技术开发区前湾港路579号 邮政编码 266510 2013第十届五一数学建模联赛编 号 专 用 页竞赛评阅编号（由竞赛评委会评阅前进行编号）：评阅记录评阅人评分备注 裁剪线 裁剪线 裁剪线 竞赛评阅编号（由竞赛评委会评阅前进行编号）：参赛队伍的参赛号码：（请各参赛队提前填写好）：20132002442013第十届五一数学建模联赛题 目 整车物流调度系统的优化设计 摘 要本文围绕整车物流调度系统在不同的约束条件下进行了优化设计。对多起运地和多目的地的物流运输问题，考虑小汽车分级标识，考虑货车评级分数的问题分别建立了相应的模型，并计算出对应的运输最低成本及运单结果。对问题一，分析题意后可以看出本题属于普通的运输优化问题。需建立0-1优化及多层次线性规划模型并借助于lingo软件进行最优解的求解。对问题二，分析附件二中的数据以及题意之后，可以看出本题属于多起运地对多目的地的物流运输问题，如果只考虑以单个起运地进行优化，效果不佳，故我们先将相邻的目的地和同一目的地的不同订单进行聚类分析，在保证最优解的前提下，进行近似运算。除此之外，本题还增加了分级以及货车附近调度和顺途运输问题，显然采取简单的线性优化模型是不可行的。因此，我们可以采取启发式算法（遗传结合模拟退火），由局部最优到全局最优，逐步递进，借助matlab数学软件进行最优解的求解。对问题三，分析题意，问题三在问题二的基础上又增加了评级分数，显然需要考虑调运货车的顺序。但运输成本与货车的评级分数间有主次关系，因此需要考虑两者的权重，即货车优先运输的可能性。关键词：线性规划模型 0-1优化 聚类分析 遗传结合模拟退火算法一 问题重述随着我国经济突飞猛进的发展，物流成为社会分工中重要的环节。物流系统的优劣也影响了业务流程的运行效率及其成本。国内某家物流公司的主要业务是从分布在全国的m个主机厂，将n种品牌商品小汽车调运到全国多个城市的4s店。请为该物流公司设计一套物流运输优化系统，以提高物流运输效率、优化运营成本。本题目不考虑小客车类型的差异，在运输过程中产生的主要运输成本包括：运输商品小汽车的业务费为0.7元/(公里辆)，货车运输途中因部分车位空闲而产生的空载运输成本为0.2元/(公里车位)，油耗动力成本为0.5元/公里，货车过路费用为0.4元/公里。 问题1：建立数学模型考虑从某个主机厂调度货车来完成运输订单，如何安排货车，可以保证在完成运输任务的基础上运输成本最低。请用附件1中的数据来验证你的模型，并根据你的结果给出运单方案。允许将不同订单用同一货车运输，但是不允许将同一订单拆分用不同货车运输；一个运力货车运单的目的地城市的数量不超过3个。说明：车位是指一个货车最多能运输小客车的数量。问题2：由于小客车品牌不同，因此在运输的时候将小汽车进行了分级标识，级别最高的为1，在同一个起运地优先安排货车运输这些级别高的小汽车。如果货车有剩余车位，则可以顺途运输其他城市的订单；如果起运地货车数量不足，可以从附近城市调运货车来运输本地订单。请建立数学模型，考虑如何安排货车，可以保证在完成运输任务的基础上运输成本最低。结合附件2中的数据，进行求解并给出运单。问题3：每辆货车对公司物流运输系统的价值和效率是不同的，通过对每一辆货车的运输汽车质损率、及时到达率、信息反馈率和服务态度等多方面进行跟踪评价，可以得到货车的评级分数，分数越高说明运输质量和效率越好。故在安排货车运输方案的时候，首先考虑运输成本最小，其次优先安排车辆评级分数较高的货车，在问题2的基础上，利用附件3中的数据进行求解并给出新的运单。二基本假设 （1）不考虑天气等客观因素对货车运输的影响（2）不考虑小客车类型的差异（3）假设不同货车在里程数一定的情况下所用时间相同（4）本题中所给任意两地之间均满足运输条件（5）每一个起运地都有一个固定的供应量，所有的供应量都必须配送到各个销地（6）每一个目的地都有一个固定的需求量，整个需求量都必须由起运地满足16三符号说明符号含义从起运地i到目的地j第k个订单的小汽车数量编号为m的货车的车位数从起运地i到目的地j的订单个数货车m装载从起运地i运往目的地j的小汽车数0-1变量 1表示货车m装载从起运地i运往目的地j的第k个订单货车m的评级分数从起运地i到目的地j第k个订单的小汽车品牌等级从起运地i到目的地j的里程数从目的地s到目的地t的里程数货车m运载小汽车的目的地个数单位里程数运输一辆小汽车的路费单位里程数运输途中空闲一个车位的运输成本单位里程数的油耗成本单位里程数货车的过路费用 起运地i到j的小汽车订单的权重从起运地i到目的地j第k个订单小汽车优先运输货车m优先等级的权重l起运地i到目的地j的成本度量从起运地i到目的地j第k个订单小汽车优先运输的可能性货车m在起运地的装载数w运输总成本表示货车m的分级分数m货车优先运输的可能性四问题分析对问题一，分析题意后可以看出本题属于普通的运输优化问题。由于附件1中给出的数据较多，显然需要借助数学软件进行处理。题目中给出几个不同的约束条件，同一货车运输到同一目的地的订单具有不确定性以及每个目的地所用的货车也具有不确定性，因此我们需建立0-1优化及多层次线性规划模型并借助于lingo软件进行最优解的求解。对问题二，分析附件二中的数据以及题意之后，可以看出本题属于多起运地对多目的地的物流运输问题，如果只考虑以单个起运地进行优化，效果不佳，故我们先将相邻的目的地和同一目的地的不同订单进行聚类，在保证最优解的前提下，进行近似运算。除此之外，本题还增加了分级以及货车附近调度和顺途运输问题，显然采取简单的线性优化模型是不可行的。因此，我们可以采取启发式算法（遗传结合模拟退火），由局部最优到全局最优，逐步递进，借助matlab数学软件进行最优解的求解。对问题三，分析题意，问题三在问题二的基础上又增加了评级分数，显然需要考虑调运货车的顺序。我们通过评级分数可以确定调运某辆货车的可能性，可近似认为是蚁群算法中的诱导因素，再结合问题二中已建好的模型加以求解。五模型的建立和求解问题一 在将不同订单用同一货车运输，但是不允许将同一订单拆分用不同货车运输；一个运力货车运单的目的地城市的数量不超过3个的约束条件下，求出最低成本。mabcm货车a ，b，c不同的目的地，到目的地a的第i个起运地到目的地b的第j个起运地到目的地c的第k个起运地其他限制条件模型一 根据对问题一的分析，做出的0-1优化多起运地多目的地线性规划模型如下：约束条件：(1)任意货车装载的小汽车总量不能超过该货车的最大车位数 m=1,2, （2）= 货车m装载从起运地i运往目的地j的第k个订单时，=1，否则，=0(3)任意货车均不能完全空载 i=1,2, (4) 货车m装载从起运地i运往目的地j的小汽车数与从起运地i到目的地j第k个订单的小汽车数量满足下列等式： = j=1,2, (5) 货车m在起运地的装载数与货车m装载从起运地i运往目的地j的小汽车数满足下列等式： i=1,2, 目标函数：minw=由于起运地唯一，i就成为定值，故模型可以简化为单起运地多目的地运输优化模型：（1）（2）不变 （1-1） = j=1,2, (1-2) (1-3)目标函数 min w=为了计算方便，我们对不同的目的地和同一目的地的不同订单进行编号，生成矩阵。下图为部分数据，细见附件1.1订单编号1234567蒙城3700000福州10107121010龙岩4100000三明3700000兰州5105101000南宁101000000贵阳10000000里程数蒙城福州龙岩三明兰州南宁贵阳蒙城0122511491010116117791732福州12250392233254616361771龙岩11493920221233413091548三明10102332210220013041487兰州1161254623342200022651707南宁177916361309130422650576贵阳173217711548148717075760蒙城福州龙岩三明兰州南宁贵阳北京884196522441834163024832447编号1234567车位数10202020152010利用lingo编写代码（见附件1.2）计算处理好的数据（见附件1.1）。运行结果见附件1.3。对结果分析，得如下结论：运费最低：334403.3元运单结果：货车编号对应目的地如下表：地点蒙城福州龙岩三明兰州南宁贵阳货车编号110、14、155516、17197地点遵义漯河商丘郑州大庆牡丹江常德货车编号2027、2827、2831182232地点长沙长春葫芦岛盘锦沈阳包头银川货车编号23402643424424、25地点东营济南青岛日照成都达州自贡货车编号343537、3837、383、124546地点杭州桐乡金华宁波衢州货车编号929414130问题二 考虑小汽车的优先分级，如果起运地货车数量不足，可以从附近城市调运货车且在有剩余车位时可以顺途运输。 在完成如上运输任务的前提下，求最低运输成本。模型二 根据对问题二的分析，显然多了汽车优先分级的约束，所以应对模型一加以改进，引进自定义分级变量，加以对模型一的约束，即单优先级多起运地多目标优化模型建模如下：定义=/ 表示从起运地i到目的地j第k个订单小汽车优先运输的可能性，仅影响货车安排次序引用模型1保持（1）（2）(3)(4)(5)不变目标函数minw=由于本问题涉及多起运地且订单过于分散，如果只考虑单个，比例太小，不便求解最优解，为了在保证最优解不变且计算方便，可以采用聚类分析思想，将数据处理如下：起运地终点站小汽车数量里程数成都市漯河市141295成都市郑州市81278天津市邯郸市10480天津市邢台市6432重庆市北京市111876芜湖市亳州市21419芜湖市巢湖市1470芜湖市合肥市10135北京市安庆市101205北京市合肥市341038此表仅为部分数据，详细表格见附件2-1顺途运输的目的地间里程表漯河商丘郑州大庆牡丹江常德漯河020116320812299683商丘201022620302248875郑州163226021132255788大庆20812030211305402708牡丹江22992248225554002923常德68387578827085400此表仅为部分数据，详细表格见附件2-1由于优先级制约条件，单纯依靠lingo优化达不到目的，因此需要借助matlab进行计算。但是模型中变量较多，需要借助遗传算法进行matlab编程，现将遗传算法的思想介绍如下。其一般性算法可以描述为：(1)初始化进化计数器。(2)随机产生初始种群,设定初始规模(3)以概率1对种群中个体进行交叉操作crossover，产生(4)以概率2对种群中个体进行变异操作mutation，产生(5 )以概率3对种群进行反转操作invertion，产生(6)调用模拟退火算法：simulatedannealing，产生(7)通过适应度函数/，对中的个体适应度进行评估；(8)将适应度最优的个体直接复制到下一代中，并按照给定概率选择其余的个体到下一代，产生新一代(9)重复以上步骤直到产生最优解为止。结合上述遗传算法编写代码，见附表2-2程序运行结果见附表2-3ans=0.5631457e+07运单部分结果如下：起运地目的地货车编号起运地目的地货车编号 成都郑州192天津沈阳203、204 成都大连193天津保定206 成都赤峰194天津北京205 成都漯河195重庆北京236 成都苏州196重庆运城238 成都大连196重庆广州239 成都洛阳196柳州衡水128天津阜阳197柳州长治129天津太原202柳州邯郸130、131郑州保定151郑州临汾150 注：运单详见matlab附表2-3问题三问题二基础上，增加了限制条件（货车的评级分数），也就相应需对模型二进一步限制，最终求最优解。定义m=/ 为货车优先运输的可能性模型三保持模型（1）(2)(3)（4）（5）不变min w=货车分级分数数据见下表，其他数据见模型二的数据：货车编号车辆评级分数1790.0054762232560.003881883490.0033966454990.0068626095720.0049909886620.0042977967890.0061694168630.0043671159440.00305004910250.00173298211770.00533758512700.0048523513610.00422847614180.00124774715470.00325800616920.00637737417770.00533758518750.00519894619900.006238736利用matlab编码求解，matlab代码只需在原有代码基础上添加限制的限制变量即可求解。最优解ans=0.612537e+07 求解部分运单结果如下：起运地目的地货车编号起运地目的地货车编号 成都郑州196天津沈阳203 成都大连194天津保定206、04 成都赤峰191天津北京205 成都漯河195重庆北京236 成都苏州196重庆运城238 成都大连196重庆广州239 成都洛阳198柳州衡水129天津阜阳197柳州长治128天津太原204柳州邯郸130、131郑州保定149郑州临汾152 注：matlab输出结果见3-3六模型的评价优点： 在不同的约束条件下，采取了不同的数学模型，并在处理大量数据的基础上得出相应的最低成本及运单结果，基本实现了全局最优化，并且采用了matlab，lingo等数学软件进行求解，使得结果更加可靠。缺点：1 样本数据时可能不具有代表性，从而使结果产生偏差。2.未考虑时间约束以及实际运输中存在的产销不平衡以及其他客观因素的影响。3.在运算过程中采取了近似算法，所得结果并不完全精确。七参考文献1徐新明，陈培友，物流调度问题的优化方法评述，商业研究，第385期：2009年5月，1071112莫金康.智能调度系统在整车物流配送中的开发应用，技术经济，2011年05期：36 413代红艳，李彦平，恩莉，配送问题的数学模型和遗传算法，计算机工程与应用，2005年31期：1891924刘立波，许国银，原静，基于遗传模拟退火算法的战时物流配送路径优化研究，现代物流，29卷07期.：2007年5郭兰英，高一凡.一种运输车辆调度聚类分析模型及仿真研究，西安公路交通大学学报，第18卷第1期：1998年1月.92966杨启帆，数学建模，北京：高等教育出版社，2005年 八附录问题一：处理好的数据（见附件1.1）lingo编写代码（见附件1.2）运行结果（附件1.3）问题二：处理好的数据（见附件2.1）lingo编写代码（见附件2.2）运行结果（附件2.3）问题三：处理好的数据（见附件3.1）代码（见附件3.2）运行结果（附件3.3）代码如下：附件1.2model:sets:yf/c1.c33/ : ci,b;sj/j1.j33/;jib(yf,sj) : a,x;endsetsdata:b=ole(1.xls,bmm);ci=ole(1.xls,cii);a=ole(1.xls,aa);enddatamin=sum(yf(i):(b(i)-sum(sj(j):x(i,j)*a(i,j)*f1*ci(i) +(sum(sj(j):x(i,j) *a(i,j) ) * f0 *ci(i) + (f2+f3)*ci(i) + b(i) *ci(i) *(f1+f2+f3);f0=0.7;f1=0.2; f2=0.5; f3=0.4;for(sj(j):sum(yf(i):x(i,j)=1);for(yf(i):sum(sj(j):x(i,j)=33);for(yf(i):sum(sj(j):x(i,j)*a(i,j)=b(i);for(jib:bin(x);end附件2.2model:sets:vi/1.33/:f;vj/1.33/:jj;vm/1.46/:q;vk/1.33/:kk;vc/1.33/:cc;vic(vi,vc):y,a;vjc(vj,vc):z,b;vkc(vk,vc):m,d;vjk(vj,vk):w;vij(vi,vj):pia;endsetsdata:f=ole(2.xls,ffff);w=ole(2.xls,ww);q=ole(2.xls,qq);a=ole(2.xls,aa);b=ole(2.xls,bb);d=ole(2.xls,dd);pia=ole(2.xls,pp);f0=0.7;f1=0.2;f2=0.5;f3=0.4;enddatafor(vi(i):(sum(vc(c):y(i,c)=33);for(vj(j):(sum(vc(c):z(j,c)=33);for(vk(k):(sum(vc(c):m(k,c)=33);for(vjc(j,c):bin(z(j,c);for(vic(i,c):bin(y(i,c);min = sum(vj(j):sum(vk(k):sum(vm(s):sum(vi(i):(sum(vc(c):y(i,c)*a(i,c)+sum(vc(c):z(j,c)*b(j,c)+sum(vc(c):m(k,c)*d(k,c)*f(i)*f0+(q(s)-(sum(vc(c):y(i,c)*a(i,c)-(sum(vc(c):z(j,c)*b(j,c)-(sum(vc(c):m(k,c)*d(k,c) * f1*f0*f(i) +(f2+f3)*f(i)+(sum(vc(c):z(j,c)*b(j,c) + sum(vc(c):m(k,c)*d(k,c)* f0 * pia(i,j) + (q(s)-(sum(vc(c):m(k,c)*d(k,c)-(sum(vc(c):m(k,c)*d(k,c)*f1*pia(i,j) + (f2+f3)*pia(i,j) + (sum(vc(c):m(k,c)*d(k,c)*f0*w(j,k) + (q(s)-(sum(vc(c):m(k,c)*d(k,c) * f1 * w(j,k)+(f2+f3)*pia(j,k)+(f2+f3)*(w(j,k)+pia(i,j)+f(i);附件3.2#include#include#include#include#define citynumber 5#define q 100#define p 0.5#define nm2 1000#define a 1#define b 5int ccdi=-1;/全局变量,用在myrand()中float myrand()/产生0-1随机数,100个,每调用一次,结果不同srand(time(0);float my100;ccdi+;if (ccdi=100) ccdi=0;for(int mi=0;mi100;mi+)float fav=rand()%10000;mymi=fav/10000;return myccdi;double fpkij(double tcitynumbercitynumber,double ncitynumbercitynumber,int tabucitynumbercitynumber,int k,int s,int i,int j )/定义函数用于计算pijk /double a=0.5,b=0.54 double sumup,pkij,sumdown; sumdown=0;for(int ati=0;aticitynumber;ati+) for(int atj=0;atjcitynumber;atj+) atatiatj=pow(tatiatj,a); for(int bni=0;bnicitynumber;bni+) for(int bnj=0;bnjcitynumber;bnj+) bnbnibnj=pow(nbnibnj,b); for (int can=0;cannumber;can+)/判断,除掉运走运单if(can=tabukci) atican=0;bnican=0; sumup=atij*bnij; for(int tj=0;tjcitynumber;tj+) sumdown=atitj*bnitj+sumdown;pkij=sumup/sumdown;return pkij;void main()double citycitynumber double dcitynumbercitynumber; /ljk是城市j to k距离 for(int j=0;jcitynumber;j+) djk=sqrt(cityj0-cityk0)*(cityj0-cityk0)+(cityj1-cityk1)*(cityj1-cityk1);/ coutdjk ; /coutn; /*从目的的j城市到目的地k城市带入运算*/ /*for (int cj=0;cj10;cj+) float c=myrand(); coutc n;*/输出随机数 double ncitynumbercitynumber;for(int ni=0;nicitynumber;ni+)for(int j=0;jcitynumber;j+)/coutn; /*初始化visibility nij*/double lcitynumber;int shortestcitynumber;double tcitynumbercitynumber;for(int ti=0;ticitynumber;ti+)for (int j=0;jcitynumber;j+) /coutttij ;/coutn;/*初始化t*/ double changtcitynumbercitynumber;/step2:for(int nc=0;ncnm2;nc+)for(int cti=0;cticitynumber;cti+) for (int j=0;jcitynumber;j+) changtctij=0;/coutchangtctij ;/coutn;/*初始化changt*/int tabucitynumbercitynumber;/tabuks表示货车m到达的目的城市ifor (int i=0;icitynumber;i+) tabutaii=0;for (int tabui1=0;tabui1citynumber;tabui1+)tabutabui10=tabui1;/*for (tai=0;taicitynumber;tai+)for (int i=0;icitynumber;i+) couttabutaii ;coutn;*/初始化tabufor(int kk=0;kkcitynumber;kk+) lkk=0; /第三步开始for(int s=0;scitynumber-1;s+)for(int k=0;kcitynumber;) int ci,ca