Задача коммивояжера (Турция)

1 августа 2011 года в 15:15 Просмотров: 91073

Маршрут по городам Турции

Решение задачи коммивояжера для Турции

Описание

Вариант решения TSP Турция от 10.04.2012

Авиатранспорт

Турецкие авиакомпании Turk Hava Yollari и Turk Hava Tasimaciligi выполняют рейсы внутри страны. Флагманская авиакомпания страны — Turkish Airlines. Зарубежные авиарейсы выполняет компания SunExpress.

В стране множество аэропортов. Крупнейшие аэропорты: имени Ататюрка и имени Сабихи Гёкчен (Стамбул), Эсенбога (Анкара).

Автомобильный транспорт

Дороги в юго-западной Турции и в туристических центрах отличаются высоким качеством.

Автобусная сеть в Турции хорошо развита, автобусы комфортабельны, а стоимость проезда относительно невысока. Однако пользоваться маршрутными автобусами для иностранцев проблематично, ввиду того, что надписи маршрутные выполнены на турецком^[1].

Железнодорожный транспорт

Турецкие государственные железные дороги (тур. Türkiye Cumhuriyeti Devlet Demiryolları) обеспечивают перевозки пассажиров и грузов по всей стране. Используется европейская колея 1435 мм. Первая железнодорожная линия в стране была построена в 1856 году^[2]. Ныне протяжённость железнодорожной сети составляет 8671 км (на 1990 год — 8430 км^[3]), из них электрифицировано 2336 км (на 1990 было электрифицировано 204 км^[3]). Используется электрификация на переменном токе 25 кВ, 50 Гц.

В локомотивном парке тепловозы (549) и электровозы (64) которые выполняют от 81 до 84 % всей перевозочной работы. До настоящего времени используются и 50 паровозов. Также эксплуатируются 83 электропоезда и 44 дизель-поезда. В вагонном парке около 17 тысяч вагонов.

Основными перевозимыми грузами являются полезные ископаемые, строительные материалы, сельскохозяйственная продукция, промышленное сырьё, скот^[3].

Используемые стандарты: ширина колеи — европейская, тормоза — воздушные, сцепка — винтовая упряжь, допускаемый подъём 28 ‰, минимальный радиус кривых — 190 метров.

С 2003 года развивается высокоскоростной железнодорожный транспорт. Линия Стамбул — Эскишехир — Анкара модернизирована для движения высокоскоростных электропоездов (используется TCDD HT65000 заказанные в Испании) со скоростью до 250 км/час. По планам Турецкого министерства транспорта и коммуникаций к 2023 году протяжённость линий используемых для скоростного движения должна составить 4000 км.

В стране имеется вагоностроение^[3] и локомотивостроение.

Метрополитен

В начале 1980-х в Турции ещё не было своего метрополитена^[3]. Однако было построено метро в Анкаре (открыто в 1996 году), Стамбуле (открыто в 2000 году), Измире (открыто в 2000 году), Адане (открыто в 2009 году).

Кроме того, в Европейской части Стамбула действует Тюнель. Эта небольшая линия подземного фуникулёра была открыта ещё в 1875 году. В 1910 году Тюнель был электрифицирован. Две станции соединены тоннелем протяжённостью 573 метра.

В Стамбуле действует также и система лёгкого метро Istanbul LRT, она была открыта в 1989 году.

Морской транспорт

У Турции несколько морских портов.

Порт Хайдарпаша имеет искусственные насыпные причалы общей протяженностью свыше 2600 м, глубины у стенок достигают 10 метров. Гавань порта защищена от штормов волноломами длиной 1700 метров.

Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра. Общая постановка задачи, впрочем, как и большинство её частных случаев, относится к классу NP-сложных задач.

Матрица

	Адана	Алания	Анкара	Анталья	Белек	Бодрум	Бурса	Ван	Бурдур	Дидим	Догубаязит	Измир	Измит	Карс	Кахра	Кемер	Конья	Калкан	Деницли	Мерсин	Эскишехир	Кайсери	Самсун	Сивас	Сиде	Стамбул	Фетхие	Чешме	Эрзурум	Эфес
Адана	0	433	485	567	536	1028	859	901	657	1098	1021	903	834	1054	195	614	359	763	794	89	708	323	739	520	498	937	764	989	851	938
Аланья	0	0	556	135	104	559	657	1325	260	584	1445	605	732	1408	619	182	264	332	358	350	500	574	963	772	66	835	332	676	1205	547
Анкара	0	0	0	546	564	711	385	1377	420	701	1181	586	349	1107	671	586	289	664	477	494	235	324	413	469	523	452	630	672	904	621
Анталья	0	0	0	0	44	429	549	1458	129	454	1523	473	625	1449	752	49	305	201	228	483	445	614	969	812	75	727	201	546	1246	416
Белек	0	0	0	0	0	467	565	1427	168	493	1492	511	640	1418	722	91	274	240	267	453	461	584	985	781	45	743	240	585	1215	455
Бодрум	0	0	0	0	0	0	556	1919	349	119	1904	249	685	1830	1213	468	686	305	254	907	613	974	1136	1193	499	792	230	323	1627	176
Бурса	0	0	0	0	0	0	0	1747	423	477	1522	333	138	1448	1042	589	505	666	480	864	151	717	750	863	598	245	632	418	1245	400
Ван	0	0	0	0	0	0	0	0	1554	1905	176	1800	1562	363	766	1511	1256	1660	1691	985	1605	941	977	867	1394	1665	1660	1886	434	1835
Бурдур	0	0	0	0	0	0	0	0	0	391	1508	410	498	1434	839	168	311	243	168	662	318	599	842	797	182	600	209	483	1231	354
Дидим	0	0	0	0	0	0	0	0	0	0	1890	170	606	1816	1200	492	672	329	226	1022	555	960	1123	1179	524	712	253	243	1613	97
Догубаязит	0	0	0	0	0	0	0	0	0	0	0	1751	1406	192	890	1562	1212	1828	1641	1109	1399	905	821	711	1446	1509	1794	1836	278	1785
Измир	0	0	0	0	0	0	0	0	0	0	0	0	461	1678	1084	506	556	407	240	906	415	844	1006	1063	537	566	332	88	1497	84
Измит	0	0	0	0	0	0	0	0	0	0	0	0	0	1335	1019	664	637	741	555	842	227	667	637	812	673	106	708	547	1132	528
Карс	0	0	0	0	0	0	0	0	0	0	0	0	0	0	823	1490	1139	1755	1569	1138	1326	833	748	639	1374	1436	1721	1763	206	1713
Кахра	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	799	544	948	979	274	893	273	621	348	683	1122	949	1174	619	1123
Кемер	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	352	166	267	530	485	661	1009	859	121	767	241	585	1292	456
Конья	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	501	448	357	343	305	694	503	235	682	501	642	937	592
Калкан	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	250	678	561	809	1084	1006	269	843	81	486	1440	357
Деницли	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	799	375	737	899	955	298	657	184	320	1390	191
Мерсин	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	719	333	749	531	413	947	679	999	932	949
Эскишехир	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	566	656	712	494	328	529	502	1147	451
Кайсери	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	448	197	539	767	805	930	630	879
Самсун	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	313	927	738	1053	1095	545	1044
Сивас	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	737	893	1086	1128	436	1077
Сиде	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	775	272	616	1177	487
Стамбул	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	811	650	1235	631
Фетхие	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	411	1443	281
Чешме	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1594	162
Эрзурум	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1511
Эфес	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0