Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

Огонь Универсиады приближается к финишу в Казани, но прежде пройдет по 43 городам республики Татарстан. Все об маршрутах огня в нашем анонсе.

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

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

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

 

Дополнение: 

Оптимальный маршрут по Московской области:

http://lmatrix.ru/news/problems/zadacha-kommivoyazhera-moskovskaya-oblast_432.html

Оптимальный маршрут по Ленинградской области:

http://lmatrix.ru/news/problems/zadacha-kommivoyazhera-leningradskaya-oblast_431.html

Оставить комментарий

Пожалуйста, введите символы, показанные на рисунке.

Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта