The Vehicle Routing Problem with Time Windows¶
This example illustrates a model for the vehicle routing problem with time windows (VRPTW).
In the VRPTW the objective is to minimize the total cost of routing vehicles from a central depot to a set of customers. Each customer must be visited exactly once within a specified time window to deliver their required demand, each customer has a service time it takes to unload the vehicle, and each vehicle has a maximum capacity of goods to deliver. If a vehicle arrives early it is allowed to wait for the customer's time window to start.
Let be graph with vertices where are the customers such that the depot is split in a 'start' and and 'end' depot and is the edges connecting all customers with each other and the depot vertices. Edge is associated with a cost and a travel time . Vertex is associated with a time window and a demand . The vehicle capacity is denoted .
Usually the problem is formulated as a path based model
where paths are feasible paths in with accumulated edge cost and expresses if path visits customer .
The corresponding network model can be formulated as
where are paths in a graph subject to time and demand constraints modeled as disposable resources. Demand with vertex consumption and bounds for all and time with edge consumption and vertex bounds for all .
The problem is implemented as
with the graph and resource constraints described above. See the modeling section for details.
# Vehicle Routing Problem with Time Windows from flowty import Model, xsum from or_datasets import vrp_rep bunch = vrp_rep.fetch_vrp_rep("solomon-1987-r1", instance="R102_025") name, n, E, c, d, Q, t, a, b, x, y = bunch["instance"] m = Model() # one graph, it is identical for all vehicles g = m.addGraph(obj=c, edges=E, source=0, sink=n - 1, L=1, U=n - 2, type="B") # adds resources variables to the graph. # travel time and customer time windows m.addResourceDisposable( graph=g, consumptionType="E", weight=t, boundsType="V", lb=a, ub=b, name="t" ) # demand and capacity m.addResourceDisposable( graph=g, consumptionType="V", weight=d, boundsType="V", lb=0, ub=Q, name="d" ) # 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()