This assignment is courtesy of Roberto Roberti. The Vehicle Routing Problem with Time Windows $($VRPTW$)$ is a generalization of the Capacitated Vehicle Routing Problem $($CVRP$),$ where each customer must be visited within a given time window.

The VRPTW can be stated as follows. A directed graph G$=($V$,$A$)$

is given, where V

is the set of vertices and A

is the set of arcs. The set of vertices V

is defined as V$=$N$\backslash$cup $\{$o$,$d$\}$

$,$ where N$=\{1,2,...,$n$\}$

is a set of n

customers and o

and d

represent the start and the end point of each route $($in practice, o

and d

represent the same depot but are kept separate for notational purposes$).$ The set of arcs A

is defined as A$=\{($i$,$j$)$:i$,$j in V$,$i$!=$j$\}$

; a travel cost cij

and a travel time tij

are associated with each arc $($i$,$j$)$ in A

$.$

Each customer i in N

requests qi

units of a given commodity and can be visited only within a given time window $[$ei$,$li$]$

$,$ where ei

and li

are the earliest and the latest time to serve customer i

; nonetheless, a vehicle is allowed to arrive at i

before ei

$,$ but, in this case, the service starts at ei

$.$ A set K$=\{1,2,...,$m$\}$

of m

vehicles can be used to serve the customers; each vehicle has capacity Q

$.$

The goal of the VRPTW is to find a set of routes of minimum total cost to assign to the vehicles, such that

No more than m

routes are selected;

Each route starts from o

within the depot time window, visits a set of customers, each within its time window, whose total requests do not exceed Q

$,$ and ends at d

within the depot time window;

Each customer is visited by exactly one of the routes.

You are given a VRPTW instance in Python code at the end of this document. The layout of the customers is as follows:

instance

find the heuristic solution of the given instance and describe it$.$