---
# System prepended metadata

title: Vehicle Routing Problem (VRP)
tags: [Meeting]

---

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

[TOC]

## 說明
- TSP 是**一台**車巡迴 (人) 所有城市的最短路徑，VRP 是 **多台**車巡迴 (人) 所有城市的最短路徑
    ![](https://i.imgur.com/ovwbew0.png)

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

## 老師講解的方法
![](https://i.imgur.com/eYUd9fc.jpg)

### 萬能科大
![](https://i.imgur.com/iowondv.png)
: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 
- 作法
    - 每一段節點相互內積，拜訪優先度的結果依照大排到小
    - 如果有車子重複拜訪都市，統一由右邊的車子負責
### 老師的想法
![](https://i.imgur.com/IHEZbkn.png)
- 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
### 改良 --- 順序、城市編號、車子混合在一起
![](https://i.imgur.com/ZHgSBk3.png)
- 只做一次 PMX
- 遇到兩台相連的車子，實際派出的車子數量-1
- 一整段基因不用分段
    - 總長度: 2n+ (m-1)
    - 0 ~ n: 拜訪順序，大的數字優先拜訪
    - n+1 ~ 2n: 城市編號
    - 2n+1 ~ 2n+(m-1): 車子編號
- Fitness
    - 解碼後再計算
    - 分數：每一台車的「起點至第一個拜訪城市之距離 + 該車負責城市之距離總和 + 最後一個拜訪城市至起點之距離」之總和
    - 分數越低愈好
### 改良 --- 城市編號、車子混合在一起
![](https://i.imgur.com/KmY3wX8.png)

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