Явуулын худалдаачны бодлого

Явуулын худалдаачны бодлого (Анг. Travelling Salesman Problem) нь худалдаачин бүх хотуудаар зөвхөн ганц удаа дайран явсаар анхны хотдоо ирэх хамгийн богино замыг олдог бодлого юм.

1930 онд анх удаа томьёологдсон бөгөөд тооцоолол нь нэлээд нүсэр болдог. Өнөөдрийн байдлаар 10000 хоттой үед бодогдсон байна.

Явуулын худалдаачны бодлого төлөвлөгөө гаргах, илгээмжийн үйлчилгээ, микрочипийн үйлдвэрлэл гэх мэт олон салбарт хэрэглэгддэг.

Түүх

Энэхүү бодлогыг хэн анх дэвшүүлсэн нь тодорхой бус байдаг. 1832 оны явуулын худалдаачдын тэмдэглэлд уг бодлогын тухай дурдсан байх бөгөөд Германаас Швейцари орох замыг жишээ болгон авсан байдаг. Гэхдээ математик үйлдлүүд нь байдаггүй аж.

Уиллиам Роуан Хэмилтон

1800-аад оны үед Явуулын худалдаачны бодлогыг Ирландын математикч Уиллиам Роуан Хэмилтон, Британийн математикч Томас Киркман нар тодорхойлжээ. Хэмилтоны Икоз тоглоом нь явуулын худалдаачны бодлогын дэд бодлого болох Хэмилтоны тойрог олоход суурилдаг. Явуулын худалдаачны бодлогыг бүрэн утгаар нь 1930-аад оны үед Австрийн Венын математикчид анх судалсан бөгөөд дараа нь Харвардын их сургуульд судлагдсан байдаг. Энэхүү эрдэм шинжилгээнд Карл Менгер онцгой үүрэг гүйцэтгэсэн байдаг.

Принстон их сургуулийн Хасслер Уитни сүүлд явуулын худалдаачны бодлого хэмээх нэрийг өгсөн юм.

1950,60-аад онд энэ бодлого Европ болон АНУ-д маш эрчимтэй судлагдах болсон. Тэдгээр дундаас АНУ-ын Санта Моника дахь РАНД Корпораци (RAND Corporation)-ийн Жорж Данзик, Делберт Рэи Фулкэрсон, Селмер Жонсон нар ихээхэн хувь нэмэр оруулсан. Тэд нар бодлогоо бүхэл тооны шугаман програмд дүрслээд хавтгай хуваах аргаар бодох аргыг боловсруулжээ. Энэхүү шинэ аргаараа тэд 49 хоттой явуулын худалдаачны бодлогоо боджээ. Үүний дараа математик, компьютерын ухаан, хими, физик, бас бусад олон шинжлэх ухааны эрдэмтэд судалсан байдаг.

1972 онд Ричард Карп Хэмилтоны тойрог бодлого NP-бүрэн гэдгийг харуулснаар Явуулын худалдаачны бодлого нь NP-хэцүү болсон. Энэ нь тооцолоход хэцүү байгаа шалтгаанд математик тайлбар өгсөн юм.

1970 оны сүүлч болон 1980 онд судалгаа маш сайн амжилттай болсон. Гротшел, Падберг, Риналди гэх хэсэг нөхөд хавтгай хуваах арга болон салаалаад хүрээлэх аргыг ашиглан 2392 хот хүртэл бодсон байна.

1990-ээд онд Апплегэйт, Биксби, Чватал, Күүк нар өмнөх хариугаа ашиглаж боддог Concorde хэмээх програмыг бүтээжээ. 2005 онд тэд нар 33,810 хоттой бодлогоос оновчтой замыг олох тооцооллыг хийжээ.

Тодорхойлолт

Графын бодлогын хувьд

4 хоттой, адил замтай явуулын худалдаачны бодлого

Явуулын худалдаачны бодлого нь ихэвчлэн чиглэлгүй жинтэй графаар дүрслэгддэг. Хотууд нь графын оройнууд, зам нь графын ирмэг, урт нь графын жин болно. Тодорхой оройноос эхлээд бүх оройнуудыг зөвхөн ганц удаа дайрна. Ихэвчлэн бүтэн граф байдаг. Хоёр хотыг холбосон зам олдохгүй бол хариунд үйлчлэхгүйгээр дурын ирмэг нэмж бодлогыг бодно.

Адил замтай/Адил бус замтай

Адил замтай явуулын худалдаачны бодлогод хоёр хотын хоорондох зай аль ч чиглэлд адил байдаг бөгөөд чиглэлгүй графаар дүрсэлдэг. Адил бус замтай явуулын худалдаачны бодлогод чиглэлээсээ хамаарч зай нь өөр байдаг. Чиглэлтэй графаар дүрсэлдэг.

Холбоотой бодлогууд

• Графын онолд адил томьёолол нь: Бүтэн жинтэй граф (оройнууд нь хот, ирмэгүүд нь зам, жин нь замын урт) өгөгдөхөд хамгийн бага жинтэй Хэмилтоны тойрог олох.
• Ерөнхийлсөн явуулын худалдаачны бодлого: Нэг хотод олон очиж болдог.

Бүхэл тооны шугаман програмын томьёолол

Бүхэл тооны шугаман програмд дараах байдлаар томьёологдоно.

${\begin{aligned}\min &\sum _{i\neq j}c_{ij}x_{ij}&\\0\leq &x_{ij}\leq 1&\forall i,j\\&x_{i,j}{\text{ integer}}&\forall i,j\\&\sum _{i=0,i\neq j}^{n}x_{ij}=1&j=0,\ldots ,n\\&\sum _{j=0,j\neq i}^{n}x_{ij}=1&i=1,\ldots ,n\\u_{i}-u_{j}&+nx_{ij}\leq n-1&1\leq i\neq j\leq n\\u_{i}\geq 0&&1\leq i\leq n.\end{aligned}}$

Дээрх томьёонд $c_{ij}$ нь $i$, $j$ хотуудын хоорондох зай, $x_{ij}$ нь $i$ хотоос $j$ хот хүрэх зам. Сүүлийн хоёр мөрд нэг шийд гарах нөхцөл өгөгдсөн байна.