It can be helpful adapting the utilities used for the TSP exercises to plot your solutions.

Task $1$: Set Partitioning Formulation

Describe how the VRPTW can be formulated as a Set Partitioning $($SP$)$ problem.

As usual, to describe a model you have at least to:

introduce the notation

write the full mathematical model

explain every row of the model justifying why it is a correct model of the problem at hand.

An analysis of the model from a computational point of view is a plus.

Task $2$: Heuristic Solution

Find a heuristic solution of the given instance and describe it$.$

Keep the heuristic simple both implementation$-$wise and computationally. A feasible solution is enough. Avoid finding the optimal solution with the

heuristic. You can describe the procedure in a few lines and maybe present the picture of the obtained routes together with calculating and reporting

the cost$/$quality of the solution.

Task $3$: Pricing Problem Formulation

Describe the Master Problem $($MP$)$ and the Restricted Master Problem $($RMP$)$ derived from the SP formulation, present and describe a mathematical

formulation of the associated pricing problem.

Task $4$: Column Generation by Hand

Starting from the columns defined in the data below, carry out a couple of generations of missing columns for the master problem by "manual

inspection" and add the additional columns to the datafile. You can use a solver for the solution of the restricted linear master problem but you must

identify promising columns by hand and justify your choice.

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:ning Formulation

Describe how the VRPTW can be formulated as a Set Partitioning $($SP$)$ problem.

As usual, to describe a model you have at least to:

introduce the notation

write the full mathematical model

explain every row of the model justifying why it is a correct model of the problem at hand.