运输优化模型参考.docx

运输问题
摘要
本文根据运输公司提供的提货点到各个客户点的路程数据，利用线性规划的优化方法与动态优化模型一一最短路径问题进行求解，得到相关问题的模型。
针对问题一，我们采用Dijkstra算法，将问题转化为线性规划模型求解得出当运送员在给第二个客户卸货完成的时，若要他先给客户10送货，此时尽可能短的行使路线
为：V2V3V8V9Vi0,总行程85公里。
针对问题二，我们首先利用prim算法求解得到一棵最小生成树：
再采用Dijkstra算法求得客户2返回提货点的最短线路为V2Vi故可得到一条理想的回
路是：ViV5V7V6V3V4V8V9V10V2Vi
后来考虑到模型的推广性，将问题看作是哈密顿回路的问题，建立相应的线性规划模型求解，最终找到一条满足条件的较理想的的货车送货的行车路线：
ViV5V7V6V3V4VV9V10V2Vi。
针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条件,
建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运输方案两辆车全程总和为295公里（见正文）；然后建立线性规划模型得出二号运输方案：两辆车全程总和为290公里（见正文）；最后再进一步优化所建的线性规划模型，为运输公司献上一个最优的决策即三号运输方案：
车号
行车路线
线路的长度
该车负责的客户
T车
i35公里
2,3,4,5,8
二号车
i45公里
6,7,9,i0
两辆车全程总和为280公里
针对问题四，我们首先用Dijkstra算法确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案：
车号
行车路线
车号
行车路线
T车
三号车
二号车
四号车
该方案得到运输总费用是645元。
关键字：Dijkstra算法，prim算法，哈密顿回路
问题重述
某运输公司为i0个客户配送货物，假定提货点就在客户i所在的位置，从第i个客
户到第j个客户的路线距离（单位公里）用下面矩阵中的（i,j）（i,j1,L,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元/公里（不
考虑空车返回的费用），请问如何安排车辆才能使得运输公司运货的总费用最省？
问题1
【模型分析与假设】
运送员在给第二个客户卸完货后，即从此处赶到第十个客户处，路程越短越好，是一个最短路
径问题，为此我们采用Dijkstra算法，考虑到建模的方便我们将问题转化为线性规划模型进行求
解。
下面是一些变量的假设与说明：
Xj为0,1变量，其值为1代表行车路线经过第j个客户，为0则代表不经过。
Cj为题中给出的邻接矩阵对应位置的值。
3．为了表达的方便，将邻接矩阵的第一行与第二行互换,第一列与第二列互换。（因为求的是客户
2至客户10的最短线路，而非提货点至客户10）同时将矩阵中数据0或用一个足够大的数
999代替。（这是因为目标函数是求最小值）
【模型建立与求解】
建立问题的模型（1）是：
将其转化为lingo代码（见附录[1]）后，求解可得以下结果：
19
Globaloptimalsolutionfoundatiteration:
Objective value: Variable X( 1, 3) X( 3, 8) X( 8, 9)
X( 9, 10)
Value





Red