运输配送货物的行使路线问题论文

《运输配送货物的行使路线问题论文》由会员分享，可在线阅读，更多相关《运输配送货物的行使路线问题论文（11页珍藏版）》请在装配图网上搜索。

1、运输问题摘要本文主要研究了配送货物的行使路线问题。根据题目要求,采用Fleury算法,建立01型整数规划模型，并利用lingo，求出了最短行使路线和装配方案，使得运输公司运货的总费用最少。针对问题一，本文将运送路线看作是10个客户点作为顶点的有向的网络图，做出赋权邻接矩阵，采用Dijkstra算法思想，利用lingo编程,求出从客户2到客户10最短的行使路线，最短行使路线为：，路程为85公里。针对问题二，要求设计货车从提货点到送货点再返回提货点的最短路线。本文采用Fleury算法思想，根据不同的权值客户与客户之间的距离，形成Euler回路，建立线性规划模型，利用lingo, 求出有最小权的Ha

2、milton圈，即最短的行驶路线。最短的行使路线为：路程为225公里。针对问题三，本文首先从每辆车的容量与各个客户的需求量之间的关系考虑，得出每辆车的载货量在36至50之间，进一步分析得出两种情况：1、两辆车分别装5个和4个客户的货物；2、两辆车分别装6个和3个客户的货物。然后分别对以上两种情况进行讨论，分别以其中一辆车行使的最小路程为目标函数，以 每个客户必须有车到达、车的装载容量和附加变量防止构成内圈为约束条件，建立01线性规划模型，利用lingo，通过比拟优化，得出最正确的配送方案如下表：车号行使路线路径长度公里总路径长度公里负责的客户1号车135 2904,5,8,9,102号车155

3、 2,3,6,7针对问题四，我们以总运费最小为目标函数，约束条件和问题三的类似，建立0-1型整数规划模型。运用lingo求得当有4辆车运送货物时总费用最小，为645元。具体运输方式为：； ；关键词：0-1型整数规划 Fleury算法 Lingo一、问题重述某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离单位公里用下面矩阵中的位置上的数表示其中表示两个客户之间无直接的路线到达。1、 运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线假定

4、上述矩阵中给出了所有可能的路线选择。2、 现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。3、 现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法进行分析。4、 如果改用更小容量

5、的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第3问，并假设每出一辆车的出车费为100元，运货的价格为1元/公里不考虑空车返回的费用，请问如何安排车辆才能使得运输公司运货的总费用最省？二、问题分析问题一的分析题目要求设计一个尽可能短的行路线，使运送员在给第2个客户卸货完成的时候让他先给客户10送货。从客户与客户之间的距离矩阵可以发现客户2到客户10无直接的路线到达，于是本文将运送路线看做是10个客户点作为顶点的有向的网络图，然后编写程序，利用lingo,求出最短的行使路线。问题二的分析题目要求设计货车从提货点1出发给10个客户配送完货物后再回到提货点尽可能短的行使路线。这

6、个问题与旅行商问题类似，于是，本文将路线转化为Hamilton圈，根据不同的权值客户与客户之间的距离，利用lingo, 求出有最小权的Hamilton圈，即最短的行驶路线。 对于问题三，我们将货物分成两种情况进行分析。第一种情况：两辆车中一辆车装载4个客户的货物，另外一辆车装载5个客户的货物。第二种情况：两辆车中一辆车装载3个客户的货物，另外一辆车装载6个客户的货物。但是每辆车货物的容量小于50大于36，我们将每辆车的容量作为约束条件。每个客户点总会有一辆车进入，然后再离开，我们对这个问题采用01规划模型进行运算。 将添加一种在原模型上附加充分的约束条件以防止产生子巡回的方法，把额外变量附加到

7、问题中。可以把这些变量看作是连续的虽然这些变量在最优解中取普通的整数值。现在附加下面形式的约束条件：将其中一辆车行使的最小路程为目标函数，建立线性规划模型。2.4问题四的分析 对于问题四，要使总费用最低，必须使出车费与运费的和最少。由于车辆的个数不限，我们首先假设用k辆车来运送货物，又根据每辆车最多可运25个单位的货物，所以至少4辆车运送货物。又因为不考虑空车辆返回时的费用，故只需考虑运输货物时的路程最短。我们建立01型整数规划模型，将最小费用作为目标函数，运用lingo求得最优解，得出最正确的配送方案。三、问题假设1、假设提货点就在客户1所在的位置，客户1所需的货物不用装车配送；2、假设每个

8、客户需要的是同一种货物。四、符号说明其中一辆车负责的客户数第i个客户到第j个客户的路程，i,j=1,2,10为1时，表示走过城市i到城市j之间的路i,j=1,2,10Z一辆运货车走过的路程W总费用五、模型的建立与求解模型一的建立与求解 由客户与客户之间的距离矩阵可以看出，这是一个有向网络图且图中有10个顶点，现需要求从顶点2到顶点10的最短路。设为赋权邻接矩阵，其分量为决策变量为，当=1时，说明弧位于顶点2至顶点n的路上；否那么=0.其数学规划表达式为：S.t. 由上面的数学规划表达式和客户与客户之间的距离矩阵，编写程序，利用lingo见附录1,求得从客户2到客户10的最短行使路线为：；最短路

9、程为：30+25+10+20=85公里.公司要求用送货员从客户1出发，给其它9个客户送货，最后再返回出发地，这和旅行商问题类似。于是，设城市的个数为 n, 是两个城市i与j之间的距离，=0或11表示走过城市i到城市j之间的路，0表示没有走过城市i到城市j之间的路，表示集合s中元素个数。有s.t. 由上面的数学规划表达式和客户与客户之间的距离矩阵，编写程序，利用lingo(见附录2),求得从客户1 出发，经过其它各个客户点再回到客户1的最短行使路线为：最短路程为：25+10+25+30+15+20+10+20+20+50=225公里.每辆车的容量要小于50，可以转换为一辆车所装载的货物大于36小

10、于50，可建立约束条件为： 因为是两辆车给顾客送货，所以说每辆车不需要经过所有的顾客点，每个顾客点只需要有车经过，然后在离开即可。因此我们采用01规划模型将进去顾客点用1表示否那么用0表示，离开顾客点用1表示否那么用0表示。所以我们建立的约束条件为： 故可建立如下模型：运用lingo见附录3可以求得以下结果表1 其中一辆车经过的路径及长度K的值满足条件的较短路径1-1路径长度单位：公里3955135由以上数据我们求出一辆车的最短路径，第二辆车的行使路径必须经过第一辆车所没经过的客户点。于是我们建立新的模型，如下所示：运用lingo求得结果如下：表2 另一辆车经过的路径及长度K的值满足条件的较短

11、路径2-1路径长度单位：公里62054155通过表1、表2，我们得出：第一种情况两辆车中一辆车装载5个客户的货物，另外一辆车装载4个客户的货物，总的路径长度为：135+155=290公里；第二种情况两辆车中一辆车装载3个客户的货物，另外一辆车装载6个客户的货物，总的路径长度为：95+205=300公里。根据题目要求行使的距离之和尽可能短，因此，第一种情况的方案较好。在执行此方案时，一号车的载货量为：9+7+5+12+9=42；二号车的载货量为：13+6+15+10=44，满足车容量条件。表3 最优的配送方案车号行使路线路径长度公里总路径长度公里负责的客户1号车135 2904,5,8,9,10

12、2号车155 2,3,6,7模型四的建立与求解每个客户有一辆车到达为其送货，所为我们建立的约束条件为：因为不考虑返回时的费用，所以我们建立的约束条件为：每辆车的最大容量为25，所以我们建立的约束条件为：以总费用最小为目标函数建立如下模型： 运用lingo计算出k等于4时，总费用W最小为645。具体路线如下表：表4 最优的配送方案车号行使路线路径长度公里负责的客户1号车402,52号车803,4,83号车556,74号车709,10六、模型的评价与推广模型的优点模型运用01线性规划模型和整数线性规划建立的模型比拟简单明了思路清晰，该模型主要运用lingo进行计算，其中还引入Hamilton圈的进

13、行求解，使得结果更加精确。我们还用统一的模型同时计算出两辆车的最优路线，得出最优解。模型的缺点及改良该模型计算量较大，数据较多，计算过程比拟繁琐。我们可以改良模型使得计算量减少，防止在计算中产生的错误。模型的推广该模型可应用于物流行业，运费减少公司获得的利润增大。还可应用于邮递员投递问题，使邮递员走的路程最短，提高工作效率。七、参考文献1?运筹学?教材编写组，运筹学修订版，北京：清华大学出版社，1990.2谢金星，薛毅编著，优化建模与LINDO/LINGO 软件，北京：清华大学出版社， 2005。3白其峥主编，数学建模案例分析，北京：海洋出版社，2000。4万保成 王田蛾，?lingo9.0

14、for windows软件及应用?，吉林农业大学数学教研室，2004。5Frank R. Giordano 著，叶其孝 姜起源译，?数学建模?，机械工程出版社，2006。八、附录附录1model:data: n=10;enddatasets: points/1.n/: F; !10个客户点; roads(points,points)/ 1,2 2,3 2,5 2,6 2,8 3,4 3,6 3,7 3,8 3,10 4,5 4,6 4,7 4,8 4,9 4,10 5,6 5,7 5,8 5,10 6,7 6,8 6,9 7,8 7,9 7,10 8,9 9,10/: D, P;endsets

15、data:D= 50 30 35 50 60 15 30 50 25 60 45 30 55 20 40 65 60 10 30 55 25 55 35 30 45 60 10 20;enddata F(n)=0; for(points(i) | i #lt# n: F(i)=min(roads(i,j): D(i,j)+F(j);); !显然，如果P(i,j)=1,那么点i到点n的最短路径的第一步是i - j，否那么就不是。 由此，我们就可方便确实定出最短路径; for(roads(i,j): P(i,j)=if(F(i) #eq# D(i,j)+F(j),1,0) );End附录2MODE

16、L:SETS: CUSTOMERS / 1. 10/: U; LINK( CUSTOMERS, CUSTOMERS): DIST,X; ENDSETS DATA: DIST = 0 50 100000 40 25 100000 30 100000 50 100000 50 0 30 100000 35 50 100000 60 10000 100000 100000 30 0 15 100000 30 50 25 100000 60 40 10000 15 0 45 30 55 20 40 65 25 15 100000 45 0 60 10 30 100000 55 100000 50 30

17、 30 60 0 25 55 35 1000000 30 100000 50 100000 10 25 0 30 45 60 100000 60 25 20 30 55 30 0 10 100000 20 100000 100000 40 100000 15 25 45 0 20 35 20 10 45 20 100000 60 100000 30 0;ENDDATA N = SIZE( CUSTOMERS); MIN = SUM( LINK: DIST * X); FOR( CUSTOMERS( K): SUM( CUSTOMERS( I)| I #NE# K: X( I, K) = 1;

18、SUM( CUSTOMERS( J)| J #NE# K: X( K, J) = 1; FOR( CUSTOMERS( J)| J #GT# 1 #AND# J #NE# K: U( J) = U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J) + ( N - 3) * X( J, K) ); ); FOR( LINK: BIN( X); FOR( CUSTOMERS( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1) );END附录3model:sets: CUSTOMERS/ 1.10/: u,D; link

19、( CUSTOMERS, CUSTOMERS):C, x; endsets min = sum( link: C*x); sum(CUSTOMERS( I)| I #ne# 1: x(I, 1)=1; sum(CUSTOMERS( I)| I #ne# 1: x(1,I)=1; FOR( CUSTOMERS(K): sum( CUSTOMERS( I)| I #ne# K: x( I, K)1; sum( CUSTOMERS( J)| J #ne# K: x(K,J)K;sum(link(I,J)|I #ne# J:x(I,J)*D(J)36;sum(link(I,J)|I #ne# J:x(

20、I,J)*D(J)86;for(CUSTOMERS(I):sum(CUSTOMERS(J): x(I,J)-sum(CUSTOMERS(J): x(J,I)=0); for(CUSTOMERS(I)|I #gt# 1:!不走走过的路; for( CUSTOMERS( J)| J#gt#1 #and# I #ne# J: u(I)-u(J)+10*x(I,J)=9); for( link: bin( x); for( link: gin( x);data: D=8,13,6,9,7,15,10,5,12,9; C=0 50 100000 40 25 100000 30 100000 50 100

21、000 50 0 30 100000 35 50 100000 60 100000 100000 100000 30 0 15 100000 30 50 25 100000 60 40 100000 15 0 45 30 55 20 40 65 25 15 100000 45 0 60 10 30 100000 55 100000 50 30 30 60 0 25 55 35 100000 30 100000 50 100000 10 25 0 30 45 60 100000 60 25 20 30 55 30 0 10 100000 20 100000 100000 40 100000 15 25 45 0 20 35 20 10 45 20 100000 60 100000 30 0;enddataend