The Multi Vehicle Routing Problem /w Capacity Constraints

Prerequisites

The mathematical Model

Sets: \begin{array}{l} V = \text{Set of }n\text{ nodes}\newline E = \text{Set of edges }(VxV)\newline K = \text{Set of vehicles} \end{array}

Parameters: \begin{array}{l} d_i = \text{demand of customer }i\in V\newline c_{ij} = \text{cost for traveling from node }i\text{ to node }j\newline c_k = \text{capacity of vehicle }k \end{array}

Variables: $$y_{ik} = \begin{cases} 1, \text{ if vehicle }k\text{ is assigned to customers }i\newline 0, \text{ else} \end{cases}$$

$$x_{ijk} = \begin{cases} 1, \text{ if vehicle }k\text{ travels directly from customer }i\text{ to customer }j\newline 0, \text{ else} \end{cases}$$

Objective: $$min \sum\limits_{i\in V} \sum\limits_{j\in V} c_{ij} \sum\limits_{k=1}^K x_{ijk}$$

Restrictions: \begin{array}{l} \sum\limits_{k=1}^K y_{ik} = 1 & \qquad \forall i\in V\setminus\text{{0}} & \text{(Each customer is assigned to one vehicle)}\newline \sum\limits_{k=1}^K y_{i0} = K & \qquad & \text{(All vehicles are assigned to the depot)}\newline \sum\limits_{j\in V} x_{ijk} = y_{ik} & \qquad \forall i\in V, k=1,...,K & \text{(Incoming Vehicle flow)}\newline \sum\limits_{j\in V} x_{jik} = y_{ik} & \qquad \forall i\in V, k=1,...,K & \text{(Outgoing Vehicle flow)}\newline \sum\limits_{i\in V} d_i y_{ik} \le c_k & \qquad \forall k = 1,...,K & \text{(Vehicle capacity)}\newline \sum\limits_{i\in S} \sum\limits_{j\in S} x_{ijk} \le \vert S\vert -1 & \qquad \forall S \subseteq V\setminus\text{{0}},\vert S\vert \ge 1,k=1,...,K & \text{(Subtour elimination)}\newline \end{array}

The Multi Vehicle Routing Problem /w Capacity Constraints