运输问题 摘要
本文主要是研究优化运输的问题。通过对十个客户两两之间的距离表进行分析并画出网络路线图，运用图与网络和最优化的方法建立相关数学模型，利用Lingo软件和Matlab软件进行计算，得出最优的行走路线。
针对问题一，求解单程最短路线问题，鉴于数据的有限性本文首先采用穷举法（枚举法）进行选定节点的单条路线分析，得到在给第二个客户卸完货时，到达客户10的最短路线，最后运用Dijkstra（迪杰斯特拉）算法进行检验，通过Lingo软件运行得到最短路程，与所求完全相同。
针对问题二，本文首先结合问题一所求最短路线进行分析，将双目标规划简化为单目标规划，并运用逐次逼近法对所给数据进行分析，获得最短的行驶路线。最后运用枚举法进行检验，发现所得数据一致。结果为：
V1?V5?V7?V6?V3?V4?V8?V9?V10?V2?V1
针对问题三，本文直接利用问题二得一辆车的最优回路，以货车容量为限制条件，建立相应的规划模型，设计了一个简单的寻路算法，最终确立合理的一号运输方案，经过模型检验，获得最优的二号方案，以下为一二号方案对比结果： 车号 行车路线 线路的长度 该车负责的客户 一号车 2，3，4，5，8 135公里 V1?V5?V2?V3?V4?V8?V9?V1 二号车 V1?V7?V6?V9?V10?V1 145公里 6，7，9，10 针对问题四，我们首先用Dijkstra算法确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案： 车号 行车路线 车号 行车路线 一号车 三号车 V1?V5?V2 V1?V7?V6 二号车 V1?V4?V3?V8 四号车 V1?V9?V10 该方案得到运输总费用是645元。
关键词; Dijkstra算法 枚举法 逐次逼近法
1.问题重述
运输问题关心的是以最低的总配送成本把供应中心(出发地)的任何产品运送到每一个接收中心(目的地)。每一个出发地都有一定供应量配送到目的地,每一个目的地都需要一定的需求量。每一个出发地都有一个固定的供应量, 所有的供应量都必须配送到目的地。与之类似,每一个目的地都有一个固定的需求量, 整个需求量都必须由出发地满足。某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的(i,j)(i,j?1,?,10)位置上的数表示（其中?表示两个客户之间无直接的路线到达）。
1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。
2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。
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符号说明
Cij--------------------------------------------------------从i点到j点
5.模型分析与求解
5.1针对问题一的模型建立与求解 5.1.1最短路问题
最短路问题是网络理论中最广泛的用法之一，许多优化问题可以使用这个模型，如设备更新、管道铺设、线路安排、厂区布局等。最短路问题的动态规划问题，是解决某些比较困难最短路问题（如道路不能整齐分段者）构造动态规划方程，使用二图论方法比较有效。
最短路问题的一般提法如下：设G=（V,E）为连通图，图中各边（vi,vj）有权lij（lij=?表示vi,vj间无边）vi,vj为图中任意两点，求一条道路?，使它是从vs到vt的
所有路中总权最小的路。即：lu?(vi,vj)???lij最小。
有些最短路问题也可以是求网格中某指定点道奇余所有节点的最短路，或求网络中任意两点间的最短路。下面我们介绍三种算法，可分别用于求解这几种最短路问题。
.5.1.2模型建立与求解
根据原数据求得各个客户之间的路线图；
图1、各个客户之间的路线图
根据题目可知运送员是在给第二个客户卸货完成的时候，而客户1被假设为提货点，因此本文将客户1作为第二个客户的可能性排除。由上图各个客户的路线图分析可得；以下三类情况。 建立模型如下；
目标函数:minZ???Cij?Xiji?1j?11010?10??Xij?1?i?1,2,?,10?j?1?10?Xij?1?j?1,2,?,10? ???i?1条件:?Xij?0或1?0,1变量???1i?1?1010?X?X????1i?10?ijij??j?1j?1?0i?1,10???（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算法,其时间复杂度为O?n3?,虽然与重复执行