运输问题研究.doc

运输问题 摘要 本文主要是研究优化运输的问题。通过对十个客户两两之间的距离表进行分析并画出网络路线图，运用图与网络和最优化的方法建立相关数学模型，利用Lingo软件和Matlab软件进行计算，得出最优的行走路线。 针对问题一，求解单程最短路线问题，鉴于数据的有限性本文首先采用穷举法（枚举法）进行选定节点的单条路线分析，得到在给第二个客户卸完货时，到达客户10的最短路线，最后运用Dijkstra（迪杰斯特拉）算法进行检验，通过Lingo软件运行得到最短路程，与所求完全相同。 针对问题二，本文首先结合问题一所求最短路线进行分析，将双目标规划简化为单目标规划，并运用逐次逼近法对所给数据进行分析，获得最短的行驶路线。最后运用枚举法进行检验，发现所得数据一致。结果为： 针对问题三，本文直接利用问题二得一辆车的最优回路，以货车容量为限制条件，建立相应的规划模型，设计了一个简单的寻路算法，最终确立合理的一号运输方案，经过模型检验，获得最优的二号方案，以下为一二号方案对比结果： 车号 行车路线 线路的长度 该车负责的客户 一号车 135公里 2，3，4，5，8 二号车 145公里 6，7，9，10 针对问题四，我们首先用Dijkstra算法确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案： 车号 行车路线 车号 行车路线 一号车 三号车 二号车 四号车 该方案得到运输总费用是645元。 关键词; Dijkstra算法 枚举法 逐次逼近法 1.问题重述 运输问题关心的是以最低的总配送成本把供应中心(出发地)的任何产品运送到每一个接收中心(目的地)。每一个出发地都有一定供应量配送到目的地,每一个目的地都需要一定的需求量。每一个出发地都有一个固定的供应量, 所有的供应量都必须配送到目的地。与之类似,每一个目的地都有一个固定的需求量, 整个需求量都必须由出发地满足。某运输公司为10个客户配送货物，从第i个客户到第j个客户的距离用下面矩阵中的位置上的数表示表示两个客户之间无直接的路线到达）。 运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。 现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。 现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法进行分析。 如果改用更小容量的车，每车容量为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.问题假设 每个出发地都有一定的供应量配送到目的地； 每个目的地都有一个固定的需求量； 从出发地到任何一个目的地的运送成本固定； 不考虑货物的装卸成本； 不考虑货物在运输途中的损坏情况； 4符号说明 --------------------------------------------