tags: Meeting

Vehicle Routing Problem (VRP)

• Vehicle Routing Problem (VRP)
  • 說明
  • 題目
  • 老師講解的方法
    • 萬能科大
    • 老師的想法
    • 改良 –- 順序、城市編號、車子混合在一起
    • 改良 –- 城市編號、車子混合在一起

說明

• TSP 是一台車巡迴 (人) 所有城市的最短路徑，VRP 是 多台車巡迴 (人) 所有城市的最短路徑
  

題目

• 資料集：Berlin52.txt
  • 基地：第 1 個城市

    每台車都從基地出發，走完負責的路徑在返回起點
    

  • 要巡迴的城市：之後 51 個城市
• 車輛數：固定為 5 台（分配的車輛數越少越好）
• 目標：如何讓 5 台車的行駛總距離最短
• 自己想解決方法
  • 先分組再排序
  • 先排序再分組

老師講解的方法

萬能科大

期刊論文

• n: 城市數量
• m: 車子數量
• 左邊基因
  • 格式：1 ～ n 不重複整數
  • 代表拜訪優先度（越大越先拜訪）
• 右邊基因
  • 格式：只有 0(不拜訪)、1（拜訪）
  • 代表要不要拜訪這個都市
• 舉例

  城市拜訪優先度	1	3	4	2
  是否要拜訪都市	1	0	1	0
  相乘結果	1	0	4	0
  城市（固定）	A	B	C	D

  結果： V₁ 拜訪的都市順序為 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
  • 每一台車的「起點至第一個拜訪城市之距離 + 該車負責城市之距離總和 + 最後一個拜訪城市至起點之距離」之總和
  • 車子全部跑得距離加總越低愈好