GLPK는 : OTSP이 부여 내가 OTSP 문제를하고 있어요

Question

"더 원시적 가능한 솔루션이 없다"그것은

문제는 간단하다 "문제는 원초적 가능한 솔루션이 없다"저를 제공합니다. 이 프로그램은 배달 차량을 사용하여 고객에게 제공하는 프로그램을 다루며 프로그램은 고객의 요구를 충족시키는 최적의 경로 (단거리)를 결정하여 각 배달 차량이 용량을 초과하지 않고 고객의 요구를 제공합니다.

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로 제한됩니다. 그건 불가능할 것 같다.