Sign In

Two-Stage Learned Decomposition for Scalable Routing on Multigraphs

μž‘μ„±μž
  • Haebom
μΉ΄ν…Œκ³ λ¦¬
Empty

μ €μž

Filip Rydin, Morteza Haghir Chehreghani, Balazs Kulcsar

πŸ’‘ κ°œμš”

λ³Έ 논문은 λ³΅μž‘ν•œ 이동 μ˜΅μ…˜(λ‹€μ–‘ν•œ ν†΅ν–‰λ£Œ, μ‹œκ°„ λ“±)을 κ³ λ €ν•  수 μžˆλŠ” λ©€ν‹°κ·Έλž˜ν”„ ν™˜κ²½μ—μ„œ μ°¨λŸ‰ 경둜 문제(VRP)λ₯Ό ν•΄κ²°ν•˜λŠ” 데 μžˆμ–΄ κΈ°μ‘΄ 신경망 λ°©λ²•λ‘ μ˜ ν™•μž₯μ„± 문제λ₯Ό κ·Ήλ³΅ν•˜λŠ” 것을 λͺ©ν‘œλ‘œ ν•©λ‹ˆλ‹€. 이λ₯Ό μœ„ν•΄ λ…Έλ“œ μˆœμ„œ κ²°μ •κ³Ό 엣지 선택을 λΆ„λ¦¬ν•˜λŠ” 두 단계 ν•™μŠ΅ 방식인 Node-Edge Policy Factorization (NEPF)을 μ œμ•ˆν•©λ‹ˆλ‹€. μ œμ•ˆλœ 방법둠은 엣지 집계λ₯Ό μœ„ν•œ 사전 인코딩, λΉ„μžκΈ°νšŒκ·€ 엣지 선택 ꡬ쑰, 계측적 κ°•ν™” ν•™μŠ΅μ„ 톡해 κΈ°μ‘΄ 졜고 μ„±λŠ₯을 μœ μ§€ν•˜λ©΄μ„œλ„ ν›ˆλ ¨ 및 μΆ”λ‘  속도λ₯Ό 크게 ν–₯μƒμ‹œμΌ°μŠ΅λ‹ˆλ‹€.

πŸ”‘ μ‹œμ‚¬μ  및 ν•œκ³„

β€’
μ‹€μ œ μ„Έκ³„μ˜ λ‹€μ–‘ν•œ 이동 μ˜΅μ…˜μ„ λͺ¨λΈλ§ν•˜λŠ” λ©€ν‹°κ·Έλž˜ν”„ VRP에 λŒ€ν•œ 효율적인 신경망 해결책을 μ œμ‹œν•©λ‹ˆλ‹€.
β€’
κΈ°μ‘΄ VRP 신경망 λͺ¨λΈμ˜ ν™•μž₯μ„± 문제λ₯Ό ν•΄κ²°ν•˜μ—¬ 더 크고 λ³΅μž‘ν•œ λ¬Έμ œμ—λ„ 적용 κ°€λŠ₯성을 λ†’μ˜€μŠ΅λ‹ˆλ‹€.
β€’
μ œμ•ˆλœ NEPF 방식은 μ†”λ£¨μ…˜ ν’ˆμ§ˆκ³Ό 계산 νš¨μœ¨μ„±μ„ λ™μ‹œμ— λ‹¬μ„±ν•˜μ—¬ μ‹€μš©μ μΈ VRP 해결에 κΈ°μ—¬ν•  수 μžˆμŠ΅λ‹ˆλ‹€.
β€’
νŠΉμ • μœ ν˜•μ˜ λ©€ν‹°κ·Έλž˜ν”„ κ΅¬μ‘°λ‚˜ 더 λ³΅μž‘ν•œ μ œμ•½ 쑰건이 좔가될 경우 μ„±λŠ₯ 및 ν™•μž₯성에 λŒ€ν•œ 좔가적인 검증이 ν•„μš”ν•©λ‹ˆλ‹€.
πŸ‘
Made with Slashpage