0815运输优化模型参考1

运输问题摘要本文根据运输公司提供的提货点到各个客户点的路程数据，利用线性规划的优化方 法与动态优化模型最短路径问题进行求解，得到相关问题的模型。针对问题一 ，我们采用 Dijkstra 算法，将问题转化为线性规划模型求解得出当 运送员在给第二个客户卸货完成的时，若要他先给客户 10 送货，此时尽可能短的行使路线为：V T V T V T V T V，总行程85公里。2 3 8 9 10针对问题二，我们首先利用 prim 算法求解得到一棵最小生成树：V T V T V T V T V T V T V T V T V T V T V1 5 7 6 3 4 8 9 10 2 1再采用Dijkstra算法求得客户2返回提货点的最短线路为V T V故可得到一条理想的21回路是： V T V T V T V T V T V T V T V T V T V T V1 5 7 6 3 4 8 9 10 2 1 后来考虑到模型的推广性，将问题看作是哈密顿回路的问题，建立相应的线性规划模型 求解，最终找到一条满足条件的较理想的的货车送货的行车路线：V TV TV TV TV TV TV TV TV TV TV 。1 5 7 6 3 4 8 9 10 2 1针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条 件，建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运 输方案:两辆车全程总和为 295 公里（见正文）；然后建立线性规划模型得出二号运输方 案：两辆车全程总和为 290 公里（见正文）；最后再进一步优化所建的线性规划模型，为运输公司献上一个最优的决策即三号运输方案：车号行车路线线路的长度该车负责的客户一号车V T V T V T V T V T V T V T V15234891135公里2，3，4，5，8二号车V T V T V T V T V T V1769101145公里6， 7， 9， 10两辆车全程总和为 280 公里。针对问题四，我们首先用 Dijkstra 算法确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一 种很理想的运输方案：车号行车路线车号行车路线号车V T V T V152三号车V T V T V176二号车V T V T V T V1438四号车V T V T V1910该方案得到运输总费用是645元。关键字：Dijkstra 算法, prim 算法,哈密顿回路问题重述某运输公司为 10 个客户配送货物，假定提货点就在客户 1 所在的位置，从第 i 个 客户到第j个客户的路线距离（单位公里）用下面矩阵中的（i, j） （i, j二1, ,10）位置上的 数表示（其中-表示两个客户之间无直接的路线到达）。123456789101-050g4025g30g50g250030g3550g60gg3g30015g305025g60440g15045305520406552515g450601030g556g503030600255535g730g50g102503045608g602520305530010g920gg40g152545020103520104520g60g3001、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户 10 送货，已知送给客户 10的货已在运送员的车上，请帮运送员设计一个到客户 10 的 尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。2、现运输公司派了一辆大的货车为这 10 个客户配送货物，假定这辆货车一次能装满 10 个客户所需要的全部货物，请问货车从提货点出发给 10 个客户配送完货物后再回到 提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。3、现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆 小货车的容量为 50 个单位，每个客户所需要的货物量分别为 8，13，6，9，7，15， 10，5，12，9 个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎 样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设 计的算法进行分析。4、如果改用更小容量的车，每车容量为25 个单位，但用车数量不限，每个客户所需要的货物量同 第3 问，并假设每出一辆车的出车费为100元，运货的价格为1 元/公里（不考虑空车返回的费 用），请问如何安排车辆才能使得运输公司运货的总费用最省？问题 1【模型分析与假设】运送员在给第二个客户卸完货后，即从此处赶到第十个客户处，路程越短越好，是一个最短路径问题，为此我们采用Dijkstra算法，考虑到建模的方便我们将问题转化为线性规划模型进 行求解。面是一些变量的假设与说明：1. X为0, 1变量，其值为1代表行车路线经过第j个客户，为0则代表不经过。ij2. C 为题中给出的邻接矩阵对应位置的值。ij3. 为了表达的方便，将邻接矩阵的第一行与第二行互换,第一列与第二列互换。（因为求的是客 户2至客户10的最短线路，而非提货点至客户10）同时将矩阵中数据0或-用一个足够大 的数 999 代替。（这是因为目标函数是求最小值）【模型建立与求解】建立问题的模型（1）是：目标函数：min Z = KY C * Xij ij i=1 j =1(=1,2,10)Y10 X=1ijY1j0=1X=1i=1X= 0或1(0,1变量)ijY10 XY10 Xijijj =1j =1(j = 1,2,10)1= 10i = 1i = 10i 丰 1,10将其转化为ling。代码（见附录1）后，求解可得以下结果:1985.00000Global optimal solution found at iteration:Objective value:VariableValueReduced CostX（ 1， 3）1.00000030.00000X（ 3， 8）1.00000025.00000X（ 8， 9）1.00000010.00000X（ 9， 10）1.00000020.00000至此可以知道，运送员应该走的最好路线是:V T V T V T V T V2 3 8 9 10总行程为 85 公里。【模型检验与评价】该模型是基于Dijkstra算法的基础上转化为线性规划模型来求最短路径的模型，优点是实 现较简单,也容易求解；但有个令人不是很满意的地方就是其模式固定,要求任两个客户点间最 短距离时，需将其一客户的位置与提货点互换，另一个客户的位置则需与客户10的位置互换，将 其看成原始的提货点到客户10最短距离的模型进行求解，这样较为烦琐，有待改进。问题2模型分析】很明显运输公司分别要对 10个客户供货，必须访问每个客户，但问题要求我们建立相应模 型寻找一条尽可能短的行车路线，首先不考虑送货员把10 个客户所需的货送完货后不返回提货 点的情形，利用求最小生成树的 prim 算法结合题中所给的邻接矩阵，很快可以得到以下一棵最 小生成树：VIV5V6V3V7V2V1V9V8V4以上路线的总行程为175公里，充分利用问题一所建的模型，很快就可以求得V （客户2）返2回V （提货点）的最线路是V T V行程50公里（注:代用模型（1）时，需先将题中的邻接矩阵的1 2 1第一行与第二行交换,第一列与第二列交换后参照附录1的代码可求解），我们有理由相信这样 构成的回路实际上也是最短回路：该回路可描述为：V T V T V T V T V T V T V T V T V T V T V1 5 7 6 3 4 8 9 10 2 1总行程为 225 公里。这种寻路方法并不比其他方法差而且它的速度也很快，只是它局限于顶点 数较少的情形，一旦顶点数扩大实现起来难度就会大大提高，而且它的不易推广，因此我们有 必要对此问题深入研究，进而建立起一个数学模型以适应顶点数变化，使它能够具有较好的推 广性，应用到现实生活中去来实现以不变应万变的现象。【模型的猜想与假设】从上分析知送货员从提货点1出发，要走遍客户2, 3,，n各至少一次，最后返 提货点 1。为了更方便地建立起模型首先作以下假设与说明：1X 为 0， 1 整形变量，其值为 1 代表行车路线经过第 j 个客户，为 0则代表不经过。 ij2C 为客户 i 到 j 的距离（题中给出的邻接矩阵的数据）。ij3.为了数据的方便处理，先将邻接矩阵中的数据-用一个足够大的数999代替。 4访问客户 i 后必须要有一个即将访问的确切客户；访问客户 j 前必须要有一个刚刚 访问过的确切客户。故我们用以下条件来分别保证我们的假设。Y x 二 1, i 二 1, 2,nijj=1Y x = 1,j = 1, 2,niji=1到此我们得到了一个模型，它是一个指派问题的整数规划模型。其目标是使式子：玆10 C * X ij ij i=1 j =1 在约束条件下取得最小值。5哈密顿图优化问题5,须添加一个额外变量u(i = 2,3,。)，目的是为了更好的防止子i巡回的产生，即须附加一个约束条件：u 一 u + n x n 一 1,2 i 丰 j ni jij到现在我就可以建立以下模型对问题求解了。模型建立与求解】可建立问题的模型(2)为：目标函数：min Z =昱工C * Xi=1昱X = 1ij丈X =iji=1X= 0或1ijX e Niju 一 u + n * Xi n 一 1 i(2 i 丰 j V （ ） T V1Get（N ）Get（N ）11k二号车V T 一T V （）T V （）T 一T V1Get（NK+!）Get（NK+2）1据上描述可建立模型：目标 : maxk艺U（N ） 50条件：z （k = 1,2,9）艺U（N ） 50iI i=1依据模型很容易求得：k=5所以根据我们所设计的算法很快找到一组合理的运输路线是：车号行车路线号车VT V TVT VT VT VT V1576341二号车VT V TVT VT VT VT V15891021（因为根据模型（1）很容易可以确定V至V的最短路径是V T V , V至V的最短路径是4 1 4 1 1 8V T V T V ,但在代用模型（1 ）的时候须注意的是相应的客户位置的变换，可参照问 158题一的求解决方法。）由此可得两车所行驶的距离之和（单位：公里）：Len = Len（L ）+ Len（L ）=（25 +10 + 25 + 30 +15 + 40）+（25 + 30 +10 + 20 + 20 + 50）=300【结果优化】从以上得到的两条行车路线来看，两车得经过经过了客户5，根据算法二号车必客户5才能保证行程较短，而根据模型（1 ）易知路径V T V优于V T V T V，因此可优化一 17157号车路线为： V TV TV TV TV TV ，经检验优化后的两条行车路线上客户货物需求 176341量总和分别是40与46均不超过货车的容量50，故认为此方案更优，这样我们可以给运输公 司提供的一号运输方案是：车号行车路线线路的长 度该车负责的客 户号车V T V T V T V T V T V176341140公里3,4,6,7二号车V T V T V T V T V T V T V15891021155公里2,5, & 9,10两辆车全程总和为295公里。很明显，以上猜想得到的模型来求解这一问题，存在着很大的缺陷，那就是没有更 好说服力，不能让人感到很满意，不过这个结果也是很客观的，不会很差。因此我们想 通建立以下模型来弥补这一缺陷。【模型建立与求解】若对以上猜得到的一种模型不够满意,我们同样可以建立相应的线性规划模型对以 上的运输方案进一步优化,考虑到本问题与问题二有相似之处即要考虑回到提货点的情 形,因此我们可以在模型（2）上进行改进, 在保证二号不超载（不超出容量）的前提下,先 确定第一辆车的最优路径,首先对模型中将会用的变量作一些简单的定义或说明:1. D 为每个客户的需货量，它是在向量（8,13,6,9,7,15,10,5,12,9）的每j个分量，据上分析 j知:36 22 X *D 50 （不考虑客户1的需求量,因为它在提货点）。ij ji=1 j=12.由于这里是分两条路线分别给 10 个客户送货，就没有必要设计每条路线都能够访问 每个客户点，但要保证送货员能回提货点，且均从提货点出发回到提货点，则送货员进入 一个客户同时也必须出来。故我们用以下条件来分别保证我们的假设：20 X 1 (j = 1,2,10) iji=1210 X= 1与210 X=11, ji,1j=2i=22 X 1 ( = 1,2,10)ij2 x 2 x =0ijijj=1j=1到此我们得到了一个模型，它是一个指派问题的整数规划模型。其目标是使式子：22 10 C * X ij ij i=1 j =1 在约束条件下取得最小值。其余变量的假设与问题二的假设一致。故可建立模型（3）如下：目标函数：min Z =昱工C * Xij ij j=1(=1,2,10)i=1艺X 1ij龙 X 1 iji=X1 = 0或1ijX e Niju 一 u + n * Xi n 一 1 G i R 0i = 1,2,1036 艺另 X *D Kiji=1 j=1艺 X = 1,艺 X =11, ji,1j=2（j = 1,2,10）G,i变量）龜型变量）K的值满足条件的较短路径（1T）路径长度（单位：公里）=7不存在符合条件的路径在36 Dj K 改为条件 Xij = 1（j = 2,3,4,6,10且j 丰 i）ijijijj =1j =1i=1 j =1即要保证第二辆访问到所有第一辆车未访问过的客户，允许其访问第一辆车访问过的客 户，故模型基本上不用改动。同样参照参加附录3的代码，可求得上述路线对应的另一 条路线为：K的值满足条件的较短路径（2-1）路径长度 （单位：公里）=7不存在符合条件的路径此时我们可以为公司提供一种更好的二号运输方案：车号行车路线线路的长度该车负责的客户一号车V T V T V T V T V T V T V14891051135公里4， 5， 8， 9， 10二号车V T V T V T V T V T V T V1523671155公里2，3，6，7两辆车全程总和为290公里。【模型优化】从以上产生的结果中很容易，往往第一辆车通过的线路，有些第二辆车也要经过，并不能保证 两条线路完全独立，显然这样话，我们可以确定第一辆车的线路的时候让其线路上的货物承受 量大一点，两车都经过的让第二辆车去送货，这样模型（3）很可能就存在缺陷了，这是由于对 条件：36 艺卫X *D 50的上界进行约束引起的，因此我们可以这个条件的上界放大，给模 ij ji=1 j=1型有更大的自由选择空间，可将它改为：36 艺另X *D 86ij j i=1 j=1，再用上述方法可以求解，但此最后形成运输方案的时候应该多考虑另一个因素，即哪些客户 的货物由走哪条线路的货车负责运送，同样地可以得到以下的运输方案：K的值满足条件的较短路径（1-2）路径长度（单位：公里）=5V T V T V T V T V T V157891956V T V T V T V T V T V T V15238911257V T V T V T V T V T V T V T V152348911358V T V T V T V T V T V T V T V T V1752348911509V T V T V T V T V T V T V T V T V T V1752348910118510不存在符合条件的路径而计算第二辆车的路径，与模型（3）的计算方法完全一样，其结果如下：K的值满足条件的较短路径（2-2）路径长度（单位：公里）=5V T V T V T V T V T V T V T V T V15234691012056V T V T V T V T V T V T V T V1764891011707V T V T V T V T V T V17691011458V T V T V T V T V T V17691011459V T V T V T V T V1769111010不存在符合条件的路径根据两个表中的路径，进行对比很容易得出一个最优的三号运输方案那就是：车号行车路线线路的长度该车负责的客户一号车V T V T V T V T V T V T V T V15234891135公里2，3，4，5，8二号车V T V T V T V T V T V1769101145公里6， 7， 9， 10两辆车全程总和为 280 公里。【结果分析与评价】虽然我们猜想模型很简单，但它是解决本问题的关键，也是我们建模思路的切入点，通过这 个模型的建立与求解我们逐渐发现问题的所在，故而引导我们对自己所建的模型一步一步地优 化，最终得到一个非常理想的三号运输方案，当然我们模型也存在不少问题，例如我们没有用 一个统一的模型来同时得出两辆车的最优路线，这是我们觉得比较郁闷的地方，我们将慢慢地 对其不断改进与完善。问题 4【模型分析与假设】由于出车费100一辆,相当于100公里的行程费用,当行程超200公里时是否以多出车来换取 小行程呢?我们认为没必要:其一从题中给出的数据阵可以看出行程超过200公里该车至少经过4 个客户点,其总货物需求量超过小车的容量 ,是不可取的;其二即使可行,但要保证加车后 ,两辆 车总行程要控制在 100 公里以内也不是一件容易的事。从此两个原因可以看出我们不必考虑加 车的方案，即根据客户总需求量与货车的容量可决定只派 4 辆车为客户送货即可。为了更好的解决问题，我们首先作一些定义：定义1： 集合Lue =,k)(1,i),G, j),(j,k)i, j,k = 2,3,弋表提货点1到第k个客户k的最短路径；定义 2：例如若函数LENCue )为提货点1到第k个客户的路径长度(单位:公里)；kLue = (1,5 ), (5,4), (4,3)3则有LENCue )= C + C + C31,55,44,3其中C , ( j = 2,3,.,10)代表题中所给的数据阵对应位置的值i,j定义 3：函数UN Cue )为从提货点1到第k个客户的路经客户所需的货物量的总和;例如若kLue = (1,5 ), (5,4), (4,3)3则有UN Cue )= U + U + U3543其中(U ,i(1,2,.,10)为向量：(8,13,6,9,7,15,10,5,12,9)的第 i 个分量的值)考虑到每辆车的出发点均是提货点1首先用Dijkstra算法类似问题一分别求得提货点1到各客户点的最短路径,分别为:Lue = 紅5), (5,2 ), Lue =紅4)(4,3), Lue = 紅4),234Lue = 紅5), Lue =紅7 )(7,6), Lue =血7),567Lue =6,5),(5,8), Lue = (1,9), Lue = (1,9),(9,10);8 9 10种比较好的方解决方案如下：从中可发现不等式：UN(Lue ) 25均成立。从而我们可设计kSt epl:初始化集合 N = bue Ik = 2,3,.10kStep2: 若 Lue 二 Lue(j 丰 k), 则册去Lue，只取路径集Lue，更新集合N；kjjkStep3:若Lue ALue鼻(j主k)，将其中一条路径删去子路径Lue A Lue，有以下两种情形:kjkjA Lue ) 25为条件j、先初始化一个临时集合M=N，若删去路径叫的子路径Luekn皿更新集合M，将路径Lue - Lue A Lue接到集合M中的每个路径上, kkj计算这些路径转到路径Lue -Lue ALue的最短路径，选出函数LENCue - Lue A Lue ）值k k j k k j最小的一条路径记为Lue ；k（ii）、先初始化一个临时集合H=N,若删去路径Lue的子路径Lue ALue更新集合M,将路j k j径Lue -Lue ALue接到集合M中的每个路径上，并以UNue -Lue ALue ） 25为条件j k j j k j计算这些路径转到路径Lue -Lue ALue的最短路径，选出函数LENCue - Lue A Lue ）值j k j j k j最小的一条路径记为 Lue ；kSt ep4:比较St ep3中得出（i）与（ii）得出的路径Lue的LEN（Lue ）值的大小，选取小的若（i）kk的小让集合M代替N,否则让集合H代替N。模型建立与求解】由分析知可以建立问题的模型（目标函数）：min Z 二 400 + LEN Cue ）k依解决方案，能得出运输公司所派出的4辆车所走的路线及每条线上的货物总需求量如下表：车号行车路线路线代号（k）Luek货物需求量UN Gue ）k号车V T V T V152220二号车V T V T V T V1438820三号车V T V T V176625四号车V T V T V19101021显然每条发车路线上的货物总需求量均不会超过货车的容量 25，故方案可行；则公司运货 的总费用：Z 二 400 + LENGue ）+ LEN Cue ）+ LEN Gue ）+ LEN Gue ）1 8 6 10二 400 + 40 + 80 + 55 + 70 二 645模型检验】我们设计的解决方案是以Dijkstra算法为基础，以小车容量为约束条件得出的一种 解决问题的方法，从模型分析可以看出我们没有必要去考虑以加车的方法来换取短路线 的方案，因此直接根据客户的总需货量可以知道，至少需要4辆小车来送货。从得出的 运输方案来看，这种办法确实是可行了，且并不会很差。结果分析在问题一中可以看出，这就是一个任意两点的最优路径的问题，若要求两点的最短 路径，只需把其中一个看成起点，另一个看成终点(即问题中的提货点与客户 10),然 后套用模型(1)求解就可得到一条最短路径，这就是Dijks tra算法的运用。从问题二的结果中，可以发现这个问题实质上就是一个旅行商问题，即一个从一个 点出发遍历每个顶点一次仅此一次然后回到起点，它没有一个成熟算法，即得到的结果 不一次是最优的回路，但至少是比较好的了。这类问题还可以用prim算法与Dijkstra 算法一起解决。对于问题三我们先通过常归思维去分析问题，得到的一号运输方案与后面建模得到 二、三号运输方案来看，相差并不是会很大，这也正说明了我们设计的算法也是比较符 合实际的，准确性也是比较高的。对于问题四我们自己设计一个算法来解决问题，得到相应的结果验证了我们算法是 可行的也是可靠的，但是局限性好大，也许这一算法仅适用于这类问题，不过我们将会 尽最大努力地改进。模型评价从我们建立的模型来看，无论是理论上或者是和现实的接近性上，都是比较合理的， 我们主要从模型的假设合理性、建模的创造性、运算的效率和结果的正确性对其作出客 观的评价：首先，我们的假设均考虑客观性合乎情理，模型(1)与模型(2)在现实中也可以广 泛的应用，与现实状况紧密相连；例如：最优路径问题与哈密顿回路问题，在现实生活 已经应运范围很广了。其次是建模的合理性分析，我们的模型的建立，经过很严密的分析，具一般性。再就是模型求解的效率性了，由于本题目的数据量不大，我们的程序运行均能瞬间 完成。最后就是结果的正确性了，通过模型的求解，我们得到与现实很接近的结果，可以说是合理、正确的。参考文献1 朱德通 最优化模型与实验 同济大学出版社 ， 2003 年。2 现代应用数学手册 运筹学与最优化理论卷 清华大学出版社。3 殷剑宏 吴开亚 图论及其算法 中国科学技术大学出版社 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)-sum( 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;Enddata end2 !第2小题目;model:set s: !定义集；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；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( 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)4sum(link(I,J)|I #ne# J:x(I,J)*D(J)36sum(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; enddata end