How to add conditional subtour elimination constraints of CVRP

[Taner Cokyasar]

Hello,

As a newbie to Pyomo, I will occupy the group for a while. Sorry for disturbance; please bear with me.

Now, I am trying to code the following CVRP:

Below is my code so far. I could not add the conditional subtour elimination constraints. Some solvers offer a conditional constraint addition, e.g., indicator constraints in docplex. However, I would like to implement this in Pyomo. If you may help, I would really appreciate it.

import numpy as np

import matplotlib.pyplot as plt

np.random.seed(0)

from __future__ import division

from pyomo.environ import *

n = 10 #number of clients

Q = 15 #vehicle capacity

N = [i for i in range(1, n+1)]

V = N + [0]

q = {i:np.random.randint(1,10) for i in N}

locx = np.random.rand(len(V))*200

locy = np.random.rand(len(V))*100

A = [(i,j) for i in V for j in V if i!=j]

c = {(i,j):np.hypot(locx[i]-locx[j],locy[i]-locy[j]) for i,j in A}

model = ConcreteModel()

model.x = Var(A, domain=Binary)

model.u = Var(N, domain=NonNegativeIntegers, bounds=(0,Q))

model.OBJ = Objective(expr = sum(c[i,j]*model.x[i,j] for i,j in A), sense=minimize)

def ax_constraint_rule(model, i):

    return sum(model.x[i,j] for j in V if i!=j) == 1

def ax_constraint_rule2(model, j):

    return sum(model.x[i,j] for i in V if i!=j) == 1

def ax_constraint_rule3(model, i):

    return q[i]<=model.u[i]

model.AxbConstraint = Constraint(N, rule=ax_constraint_rule)

model.AxbConstraint2 = Constraint(N, rule=ax_constraint_rule2)

model.AxbConstraint3 = Constraint(N, rule=ax_constraint_rule3)

opt = SolverFactory('glpk')

opt.solve(model)

Best,

Taner

[Jeffrey Kantor]

Hi Taner,

I'm scratching my head a bit on this particular formulation of the CVRP.  

The strict equality specifying that all nodes are visited just once, including the 'depot' node. Given your problem data, however,

a single vehicle doesn't have capacity to meet demand at all customers.  And there is only one vehicle in the problem.  

So is this problem even feasible as written?

Also, I don't see the incremental loading of the vehicle in your implementation (i.e., constraint 4 in the mathematical formulation).

With regard to subtour elimination, here's an AMPL implementation that I've used which doesn't require constraint 

generation and which provides for multiple vehicles

https://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/05.05-Traveling-Salesman-Problem-with-Time-Windows.ipynb

This is basically the Miller-Tucker-Zemlin technique for subtour elimination. With minor modification you could alter this

to get the somewhat tighter Desrochers-Laporte formulation.

These techniques introduce n**2 constraints which gets prohibitively large for larger problems. That's when constraint generation 

becomes the more effective approach.

Jeff

[Soheil.mt]

HiTaner,

First of all, you should also define Sets and Params, like model.V = Set(), model.Q = Param(), model.q = Param(model.V, model.V), model.c =Param(model.V, model.V).

second:

def Cons1(model, i,j):

    if i!=j:

        return model.U[j] >= model.U[i] + model.d[j] - M*(1-model.X[i,j])

    else:

        return Constaint.skip

model.Cons1 = Constraint(model.V, model.V , rule = Cons1)

,where M is a big number.

Soheil

--
You received this message because you are subscribed to the Google Groups "Pyomo Forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pyomo-forum...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/pyomo-forum/167e77cd-5097-4d34-ab29-f0038d464e27%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.