GLPK ： OTSP提供"has no primal feasible solution"

Question

我正在做一个OTSP问题，它给了我"问题没有原始可行的解决方案"

问题很简单。该计划涉及使用送货车辆向客户提供服务，该计划确定最佳路线（短距离）以满足客户的需求，以便每辆送货车辆在不超出其容量的情况下满足客户的需求。

set Rep;    # Dealer vehicles
set Cli;
param cantCli;
param cantRep;
param dem { Cli };
param capacRep { Rep };
param coordxCli { Cli };
param coordyCli { Cli };
param distCli { i in Cli , j in Cli : i != j } := sqrt((coordxCli[i] - coordxCli[j])^2 + (coordyCli[i] - coordyCli[j])^2); # Distance
var X { i in Cli, j in Cli , k in Rep : i != j }, binary;       # Variable of route (used arcs)
var u { i in Cli :i != 'rep' } >= 0;                            # To delete de subroutes
var visitRep { i in Cli , k in Rep },binary;                    # 1 if dealer vehicle k visit client i.

s.t. R1 { j in Cli , k in Rep : j != 'rep' } : sum { i in Cli : i != j } X[i,j,k] = 1;      # Just enter 1 arc on each client
s.t. R2 { i in Cli , k in Rep : i != 'rep' } : sum { j in Cli : i != j } X[i,j,k] = 1;      # Just 1 arc leaves each client
s.t. R3 { k in Rep } : sum { i in Cli , j in Cli : j == 'rep' and i != j } X[i,j,k] <= cantRep;     # All the dealer vehicles must enter to the 'rep' (depot)
s.t. R4 { k in Rep } : sum { i in Cli , j in Cli : i == 'rep' and i != j } X[i,j,k] <= cantRep;     # All the dealer vehicles must leave the 'rep' (depot)
s.t. R5 { i in Cli , j in Cli , k in Rep : i != 'rep' and j != 'rep' and i != j } : u[j] - u[i] + capacRep[k] * (1 - X[i,j,k]) >= 1;    # Delete subroutes
s.t. R6 { i in Cli : i != 'rep' } : sum { k in Rep } visitRep[i,k] = 1;                     # Each client is visited only once
s.t. R7 { k in Rep } : sum { i in Cli : i!= 'rep' } dem[i] <= capacRep[k];                  # The capacity of the dealer vehicle must not be exceeded
minimize Z { k in Rep } : sum { i in Cli , j in Cli  : i != j } distCli[i,j] * X[i,j,k];
solve;
for { k in Rep , i in Cli, j in Cli : i != j and  X[i,j,k] == 1 } {
    printf " %s  %5s %5s %8s  n",i,j,k,X[i,j,k];
}
data;
param cantCli := 8;
param cantRep := 3;
param : Rep : capacRep :=           # The dealer Vehicles
        'Rep1'  80
        'Rep2'  150
        'Rep3'  100;
# Clients and their choords
param : Cli : coordxCli  coordyCli dem :=
        'rep'   20  0   40
        'c1'    40  200 30
        'c2'    150 -50 20
        'c3'    60  100 50
        'c4'    80  150 20
        'c5'    120 50  30
        'c6'    150 100 30
        'c7'    200 120 10
        'c8'    250 50  40;
end;

注意：目前代码用于 TSP + 总线路由 ，但目标是 OTSP + 总线路由。

这是代码。提前谢谢你

Answer 1

它是你的约束编号 7 s.t. R7，它会导致你的问题变得不可行。

所有客户需求的总和应低于或等于相应的汽车容量。虽然总需求是230但车辆的最大容量仅限于80，100和150。这似乎是不可行的。