运输优化模型参考

《运输优化模型参考》由会员分享，可在线阅读，更多相关《运输优化模型参考（11页珍藏版）》请在装配图网上搜索。

1、运输问题摘要本文根据运输公司提供的提货点到各个客户点的路程数据，利用线性规划的优化方法 与动态优化模型最短路径问题进行求解，得到相关问题的模型。针对问题一，我们采用Dijkstra算法，将问题转化为线性规划模型求解得出当运 送员在给第二个客户卸货完成的时，若要他先给客户10送货，此时尽可能短的行使路线 为：V T V T V T V T V，总行程85公里。2 3 8 9 10针对问题二，我们首先利用prim算法求解得到一棵最小生成树：再采用Dijkstra算法求得客户2返回提货点的最短线路为V T V故可得到一条理想的回21路是： V T V T V T V T V TV T V T V T

2、 V T V T V1 5 7 6 3 4 8 9 10 2 1后来考虑到模型的推广性，将问题看作是哈密顿回路的问题，建立相应的线性规划模型求 解，最终找到一条满足条件的较理想的的货车送货的行车路线：V T V T V T V T V TV T V T V T V TV T V 。1 5 7 6 3 4 8 9 10 2 1针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条 件，建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运输方案:两辆车全程总和为295公里（见正文）；然后建立线性规划模型得出二号运输方案：两辆车全程总和为290公里（见正文）；最

3、后再进一步优化所建的线性规划模型，为运输 公司献上一个最优的决策即三号运输方案：车号行车路线线路的长度该车负责的客户一号车135公里2, 3, 4, 5, 8二号车145公里6, 7， 9, 10两辆车全程总和为280公里。针对问题四，我们首先用Dijkstra算法确定提货点到每个客户点间的最短路线，然 后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很 理想的运输方案：车号行车路线车号行车路线号车三号车二号车四号车该方案得到运输总费用是645元。关键字： Dijkstra算法，prim算法，哈密顿回路问题重述某运输公司为10个客户配送货物，假定提货点就在客户1所在

4、的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的（i, j） （i, j = 1,L ,10）位置上的数表示 （其中表示两个客户之间无直接的路线到达）。1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送 货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能 短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个 客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货 点所行使的尽可能短的行使路线？对所设计的算法进行

5、分析。3、现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小 货车的容量为50个单位，每个客户所需要的货物量分别为8， 13， 6， 9， 7， 15， 10， 5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路 线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法 进行分析。4、如果改用更小容量的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第3问， 并假设每出一辆车的出车费为100元，运货的价格为1元/公里（不考虑空车返回的费用），请问如何安 排车辆才能使得运输公司运货的总费用最省？问题1【模型分

6、析与假设】 运送员在给第二个客户卸完货后，即从此处赶到第十个客户处，路程越短越好，是一个最短路径问题，为此我们采用Dijkstra算法，考虑到建模的方便我们将问题转化为线性规划模型进行求 解。下面是一些变量的假设与说明：1. X为0,1变量，其值为1代表行车路线经过第j个客户，为0则代表不经过。ij2. C 为题中给出的邻接矩阵对应位置的值。ij3. 为了表达的方便，将邻接矩阵的第一行与第二行互换,第一列与第二列互换。（因为求的是客户 2至客户10的最短线路，而非提货点至客户10）同时将矩阵中数据0或-用一个足够大的数999 代替。（这是因为目标函数是求最小值）【模型建立与求解】 建立问题的模

7、型（1）是：将其转化为ling。代码（见附录1）后，求解可得以下结果：Global optimal solution found at iteration:19Objective value:85.00000VariableValueReduced CostX( 1, 3)1.00000030.00000X( 3, 8)1.00000025.00000X( 8, 9)1.00000010.00000X( 9, 10)1.00000020.00000至此可以知道，运送员应该走的最好路线是: 总行程为85公里。【模型检验与评价】该模型是基于 Dijkstra 算法的基础上转化为线性规划模型来求最短

8、路径的模型,优点是实现较 简单,也容易求解；但有个令人不是很满意的地方就是其模式固定,要求任两个客户点间最短距离 时,需将其一客户的位置与提货点互换,另一个客户的位置则需与客户10的位置互换,将其看成原始 的提货点到客户 10 最短距离的模型进行求解，这样较为烦琐,有待改进。问题2【模型分析】很明显运输公司分别要对 10 个客户供货，必须访问每个客户，但问题要求我们建立相应模型 寻找一条尽可能短的行车路线，首先不考虑送货员把 10 个客户所需的货送完货后不返回提货点的情形，利用求最小生成树的 prim 算法结合题中所给的邻接矩阵，很快可以得到以下一棵最小生成 树：V1V5以上路线的总行程为17

9、5 公里V7*分利用问题一所建的模V6V3:很快就可以求得V （客户2）返回V （提货点）的最线路是V T 与第二行交换V2第一列与第 路实际上也是最短回路：V行程50公里（注:代用模型（1）时,需先将题中的邻接矩阵的第一行 有理理由相后参照附录1風的代码，我们有理由信这样构成的回述为：*V5V7V6V3该回总行程为225公里。这种寻路方法并不比其他方法差而且它的速度也很快，只是它局限于顶点数较 少的情形，一旦顶点数扩大实现起来难度就会大大提高，而且它的不易推广，因此我们有必要对 此问题用到现实生活中去来实现以不变应【模从上分析知送货员从提货点1出发，要走遍客户2，3，n各至少一次，最后返提研

10、究，进想与假设2起一个数学模 变的现以适应顶点数象。 V8具有较好的推广性，应变化，使/货点 1。为了更方便地建立起模型首先作以下假设与说明1 X 为 0，1 整形变量，其值为 1 代表行车路线经过第 j 个客户，为 0 则代表不经过。 ij2C 为客户 i 到 j 的距离（题中给出的邻接矩阵的数据）。ij3.为了数据的方便处理，先将邻接矩阵中的数据用一个足够大的数999代替。4访问客户i后必须要有一个即将访问的确切客户；访问客户j前必须要有一个刚刚访问 过的确切客户。故我们用以下条件来分别保证我们的假设。到此我们得到了一个模型，它是一个指派问题的整数规划模型。其目标是使式子：兹10 C *X

11、ij ij i=1 j=1在约束条件下取得最小值。5.哈密顿图优化问题5，须添加一个额外变量u（i = 2,3,A ,10），目的是为了更好的防止子巡i回的产生，即须附加一个约束条件： 到现在我就可以建立以下模型对问题求解了。【模型建立与求解】可建立问题的模型（2）为：同样借助数学软件求解可得结果： 从中可以找出一条较为理想的回路是： 可见按此模型求解的结果与采用prim算法求解的结果是一样的。问题3【模型分析与猜想】 用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行 程之和最短，我们假设每个客户的货物都由同一辆货车提供，这样只要找出两条尽可能短 的回路，并保证每条

12、线路客户总需求量在50个单位以内。实际 上这样的两条回路是存在的：由题二得到了一条哈密顿回路 可根据货物需求量的大小将其分为前后两部分，并将之分别构成回路。（注：由于提货点 在客户1所在的位置，故不必考虑为客户1送货的情况。）为了更好地建立模型，先作以下定义:心宀亠人丨V T V , V T V ,V T V ,V T V ,V T V , I八、士丄丄卄右/、亠小/口 ,定义 1：顺序集合N斗1557766334 L代表由模型（2）求解得出|V T V ,V T V ,V T V ,V T V ,V T V I488991010221的哈密顿回路的路径全集（集合中的元素是不可调换的，故称它为

13、顺序集合）；定义2：J函数Get（N ）为集合N中第i个元素终点所对应的下标。（即若i=3,贝V, Get（N ）= 7i3定义3：J函数U（N ）为集合N中第i个元素终点所对客户的货物需求量（即若i=3则iU（N ）= T ）其中（T , （1,2,A ,10）为向量：（8,13,6,9,7,15,10,5,12,9）的第 i 个分量的值）。 3Get （N3 ）i接下来我们设计一个简单的算法来寻找较好的路径：St epl：根据以下模型获得一个值k；St ep2：依k的取值分两条路径：St ep3：利用模型（1 ）分别求得V （）到V的最短路径：V （V以及Get（Nk ）1Get（NK ）

14、1V1 到 VGet （N ）的最短路径：V TAT VGet（N ）K+1K+1Step4：从而获取两辆货车的路线如下表:车号路线号车二号车据上描述可建立模型：依据模型很容易求得：k=5所以根据我们所设计的算法很快找到一组合理的运输路线是车号行车路线号车二号车（因为根据模型（1）很容易可以确定V至V的最短路径是V T V , V至V。的最短路径是414118V TV TV ，但在代用模型（1）的时候须注意的是相应的客户位置的变换，可参照问题 158一的求解决方法。）由此可得两车所行驶的距离之和（单位：公里）：【结果优化】从以上得到的两条行车路线来看，两车得经过经过了客户5，根据算法二号车必客

15、户5才能保证行程较短，而根据模型（1 ）易知路径V T V优于V T V T V，因此可优化一号1 7 1 5 7车路线为：V T V T V T V T V T V，经检验优化后的两条行车路线上客户货物需求量总和分176341别是40与46均不超过货车的容量50，故认为此方案更优，这样我们可以给运输公司提供的号运输方案是：车号行车路线线路的长 度该车负责的客 户号车140公里3,4,6,7二号车155公里2,5, 8, 9,10两辆车全程总和为295公里。很明显，以上猜想得到的模型来求解这一问题，存在着很大的缺陷，那就是没有更好 说服力，不能让人感到很满意，不过这个结果也是很客观的，不会很差

16、。因此我们想通建 立以下模型来弥补这一缺陷。【模型建立与求解】 若对以上猜得到的一种模型不够满意,我们同样可以建立相应的线性规划模型对以上 的运输方案进一步优化,考虑到本问题与问题二有相似之处即要考虑回到提货点的情形,因 此我们可以在模型（2）上进行改进, 在保证二号不超载（不超出容量）的前提下,先确定第一 辆车的最优路径,首先对模型中将会用的变量作一些简单的定义或说明:1. D.为每个客户的需货量，它是在向量（8,13,6,9,7,15,10,5,12,9）的每j个分量，据上分析知:36 世10 X *D 50 （不考虑客户1的需求量,因为它在提货点）。ij ji=1 j =12. 由于这里

17、是分两条路线分别给10个客户送货，就没有必要设计每条路线都能够访问每 个客户点，但要保证送货员能回提货点，且均从提货点出发回到提货点，则送货员进入一个 客户同时也必须出来。故我们用以下条件来分别保证我们的假设：到此我们得到了一个模型，它是一个指派问题的整数规划模型。其目标是使式子：茲10 C *Xijiji=1 j=1 在约束条件下取得最小值。其余变量的假设与问题二的假设一致。故可建立模型（3）如下：在36 Dj 50约束下，参加附录的代码，在1 ing。中求解可得以下结果:K的值满足条件的较短路径（1-1）路径长度（单位：公里）=7不存在符合条件的路径以上可视为确定首先确定的第一辆车的行车方

18、案；则这两条路线所对的第二辆车最优路线的选择，（以长度为95公里的路线为例）只需将模型（3）中的条件：艺X -艺X =0 ij ij j =1j =1与近2 X K 改为条件 Xij = 1（j = 2,3,4,6,10且/ 丰 i）iji =1 j =1即要保证第二辆访问到所有第一辆车未访问过的客户，允许其访问第一辆车访问过的客 户，故模型基本上不用改动。同样参照参加附录3的代码，可求得上述路线对应的另一条 路线为：K的值满足条件的较短路径（2-1）路径长度 （单位：公里）=7不存在符合条件的路径此时我们可以为公司提供一种更好的二号运输方案：车号行车路线线路的长度该车负责的客户一号车135公

19、里4， 5, 8, 9, 10二号车155公里2， 3， 6， 7两辆车全程总和为290公里。【模型优化】从以上产生的结果中很容易，往往第一辆车通过的线路，有些第二辆车也要经过，并不能保证两条线路完全独立，显然这样话，我们可以确定第一辆车的线路的时候让其线路上的货物承受量大一点，两车都经过的让第二辆车去送货，这样模型（3）很可能就存在缺陷了，这是由于对条件：36 艺2 X *D 50的上界进行约束引起的，因此我们可以这个条件的上界放大，给模型有更大 ij ji=1 j =1的自由选择空间，可将它改为： 36 210 210 X *D 86ij ji=1 j =1，再用上述方法可以求解，但此最后

20、形成运输方案的时候应该多考虑另一个因素，即哪些客户的 货物由走哪条线路的货车负责运送，同样地可以得到以下的运输方案：K的值满足条件的较短路径（1-2）路径长度（单位：公里）=595612571358150918510不存在符合条件的路径而计算第二辆车的路径，与模型（3）的计算方法完全一样，其结果如下：K的值满足条件的较短路径（2-2）路径长度(单位：公里)=5205617071458145911010不存在符合条件的路径根据两个表中的路径，进行对比很容易得出一个最优的三号运输方案那就是：车号行车路线线路的长度该车负责的客户一号车135公里2， 3， 4， 5， 8二号车145公里6， 7， 9

21、， 10两辆车全程总和为 280 公里。【结果分析与评价】虽然我们猜想模型很简单，但它是解决本问题的关键，也是我们建模思路的切入点，通过这个 模型的建立与求解我们逐渐发现问题的所在，故而引导我们对自己所建的模型一步一步地优化， 最终得到一个非常理想的三号运输方案，当然我们模型也存在不少问题，例如我们没有用一个统 一的模型来同时得出两辆车的最优路线，这是我们觉得比较郁闷的地方，我们将慢慢地对其不断 改进与完善。问题 4【模型分析与假设】由于出车费 100一辆,相当于 100 公里的行程费用,当行程超200 公里时是否以多出车来换取小 行程呢?我们认为没必要:其一从题中给出的数据阵可以看出行程超过

22、200公里该车至少经过4个客 户点,其总货物需求量超过小车的容量,是不可取的;其二即使可行,但要保证加车后,两辆车总行程 要控制在100公里以内也不是一件容易的事。从此两个原因可以看出我们不必考虑加车的方案，即 根据客户总需求量与货车的容量可决定只派 4 辆车为客户送货即可。为了更好的解决问题，我们首先作一些定义：定义1：集合Lue =,k)(1,i)G, j),A ,(j,k) i, j,k = 2,3,A ,10)代表提货点1到第k个客户的 k最短路径；定义2：J函数LEN Cue)为提货点1到第k个客户的路径长度(单位:公里)；k例如若 则有 其中C , ( j = 2,3,A ,10)

23、代表题中所给的数据阵对应位置的值i , j定义3:J函数UN(Lue )为从提货点1到第k个客户的路经客户所需的货物量的总和;例如若k则有其中(U , 6,2,A ,10)为向量:(8,13,6,9,7,15,10,5,12,9)的第 i 个分量的值)i考虑到每辆车的出发点均是提货点1首先用Dijkstra算法类似问题一分别求得提货点1到各客 户点的最短路径,分别为:Lue = 血5), G,2), Lue = (1,4 ),(4,3), Lue = (1,4),234Lue = (1,5),Lue = (1,7),(7,6) , Lue =(1,7),567Lue =(1,5),(5,8),

24、 Lue =(1,9), Lue =(1,9),(9,10);8 9 10从中可发现不等式：UN(Lue ) 25均成立。从而我们可设计一种比较好的方解决方案如下: kSt epl:初始化集合 N =bue Ik = 2,3, A 10）kStep2:若Lue q Lue（j丰k），则册去Lue，只取路径集Lue，更新集合N；kjjkStep3:若Lue I Lue工（j丰k），将其中一条路径删去子路径Lue I Lue，有以下两种情形:kjkj（i）、先初始化一个临时集合M=N,若删去路径Lue的子路径Lue I Lue更新集合M,将路径k k jLue - Lue I Lue接到集合M中的

25、每个路径上，并以UN Que - Lue I Lue ） 25为条件计算k k j k k j这些路径转到路径Lue -Lue I Lue的最短路径，选出函数LENQue - Lue I Lue ）值最小的k k j k k j一条路径记为 Lue ；k（ii）、先初始化一个临时集合H=N，若删去路径Lue的子路径Lue I Lue更新集合M,将路径jkjLue - Lue I Lue接到集合M中的每个路径上，并以UN（Lue - Lue I Lue ） 25为条件计算jkjjkj这些路径转到路径Lue -Lue I Lue的最短路径，选出函数LENOue -Lue I Lue ）值最小的jk

26、jjkj一条路径记为 Lue ；kSt ep4:比较St ep3中得出（i）与（ii）得出的路径Lue的LEN （Lue ）值的大小，选取小的若（i）的kk小让集合M代替N,否则让集合H代替N。【模型建立与求解】 由分析知可以建立问题的模型（目标函数）：依解决方案，能得出运输公司所派出的4辆车所走的路线及每条线上的货物总需求量如下表：、车号行车路线路线代号（k）货物需求量号车220二号车820三号车625四号车1021显然每条发车路线上的货物总需求量均不会超过货车的容量 25，故方案可行；则公司运货的 总费用：【模型检验】我们设计的解决方案是以Dijkstra算法为基础，以小车容量为约束条件得

27、出的一种解 决问题的方法，从模型分析可以看出我们没有必要去考虑以加车的方法来换取短路线的方 案，因此直接根据客户的总需货量可以知道，至少需要4辆小车来送货。从得出的运输方 案来看，这种办法确实是可行了，且并不会很差。结果分析在问题一中可以看出，这就是一个任意两点的最优路径的问题，若要求两点的最短路 径，只需把其中一个看成起点，另一个看成终点（即问题中的提货点与客户10）,然后套 用模型（1）求解就可得到一条最短路径，这就是Dijks tra算法的运用。从问题二的结果中，可以发现这个问题实质上就是一个旅行商问题，即一个从一个点 出发遍历每个顶点一次仅此一次然后回到起点，它没有一个成熟算法，即得到

28、的结果不一 次是最优的回路，但至少是比较好的了。这类问题还可以用prim算法与Dijkstra算法一 起解决。对于问题三我们先通过常归思维去分析问题，得到的一号运输方案与后面建模得到 二、三号运输方案来看，相差并不是会很大，这也正说明了我们设计的算法也是比较符合 实际的，准确性也是比较高的。对于问题四我们自己设计一个算法来解决问题，得到相应的结果验证了我们算法是可 行的也是可靠的，但是局限性好大，也许这一算法仅适用于这类问题，不过我们将会尽最 大努力地改进。模型评价从我们建立的模型来看，无论是理论上或者是和现实的接近性上，都是比较合理的， 我们主要从模型的假设合理性、建模的创造性、运算的效率和

29、结果的正确性对其作出客观 的评价：首先，我们的假设均考虑客观性合乎情理，模型（1）与模型（2）在现实中也可以广泛 的应用，与现实状况紧密相连；例如：最优路径问题与哈密顿回路问题，在现实生活已经 应运范围很广了。其次是建模的合理性分析，我们的模型的建立，经过很严密的分析，具一般性。再就是模型求解的效率性了，由于本题目的数据量不大，我们的程序运行均能瞬间完 成。最后就是结果的正确性了，通过模型的求解，我们得到与现实很接近的结果，可以说 是合理、正确的。参考文献1 朱德通 最优化模型与实验 同济大学出版社 ，2003年。2 现代应用数学手册 运筹学与最优化理论卷 清华大学出版社。3 殷剑宏 吴开亚

30、图论及其算法 中国科学技术大学出版社 2003年。4 严蔚敏吴伟民数据结构（C语言版） 清华大学出版社。5 姜启源 谢金星 叶俊 数学建摸 高等教育出版社 2003年。附录1 !第1小题目;model:sets:v/1.10/;TL(v,v):c,x;Endsetsmin=sum(TL(I,J):c(I,J)*x(I,J);for(TL(I,J):bin(x(I,J);for(v(I):bin(sum(v(J):x(I,J);for(v(J):bin(sum(v(I):x(I,J);sum(v(J): x(1,J)-sum(v(J): x(J,1)=1;sum( v(J): x(10,J)-s

31、um( v(J): x(J,10)=-1;for(v(I)|I #ne# 1 #and# I #ne# 10:sum(v(J): x(I,J)-sum(v(J): x(J,I)=0);data:c=999 50 30 999 35 60 999 30 999;Enddataend2 !第2小题目;model:sets: !定义集；v / 1. 10/: u;link( v, v):C, x；endsetsn = size( v)；min = sum( link: C* x); !目标函数；FOR( v(K):!开往第K个客户；sum( v( I)| I #ne# K: x( I, K) = 1

32、;sum( v( J)| J #ne# K: x(K,J) = 1; !离开开往第K个客户；);for(v(I)|I #gt# 1 : !不走走过的路；for( v( J)| J#gt#1 #and# I #ne# J: u(I)-u(J)+n*x(I,J)=n-1)；for ( link: bin ( x);!定义X为01变量；for ( link: gin ( x);!定义X为整形变量；data:!这里是数据；C =0 50 999 40 25 999 60 999 30 0;EnddataEnd3 !第3小题目;model:sets: !定义集；v / 1. 10/: u,D;link(

33、 v, v):C,y, x； endsetsmin = sum( link: C*x);sum(v( I)| I #ne# 1: x(I, 1)=1;sum(v( I)| I #ne# 1: x(1,I)=1;FOR( v(K):sum( v( I)| I #ne# K: x( I, K)1;sum( v( J)| J #ne# K: x(K,J)4 sum(link(I,J)|I #ne# J:x(I,J)*D(J)36 sum(link(I,J)|I #ne# J:x(I,J)*D(J)86;for(v(I):sum(v(J): x(I,J)-sum(v(J): x(J,I)=0); for(v(I)|I #gt# 1:!不走走过的路;for( v( 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 999 40 25 999 60 999 30 0;enddataend