Алгоритмы для решения прикладной задачи маршрутизации транспорта

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