运输问题研究Word文档格式.doc
《运输问题研究Word文档格式.doc》由会员分享，可在线阅读，更多相关《运输问题研究Word文档格式.doc（20页珍藏版）》请在冰点文库上搜索。
3、现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。
每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？
4、如果改用更小容量的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第3问，并假设每出一辆车的出车费为100元，运货的价格为1元/公里（不考虑空车返回的费用），请问如何安排车辆才能使得运输公司运货的总费用最省？
2.问题分析
2.1对问题一的分析
运送员到客户10的最短路程，首先运用数据分析，得到各个客户之间的连通图，并且将第二个用户分别假设为2、3、4、5、6、7、8、9，再运用穷举法对所给路线进行最优选择，通过Lingo软件计算出各个不同客户到客户10的最短路。
2.2对问题二的分析
本文结合第一问，将双目标规划简化为单目标规划，首先运用逐次逼近法对所给数据进行分析，通过逐次筛选，获得最短的出发路线，然后将最后一个目的地看做起始点，以始发地看做目的地，求得其最短路程。
2.3对问题三的分析
对于问题三我们先通过常归思维去分析问题，得到的一号运输方案并与后面建模得到二、三号运输方案比较，两者相差不大，随后本文运用逐步筛选的算法，得到最优路线。
同时，这正说明了我们设计的算法是比较符合实际的，准确性是比较高的。
2.4对问题四的分析
对于问题四本文设计一个算法来解决问题，得到相应的结果验证了我们算法是可行的也是可靠的，但是局限性好大，也许这一算法仅适用于这类问题，不过我们将会尽最大努力地改进。
3.问题假设
（1）每个出发地都有一定的供应量配送到目的地；
（2）每个目的地都有一个固定的需求量；
（3）从出发地到任何一个目的地的运送成本固定；
（4）不考虑货物的装卸成本；
（5）不考虑货物在运输途中的损坏情况；
4符号说明
--------------------------------------------------------从i点到j点
5.模型分析与求解
5.1针对问题一的模型建立与求解
5.1.1最短路问题
最短路问题是网络理论中最广泛的用法之一，许多优化问题可以使用这个模型，如设备更新、管道铺设、线路安排、厂区布局等。
最短路问题的动态规划问题，是解决某些比较困难最短路问题（如道路不能整齐分段者）构造动态规划方程，使用二图论方法比较有效。
最短路问题的一般提法如下：
设G=（V,E）为连通图，图中各边（）有权（=表示间无边）为图中任意两点，求一条道路，使它是从到的所有路中总权最小的路。
即：
最小。
有些最短路问题也可以是求网格中某指定点道奇余所有节点的最短路，或求网络中任意两点间的最短路。
下面我们介绍三种算法，可分别用于求解这几种最短路问题。
.5.1.2模型建立与求解
根据原数据求得各个客户之间的路线图；
图1、各个客户之间的路线图
根据题目可知运送员是在给第二个客户卸货完成的时候，而客户1被假设为提货点，因此本文将客户1作为第二个客户的可能性排除。
由上图各个客户的路线图分析可得；
以下三类情况。
建立模型如下；
（1）由客户2到客户10，共有5种路线，如下图：
由客户4到客户10，有一种，如下图；
由客户7到客户10，有两种，如下图；
由图分析可知：
假设由客户2出发则到达客户10时，最短路为2-3-8-9-10，总路程为85；
同理可知，假设由客户3出发则到达客户10时，最短路为3-8-9-10，总路程为55；
假设由客户4出发到达客户10，最短路为4-8-9-10；
总路程为50；
假设由客户5出发到达客户10，最短路为5-10，总路程为55；
假设由客户6出发到达客户10，最短路为6-9-10，总路程为55；
假设由客户7出发到达客户10，最短路为7-10，总路程为60；
假设由客户8出发到达客户10，最短路8-9-10；
总路程为30；
假设由客户9出发到达客户10，最短路为9-10，总路程20；
5.1.3模型检验
Dijkstra（迪杰斯特拉）算法是图论中确定最短路的基本方法,也是其它算法的基础。
为了求出赋权图中任意两结点之间的最短路径,通常采用两种方法。
一种方法是每次以一个结点为源点,重复执行Dijkstra算法n次。
另一种方法是由Floyd于1962年提出的Floyd算法,其时间复杂度为,虽然与重复执行Dijkstra算法n次的时间复杂度相同,但其形式上略为简单,且实际运算效果要好于前者。
Dijkstra算法基本步骤③：
令：
并令：
1、对，求。
2、求得，使=
令
3、若则已找到到的最短路距离，否则令从中删去转1
这样经过有限次迭代则可以求出到的最短路线，可以用一个流程图来表示：
第一步先取意即到的距离为0,而是对所赋的初值。
第二步利用已知,根据对进行修正。
第三步对所有修正后的求出其最小者。
其对应的点是所能一步到达的点中最近的一个,由于所有。
因此任何从其它点中转而到达的通路上的距离都大于直接到的距离,因此就是到的最短距离,所以在算法中令并从s中删去,若k=n则就是到的最短路线,计算结束。
否则令回到第二步,继续运算,直到k=n为止。
这样每一次迭代,得到到一点的最短距离,重复上述过程直到。
Floyd算法的基本原理和实现方法为:
如果一个矩阵其中表示与间的距离,若与间无路可通,则为无穷大。
与间的最短距离存在经过与间的和不经过两种情况,所以可以令,n（n为节点数）。
检查与的值,在此,与分别为目前所知的到与到的最短距离,因此,就是到经过的最短距离。
所以,若有,就表示从出发经再到的距离要比原来的到距离短,自然把到的重写成。
每当一个搜索完,就是目前到的最短距离。
重复这一过程,最后当查完所有时,就为到的最短距离。
运用迪杰斯特拉方法，通过Lingo软件求解得到如下数据：
（程序见附录）
通过检验求得结果相同，因此可以证明以上答案；
5.2针对问题二的模型建立与求解
5.2.1模型分析
很明显运输公司分别要对10个客户供货，必须访问每个客户，但问题要求我们建立相应模型寻找一条尽可能短的行车路线，首先不考虑送货员把10个客户所需的货送完货后不返回提货点的情形，利用求最小生成树的prim算法结合题中所给的邻接矩阵，很快可以得到以下一棵最小生成树：
1
5
7
6
9
8
4
3
10
2
以上路线的总行程为175公里，充分利用问题一所建的模型
（1）,很快就可以求得（客户2）返回（提货点）的最线路是行程50公里（注:
代用模型
（1）时,需先将题中的邻接矩阵的第一行与第二行交换,第一列与第二列交换后参照附录[1]的代码可求解），我们有理由相信这样构成的回路实际上也是最短回路：
1000000000000
该回路可描述为：
总行程为225公里。
这种寻路方法并不比其他方法差而且它的速度也很快，只是它局限于顶点数较少的情形，一旦顶点数扩大实现起来难度就会大大提高，而且它的不易推广，因此我们有必要对此问题深入研究，进而建立起一个数学模型以适应顶点数变化，使它能够具有较好的推广性，应用到现实生活中去来实现以不变应万变的现象。
5.2.2模型建立与求解
可建立问题的模型
（2）为：
同样借助数学软件求解可得结果：
从中可以找出一条较为理想的回路是：
可见按此模型求解的结果与采用prim算法求解的结果是一样的。
5.2.3模型检验
在程序设计中，有时会用到由若干个有限数据元素组成的集合，程序中某个变量取值仅限于集合中的元素。
此时，可将这些数据集合定义为枚举类型。
因此，枚举类型是某类数据可能取值的集合：
下面为运用枚举法求解所得到的数据；
一种方式；
第二种方式：
通过总路程对比可知，两种方法所得数据相同，因此可以证明此结论正确；
5.3针对问题三的模型建立与求解
5.3.1模型的猜想
用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短，我们假设每个客户的货物都由同一辆货车提供，这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内。
实际
上这样的两条回路是存在的：
由题二得到了一条哈密顿回路
可根据货物需求量的大小将其分为前后两部分，并将之分别构成回路。
（注：
由于提货点在客户1所在的位置，故不必考虑为客户1送货的情况。
）
（1）由此思想建立以下模型
Step1：
根据以下模型获得一个值k；
Step2：
依k的取值分两条路径：
Step3：
利用模型
（1）分别求得到的最短路径：
以及
到的最短路径：
Step4：
从而获取两辆货车的路线如下表：
路线
据上描述可建立模型；
依据模型很容易求得：
k=5
所以根据我们所设计的算法很快找到一组合理的运输路线是：
（2）模型优化
由上知，两辆车都经过了客户5，根据算法二号车必经过客户5，因此将一号车进行优化可得如下所示；
140公里
3,4,6,7
155公里
2,5,8,9,10
两辆车全程总和为295公里。
5.3.2模型建立与求解
用两辆容容量相等的货车为这10个客户分配货物，要求使行驶的路线尽量最短，因此本文运用问题二所求得的最短行驶路线，进行假设分析；
同样本文建立线性规划模型对运输方案进一步优化，并且将问题简化为单目标，首先确定第一辆车的最优行驶路线，再将模型进行简化定义和说明；
1．为每个客户的需货量,它是在向量的每j个分量,据上分析知:
（不考虑客户1的需求量,因为它在提货点）。
2．由于这里是分两条路线分别给10个客户送货,就没有必要设计每条路线都能够访问每个客户点,但要保证送货员能回提货点,且均从提货点出发回到提货点，则送货员进入一个客户同时也必须出来。
故我们用以下条件来分别保证我们的假设：
到此我们得到了一个模型，它是一个指派问题的整数规划模型。
其目标是使式子：
在约束条件下取得最小值。
其余变量的假设与问题二的假设一致。
故可建立模型（3）如下：
在约束下，参加附录[3]的代码，在lingo中求解可得以下结果：
K的值
满足条件的较短路径（1-1）
路径长度（单位：
公里）
<
=5
95
135
>
=7
不存在符合条件的路径
……
以上可视为确定首先确定的第一辆车的行车方案；
则这两条路线所对的第二辆车最优路线的选择，（以长度为95公里的路线为例）只需将模型（3）中的条件：
与改为条件
即要保证第二辆访问到所有第一辆车未访问过的客户，允许其访问第一辆车访问过的客户，故模型基本上不用改动。
同样参照参加附录[3]的代码，可求得上述路线对应的另一条路线为：
满足条件的较短路径（2-1）
路径长度
（单位：
205
155
此时我们可以为公司提供一种更好的二号运输方案：
4，5，8，9，10
2，3，6，7
两辆车全程总和为290公里。
5.3.3模型检验
从以上产生的结果中很容易，往往第一辆车通过的线路，有些第二辆车也要经过，并不能保证两条线路完全独立，显然这样话，我们可以确定第一辆车的线路的时候让其线路上的货物承受量大一点，两车都经过的让第二辆车去送货，这样模型（3）很可能就存在缺陷了，这是由于对条件：
的上界进行约束引起的，因此
们可以这个条件的上界放大，给模型有更大的自由选择空间，可将它改为：
，再用上述方法可以求解，但此最后形成运输方案的时候应该多考虑另一个因素，即哪些客户的货物由走哪条线路的货车负责运送，同样地可以得到以下的运输方案：
满足条件的较短路径（1-2）
125
150
185
而计算第二辆车的路径，与模型（3）的计算方法完全一样，其结果如下：
满足条件的较短路径（2-2）
170
145
110
根据两个表中的路径，进行对比很容易得出一个最优的三号运输方案那就是：
两辆车全程总和为280公里。
5.4问题四的模型建立与求解
5.4.1模型的假设
由于出车费100一辆,相当于100公里的行程费用,当行程超200公里时是否以多出车来换取小行程呢?
我们认为没必要:
其一从题中给出的数据阵可以看出行程超过200公里该车至少经过4个客户点,其总货物需求量超过小车的容量,是不可取的;
其二即使可行,但要保证加车后,两辆车总行程要控制在100公里以内也不是一件容易的事。
从此两个原因可以看出我们不必考虑加车的方案，即根据客户总需求量与货车的容量可决定只派4辆车为客户送货即可。
（1）假设派四辆车运送货物；
分析，首先将10个地点分成4条路线去完成，即每条线路行驶的路程最短，货物量不得超过25各单位，每辆车的出车费为100元，每公里的路程为1元，（不考虑空车返回时的费用），计算费用最优；
5.4.2模型建立
由问题可知，十个客户总的货物需求量为94个单位，每辆货车最多承载25个单位，假设每辆货车只是送一趟货，而且尽量使每辆车在运输过程中经过的站点不重复，那么至少需要的货车数为。
因此本文首先以四辆车进行送货尝试，除去固定的出车费用外要求总的运输成本最小，则该问题可以转化为寻求每辆车所行驶的最短路径问题。
设为每辆车行驶的路线，每条路线经过的站点且有其中为所有的客户站点，为第条路线前一个站点到第站点距离，为每条路线的最短距离。
引入0—1变量，建立的最优化模型：
根据该解决方案，利用Lingo软件可以得出运输公司所派出的4辆车所走的路线及每条线上的货物总需求量如下表：
路线总长度
货物需求量
40
20
80
55
25
70
21
显然每条发车路线上的货物总需求量均不会超过货车的容量25，故方案可行；
则公司运货的总费用：
（元）
5.4.3模型的检验
由以上分析可得若派出四辆车，则最小费用为645元，但是问题当中没有对时间进行限制，因此，我们也可假设只雇用一辆车，按以上运输方案进行运输，如下表所得;
则最小费用为c=100+40+80+55+70=345（元）；
6.模型评价
6.1模型的优点
本文从模型建立来看，无论是理论值还是实际值都比较接近，而且我们从模型的假设到模型的创新，以及方法运用上都是合理的，因此可以说明本文实际运用性比较强，可以与用于其他问题的研究和求解。
首先，该模型是基于Dijkstra算法的基础上转化为线性规划模型来求最短路径的模型,优点是实现较简单,也容易求解；
其次，虽然我们猜想模型很简单，但它是解决本问题的关键，也是我们建模思路的切入点，通过这个模型的建立与求解我们逐渐发现问题的所在，故而引导我们对自己所建的模型一步一步地优化，最终得到一个非常理想的运输方案
最后，我们设计的解决方案是以Dijkstra算法为基础，以小车容量为约束条件得出的一种解决问题的方法，从模型分析可以看出我们没有必要去考虑以加车的方法来换取短路线的方案，因此直接根据客户的总需货量可以知道，至少需要4辆小车来送货。
从得出的运输方案来看，这种办法确实是可行了，且并不会很差。
6.2模型的缺点
首先本文有个令人不是很满意的地方就是其模式固定,要求任两个客户点间最短距离时,需将其一客户的位置与提货点互换,另一个客户的位置则需与客户10的位置互换,将其看成原始的提货点到客户10最短距离的模型进行求解，这样较为烦琐,有待改进。
其次，本文模型也存在不少问题，例如我们没有用一个统一的模型来同时得出两辆车的最优路线，这是我们觉得比较郁闷的地方，我们将慢慢地对其不断改进与完善。
6.3模型的推广
最短路径问题在交通网络结构的分析，交通运输线路（公路、铁路、河流航运线、航空线、管道运输线路等）的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。
在很多目标信息引导系统的设计中．需要获得最优化路径引导信息。
例如，在日益增多的高层建筑、大型公共建筑（超级市场、博物馆、医院、游乐场等）场台的火灾事故现场救生疏导系统，需要根据现场情况动态地为逃生者实时提供最短的安全通道指引信息；
而当这些场合发生盗窃、抢劫等突发犯罪事件时，安全监控系统如能为警方实时提供通向罪犯所处位置最短搜索路径信息．则可以达到迅速制止犯罪的目的。
在设计一个大型高层建筑火灾事故现场救生疏导系统时，将图论中Dijkstra算法应用于目标信息引导系统的设计中，通过Dijkstra算法，首先计算出任一指定位置点距各疏导出口的最短路径树，进而通过编制辅助方向指示箭头程序．动态地将火灾事故现场救生疏导路径引导图加以显示，从而达到优化目标引导路径的目的．
7.参考文献
【1】卜月华图论及其应用南京：
东南大学出版社，2000
【2】最短路问题在运输网络中的应用李玲2006
【3】戴文舟.交通网络中最短路径算法的研究[D].重庆大学硕士学位论文,2004.
【4】荣玮.基于道路网的最短路径算法的研究与实现.武汉理工大学硕士学位论文[D],2005.
【5】朱建青,张国梁.数学建模方法M.郑州大学出版社.
【6】杨民助,运筹学M.西安交通大学出版社.
【7】殷剑宏,吴开亚.图论及其算法M.中国科学技术出版社.
【8】王朝瑞.图论M.国防工业出版社.
【9】姚思瑜.数学规划与组合优化M.浙江大学出版社.
【10】秦裕瑗,秦明复.运筹学简明教材M.高等教育出版社.
8.附录
附录一
求解问题一
n=9;
a=zeros（n）;
a（1,2）=30;
a（1,4）=35;
a（1,5）=50;
a（1,7）=60;
a（2,3）=15;
a（2,5）=30;
a（2,6）=50;
a（2,7）=25;
a（2,9）=60;
a（3,4）=45;
a（3,5）=30;
a（3,6）=55;
a（3,7）=20;
a（3,8）=40;
a（3,9）=65;
a（4,5）=60;
a（4,6）=10;
a（4,7）=30;
a（4,9）=55;
a（5,6）=25;
a（5,7）=55;
a（5,8）=35;
a（6,7）=30;
a（6,8）=45;
a（6,9）=60;
a（7,8）=10;
a（8,9）=20;
a=a+a'
;
M=max（max（a））*n^2;
%M为充分大的正实数
a=a+（（a==0）-eye（n））*M;
path=zeros（n）;
fork=1:
n
fori=1:
forj=1:
ifa（i,j）>
a（i,k）+a（k,j）
a（i,j）=a（i,k）+a（k,j）;
path（i,j）=k;
end
a,path
a=
03045355045556585
30015553050253555
45150453050203050
升级会员 