###### tags: `Meeting`
# Vehicle Routing Problem (VRP)

[TOC]

## 說明
- TSP 是**一台**車巡迴 (人) 所有城市的最短路徑，VRP 是 **多台**車巡迴 (人) 所有城市的最短路徑

## 題目
- 資料集：`Berlin52.txt`
- 基地：第 1 個城市
> 每台車都從基地出發，走完負責的路徑在返回起點
> 
- 要巡迴的城市：之後 51 個城市
- 車輛數：固定為 5 台（分配的車輛數越少越好）
- 目標：如何讓 5 台車的行駛總距離最短
- 自己想解決方法
- 先分組再排序
- 先排序再分組
<!--  -->

## 老師講解的方法

### 萬能科大
:point_right: [期刊論文](https://drive.google.com/file/d/1fI7-OgRkyB2qrJwP7qKSZwN-TMWY2ipK/view?usp=sharing)
- n: 城市數量
- m: 車子數量
- 左邊基因
- 格式：1 ～ n 不重複整數
- 代表拜訪優先度（越大越先拜訪）
- 右邊基因
- 格式：只有 0(不拜訪)、1（拜訪）
- 代表要不要拜訪這個都市
- 舉例
| | | |||
| -------- | -------- | -------- | -------| ----|
| 城市拜訪優先度 | 1 | 3 | 4 | 2|
| 是否要拜訪都市 | 1 | 0 | 1 | 0|
| 相乘結果 | 1 | 0 | 4 | 0|
| 城市（固定） | A | B | C | D|
> 結果： V~1~ 拜訪的都市順序為 C -> A
- 作法
- 每一段節點相互內積，拜訪優先度的結果依照大排到小
- 如果有車子重複拜訪都市，統一由右邊的車子負責
### 老師的想法
- n: 城市數量
- m: 車子數量
- 左邊基因
- 格式：1 ～ n 不重複整數
- 代表拜訪順序
- 大的數字優先拜訪
- 右邊基因
- 格式：1 ～ n+(m-1) 不重複整數
- 1～n 代表拜訪城市編號
- n～(n+m-1) 代表車子編號
- 意義
- 右邊車子編號前一整段是那台車要拜訪的城市們（不包含拜訪順序），如果車子編號**相連**代表一台車
- VH1 要拜訪 3, 8, n, 1 這些城市
- 對應至左邊一段相同長度的編碼代表拜訪城市的順序
- 1, 9, 6, 4 代表第一個拜訪 8 號城市（優先度9）；第二個拜訪 n 號城市（優先度6）；第三個拜訪 1 號城市（優先度3）；第四個拜訪 1 號城市（優先度1）
- 優勢：
- 組合和排列分開做，但共同演化
- 每個城市一定都會被拜訪一次（不用考慮重複拜訪）
- 派出的車子數量可能小於 m
### 改良 --- 順序、城市編號、車子混合在一起
- 只做一次 PMX
- 遇到兩台相連的車子，實際派出的車子數量-1
- 一整段基因不用分段
- 總長度: 2n+ (m-1)
- 0 ~ n: 拜訪順序，大的數字優先拜訪
- n+1 ~ 2n: 城市編號
- 2n+1 ~ 2n+(m-1): 車子編號
- Fitness
- 解碼後再計算
- 分數：每一台車的「起點至第一個拜訪城市之距離 + 該車負責城市之距離總和 + 最後一個拜訪城市至起點之距離」之總和
- 分數越低愈好
### 改良 --- 城市編號、車子混合在一起

- 一整段基因不用分段
- 總長度: n+ (m-1)
- 0 ~ n: 城市編號
- n+1 ~ n+(m-1): 車子編號
- Fitness
- 每一台車的「起點至第一個拜訪城市之距離 + 該車負責城市之距離總和 + 最後一個拜訪城市至起點之距離」之總和
- 車子全部跑得距離加總越低愈好