Наберите проблему поездки на Python, используя CPLEX - PullRequest
Новая
       18

Наберите проблему поездки на Python, используя CPLEX

0 голосов
/ 12 февраля 2020

Я пытаюсь запрограммировать проблему набора номера на основе модели Кордо и Лапорта. Я упростил модель: -Только одно транспортное средство -Начать равный терминал -Строить временные ограничения

Мне удается получить некоторые результаты с docplex на python Но есть проблема ... Я не могу заставить его доставить клиент 1 на свой терминал. Я имею в виду, что он работает как VRP, он проходит через все узлы, даже если это пикап или доставка.

Если у кого-то уже была эта проблема. спасибо заранее.

вот мой код: 

import numpy as np
import matplotlib.pyplot as plt
from docplex.mp.model import Model

rnd=np.random
rnd.seed(0)

#Number of client
n=3

#Pickup locations
P=[i for i in range(1,n+1)]

#Delivery locations
D=[i for i in range(n+1,2*n+1)]

#N the set of all nodes 0 and 2n+1 are the start and end terminal.
N=[0]+P+D

#Set of vehicule
K=[1]

#Maximum Capacity of the vehicle
Q=15

#A set of edges
A = [(i,j) for i in N for j in N if i!=j]

#Amount loaded onto vehicle at node i, qi = qi+n (q pickup = q delivery for the same node i)
q ={i:rnd.randint(1,10)for i in P}
q1={i:-q[i-n] for i in D}
q.update(q1)
print(q)
# Generating random numbers between (0 and 2n+1) * 200.
loc_x = rnd.rand(len(N))*200
# Generating random numbers between (0 and 2n+1) * 100.
loc_y = rnd.rand(len(N))*100

plt.scatter(loc_x[1:n+1],loc_y[1:n+1],c='b')
plt.scatter(loc_x[n+1:],loc_y[n+1:],c='g')

#Pickup and Delivery points
for i in P:
    plt.annotate('$Pq_%d=%d$'%(i,q[i]),(loc_x[i],loc_y[i]))

for i in D:
    plt.annotate('$Dq_%d=%d$'%(i-n,q[i]),(loc_x[i],loc_y[i]))

#Depot point
plt.plot(loc_x[0],loc_y[0],c='r' ,marker='s')

plt.show()

#cost of each arc
c= {(i,j):np.hypot(loc_x[i]-loc_x[j],loc_y[i]-loc_y[j]) for i,j in A}

#CPLEX Model
mdl = Model('DARP')

#Initializing our binary variable x_i,j
x=mdl.binary_var_dict (A,name='x')

#Initializing our cumulative demand u
u=mdl.continuous_var_dict (N,ub=Q ,name = 'u')

#Initializing the objectif function
mdl.minimize(mdl.sum(c[i,j]*x[i,j]for i,j in A))

#Initialzing constraint every request is served exactly once
mdl.add_constraints(mdl.sum(x[i,j]for j in N if j!=i)==1 for i in P)

#Initialzing constraint same vehicle services pickup and delivery
mdl.add_constraints(((mdl.sum(x[i,j]for j in N if j!=i))-(mdl.sum(x[n+i,j] for j in N if j!=(n+i))))==0 for i in P)

#Initialzing constraint the same vehicle that enters a node leaves the node
mdl.add_constraints(((mdl.sum(x[j,i]for j in N if j!=i))-(mdl.sum(x[i,j] for j in N if j!=i)))==0 for i in (P+D))

#Initialzing constraint every vehicle enters the end terminal
mdl.add_constraints(mdl.sum(x[i,k] for i in N if i!=k)==1 for k in[0])
mdl.add_constraints(mdl.sum(x[k,j] for j in N if j!=k)==1 for k in[0])

#Initialzing constraints setting and checking vehicle load
mdl.add_indicator_constraints_(mdl.indicator_constraint(x[i,j],u[i]+q[j]==u[j])for i in N[1:] for j in N[1:] if i!=j)
mdl.add_constraints(u[i]>=q[i] for i in N[1:])
mdl.add_constraints(u[i]<=min(Q,Q+q[i]) for i in N[1:])

#Getting the solution
solution =mdl.solve(log_output=True)
#Printing the solution
print(solution)

#Identifing the active arcs.
active_arcs =[  a for a in A if x[a].solution_value==1]

#Pickup and Delivery points
plt.scatter(loc_x[1:n+1],loc_y[1:n+1],c='b')
plt.scatter(loc_x[n+1:],loc_y[n+1:],c='g')

for i in P:
    plt.annotate('$Pq_%d=%d$'%(i,q[i]),(loc_x[i],loc_y[i]))

for i in D:
    plt.annotate('$Dq_%d=%d$'%(i-n,q[i]),(loc_x[i],loc_y[i]))

for i,j in active_arcs :
#Coloring the active arcs
    plt.plot([loc_x[i],loc_x[j]],[loc_y[i],loc_y[j]],c='g',alpha=0.3)

#Depot point
plt.plot(loc_x[0],loc_y[0],c='r' ,marker='s')

plt.show()
...