# ITS2020メモ

## 1/28

### Formulation

Here, we formulate the Co-AVP problem on the graph $G$. Given vehicles $\mathcal{A}$, whose tasks are represented by $\mathcal{O}$ and $\mathcal{D}$, we solve the problem as a network flow problem on a time-expanded network with aggregation nodes $N^+$. Following the idea explained in Sec.IV-B, paths are bundled in terms of vehicle roles, and labeld by _flow index_. The set of the flow index is $\mathcal{K} = \{1,2,3,\dots,|\mathcal{K}|\}$, where $|\mathcal{K}| = |{\rm P}_{{\rm out}}| + |{\rm EX}_{{\rm out}}|$. In our formulation, flows $f_k(e): E^{N^+}\to \{0, 1\}$ for each flow index $k\in\mathcal{K}$ and edge $e\in E^{N^+}$ are optimized to minimize a specified cost function defined by the weights $w_k(e)$. Importantly, the weight $w_k(e)$ can be designed according to the purpose of the Co-AVP system, as we explain in Sec.IV-D.

Formally, our ILP formulation is defined as minimizing:

## 1/27

### Sec.4-E Approach

#### 今: Approach

- In this section, we describe our proposed method to solve the Co-AVP problem.
- For the formulation shown in Sec.IV-C, a solution can be obtained when the extension time $T$ of the time-expanded network is sufficient _large_; otherwise, no solution can be obtained.
- For example, for a problem that requires 10 time steps to complete all exiting and parking tasks, no feasible solutions can be obtained if $T\leq 9$.
- Therefore, it is necessary to find the optimal extension time $T$ for obtaining the optimal solution; however, the optimal value of $T$ is not always the smallest one since it is decided depending on the cost function.
- Consequently, we determine the optimal value of $T$, which has a solution and is as small as possible.
- Let $\pi_i^{{\rm sp}}$ be the shortest path for $a_i \in \mathcal{A}_e$ from its initial location to its given exit node without considering other vehicles, and $|\pi_i^{{\rm sp}}|$ is defined as the length of the path.
- The lower bound of $T$ for obtaining a feasible solution is $\max_i|\pi_i^{{\rm sp}}|, a_i \in \mathcal{A}_e$.
- We start to solve the ILP with a lower bound of $T$ and increase by $\beta \in \mathbb{N}$ until a feasible solution is derived.

#### 案: Finding Co-AVP solution using the ILP 少し短くした

- In this section, we describe our proposed method to solve the Co-AVP problem.
- For the formulation shown in Sec.IV-C, a solution can be obtained when the extension time $T$ of the time-expanded network is sufficient _large_; otherwise, no solution can be obtained.
- For example, for a problem that requires 10 time steps to complete all <s>exiting and parking</s> tasks, no feasible solutions are found if $T \leq 9$.
- Therefore, it is necessary to find the optimal extension time $T^\star$ for obtaining the optimal solution because larger $T$ requires longer computational times.
- We propose to find $T^\star$ according to the cost functions developed in Sec.IV-D following a linear search manner: We start to solve the ILP with a lower bound of $T$ and increase by $\beta \in \mathbb{N}$ until _any_ feasible solution is derived.
- Note that the straightforward lower bound of $T$, used in our experiments, is computed by $\max_i|\pi_i^{{\rm sp}}|, a_i \in \mathcal{A}_e$, where $|\pi_i^{{\rm sp}}|$ is the length of a shortest path of $a_i$ to exit.

### Sec.5-B 案 (Fig.10 showsの後ろから)

#### proposed-sod, -hybrid

(手法のこと)
For these functions, optimal solutions can be found when larger $T~(> T^\star)$ is used in our framework proposed in Sec.IV-E.
Therefore, relatively small computational times are required when the ratio is larger than 0.6 as shown in Fig.10(d) because we do not need to exactly find $T^\star$.

(中身のこと)
In terms of the quality of solutions, these two functions showed different results. Fig.10b indicates that the total travel distance can be minimized by SOD; however, the total exiting time by SOD could be larger than those by -hybrid functions particularly when the ratio is 1.0. This result is from the fact that the cost function SOD does not evaluate the exiting time due to its definition.
Thus, multiple solutions with different exiting times can be found by the solver.

In contrast, Fig.10(a) indicates that the total exiting time can be minimized by the -hybrid function. Interestingly, we could obtain solutions with small travel distance, which are a bit (10%?) longer than the result by SOD, with -hybrid as shown in Fig.10(b). These results mean that the hybrid function could take a balance between the total exiting time and the total travel distance.

The parameter $\alpha$ ... (大社さんの説明)

#### proposed-makespan

(手法のこと)
For the makespan function, in contrast to the previous two functions, the ILP in Sec.IV-C is completely different from those by other functions because the makespan formulation is \textit{not} a network flow problem.
Following our framework in Sec.IV-E, we iteratively solve the ILP in Sec.IV-C with $\beta=1$ possibly many times, and decide the given solution with time $T$ is optimal when any feasible solution is found.
Fig.10(d) shows this difference in computational times; longer times are needed particularly when the ratio is larger than 0.5.

(中身のこと)
In terms of the quality of solutions, it is obvious that the results by -makespan achieved the least makespan of paths, as shown in Fig.10c.
However, the total exiting and travel time were larger than those by -hybrid.

(以下はFigre 11 shows)

## 1/26

今グラフ$\star$のV, Eを$V^\star, E^\star$と書く，と言っているので (4pぐらい)，$N=(G, T)$の$G$の頂点と辺の集合は$V^{N}, E^{N}$になる．

agg nodeの集合を$V_\mathrm{add}$として，新しく作ったネットワークを$N^+$とするとグラフは$(V^{N^+}, E^{N^+})$で，$V^{N^+} = V^{N}\cup V_\mathrm{add}$ とかになるはずだけど，ここまで細かく書かなくても新しいネットワークは$N^+$と書きます，で良いかな，と結局思ったという話