Алгоритмы для решения прикладной задачи маршрутизации транспорта
Древоподобные структуры транспортных коммуникаций. Частный случай, когда граф представлен в виде дерева. Слияние смежных маршрутов и добавления вершин выше по дереву. "Параллельная" обработка маршрутов. Общая сумма дистанций всех транспортных средств.
| Рубрика | Транспорт |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 28.08.2018 |
| Размер файла | 120,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
cur_route = get_route_by_id(Veh_routes, route_id_to_work_with)
if debug: print("-")
res, cur_route = step(cur_route, Veh_routes, the_Tree)
Veh_routes.remove(get_route_by_id(Veh_routes, cur_route.id))
Veh_routes.append(cur_route)
if debug: print("*")
if debug: output_all_routes(Veh_routes, the_Tree)
total_dist = count_total_dist_of_all_routes(Veh_routes)
impossible_total_dist = doubled_total_sum_by_arcs_weight(the_Tree.arcs)
total_dist_coef = total_dist / impossible_total_dist
if debug: print("**[main_iter]->finish")
return total_dist_coef
def revalidate_served_ids(Veh_routes, the_Tree):
for route in Veh_routes:
for n_id in route.nodes_to_take:
the_Tree.served_nodes_id.add(n_id)
def make_veh_route_to_every_not_served(not_served_ids, the_tree, routes):
global debug
if the_tree.matr == None:
make_graph(the_tree)
new_routes = {}
def get_highest_existing_id(routes):
highest_id = 0
f_f = True
for r in routes:
if f_f:
highest_id = r.id
f_f = False
continue
if r.id > highest_id:
highest_id = r.id
return highest_id + 1
id = get_highest_existing_id(routes)
for node in the_tree.nodes:
if not node.id in not_served_ids:
continue
node_id = node.id
the_tree.served_nodes_id.add(node_id)
if debug: print("node id: ", node_id)
if node_id == 1:
continue
way = go_for_BFS(the_tree, 1, node_id)
if debug: print("way: ", way)
new_routes[id] = way
id += 1
if debug: print("routes:", new_routes)
new_Veh_routes = []
for r_id in new_routes:
if debug: print("route id: ", r_id, " route: ", new_routes[r_id][0])
route_to_add = Veh_route(r_id, new_routes[r_id][0])
route_to_add.take_node(route_to_add.way[-1])
the_tree.served_nodes_id.add(route_to_add.way[-1]) # ?
new_Veh_routes.append(route_to_add)
for r in new_Veh_routes:
if debug: print("_____________")
r.sort_way(the_tree.nodes)
if debug: print("r id:", r.id, "way", r.way)
r.valuate_route(the_tree)
if debug:
print("distance: ", r.distance)
print("goods: ", r.goods)
def valuate_new_routes(new_routes, old_routes):
def get_routes_failed_to_add_current_node(cur_node_id, routes):
result = set()
for r in routes:
if cur_node_id in r.failed_to_add_vertexes_id:
result.add(r.id)
return result
for n_r in new_routes:
for ntt_id in n_r.nodes_to_take:
n_r.failed_to_merge_routs_id = get_routes_failed_to_add_current_node(ntt_id, old_routes)
valuate_new_routes(new_Veh_routes, routes)
return new_Veh_routes
def list_minus_list(list1, list2):
result_list = copy.deepcopy(list1)
for l in list1:
if l in list2:
result_list.remove(l)
return result_list
def main_base(amount_of_nodes, Cap):
global debug
debug = False
if debug: print("## [make_tree]->start")
the_Tree = make_tree(amount_of_nodes, Cap)
if debug: print("## [make_tree]->finish")
if debug: print("## [make_way_to_every_leaf_from_root]->start")
routes = make_way_to_every_leaf_from_root(the_Tree)
if debug: print("routes: ", routes)
if debug: print("## [make_way_to_every_leaf_from_root]->finish")
if debug: print("## [valuate_after_route_to_leafs]->start")
Veh_routes = valuate_after_route_to_leafs(routes, the_Tree)
if debug: print("## [valuate_after_route_to_leafs]->finish")
the_Tree.served_nodes_id.add(1)
if debug: print("## [step]->start")
dist_coef = main_iter(Veh_routes, the_Tree)
if debug: print("## [step]->finish")
return dist_coef
def main_main():
def min_max_avarage(one, two, type):
if type not in ["min", "max", "avarage"]:
print("Fail")
exit(0)
if type == "max":
return one if one > two else two
if type == "min":
return one if one < two else two
return (one + two) # /2 delim by 2 in the end
step = 10
multiple = 1
amount_of_nodes = step * multiple
data_collecting = {
"time": {},
"dist": {},
}
runs_for_every_step = 20
max_amount_of_nodes = 100
Cap = 10
while (amount_of_nodes < max_amount_of_nodes + step):
print("amount of nodes: ", amount_of_nodes)
time_collect_of_one_step = {
"min": None,
"max": None,
"avarage": None,
}
dist_collect_of_one_step = {
"min": None,
"max": None,
"avarage": None,
}
global debug
debug = False
for i in range(runs_for_every_step):
time_start = time.time()
if debug: print("## [main_base]->start")
dist_coef = main_base(amount_of_nodes, Cap)
if debug: print("## [main_base]->finish")
time_of_work = time.time() - time_start
if not time_collect_of_one_step["min"]:
time_collect_of_one_step["min"] = time_of_work
else:
time_collect_of_one_step["min"] = min_max_avarage(time_collect_of_one_step["min"], time_of_work, "min")
if not dist_collect_of_one_step["min"]:
dist_collect_of_one_step["min"] = dist_coef
else:
dist_collect_of_one_step["min"] = min_max_avarage(dist_collect_of_one_step["min"], dist_coef, "min")
if not time_collect_of_one_step["max"]:
time_collect_of_one_step["max"] = time_of_work
else:
time_collect_of_one_step["max"] = min_max_avarage(time_collect_of_one_step["max"], time_of_work, "max")
if not dist_collect_of_one_step["max"]:
dist_collect_of_one_step["max"] = dist_coef
else:
dist_collect_of_one_step["max"] = min_max_avarage(dist_collect_of_one_step["max"], dist_coef, "max")
if not time_collect_of_one_step["avarage"]:
time_collect_of_one_step["avarage"] = time_of_work
else:
time_collect_of_one_step["avarage"] = min_max_avarage(time_collect_of_one_step["avarage"], time_of_work,
"avarage")
if not dist_collect_of_one_step["avarage"]:
dist_collect_of_one_step["avarage"] = dist_coef
else:
dist_collect_of_one_step["avarage"] = min_max_avarage(dist_collect_of_one_step["avarage"], dist_coef,
"avarage")
time_collect_of_one_step["avarage"] /= runs_for_every_step
dist_collect_of_one_step["avarage"] /= runs_for_every_step
data_collecting["time"][amount_of_nodes] = time_collect_of_one_step
data_collecting["dist"][amount_of_nodes] = dist_collect_of_one_step
multiple += 1
amount_of_nodes = step * multiple
print("time data")
for amount_of_nodes in data_collecting["time"]:
print("amount of nodes: %s, min: %s, max: %s, avarage: %s" % (
amount_of_nodes, data_collecting["time"][amount_of_nodes]["min"],
data_collecting["time"][amount_of_nodes]["max"], data_collecting["time"][amount_of_nodes]["avarage"]))
print("dist data")
for amount_of_nodes in data_collecting["dist"]:
print("amount of nodes: %s, min: %s, max: %s, avarage: %s" % (
amount_of_nodes, data_collecting["dist"][amount_of_nodes]["min"],
data_collecting["dist"][amount_of_nodes]["max"], data_collecting["dist"][amount_of_nodes]["avarage"]))
if __name__ == "__main__":
main_main()
Размещено на Allbest.ur
...Подобные документы
Задачи и структура транспортного хозяйства в составе предприятия. Определение грузооборотов предприятия, маршрутов транспорта и необходимого количества транспортных средств, диспетчирование работы. Способы решения транспортной задачи методами оптимизации.
реферат [408,0 K], добавлен 08.05.2009Автомобильные перевозки на территории Республики Беларусь. Международные автобусные маршруты. Выявление наименее прибыльных направлений и поиск путей увеличения экспорта транспортных услуг путем открытия новых международных пассажирских маршрутов.
дипломная работа [60,2 K], добавлен 07.02.2012Проблемы российского транспорта. Сведения о международных транспортных коридорах (МТК), история их развития. Критерии выбора транспортных коммуникаций. Задачи и алгоритм формирования МТК, их значение для России с точки зрения национальной безопасности.
курсовая работа [40,1 K], добавлен 27.06.2009Размещение оборудования в основных и вспомогательных цехах предприятия. Средства механизации погрузочно-разгрузочных и подъёмно-транспортных работ. Определение требуемого количества транспорта. Расчет тягового усилия тележки. Выбор транспортных средств.
дипломная работа [2,7 M], добавлен 08.03.2015Формирование маршрутов перевозок, выбор типа подвижного состава и расчет грузооборота. Расчет времени и скорости доставки грузов. Расчет технико-эксплуатационных и экономических показателей использования транспортных средств различных видов транспорта.
курсовая работа [997,7 K], добавлен 25.12.2010Характеристика видов транспорта: сухопытный, водный, авиационный. Признаки классификации транспортных путешествий, рейтинг привлекательности транспортных средств. Анализ развития транспортной отрасли и и туристический потенциал Тверской области.
курсовая работа [25,4 K], добавлен 29.06.2010Роль транспорта и транспортных услуг в системе международных экономических отношений. Понятие транспорта, транспортных операций и международных транспортных услуг. Основные виды и классификация транспортных операций и международных транспортных услуг.
лекция [114,3 K], добавлен 10.05.2013Основные положения по организации автобусных маршрутов. Анализ зарубежного опыта организации наземного пассажирского транспорта. Создание выделенных полос для городских маршрутов. Схема действующих полос по г. Москве. Обзор оценки свободного времени.
дипломная работа [2,0 M], добавлен 20.06.2013Активы автотранспортного предприятия. Резерв на ремонт транспортных средств. Ежемесячная сумма резервирования. Размер отчислений на дорогостоящие виды ремонта. Порядок отражения на счетах бухгалтерского учета. Долгосрочный ремонт грузовых автомобилей.
реферат [20,4 K], добавлен 07.03.2009Ознакомление с технико-эксплуатационными показателями работы автомобилей. Рассмотрение результатов решения задачи маршрутизации методом потенциалов. Анализ технологического расчета маршрутов. Характеристика сводных показателей сменно-суточного пробега.
курсовая работа [462,7 K], добавлен 29.10.2017Факторы, влияющие на формирование тарифов на услуги транспорта. Ценообразование в сфере транспортных услуг. Государственное регулирование цен на рынке транспортных услуг. Тарифы железнодорожного, водного, автомобильного и воздушного транспорта.
контрольная работа [136,8 K], добавлен 25.11.2010Характерные особенности различных видов транспорта, используемых при перевозках. Определение характеристик различных маршрутов доставки груза. Оценка эффективности использования различных видов транспорта при грузовых перевозках на различные расстояния.
курсовая работа [880,5 K], добавлен 17.03.2015Планирование автобусных перевозок. Сущность задачи выбора схемы автобусных маршрутов в городах. Возможности повышения степени использования вместимости автобусов на схеме маршрутов. Определение кратчайших путей. Пассажиропоток по участкам сети.
реферат [676,1 K], добавлен 08.04.2011Использование математических методов линейного программирования для решения логистических задач. Алгоритм разработки оптимальных маршрутов движения транспортных перевозок. Расчет средней стоимости и методы снижения затрат доставки продукции на склады.
курсовая работа [373,1 K], добавлен 21.01.2015Грузооборот морского транспорта, роль портов в экономике страны. Экономические показатели продукции транспорта, грузопотоки и грузооборот. Расчет количества транспортных средств, организация и планирование перевозок по стандартным расписаниям и заявкам.
реферат [39,5 K], добавлен 03.06.2010Ресурсы логистики как основные элементы цепи поставок. Составные элементы транспортных операций. Организационные виды транспортных перевозок. Виды транспорта и их характеристика. Проблема повышения эффективности интермодальных транспортных терминалов.
курсовая работа [1,1 M], добавлен 22.05.2012Выбор поставщика балльно-экспертным методом. Расчет величины суммарного материального потока и стоимости грузопереработки на складе. Количество транспортных средств для перевозки. Разработка маршрутов и графиков доставки товаров автомобильным транспортом.
контрольная работа [76,1 K], добавлен 06.01.2012Понятие международной перевозки и зависимость ее себестоимости от различных технико-эксплуатационных факторов. Расчет затрат на топливо и обеспечение, заработную плату и техническое обслуживание. Выбор рациональных маршрутов работы транспортных средств.
курсовая работа [88,2 K], добавлен 15.08.2009Роль транспорта в социально-экономическом развитии. Экономическая сущность транспортных тарифов. Виды транспорта, правила формирования на них транспортных тарифов. Проблемы развития транспорта в Российской Федерации. Перспективы развития тарифной системы.
курсовая работа [251,7 K], добавлен 15.10.2013Техническая характеристика транспортного средства ГАЗ-66, эксплуатационные особенности. Разработка маршрутов и составление графиков доставки товаров автомобильным транспортом. Расходы по содержанию и эксплуатации транспортных средств, штрафные санкции.
курсовая работа [1,6 M], добавлен 07.12.2013
