Skip to content

Callback: Custom Resource

Consider again the Vehicle Routing Problem with Time Windows but let's do the time resource ourselves.

Hook into the dynamic programming algorithm and do initialization, extension and dominance manually. The time state is initialized to zero at the start vertex,

Stime,0=0S_{time,0} = 0

and the extension function is the classical

Stime,j=max{aj,Stime,i+tij}S_{time,j} = \max \{ a_j, S_{time,i} + t_{ij} \}

where Stime,jbjS_{time,j} \leq b_j for the extension to be feasible with time window [aj,bj][a_j, b_j] at vertex jj and travel time tijt_{ij} from ii to jj.

The dominance is done using \leq such that

Stime,iStime,iS_{time,i} \leq S'_{time,i}

when SS dominates SS'.

# Vehicle Routing Problem with Time Windows

from flowty import Model, xsum, CallbackModel, Where
from flowty.datasets import vrp_rep

bunch = vrp_rep.fetch_vrp_rep("solomon-1987-r1", instance="R101_025")
name, n, es, c, d, Q, t, a, b, x, y = bunch["instance"]

m = Model()

# Make sure to invoke callback in the dynamic progrmaming algorithm
m.setParam("CallbackDP", "On")

# one graph, it is identical for all vehicles
g = m.addGraph(obj=c, edges=es, source=0, sink=n - 1, L=1, U=n - 2, type="B")

# adds resources variables to the graph.
# demand and capacity
m.addResourceDisposable(
    graph=g, consumptionType="V", weight=d, boundsType="V", lb=0, ub=Q, name="d"
)

# A custom resource to handle time
m.addResourceCustom(graph=g, name="time")


# The callback for handling the time resource
def callback(cb: CallbackModel, where: Where):
    # initialization
    if where == Where.DPInit:
        cb.setResource("time", 0)

    # extension
    if where == Where.DPExtend:
        e = cb.edge
        j = es[e][1]
        value = cb.getResource("time")
        value = max(a[j], value + t[e])

        if value > b[j]:
            cb.skip()
        else:
            cb.setResource("time", value)

    # dominance
    if where == Where.DPDominate:
        value = cb.getResource("time")
        other = cb.getResourceOther("time")

        # label is not dominated
        if other < value:
            cb.keep()


m.setCallback(callback)

# set partition constriants
for i in range(n)[1:-1]:
    m += xsum(x * 1 for x in g.vars if i == x.source) == 1

# packing set
for i in range(n)[1:-1]:
    m.addPackingSet([x for x in g.vars if i == x.source])

status = m.optimize()
print(f"ObjectiveValue {round(m.objectiveValue, 1)}")

# get the variable values
for var in m.vars:
    if var.x > 0:
        print(f"{var.name} = {round(var.x, 1)}")