vrp 问题 如何做lingo方案

catmice

某大型超市，有120个分店，一个仓库，80辆车，地图路径算已知，没有时间**，每日各分店需求d，仓库有充足货源，求每日最优车辆安排表。

catmice

下面是一个简单的vrp linggo 示例


MODEL:



! The Vehicle Routing Problem (VRP);



SETS:

! Q(I) is the amount required at city I,

   U(I) is the accumulated delivers at city I ;

  CITY/1..8/: Q, U;



! DIST(I,J) is the distance from city I to city J

   X(I,J) is 0-1 variable: It is 1 if some vehicle

   travels from city I to J, 0 if none;

  CXC( CITY, CITY): DIST, X;

ENDSETS



DATA:

! city 1 represent the common depo;

  Q  =  0    6    3    7    7   18    4    5;



! distance from city I to city J is same from city

   J to city I distance from city I to the depot is

   0, since the vehicle has to return to the depot;



  DIST =  ! To City;

! Chi  Den Frsn Hous   KC   LA Oakl Anah   From;

     0  996 2162 1067  499 2054 2134 2050!Chicago;

     0    0 1167 1019  596 1059 1227 1055!Denver;

     0 1167    0 1747 1723  214  168  250!Fresno;

     0 1019 1747    0  710 1538 1904 1528!Houston;

     0  596 1723  710    0 1589 1827 1579!K. City;

     0 1059  214 1538 1589    0  371   36!L. A.;

     0 1227  168 1904 1827  371    0  407!Oakland;

     0 1055  250 1528 1579   36  407    0;!Anaheim;



! VCAP is the capacity of a vehicle ;

  VCAP = 18;

ENDDATA



! Minimize total travel distance;

  MIN = @SUM( CXC: DIST * X);



! For each city, except depot....;

  @FOR( CITY( K)| K #GT# 1:



! a vehicle does not traval inside itself,...;

    X( K, K) = 0;



! a vehicle must enter it,... ;

    @SUM( CITY( I)| I #NE# K #AND# ( I #EQ# 1 #OR#

     Q( I) + Q( K) #LE# VCAP): X( I, K)) = 1;



! a vehicle must leave it after service ;

    @SUM( CITY( J)| J #NE# K #AND# ( J #EQ# 1 #OR#

     Q( J) + Q( K) #LE# VCAP): X( K, J)) = 1;



! U( K) is at least amount needed at K but can't

   exceed capacity;

    @BND( Q( K), U( K), VCAP);



! If K follows I, then can bound U( K) - U( I);

    @FOR( CITY( I)| I #NE# K #AND# I #NE# 1:

     U( K) >= U( I) + Q( K) - VCAP + VCAP *

      ( X( K, I) + X( I, K)) - ( Q( K) + Q( I))

       * X( K, I);

    );



! If K is 1st stop, then U( K) = Q( K);

    U( K) <= VCAP - ( VCAP - Q( K)) * X( 1, K);



! If K is not 1st stop...;

    U( K)>= Q( K)+ @SUM( CITY( I)|

     I #GT# 1: Q( I) * X( I, K));

  );



! Make the X's binary;

  @FOR( CXC: @BIN( X));



! Minimum no. vehicles required, fractional

   and rounded;

  VEHCLF = @SUM( CITY( I)| I #GT# 1: Q( I))/ VCAP;

  VEHCLR = VEHCLF + 1.999 -

   @WRAP( VEHCLF - .001, 1);



! Must send enough vehicles out of depot;

  @SUM( CITY( J)| J #GT# 1: X( 1, J)) >= VEHCLR;

END

jim123liu

学习一下，谢谢！。。。。。。。。。

hupanfeng

谢谢楼主~~~~~~~~~~~~~~~~~~~~~~~~~

yiza

回复 catmice 的帖子


    楼主帮我看看我的程序错在哪了，谢谢！
model:

sets:
!required(i)表示每个站点的货物需求量,accumulated(i)表示在完成i站点的服务后，前面所有服务累计的货物量;
point/1..4/:required,accumulated;

!distance(i,j)站点i和站点j之间的距离，flag（i，j）表示汽车运输顺序，取值0和1;
cxc(point,point):distance,flag;
endsets

data:
!汽车容量;
vehicle_cap = 20;

required = 30 11 12 9;

!站点之间的距离矩阵;
distance = 0  4  6  8
           4  0  1  9
           6  1  0  2
           8  9  2  0;
enddata

!目标函数;
min = @sum(cxc:distance*flag);

!汽车不能在城市内部运输;
@for(point(i)|i#gt#1:flag(i,i)=0;

!两个点之间能够实现运输的条件;
@sum(point(i)|i#ne#k#and#(i#eq#1#or#required(i)+required(k)#le#vehicle_cap):flag(i,k))=1;

!每个站点同一辆车进去，同一辆车出去;
@sum(point(j)|j#ne#k#and#(j#eq#1#or#required(j)+required(k)#le#vehicle_cap):flag(k,j))=1;

!累积的货物量的值的边界;
@bnd(required(k),accumulated(k),vehicle_cap);

!如果站点i服务完后服务k点，那么k点的累计货物量应该满足以下条件;
@for(point(i)|i#ne#k#and#i#ne#1:accumulated(k)>=accumulated(i)+required(k)- vehicle_cap + vehicle_cap*(flag(i,k)+flag(k,i))-(required(i)+required(k))*flag(k,i);
);

!如果k点是服务的第一个点;
accumulated(k)<= vehicle_cap-(vehicle_cap-required(k))*flag(1,k);

!如果k不是服务的第一点;
accumulated(k)>= required(k)+ @sum(point(i)|i#ge#1:required(i)*flag(i,k));
);

!确定flag的取值为0或1;
@for(cxcBIN(flag));

!最小化汽车的使用数量;
vehicle_number = @sum(point(i)|i#ge#1:required(i))/vehicle_cap;

vehicle_real = vehicle_number + 1.999 - @wrap(vehicle_number - 0.001,1);

!需要满足所有客户的汽车数目;
@sum(point(j)|j#gt#1:flag(1,j))>= vehicle_real;

end

yinfeng0814

catmice 发表于 2009-11-20 13:36
下面是一个简单的vrp linggo 示例

我把这些代码复制到LINGO里，报错了啊

liyunan220

是啊 谁还有关于vrp的lingo程序啊 谢谢了 我从http://www.madio.net/forum.php?mod=viewthread&tid=165944 下载过后找不到在哪了 奇怪

苏小北923

很好用  谢谢楼主~~~