Assgm 01 - DMTM

Formulating and solving the basic routing problem

min \sum_{i \in N} \sum_{j \in N} c_{i j} x_{i j}

such that:

\begin{array}{r} \sum_{j \in N} x_{i j} = 1 \forall i \in N \\ \sum_{i \in N} x_{i j} = 1 \forall j \in N \end{array}

\begin{aligned} u_{i} - u_{j} + n x_{i j} \leq n - 1 & \forall i, j \in N, i \neq j, \\ 2 \leq u_{i} \leq n & \forall i \in N ∖ {1}, \\ u_{1} = 1 \end{aligned}

x_{i j} \in {0, 1} \forall i, j \in N

min \sum_{i \in N} \sum_{j \in N} c_{i j} x_{i j}

such that:

\begin{array}{r} \sum_{j \in N} x_{i j} = 1 \forall i \in N \\ \sum_{i \in N} x_{i j} = 1 \forall j \in N \end{array}

\sum_{i \in S} \sum_{j \in S} x_{i j} \leq | S | - 1 \forall S \subset N, | S | \geq 2

x_{i j} \in {0, 1} \forall i, j \in N

Decision variables:

min \sum_{i \in N} \sum_{j \in N} c_{i j} x_{i j}

such that:

\begin{array}{r} \sum_{j \in N} x_{i j} = 1 \forall i \in N ∖ {0} \\ \sum_{i \in N} x_{i j} = 1 \forall j \in N ∖ {0} \end{array}

\begin{aligned} u_{i} - u_{j} + Q x_{i j} \leq Q - q_{j}, & \forall i \in N, \forall j \in N ∖ {0}, i \neq j, \\ q_{j} \leq u_{i} \leq Q, & \forall i \in N ∖ {0}, \\ u_{0} = 0, \end{aligned}

\begin{aligned} T_{i} + s_{i} + t_{i j} - T_{j} \leq M (1 - x_{i j}), & \forall i, j \in N, i \neq j \\ a_{i} \leq T_{i} \leq b_{i}, & \forall i \in N \\ T_{0} = 0, \end{aligned}

x_{i j} \in {0, 1} \forall i, j \in N

Parameters:

$c_{i j} :$ Cost of edge $(i, j)$
$t_{i j} \equiv c_{i j} :$ Time travel on edge $(i, j)$ (We just use $c_{i j}$ in the constraints, because speed is $60 \frac{k m}{h}$ )
$Q :$ Capacity of a vehicle
$q_{i} :$ Demand of node $i$
$C :$ Cost of activating a route
Decision variables:
$x_{i j k} :$ Binary. 0 = do not use edge, 1 = use edge $(i, j)$ with vehicle $k$
$u_{i k} :$ Continuous. Amount of goods delivered to node $i$ by vehicle $k$
$T_{i k} :$ Continuous. Time at which node $i$ is visited by vehicle $k$

min \sum_{k \in K} \sum_{i \in N} \sum_{j \in N} c_{i j k} x_{i j k} + \sum_{k \in K} ((\sum_{i \in N} \sum_{j \in N} x_{i j k}) - 1)

such that:

\begin{aligned} \sum_{j \in N} x_{i j k} = 1 & \forall i \in N ∖ {0}, \forall k \in K \\ \sum_{i \in N} x_{i j k} = 1 & \forall j \in N ∖ {0}, \forall k \in K \\ \sum_{k \in K} x_{i j k} \leq 1 & \forall i, j \in N ∖ {0} \end{aligned}

\begin{aligned} u_{i k} - u_{j k} + Q x_{i j k} \leq Q - q_{j}, & \forall i \in N, \forall j \in N ∖ {0}, i \neq j, \forall k \in K \\ q_{j} \leq u_{i k} \leq Q, & \forall i \in N ∖ {0}, \forall k \in K \\ u_{0 k} = 0, & \forall k \in K \end{aligned}

\begin{aligned} T_{i k} + s_{i} + t_{i j} - T_{j k} \leq M (1 - x_{i j k}), & \forall i, j \in N, i \neq j, \forall k \in K \\ a_{i} \leq T_{i k} \leq b_{i}, & \forall i \in N, \forall k \in K \\ T_{0 k} = 0, & \forall k \in K \end{aligned}

x_{i j k} \in {0, 1} \forall i, j \in N, \forall k \in K