اﻟﮕﻮرﯾﺘﻢ ﺗﺨﺼﯿﺺ ﺗﺮاﻓﯿﮏ ﺑﺮ ﭘﺎﯾﻪ ﻣﺴﯿﺮ ﺑﺎ اﺳﺘﻔﺎده از ﺣﻞ دﺳﺘﮕﺎه ﻫﺎي ﻣﻌﺎدﻻت ﺧﻄﯽ

ﻣﺴﺌﻠﻪ ﺗﺨﺼﯿﺺ ﺗﺮاﻓﯿﮏ ﻫﻤﺎن ﻣﺴﺌﻠﻪ ﺗﻌﯿﯿﻦ ﺟﺮﯾﺎن ﺗﻌﺎدﻟﯽ در ﯾﮏ ﺷﺒﮑﻪ ﺣﻤﻞ و ﻧﻘﻞ اﺳﺖ ﮐﻪ در ﺣﺎﻟﺖ ﻋﻤﻮﻣﯽ ﺑﻪ ﺻﻮرت ﯾﮏ ﻣﺪل ﺗﮑﻤﯿﻠﯽ ﻏﯿﺮﺧﻄﯽ ﺑﺮ ﺣﺴﺐ ﺟﺮﯾﺎن در ﻣﺴﯿﺮﻫﺎ ﺑﯿﺎن ﻣﯽ ﺷﻮد.اﻟﮕﻮرﯾﺘﻢﻫﺎي ﺗﺨﺼﯿﺺ ﺗﺮاﻓﯿﮏ ﺑﺮ ﭘﺎﯾﻪ ﻣﺴﯿﺮ ﺧﺎﻧﻮاده اي از روشﻫﺎي ﺣﻞ ﻣﺪل ﺗﮑﻤﯿﻠﯽ ﻫﺴﺘﻨﺪ ﮐﻪ در آﻧﻬﺎ ﺟﺮﯾﺎن در ﻣﺴﯿﺮﻫﺎي ﺑﯿﻦ زوجﻫﺎي ﻣﺒﺪأ- ﻣﻘﺼﺪ ﺑﻪ ﻃﻮر ﺗﮑﺮاري ﺑﺎ ﺣﺮﮐﺖ ﺑﻪ ﺳﻤﺖ ﺟﻮاب ﺗﻌﺎدﻟﯽ ﺑﻬﻨﮕﺎم ﻣﯽ ﺷﻮﻧﺪ. در ﻫﺮ ﺗﮑﺮار اﯾﻦ روش ﻫﺎ، ﺑﺎ اﺳﺘﻔﺎده از دو اﯾﺪه ﺗﺠﺰﯾﻪ ﻣﺴﺌﻠﻪ و ﺗﻮﻟﯿﺪ ﻣﺴﯿﺮ، ﺑﻪ ﺟﺎي ﺣﻞ ﻣﺴﺌﻠﻪ اﺻﻠﯽ ﯾﮑﺰﯾﺮﻣﺴﺌﻠﻪ ﺑﺴﯿﺎر ﮐﻮﭼﮏ ﺗﺮ ﺑﺮاي ﻫﺮ زوج ﻣﺒﺪأ- ﻣﻘﺼﺪ ﺣﻞ ﻣﯽ ﺷﻮد. ﻣﺘﻐﯿﺮﻫﺎي اﯾﻦ زﯾﺮﻣﺴﺌﻠﻪ ﺷﺎﻣﻞ ﺟﺮﯾﺎن در ﻣﺴﯿﺮﻫﺎي ﻓﻌﺎل ﺑﯿﻦ آن زوج ﻣﺒﺪأ- ﻣﻘﺼﺪ اﺳﺖ. ﻣﺠﻤﻮﻋﻪ ﻣﺴﯿﺮﻫﺎي ﻓﻌﺎل در ﻫﺮ ﺗﮑﺮار ﺑﺎ ﺗﻮﻟﯿﺪ ﮐﻮﺗﺎﻫﺘﺮﯾﻦ ﻣﺴﯿﺮ از ﻣﺒﺪأ ﺑﻪ ﻣﻘﺼﺪ و اﻓﺰودن آن ﺑﻪ ﻣﺴﯿﺮﻫﺎي ﻓﻌﺎل ﺗﮑﺮار ﻗﺒﻠﯽ ﺑﻬﻨﮕﺎم ﻣﯽ ﺷﻮد. زﯾﺮ ﻣﺴﺌﻠﻪ ﻣﺮﺑﻮط ﺑﻪ ﻫﺮ زوج ﻣﺒﺪأ- ﻣﻘﺼﺪ ﺧﻮد ﯾﮏ ﻣﺴﺌﻠﻪ ﺗﮑﻤﯿﻠﯽ ﻏﯿﺮﺧﻄﯽ اﺳﺖ ﮐﻪ ﺣﻞ آن ﺑﻪ ﺧﺎﻃﺮ ﻣﺎﻫﯿﺖ ﻏﯿﺮﺧﻄﯽ ﺳﺨﺖ اﺳﺖ. ﺳﺎل ﻫﺎ ﻗﺒﻞ روش ﺗﮑﺮاري ﺑﻪ ﻧﺎم روش ﺧﻄﯽﺳﺎزي ﺑﺮاي ﺣﻞ زﯾﺮﻣﺴﺎﯾﻞ ﻏﯿﺮﺧﻄﯽ در اﻟﮕﻮرﯾﺘﻢﻫﺎي ﺑﺮ ﭘﺎﯾﻪ ﻣﺴﯿﺮ اراﯾﻪ ﺷﺪ. در ﻫﺮ ﺗﮑﺮار اﯾﻦ روش، ﻣﺴﺌﻠﻪ در ﺟﻮاب ﻓﻌﻠﯽ ﺧﻄﯽﺳﺎزي و ﺑﻪ ﺻﻮرت ﯾﮏ ﻣﺴﺌﻠﻪ ﺗﮑﻤﯿﻠﯽ ﺧﻄﯽ ﮐﻪ ﺣﻞ آن راﺣﺖﺗﺮ اﺳﺖ ﺗﺒﺪﯾﻞ ﻣﯽ ﺷﻮد. ﺟﻮاب اﯾﻦ ﻣﺴﺌﻠﻪ ﺧﻄﯽ از روش ﻫﺎي ﻋﻤﻮﻣﯽ رﯾﺎﺿﯽ ﺑﺪﺳﺖ ﻣﯽ آﯾﺪ.ﻫﺪف از اﯾﻦ ﭘﮋوﻫﺶ اراﯾﻪ ﯾﮏ اﻟﮕﻮرﯾﺘﻢ ﺑﺮ ﭘﺎﯾﻪ ﻣﺴﯿﺮ اﺳﺖ ﮐﻪ در آن زﯾﺮ ﻣﺴﺎﯾﻞ ﻏﯿﺮﺧﻄﯽ ﺑﻪ ﺻﻮرت ﺗﮑﺮاري و ﺑﺎ ﺗﺒﺪﯾﻞ ﺑﻪ دﺳﺘﮕﺎه ﻣﻌﺎدﻻت ﺧﻄﯽ ﺣﻞ ﻣﯽ ﺷﻮﻧﺪ. ﺑﺮاي ﺣﻞ دﺳﺘﮕﺎه ﻣﻌﺎدﻻت روﺷﯽ ﮐﺎرا ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺳﺎﺧﺘﺎر ﺧﺎص ﻣﺴﺌﻠﻪ ﺗﺨﺼﯿﺺ ﺗﺮاﻓﯿﮏ اراﯾﻪ ﻣﯽ ﺷﻮد. در ﻧﻬﺎﯾﺖ، ﻧﺘﺎﯾﺞ اﺟﺮاي اﻟﮕﻮرﯾﺘﻢ ﺑﺮاي ﯾﮏ ﺷﺒﮑﻪ آزﻣﺎﯾﺸﯽ در ﻣﻘﺎﯾﺴﻪ ﺑﺎ ﻧﺘﺎﯾﺞ روش ﺧﻄﯽ ﺳﺎزي در ﺳﻄﻮح ﻣﺨﺘﻠﻒ ﺗﺮاﮐﻢ اراﯾﻪ و ﺑﺤﺚ ﺧﻮاﻫﻨﺪ ﺷﺪ.