VRP гетерогенная сайт-зависимость

Question

В моем коде мне удалось реализовать различные типы транспортных средств (я думаю) и указать зависимость от сайта. Однако, похоже, что в результате моей оптимизации транспортные средства могут проехать более одного маршрута. Я хотел бы реализовать, что мое транспортное средство, как только оно возвращается в депо (узел 0), что новое транспортное средство назначается для выполнения другого маршрута. Не могли бы вы помочь мне с этим? :)

Я работаю на ноутбуке Python Jupyter с решателем Docplex

all_units = [0,1,2,3,4,5,6,7,8,9]
ucp_raw_unit_data = {
    "customer": all_units,
    "loc_x": [40,45,45,42,42,42,40,40,38,38],
    "loc_y" : [50,68,70,66,68,65,69,66,68,70],
   "demand": [0,10,30,10,10,10,20,20,20,10],
    "req_vehicle":[[0,1,2], [0], [0], [0],[0], [0], [0], [0], [0], [0]],
    }

df_units = DataFrame(ucp_raw_unit_data, index=all_units)

# Display the 'df_units' Data Frame
df_units

Q = 50
N = list(df_units.customer[1:])
V = [0] + N
k = 15
# n.o. vehicles
K = range(1,k+1)
# vehicle 1 = type 1 vehicle 6 = type 2 and vehicle 11 = type 0
vehicle_types = {1:[1],2:[1],3:[1],4:[1],5:[2],6:[2],7:[2],8:[2],9: 
[2],10:[2],11:[0],12:[0],13:[0],14:[0],15:[0]}
lf = 0.5
R = range(1,11)

# Create arcs and costs
A = [(i,j,k,r) for i in V for j in V for k in K for r in R if i!=j]
Y = [(k,r) for k in K for r in R]
c = {(i,j):np.hypot(df_units.loc_x[i]-df_units.loc_x[j], 
df_units.loc_y[i]-df_units.loc_y[j]) for i,j,k,r in A}

from docplex.mp.model import Model
import docplex

mdl = Model('SDCVRP')

# decision variables
x = mdl.binary_var_dict(A, name = 'x')
u = mdl.continuous_var_dict(df_units.customer, ub = Q, name = 'u')
y = mdl.binary_var_dict(Y, name = 'y')
# objective function
mdl.minimize(mdl.sum(c[i,j]*x[i,j,k,r] for i,j,k,r in A))

#constraint 1 each node only visited once
mdl.add_constraints(mdl.sum(x[i,j,k,r] for k in K for r in R for j in V 
if j != i and vehicle_types[k][0] in df_units.req_vehicle[j]) == 1 for i 
in N)
##contraint 2 each node only exited once
mdl.add_constraints(mdl.sum(x[i,j,k, r] for k in K for r in R for i in V 
if i != j and vehicle_types[k][0] in df_units.req_vehicle[j]) == 1 for j 
in N )

##constraint 3 -- Vehicle type constraint (site-dependency)
mdl.add_constraints(mdl.sum(x[i,j,k,r] for k in K for r in R for i in V 
if i != j and vehicle_types[k][0] not in 
df_units.req_vehicle[j]) == 0 for j in N)

#Correcte constraint 4 -- Flow constraint
mdl.add_constraints((mdl.sum(x[i, j, k,r] for j in V if j != i)  - 
                mdl.sum(x[j, i, k,r] for j in V if i != j)) == 0 for i in 
N for k in K for r in R)

#constraint 5 -- Cumulative load of visited nodes
mdl.add_indicator_constraints([mdl.indicator_constraint(x[i,j,k,r],u[i] + 
df_units.demand[j]==u[j]) for i,j,k,r in A if i!=0 and j!=0])

## constraint 6 -- one vehicle to one route
mdl.add_constraints(mdl.sum(y[k,r] for r in R) <= 1 for k in K)
mdl.add_indicator_constraints([mdl.indicator_constraint(x[i,j,k,r],y[k,r] 
== 1) for i,j,k,r in A if i!=0 and j!=0])

##constraint 7 -- cumulative load must be equal or higher than demand in 
this node
mdl.add_constraints(u[i] >=df_units.demand[i] for i in N)

##constraint 8 minimum load factor 
mdl.add_indicator_constraints([mdl.indicator_constraint(x[j,0,k,r],u[j] 
>= lf*Q) for j in N for k in K for r in R if j != 0])

mdl.parameters.timelimit = 15
solution = mdl.solve(log_output=True)

print(solution)

Я ожидаю, что каждый маршрут будет посещен другим транспортным средством, однако одни и те же транспортные средства выполняют несколько маршрутов. Кроме того, теперь совокупная нагрузка рассчитывается для посещенных узлов, и я хотел бы, чтобы она была для транспортного средства на маршрутах, чтобы можно было выполнить последнее ограничение (минимальный коэффициент нагрузки).

Answer 1

Я понимаю, что индексы K относятся к транспортным средствам, а R - для маршрутов.Я запустил ваш код и получил следующие задания:

y_11_9=1
y_12_4=1
y_13_7=1
y_14_10=1
y_15_10=1

, которые, кажется, показывают, что многие транспортные средства используют один и тот же маршрут.Это не запрещено ограничением суммы (y [k, r] для r в R) <= 1), поскольку оно запрещает одному транспортному средству работать на нескольких маршрутах.Вы хотите ограничить количество назначенных транспортных средств одним маршрутом до 1, так как это симметричное ограничение из ограничения № 6?Если я ошибся, пришлите решение, которое вы получаете, и ограничение, которое вы хотите добавить. </p>

Если я добавлю симметричное ограничение, то есть ограничим назначения транспортных средств маршрутами до 1 (нет двух транспортных средств на одном и том жемаршрут), по:

mdl.add_constraints(mdl.sum(y[k, r] for r in R) <= 1 for k in K)
mdl.add_constraints(mdl.sum(y[k, r] for k in K) <= 1 for r in R)

Я получаю решение с той же стоимостью, и только три назначения маршрута транспортного средства:

y_11_3=1
y_12_7=1
y_15_9=1

Тем не менее, я думаю, что лучшее решение было быдобавьте некоторый фактор стоимости использования транспортного средства и внесите это в конечную цель.Это также может уменьшить симметрию в задаче.

Филипп.