Задача коммивояжера (Россия)

20 октября 2011 года в 01:01 Просмотров: 31559

Оптимальный маршрут по крупным городам России

Решение задачи коммивояжера (TSP) для городов России

Описание

Транспортная система России

Транспортная система России характеризуется развитой транспортной сетью, включающей в себя 87 тыс. км железных дорог, более 745 тыс. км автомобильных дорог с твердым покрытием, свыше 600 тыс. км воздушных линий, 70 тыс. км магистральных нефте- и продуктопроводов, свыше 140 тыс. км магистральных газопроводов, 115 тыс. км речных судоходных путей и множество морских трасс. В ней занято свыше 3,2 млн человек, что составляет 4,6 % работающего населения.

Огромные пространства и суровый климат предопределили первостепенное значение для России всепогодных видов наземного транспорта — железнодорожный и трубопроводный. На них падает основной объём грузовой работы. Водный транспорт играет в России значительно меньшую роль из-за короткого навигационного периода. Роль автомобильного транспорта в общем грузообороте в связи с крайне незначительными средними расстояниями перевозок (в пределах городов и пригородов, в карьерах открытых разработок полезных ископаемых, на лесовозных дорогах в районах лесозаготовок и т. д.) также невелика, несмотря на то, что им перевозится больше половины грузов. Важной особенностью транспортной системы России является её тесная взаимосвязь с производством.

Современное состояние транспортной системы характеризуется низким техническим уровнем производственной базы большинства предприятий и износом подавляющего большинства транспортных средств, что приводит к снижению безопасности их работы, а также отсутствием инвестиций для преодоления данных проблем[1]. Важной характеристикой транспортной системы России является тот факт, что, по данным Росстата, по состоянию на 2011 год в межсезонье 10 % населения страны фактически отрезаны от остальной территории страны (не имеет доступа к сети круглогодично эксплуатируемых автодорог и/или не имеет доступа к железнодорожным станциям и аэродромам). Средняя подвижность населения России (на 2011 год) — около 6300 км на душу населения в год (в странах Западной Европы — 15-20 тыс. км, в США, Канаде — 25-30 тыс. км в год). Существенным фактором, обуславливающим территориальную разобщённость страны, является построение её транспортной системы по звездообразному принципу с центром в столице.

Транспортное пространство представляет собой совокупность самостоятельных организаций — перевозчиков и посредников — с преобладанием мелкого капитала, что явилось следствием дезинтеграции экономики в 90-е годы XX века.

Основным государственным источником финансирования дорожного хозяйства России с 2011 года является Федеральный дорожный фонд, запланированный объём отчислений в него в 2011 году составляет 386,7 млрд руб..

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

Общая длина автомобильных дорог с твёрдым покрытием в России составляет 754 тыс. км (2008).[4] В 2008 году автомобильным транспортом было перевезено 6,9 млрд тонн грузов, его грузооборот в том же году составил 216 млрд тонно-километров.[4]

С 2000 по 2008 годы объём перевозки грузов на автомобильном транспорте увеличился на 17 %, грузооборот — на 41 %.

По общей протяженности автомобильных дорог Россия превосходит почти все европейские страны, кроме Франции, и занимает 7-е место во всем мире. По отношению к численности населения плотность автомобильных дорог с твердым покрытием в Российской Федерации составляет около 5,3 км на 1 тыс. жителей, что несколько выше, чем на Украине или в Казахстане (3,3 и 5,0 соответственно), но ниже, чем ряде других стран: так, в Финляндии данный показатель составляет около 10 км, в США — около 13 км, во Франции — 15,1 км на 1 тыс. жителей. Общая протяжённость автодорог — 910 тыс. км, из них 745 тыс. км покрыты асфальтом, 45,4 тыс. км дорог федерального значения. По данным на 2011 год, 92 % протяжённости федеральных трасс страны представляют собой дороги, где движение осуществляется по одной полосе в каждом направлении; 29 % федеральных трасс работают в режиме перегрузки. Плохое состояние автодорог страны влечёт за собой крайне низкую среднюю скорость перемещения коммерческих грузов автотранспортом — около 300 км в сутки (в странах Европы — приближается к 1500 км в сутки).

Деятельность транспортно-экспедиционных компаний по доставке грузов наземным автотранспортом в настоящее время регулируется Уставом автомобильного транспорта.

В сентябре 2010 года было завершено строительство автомагистрали «Амур».

Матрица

===========	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37
1 Астрахань	0	3939	9541	436	1001	2299	1810	5567	1467	3968	910	4504	1071	479	1406	1629	1468	4087	3711	3058	1627	1144	2131	888	1221	2158	1203	825	1204	3967	3809	2526	1252	1690	8779	2092	1676
2 Барнаул	0	0	6067	3518	3601	1835	2508	2093	2796	494	4370	2424	3516	4368	3610	2557	3195	348	232	885	2623	3093	2193	4097	3123	4319	2714	3154	2758	493	3711	1519	2971	2278	5305	1854	3563
3 Владив-к	0	0	0	9126	9210	7444	8117	3981	8404	5586	9979	5039	9125	9977	9219	8166	8803	5810	5846	6494	8232	8702	7802	9706	9139	9928	8322	8762	8367	5626	9319	6152	8580	7887	732	7462	9172
4 Волгоград	0	0	0	0	578	1800	1387	5144	1044	3545	704	4081	649	850	983	1206	1046	3665	3288	2635	1204	606	1708	492	799	1690	798	373	781	3544	881	2103	829	1267	8356	1669	1236
5 Воронеж	0	0	0	0	0	1855	1456	5190	1059	3604	847	4130	128	1407	531	1274	748	3744	3345	2677	1345	514	1737	577	449	1272	960	507	862	3614	351	2153	856	1342	8439	1739	796
6 Екат-бург	0	0	0	0	0	0	653	3473	1061	1887	2558	2413	1757	2649	1823	809	1452	2027	1628	960	851	1341	380	2288	1789	2393	978	1411	1012	1897	1988	328	1091	495	6722	202	1572
7 Ижевск	0	0	0	0	0	0	0	4126	392	2540	2175	3066	1365	2266	1220	198	799	2680	2281	1613	761	969	281	1905	1200	1956	605	1028	629	2550	1391	981	587	398	7375	805	1093
8 Иркутск	0	0	0	0	0	0	0	0	4396	1586	5893	1060	5092	5984	5200	4144	4779	1808	1845	2513	4186	4676	3852	5623	5124	5866	4313	4746	4347	1646	5323	3145	4426	3830	3249	3451	5045
9 Казань	0	0	0	0	0	0	0	0	0	2810	1766	3336	968	1952	823	228	402	2950	2551	1883	718	572	673	1496	803	1559	379	713	329	2820	994	1359	267	548	7645	945	767
10 Кемерово	0	0	0	0	0	0	0	0	0	0	4307	526	3506	4398	3614	2558	3193	222	259	927	2600	3090	2267	4037	3538	4280	2727	3160	2761	205	3737	1559	2840	2244	4835	1865	3459
11 Красн-дар	0	0	0	0	0	0	0	0	0	0	0	4833	963	848	1366	1977	1550	4447	4848	3380	1985	1221	2456	272	1284	2107	1600	1147	1565	4317	1186	2856	1582	2053	9142	2442	1631
12 Красн-ск	0	0	0	0	0	0	0	0	0	0	0	0	4032	4924	4140	3084	3719	748	785	1453	3126	3616	2793	4563	4064	4806	3253	3686	3287	586	4263	2085	3366	2770	4309	2391	3985
13 Липецк	0	0	0	0	0	0	0	0	0	0	0	0	0	1488	456	1176	646	3646	3247	2579	1242	416	1646	693	262	1203	838	510	764	3516	266	2055	758	1244	8341	1641	721
14 Махач-ла	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1824	2068	1882	4538	4139	3471	2088	1455	2547	967	1632	2571	1703	1238	1656	4408	1719	2947	1685	2136	9233	2533	2089
15 Москва	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1056	428	3754	3355	2687	1453	627	1443	1096	179	734	1049	824	975	3624	174	2163	903	1342	8449	1749	267
16 Н Челны	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	635	2698	2299	1631	563	760	479	1707	1036	1792	407	838	431	2568	1227	1107	440	286	7393	693	1000
17 НН	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	3333	2934	2266	1109	449	1011	1280	425	1164	725	646	666	3203	599	1742	482	921	8028	1328	370
18 Новокуз	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	399	1067	2740	3230	2407	4177	3678	4420	2867	3300	2901	427	3877	1699	2980	2384	5057	2005	3599
19 Новос-к	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	668	2341	2831	2008	3778	3279	4021	2468	2901	2502	275	3478	1300	2581	1985	5094	1606	3200
20 Омск	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1673	2163	1340	3110	2611	3353	1800	2233	1834	937	2810	632	1913	1317	5762	938	2532
21 Орен-г	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	826	915	1715	1274	2199	411	838	497	2610	1473	1149	627	354	7435	735	1474
22 Пенза	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1250	951	448	1373	422	224	348	3100	647	1639	315	828	7925	1225	770
23 Пермь	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	2186	1481	2013	920	1309	910	2277	1625	708	868	522	7102	582	1192
24 Ростов	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1014	1837	1330	877	1295	4047	916	2586	1312	1775	8872	2172	1361
25 Рязань	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	925	870	645	796	3548	187	2087	674	1276	8373	1673	439
26 СПб	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	1795	1570	1721	4290	910	2721	1639	2078	9115	2485	816
27 Самара	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	453	93	2737	1069	1276	243	465	7562	862	1090
28 Саратов	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	418	3170	741	1709	446	898	7995	1295	967
29 Тольят	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	2771	995	1310	184	499	7596	896	1031
30 Томск	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	3747	1569	2850	2254	4895	1875	3469
31 Тула	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	0	2286	861	1475	8572	1872	449
32 Тюм.	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	0	0	1389	793	6394	414	1900
33 Ульян.	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	0	0	0	578	7675	975	847
34 Уфа	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	0	0	0	0	7079	379	1286
35 Хабар.	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	0	0	0	0	0	6700	8294
36 Челяб.	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	0	0	0	0	0	0	1693
37 Яросл.	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	0	0	0	0	0	0	0