可以用运筹学命题解决收派路径中最短距离的问题

elbobby

可以用运筹学命题解决收派路径中最短距离的问题
运筹学命题中，有关于货郎担原理，有一个串村走户卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄，问应如何选择行走路线，能使总的行程最短。我觉得这个问题可以很快引申到我们收派员的收派路径的问题，有一些收派员会有固定的收派线路，首先背包从网点出发，经过若干个客户，再回到网点，到底哪条线路是最短的，最省时省力的，笔者从中总结和解算出一些案例，跟大家分享一下。
模型：
某收派员有3个客户，上午要从1网点出发，要经过2、3、4客户，哪些线路是最短的？




并且已知各自距离矩阵：



问题需要解出收派员从1出发，经历三个客户的最短距离和线路？
解题思路：
  现在将问题一般化，设有n个客户，以1，2，3…..表示之。dij表示从i客户到j客户的距离，一个收派员从网点1出发到其他每个客户去一次且仅仅是一次，然后回来网点1，问他如何选择收派的路线，使总的路程最短，这个问题属于组合最优化的问题，当n不太大时，利用动态规划方法求解是很方便的。
由于规定收派员是从网点1到i客户的中间客户集合。
定义最优函数fk(I,S)为网点1开始经由k个中间客户的S集合到i客户的最短路线的距离，则可写出动态规划的递推关系为
fk(I,S)=min[fk-1(j,S\{j})+dji]
(k=1,2…..,n-1。i=2,3,….,n。)
边界条件为f0(i, Φ)= d1i
Pk(i,S)为最优决策函数，它表示从网点1开始经k个中间客户的S集合到i客户的最短路线上紧挨着i城前面的那个客户。
解：
  由边界条件可知
   f0=(2,Φ)=d12=300,  f0(3, Φ)=d13=450, f0(4, Φ)=d14=200
   当k=1时，即从1网点开始，中间经过一个客户到达i客户的最短距离是
  f1(2,{3})=f0(3, Φ)+d32=450+500=950
  f1(2,{4})=f0(4, Φ)+d42=200+250=450
  f1(3,{2})=f0(2, Φ)+d23=300+600=900
  f1(3,{4})=f0(4, Φ)+d43=200+550=750
  f1(4,{2})=f0(2, Φ)+d24=300+300=600
  f1(4,{3})=f0(3, Φ)+d34=450+650=1100

   当k=2时，即从1网点开始，中间经过两个客户（它们的顺序随便）到达i客户的最短距离是
f2(2,{3,4})=min[f1(3,{4})+d32, f1(4,{3})+d42]
           =min[750+500,1100+250]
           =min[1250,1350]
           =1250
          所以p2(2,{3,4})=3
f2(3,{2,4})=min[f1(2,{4})+d23,f1(4,{2})+d43]
            =min[450+600,600+550]
            =min[1050,1150]
            =1050
          所以p2(3,{2,4})=2
f2(4,{2,3})=min[f1(2,{3})+d24,f1(3,{2})+d34]
           =mim[950+300,900+650]
           =min[1250,1550]
           =1250
         所以p2(4,{2,3})=2

  当k=3时，即从1网点开始，中间经过三个客户（顺序随便），回到点部的最短距离是
  f3(1,{2,3,4})=min[f2(2,{3,4})+d24,f2(3,{2,4})+d31,f2(4,{2,3})+d41]
            =min(1250+200,1050+400,1250+150)
            =min[1450,1450,1400]
            =1400
       所以p3(1,{2,3,4})=4
所以无论怎么走，最短距离肯定是1400M，最短收派路线为1>3>2>4>1.

独酌