---
tags: labnote
---

# Rooの最適化問題 (opt)

## Input

- $n$ ride requests $\mathcal{T}=\langle \mathrm{tr}_1,\dots,\mathrm{tr}_n\rangle$
- $K$ vehicles (each vehicle has $C$ capacity)
- OD graph $G'=(V', E')$
- $V'=V'_o\sqcup V'_d$: origin, destinations
- For each $\mathrm{tr}_i$, add $i$ to $V'_o$ as $v_i=\mathrm{tr}_i.o$ and add $i+n$ to $V'_d$ as $v_{i+n}=\mathrm{tr}_i.d$.
- $G'$: directed complete graph as $(i,j)$ has a wegith $D_{i,j}=\mathrm{SPDist}(v_i,v_j)$ on road network $G$.
- $\langle i, j\rangle$ request in $G'$

## Decision variables

- $y_{k,i,j} = 1$ if vehicle $k$ passes edge $(i, j)$
- $\epsilon_{k,i} = 1$ if vehicle $k$ passes vertex $i$
- $u_{k,i}$ the number of passengers on vehicle $k$ when it leaves vertex $i$
- $a_i$ time at which a vehicle arrives at vertex $i$
- $z_{k,i}$ the auxiliary binary variable

## Parameters

- $M$ large value
- $s_c$ average speed of vehicles
- $\mathrm{WT}$ max waiting time threshold

## Problem

### Objective function

$$
(1) \min \frac{1}{\sum_{\langle i,j\rangle\in\mathcal{T}}} \left[\sum_{k=1}^K \sum_{(i,j)\in E'} D_{i,j} y_{k,i,j} + \sum_{\langle i, j\rangle\in\mathcal{T}} D_{i,j}\left(1 - \sum_{k=1}^K \epsilon_{k, i}\right)\right]
$$

- 第一項 車両の移動コスト
- 第二項 unmatch (誰も頂点$i$にこない = originにこない) ときの移動コスト

### Constraints

#### (2)-(3)

- ある頂点は少なくとも1度しか訪れない

$$
(2) \sum_{k=1}^K \sum_{j \mid (i, j)\in E'} y_{k,i,j} \leq 1 \text{ for all }i\in V'
$$

$$
(3) \sum_{k=1}^K \sum_{j \mid (i, j)\in E'} y_{k,j,i} \leq 1 \text{ for all }i\in V'
$$

### 4

頂点$i$が車両$k$によって訪れられるかどうかの補助変数 (ただしexclusive or)

$$
(4) z_{k,i} = \sum_{j\mid (j, i)\in E'} y_{k,j,i} \oplus \sum_{j\mid (i, j)\in E'}\text{ for all }i\in V', k\in [K]
$$

#### 5

到着して出発するならば，同じ車両でなければならない

$$
(5) z_{k,i} - M\left(
2 - \sum_{k=1}^K \sum_{j\mid (j, i)\in E'} y_{k,j,i} - \sum_{k=1}^K \sum_{j\mid(i, j)\in E'} y_{k,i,j}
\right)
\leq 0 \text{ for all }i\in V', k\in [K]
$$

#### 6

2つのdirected chainが同じ車両で担当されない (?)

$$
(6) \sum_{l\mid (i, l)\in E'} y_{k,i,l} + \sum_{l\mid (j, l)\in E'} y_{k,j,l} \leq 1 + M\sum_{k=1}^K \left( \sum_{l\mid(l, i)\in E'} y_{k,l,i} + \sum_{l\mid(l, j)\in E'} y_{k,l,j} \right)
\text{ for all }i\in V', j\in V', i\neq j, k\in [K]
$$

#### 7-8

$\epsilon$の計算

$$
(7) \sum_{j\mid(i, j)\in E'} y_{k,i,j} = \epsilon_{k,i} \text{ for all }i\in V'_o, k\in [K]
$$

$$
(8) \sum_{j\mid(j, i)\in E'} y_{k,i,j} = \epsilon_{k,i} \text{ for all }i\in V'_d, k\in [K]
$$

### 9

ある車両が場所iを通過するならばjも通過する = pickとdropを両方担当する

$$
(9) \epsilon_{k,i} = \epsilon_{k,j} \text{ for all }k\in [K], \langle i, j\rangle \in\mathcal{T}
$$

### 10

number of directed chainsが最大で$K$個 (車両数)

$$
(10)
0 \leq \sum_{k=1}^K \sum_{i\in V'} \epsilon_{k,i} - \sum_{k=1}^K \sum_{(i,j)\in E'} y_{k,i,j} \leq K
$$

### 11-12

O/Dを経由すると人数が+1/-1される

$$
(11)
u_{k,j} \geq u_{k, i} + 1 - M(1 - y_{k,i,j}) \text{ for all }(i, j)\in E', j\in V'_o, k\in [K]
$$

$$
(12)
u_{k,j} \geq u_{k, i} - 1 - M(1 - y_{k,i,j}) \text{ for all }(i, j)\in E', j\in V'_d, k\in [K]
$$

### 13

容量制約を満たす

$$
(13)
u_{k,i} \leq C \text{ for all }i\in V', k\in [K]
$$

### 14

到着時刻の計算

$$
(14)
a_j \geq a_i + \frac{1}{s_c} D_{i,j} - M(1 - \sum_{k=1}^K y_{k,i,j})\text{ for all }(i, j)\in E'
$$

### 15

待ち時間を守る

$$
(15)
\mathrm{tr}_i.o_t - \mathrm{WT} \leq a_i \leq \mathrm{tr}_i.o_t + \mathrm{WT}\text{ for all }i\in V'_o
$$

### 16

Pickup-deliveryの時系列保存

$$
(16)
a_i \leq a_j \text{ for all }\langle i, j\rangle\in\mathcal{T}
$$

### 17

変数定義

$$
y_{k,i,j}, \epsilon_{k,i}, z_{k,i} \in \{0, 1\}, u_{k, i}, a_i \geq 0 \text{ for all }i\in V', (i, j)\in E', k\in [K]
$$