配送问题模型
一、摘要
本文通过给出运输公司为十个客户配送货物，从第i个客户到第j个客户的路线距离（单位公里），求出最短的路径，即最短路径法。
针对问题一、二，要求出第i个客户到第j个客户的最短路径。这个问题可以使用图论的方法解决。我们分别用1,2 ，…，10十个点表示从第i个客户到第j个客户的位置，
再把所有的点对都用边连接起来，边（i，j）上赋以数值w ij,它表示从第i个客户到第j 个客户的距离。因此使用Dijkstra(迪杰斯特拉)算法求出这个问题的最优策略，得到最短距离。Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运输方案:两辆车全程总和为295公里；然后建立线性规划模型得出二号运输方案：两辆车全程总和为290公里；最后再进一步优化所建的线性规划
针对问题四，我们首先用Dijkstra算法确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行
该方案得到运输总费用是645元。
关键词：Dijkstra(迪杰斯特拉)算法最短路径
二、问题重述
某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的
i j=位置上的数表示（其中∞表示两个客户之间无直接的路线到(,)
i j(,1,,10)
达）。
123456789101050
4025
30
50250030355060
330015305025
604401504530552040655251545060103055650303060025553573050102503045608602520305530010920401525450201035
201045206030
0∞
∞
∞
∞⎡⎢∞∞∞
∞⎢⎢∞∞∞
⎢∞⎢⎢∞∞⎢∞∞⎢⎢∞∞⎢∞∞⎢∞∞∞∞∞⎣⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎢⎥⎢⎥⎢⎥⎦
图（一）
分别解决以下问题：
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元/公里（不考虑空车返回的费用），请问如何安排车辆才能使得运输公司运货的总费用最省？
四、 问题分析
对于问题一，它是在运送员给第二个客户卸货完成的时候，才临时接到新的调度通知，让他先给客户10送货，并且送给客户10的货已在运送员的车上，为了帮运送员设计一个到客户10的尽可能短的行驶路线。所以，可以考虑用图论的方法来解决。在这里，我们分别用1,2，…，10十个点表示这十个客户所在的位置，并根据矩阵中的信息将其有路线的点连接起来，边（i,j ）(i,j=1,2,…，10)上赋予数值w ij 它表示从第i 个客户到第j 个客户的总路程。因此我们可以画出运送员的路线选择图，再运用Dijkstra 算法求出这个问题的最短的行驶路线。
对于问题二，它所要求的是货车从提货点出发给10个客户配送完货物后再回到提货点所行驶的尽可能短的行驶路线。因此可以类似地运用问题一的解决方法来进行求解。 方案一： 方案二：
⎪⎪⎩
⎪
⎪⎨===⋯==-
25
0}10,32{s },1{15
51w l l s ）（）（
，， ⎪⎪⎩
⎪
⎪⎨===⋯==-
25
0}10,32{s },1{15
51w l l s ）（）（
，， ⎪⎪⎩
⎪
⎪⎨⎧=====-
25
0}109,8,6,4,32{s },7{76
67w l l s ）（）（
，， ⎪⎪⎩
⎪
⎪⎨⎧=====-
10
0}109,8,7,6,4,3,2{s },5{57
75w l l s ）（）（
， ⎪⎪⎩
⎪
⎪⎨⎧=====-
30
0}109,8,4,32{s },6{63
36w l l s ）（）（
，， ⎪⎪⎩
⎪
⎪⎨⎧=====-
30
0}109,8,4,32{s },6{64
46w l l s ）（）（
，， ⎪⎪⎩
⎪
⎪⎨⎧=====-
15
0}109,8,4,2{s },3{34
43w l l s ）（）（
， ⎪⎪⎩
⎪
⎪⎨⎧=====-
15
0}109,8,3,2{s },4{43
34w l l s ）（）（
， ⎪⎪⎩
⎪
⎪⎨⎧=====-
20
}109,82{s },4{48
84w l l s ）（）（，， ⎪⎪⎩
⎪
⎪⎨⎧=====-
25
0}109,82{s },3{38
83w l l s ）（）（
，， ⎪⎪⎩
⎪
⎪⎨⎧=====-
10
0}109,2{s },8{89
98w l l s ）（）（
， ⎪⎪⎩
⎪
⎪⎨⎧=====-
10
0}109,2{s },8{89
98w l l s ）（）（
， ⎪⎪⎩
⎪
⎪⎨⎧=====-
20
0}10,2{s },9{10
.9109w l l s ）（）（
⎪⎪⎩
⎪
⎪⎨⎧=====-
20
0}10,2{s },9{10
.9109w l l s ）（）（
