运输问题摘要 本文根据运输公司提供的提货点到各个客户点的路程数据，利用线性规划的优化方法与动态优化模型——最短路径问题进行求解，得到相关问题的模型。

针对问题一 ，我们采用Dijkstra 算法，将问题转化为线性规划模型求解得出当运送员在给第二个客户卸货完成的时，若要他先给客户10送货，此时尽可能短的行使路线为：109832V V V V V →→→→，总行程85公里。

针对问题二，我们首先利用prim 算法求解得到一棵最小生成树：再采用Dijkstra 算法求得客户2返回提货点的最短线路为12V V →故可得到一条理想的回路是：121098436751V V V V V V V V V V V →→→→→→→→→→后来考虑到模型的推广性，将问题看作是哈密顿回路的问题，建立相应的线性规划模型求解，最终找到一条满足条件的较理想的的货车送货的行车路线：121098436751V V V V V V V V V V V →→→→→→→→→→。

针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运输方案:两辆车全程总和为295公里（见正文）；然后建立线性规划模型得出二号运输方案：两辆车全程总和为290公里（见正文）；最后再进一步优化所建的线性规划模型，为运输公针对问题四，我们首先用Dijkstra 算法确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理该方案得到运输总费用是645元。

关键字：Dijkstra 算法, prim 算法, 哈密顿回路问题重述某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i 个客户到第j个客户的路线距离（单位公里）用下面矩阵中的(,)i j(,1,,10)i j=位置上的数表示（其中∞表示两个客户之间无直接的路线到达）。

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算法，考虑到建模的方便我们将问题转化为线性规划模型进行求解。

下面是一些变量的假设与说明：X为0，1变量，其值为1代表行车路线经过第j个客户，为0则代表不经过。

1．ijC为题中给出的邻接矩阵对应位置的值。

2．ij3．为了表达的方便，将邻接矩阵的第一行与第二行互换,第一列与第二列互换。

（因为求的是客户2至客户10的最短线路，而非提货点至客户10）同时将矩阵中数据0或∞用一个足够大的数999代替。

（这是因为目标函数是求最小值）【模型建立与求解】建立问题的模型(1)是：将其转化为lingo代码（见附录[1]）后，求解可得以下结果：Global optimal solution found at iteration: 19Objective value: 85.00000Variable Value Reduced CostX( 1, 3) 1.000000 30.00000X( 3, 8) 1.000000 25.00000X( 8, 9) 1.000000 10.00000X( 9, 10) 1.000000 20.00000至此可以知道，运送员应该走的最好路线是:总行程为85公里。

【模型检验与评价】该模型是基于Dijkstra算法的基础上转化为线性规划模型来求最短路径的模型,优点是实现较简单,也容易求解；但有个令人不是很满意的地方就是其模式固定,要求任两个客户点间最短距离时,需将其一客户的位置与提货点互换,另一个客户的位置则需与客户10的位置互换,将其看成原始的提货点到客户10最短距离的模型进行求解，这样较为烦琐,有待改进。

问题2【模型分析】很明显运输公司分别要对10个客户供货，必须访问每个客户，但问题要求我们建立相应模型寻找一条尽可能短的行车路线，首先不考虑送货员把10个客户所需的货送完货后不返回提货点的情2V （客户2）返回1V从上分析知送货员从提货点1出发，要走遍客户2，3，…，n 各至少一次，最后返提货点1。

为了更方便地建立起模型首先作以下假设与说明：1．ij X 为0，1整形变量，其值为1代表行车路线经过第j 个客户，为0则代表不经过。

2．ij C 为客户i 到j 的距离（题中给出的邻接矩阵的数据）。

3．为了数据的方便处理，先将邻接矩阵中的数据∞用一个足够大的数999代替。

4．访问客户i 后必须要有一个即将访问的确切客户；访问客户j 前必须要有一个刚刚访问过的确切客户。

故我们用以下条件来分别保证我们的假设。

到此我们得到了一个模型，它是一个指派问题的整数规划模型。

其目标是使式子：∑∑==*101101i j ij ij X C在约束条件下取得最小值。

5．哈密顿图优化问题[5]，须添加一个额外变量()10,,3,2 =i u i ，目的是为了更好的防止子巡回的产生，即须附加一个约束条件：到现在我就可以建立以下模型对问题求解了。

【模型建立与求解】可建立问题的模型(2)为：同样借助数学软件求解可得结果：从中可以找出一条较为理想的回路是：可见按此模型求解的结果与采用prim 算法求解的结果是一样的。

问题3【模型分析与猜想】用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短，我们假设每个客户的货物都由同一辆货车提供，这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内。

实际上这样的两条回路是存在的：由题二得到了一条哈密顿回路可根据货物需求量的大小将其分为前后两部分，并将之分别构成回路。

（注：由于提货点在客户1所在的位置，故不必考虑为客户1送货的情况。

）为了更好地建立模型，先作以下定义:『定义1：』 顺序集合⎭⎬⎫⎩⎨⎧→→→→→→→→→→=1221010998844336677551,,,,,,,,,V V V V V V V V V V V V V V V V V V V V N 代表由模型(2)求解得出的哈密顿回路的路径全集（集合中的元素是不可调换的，故称它为顺序集合）；『定义2：』 函数()i N Get 为集合N 中第i 个元素终点所对应的下标。

（即若i=3，则，()73=N Get ） 『定义3：』 函数()i N U 为集合N 中第i 个元素终点所对客户的货物需求量（即若i=3则())(33N Get T N U =）其中（()10,,2,1, i T 为向量: ()9,12,5,10,15,7,9,6,13,8的第i 个分量的值）。

接下来我们设计一个简单的算法来寻找较好的路径：Step1：根据以下模型获得一个值k ；Step2：依k 的取值分两条路径：Step3：利用模型(1)分别求得()k N Get V 到1V 的最短路径：()1V V K N Get →→ 以及1V 到()1+K N Get V 的最短路径：()11+→→K N Get V V依据模型很容易求得：k=5（因为根据模型(1)很容易可以确定4V 至1V 的最短路径是14V V →，1V 至8V 的最短路径是851V V V →→，但在代用模型(1)的时候须注意的是相应的客户位置的变换，可参照问题一的求解决方法。

）由此可得两车所行驶的距离之和（单位：公里）：【结果优化】从以上得到的两条行车路线来看，两车得经过经过了客户5，根据算法二号车必客户5才能保证行程较短，而根据模型(1)易知路径71V V →优于751V V V →→，因此可优化一号车路线为：143671V V V V V V →→→→→，经检验优化后的两条行车路线上客户货物需求量总和分别是40与46均不超过货车的容量50，故认为此方案更优，这样我们可以给运输公司提供的一号很明显，以上猜想得到的模型来求解这一问题，存在着很大的缺陷，那就是没有更好说服力，不能让人感到很满意，不过这个结果也是很客观的，不会很差。

因此我们想通建立以下模型来弥补这一缺陷。

【模型建立与求解】若对以上猜得到的一种模型不够满意,我们同样可以建立相应的线性规划模型对以上的运输方案进一步优化,考虑到本问题与问题二有相似之处即要考虑回到提货点的情形,因此我们可以在模型(2)上进行改进, 在保证二号不超载(不超出容量)的前提下,先确定第一辆车的最优路径,首先对模型中将会用的变量作一些简单的定义或说明:1．j D 为每个客户的需货量,它是在向量()9,12,5,10,15,7,9,6,13,8的每j 个分量,据上分析知:5036101101≤*≤∑∑==j i j ij D X(不考虑客户1的需求量,因为它在提货点)。

2．由于这里是分两条路线分别给10个客户送货,就没有必要设计每条路线都能够访问每个客户点,但要保证送货员能回提货点,且均从提货点出发回到提货点，则送货员进入一个客户同时也必须出来。

故我们用以下条件来分别保证我们的假设：到此我们得到了一个模型，它是一个指派问题的整数规划模型。

其目标是使式子：∑∑==*101101i j ij ij X C在约束条件下取得最小值。

其余变量的假设与问题二的假设一致。

故可建立模型（3）如下：在5036≤≤j D约束下，参加附录[3]的代码，在lingo 中求解可得以下结果：路线的选择，（以长度为95公里的路线为例）只需将模型（3）中的条件：0101101∑∑===-j j ij ij X X与∑∑==≥101101i j ij K X 改为条件()i j j Xij ≠==且10,6,4,3,21即要保证第二辆访问到所有第一辆车未访问过的客户，允许其访问第一辆车访问过的客户，故模型基本上不用改动。