GLPK: OTSP Gives не имеет изначального возможного решения

Я выполняю задачу 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 + Bus, но целью является маршрутизация OTSP + Bus.

Вот код. заранее спасибо


person olavidps    schedule 26.01.2017    source источник


Ответы (1)


Это ваше ограничение номер 7 s.t. R7, которое делает вашу проблему невыполнимой.

Сумма всех требований Клиента должна быть меньше или равна соответствующей Вместимости Автомобиля. Пока суммарный спрос равен 230, максимальная вместимость транспортных средств ограничена 80, 100 и 150. Это кажется невозможным.

person Paul G.    schedule 27.01.2017