1# Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo 2# Copyright (C) 2016-2019 German Aerospace Center (DLR) and others. 3# SUMOPy module 4# Copyright (C) 2012-2017 University of Bologna - DICAM 5# This program and the accompanying materials 6# are made available under the terms of the Eclipse Public License v2.0 7# which accompanies this distribution, and is available at 8# http://www.eclipse.org/legal/epl-v20.html 9# SPDX-License-Identifier: EPL-2.0 10 11# @file routing.py 12# @author Joerg Schweizer 13# @date 14# @version $Id$ 15 16import os 17import numpy as np 18 19from agilepy.lib_base.processes import Process, CmlMixin, ff, call 20 21 22class priorityDictionary(dict): 23 def __init__(self): 24 '''Initialize priorityDictionary by creating binary heap 25 of pairs (value,key). Note that changing or removing a dict entry will 26 not remove the old pair from the heap until it is found by smallest() or 27 until the heap is rebuilt.''' 28 self.__heap = [] 29 dict.__init__(self) 30 31 def smallest(self): 32 '''Find smallest item after removing deleted items from heap.''' 33 if len(self) == 0: 34 raise IndexError, "smallest of empty priorityDictionary" 35 heap = self.__heap 36 while heap[0][1] not in self or self[heap[0][1]] != heap[0][0]: 37 lastItem = heap.pop() 38 insertionPoint = 0 39 while 1: 40 smallChild = 2*insertionPoint+1 41 if smallChild+1 < len(heap) and \ 42 heap[smallChild][0] > heap[smallChild+1][0]: 43 smallChild += 1 44 if smallChild >= len(heap) or lastItem <= heap[smallChild]: 45 heap[insertionPoint] = lastItem 46 break 47 heap[insertionPoint] = heap[smallChild] 48 insertionPoint = smallChild 49 return heap[0][1] 50 51 def __iter__(self): 52 '''Create destructive sorted iterator of priorityDictionary.''' 53 def iterfn(): 54 while len(self) > 0: 55 x = self.smallest() 56 yield x 57 del self[x] 58 return iterfn() 59 60 def __setitem__(self, key, val): 61 '''Change value stored in dictionary and add corresponding 62 pair to heap. Rebuilds the heap if the number of deleted items grows 63 too large, to avoid memory leakage.''' 64 dict.__setitem__(self, key, val) 65 heap = self.__heap 66 if len(heap) > 2 * len(self): 67 self.__heap = [(v, k) for k, v in self.iteritems()] 68 self.__heap.sort() # builtin sort likely faster than O(n) heapify 69 else: 70 newPair = (val, key) 71 insertionPoint = len(heap) 72 heap.append(None) 73 while insertionPoint > 0 and val < heap[(insertionPoint-1)//2][0]: 74 heap[insertionPoint] = heap[(insertionPoint-1)//2] 75 insertionPoint = (insertionPoint-1)//2 76 heap[insertionPoint] = newPair 77 78 def setdefault(self, key, val): 79 '''Reimplement setdefault to call our customized __setitem__.''' 80 if key not in self: 81 self[key] = val 82 return self[key] 83 84 def update(self, other): 85 for key in other.keys(): 86 self[key] = other[key] 87 88 89def dijkstra(id_node_start, nodes, edges, ids_node_target=None, weights={}): 90 """ 91 OUTDATED!!! see edgedijkstra 92 Calculates minimum cost tree and minimum route costs from 93 id_node_start to all nodes of the network or to 94 target nodes given in set ids_node_target. 95 Attention does not take into consideration missing connectors!! 96 """ 97 # print '\n\ndijkstraPlain',id_node_start.getID() 98 # dictionary of final distances 99 D = {} 100 # dictionary of predecessors 101 P = {} 102 # est.dist. of non-final vert. 103 Q = priorityDictionary() 104 Q[id_node_start] = 0 105 for v in Q: 106 D[v] = Q[v] 107 108 if ids_node_target is not None: 109 ids_node_target.discard(v) 110 # if ids_node_target.discard(v): 111 if len(ids_node_target) == 0: 112 return (D, P) 113 # print ' v=',v.getID(),len(v.getOutgoing()) 114 for id_edge in nodes.ids_outgoing[v]: 115 # print ' ',edge.getID(),edge._to.getID() 116 w = edges.ids_tonode[id_edge] 117 #vwLength = D[v] + weights.get(edge,edge._cost) 118 vwLength = D[v] + weights.get(id_edge, edges.lengths[id_edge]) 119 if w not in D and (w not in Q or vwLength < Q[w]): 120 Q[w] = vwLength 121 P[w] = id_edge 122 return (D, P) 123 124 125def edgedijkstra_backwards(id_edge_start, cost_limit, 126 weights=None, bstar=None): 127 """ 128 Calculates minimum cost tree and minimum route costs from 129 id_edge_start to all edges of the network or to 130 target edges given in set ids_edge_target. 131 132 """ 133 ids_origin = set() 134 # print 'edgedijkstra_backwards id_edge_start',id_edge_start,'cost_limit',cost_limit 135 # dictionary of final distances 136 D = {} 137 138 # dictionary of predecessors 139 P = {} 140 # est.dist. of non-final vert. 141 142 if weights[id_edge_start] < 0: 143 print ' no access id_edge_start, weights', id_edge_start, weights[id_edge_start] 144 return ([], {}, {}) 145 146 Q = priorityDictionary() 147 Q[id_edge_start] = weights[id_edge_start] 148 ids_edges_nochange = set() 149 for e in Q: 150 if (e not in ids_edges_nochange) & (e not in ids_origin): 151 152 D[e] = Q[e] 153 has_changed = False 154 155 # print ' --------------' 156 # print ' toedge',e,'ids_bedge',bstar[e] 157 # print ' D=',D 158 # print ' Q=',Q 159 if not bstar.has_key(e): 160 print 'WARNING in edgedijkstra: bstar has no edge', e 161 print 'routes = \n', P 162 return ([], None, P) 163 164 for id_edge in bstar[e]: 165 if 0: 166 weight_tot = D[e] + weights[id_edge] 167 newstate = '|' 168 if id_edge not in D: 169 newstate += '*D' 170 if id_edge not in Q: 171 newstate += '*Q' 172 elif weight_tot < Q[id_edge]: 173 newstate += '<Q' 174 else: 175 newstate += '>Q|' 176 print ' id_bedge', id_edge, 'w=%.2f,w_tot=%.2f' % ( 177 weights[id_edge], weight_tot), weights[id_edge] >= 0, D[e] + weights[id_edge] < cost_limit, id_edge not in D, (id_edge not in Q or weight_tot < Q[id_edge]), newstate 178 179 if weights[id_edge] >= 0: # edge accessible? 180 weight_tot = D[e] + weights[id_edge] 181 if weight_tot < cost_limit: 182 if id_edge not in D and (id_edge not in Q or weight_tot < Q[id_edge]): 183 Q[id_edge] = weight_tot 184 P[id_edge] = e 185 has_changed = True 186 else: 187 # print ' **found origin',e 188 ids_origin.add(e) 189 190 # print ' has_changed',e,has_changed 191 if not has_changed: 192 # break 193 ids_edges_nochange.add(e) 194 195 # print ' P',P 196 # print ' D',D 197 return (ids_origin, D, P) # returns in tree with all reachable destinations 198 199 200def edgedijkstra(id_edge_start, ids_edge_target=None, 201 weights=None, fstar=None): 202 """ 203 Calculates minimum cost tree and minimum route costs from 204 id_edge_start to all edges of the network or to 205 target edges given in set ids_edge_target. 206 207 """ 208 ids_target = ids_edge_target.copy() 209 # print 'edgedijkstra' 210 # dictionary of final distances 211 D = {} 212 213 # dictionary of predecessors 214 P = {} 215 # est.dist. of non-final vert. 216 217 if weights[id_edge_start] < 0: 218 print ' WARNING in edgedijkstra: no access id_edge_start, weights', id_edge_start, weights[id_edge_start] 219 return ({}, {}) 220 221 Q = priorityDictionary() 222 Q[id_edge_start] = weights[id_edge_start] 223 224 for e in Q: 225 D[e] = Q[e] 226 227 if ids_target is not None: 228 ids_target.discard(e) 229 if len(ids_target) == 0: 230 return (D, P) 231 if not fstar.has_key(e): 232 print 'WARNING in edgedijkstra: fstar has no edge', e 233 print 'routes = \n', P 234 return (None, P) 235 for id_edge in fstar[e]: 236 if weights[id_edge] >= 0: # edge accessible? 237 weight_tot = D[e] + weights[id_edge] 238 if id_edge not in D and (id_edge not in Q or weight_tot < Q[id_edge]): 239 Q[id_edge] = weight_tot 240 P[id_edge] = e 241 return (D, P) # returns in tree with all reachable destinations 242 243 244def get_mincostroute_edge2edge(id_rootedge, id_targetedge, D=None, P=None, 245 weights=None, fstar=None): 246 """ 247 Returns cost and shortest path from rootedge to a specific targetedge. 248 D, P must be precalculated for rootnode with function dijkstraPlainEdge 249 250 """ 251 if D is None: 252 D, P = edgedijkstra(id_rootedge, set([id_targetedge, ]), 253 weights=weights, fstar=fstar) 254 255 route = [id_targetedge] 256 if not P.has_key(id_targetedge): 257 return 0.0, [] 258 259 e = id_targetedge 260 while e != id_rootedge: 261 id_edge = P[e] 262 route.append(id_edge) 263 e = id_edge 264 # route.append(e) 265 route.reverse() 266 return D[id_targetedge], route 267 268 269def get_mincostroute_node2node(id_rootnode, id_targetnode, D, P, edges): 270 """ 271 Returns cost and shortest path from rootnode to a specific targetnode. 272 D, P must be precalculated for rootnode with function dijkstraPlain 273 274 """ 275 # print 'getMinCostRoute node_start=%s, edge_end =%s node_end=%s'%(rootnode.getID(),P[targetnode].getID(),targetnode.getID()) 276 id_node = id_targetnode 277 route = [] 278 if not P.has_key(id_targetnode): 279 return 0.0, [] 280 281 while id_node != id_rootnode: 282 id_edge = P[id_node] 283 route.append(id_edge) 284 id_node = edges.ids_fromnode[id_edge] 285 286 # for edge in route: 287 # print ' ',edge.getID() 288 route.reverse() 289 return D[id_targetnode], route 290 291 292def duaroute(tripfilepath, netfilepath, routefilepath, options='-v --ignore-errors'): 293 """ 294 Simple shortes path duaoute function 295 """ 296 # do not use options: --repair --remove-loops 297 cmd = 'duarouter '+options+' --trip-files %s --net-file %s --output-file %s'\ 298 % (ff(tripfilepath), ff(netfilepath), ff(routefilepath)) 299 return call(cmd) 300 301 302def init_random(self, **kwargs): 303 optiongroup = 'random' 304 self.add_option('is_timeseed', kwargs.get('is_timeseed', False), 305 groupnames=[optiongroup, 'options', ], 306 name='Time seed', 307 perm='rw', 308 info='Initialises the random number generator with the current system time.', 309 cml='--random', 310 ) 311 312 self.add_option('seed', kwargs.get('seed', 23423), 313 groupnames=[optiongroup, 'options', ], 314 name='Random seed', 315 perm='rw', 316 info='Initialises the random number generator with the given value.', 317 cml='--seed', 318 ) 319 320 321class RouterMixin(CmlMixin, Process): 322 def init_tripsrouter(self, ident, net, 323 trips, 324 netfilepath=None, 325 outfilepath=None, 326 name='Duarouter', 327 info='Generates routes from trips, flows or previous routes', 328 is_export_net=True, 329 logger=None, cml='duarouter'): 330 331 self._init_common(ident, name=name, 332 parent=net, 333 logger=logger, 334 info=info, 335 ) 336 337 self.init_cml(cml) # pass main shell command 338 self.is_export_net = is_export_net 339 self._trips = trips 340 341 if netfilepath is None: 342 netfilepath = net.get_filepath() 343 344 self.add_option('netfilepath', netfilepath, 345 groupnames=['_private'], 346 cml='--net-file', 347 perm='r', 348 name='Net file', 349 wildcards='Net XML files (*.net.xml)|*.net.xml', 350 metatype='filepath', 351 info='SUMO Net file in XML format.', 352 ) 353 354 if outfilepath is None: 355 outfilepath = trips.get_routefilepath() 356 357 self.add_option('outfilepath', outfilepath, 358 groupnames=['_private'], 359 cml='--output-file', 360 perm='r', 361 name='Out routefile', 362 wildcards='Route XML files (*.rou.xml)|*.rou.xml', 363 metatype='filepath', 364 info='Output file of the routing process, which is a SUMO route file in XML format.', 365 ) 366 367 def init_options_time(self, **kwargs): 368 optiongroup = 'time' 369 self.add_option('time_begin', kwargs.get('time_begin', -1), 370 groupnames=[optiongroup, 'options', ], 371 name='Start time', 372 perm='rw', 373 info='Defines the begin time; Previous trips will be discarded. The value of -1 takes all routes from the beginning.', 374 unit='s', 375 cml='--begin', 376 is_enabled=lambda self: self.time_begin >= 0.0, 377 ) 378 379 self.add_option('time_end', kwargs.get('time_end', -1), 380 groupnames=[optiongroup, 'options', ], 381 name='End time', 382 perm='rw', 383 info='Defines the end time; Later trips will be discarded; The value of -1 takes all routes to the end.', 384 unit='s', 385 cml='--end', 386 is_enabled=lambda self: self.time_end >= 0.0, 387 ) 388 389 def init_options_processing_common(self, **kwargs): 390 optiongroup = 'processing' 391 392 self.add_option('n_alternatives_max', kwargs.get('n_alternatives_max', 5), 393 name='Max. alternatives', 394 info='Maximum number of considered route alternatives.', 395 cml='--max-alternatives', 396 groupnames=[optiongroup, 'options', ], 397 perm='rw', 398 ) 399 400 self.add_option('is_ignore_errors', kwargs.get('is_ignore_errors', True), 401 name='Ignore disconnected', 402 info='Continue if a route could not be build.', 403 cml='--ignore-errors', 404 groupnames=[optiongroup, 'options', ], 405 perm='rw', 406 ) 407 408 self.add_option('n_threads', kwargs.get('n_threads', 0), 409 name='Parallel threads', 410 info="The number of parallel execution threads used for routing.", 411 cml='--routing-threads', 412 groupnames=[optiongroup, 'options', ], 413 perm='rw', 414 ) 415 416 def init_options_processing_dua(self, **kwargs): 417 optiongroup = 'processing' 418 419 self.add_option('time_preload', kwargs.get('time_preload', 200), 420 name='Preload time', 421 unit='s', 422 info='Load routes for the next number of seconds ahead.', 423 cml='--route-steps', 424 groupnames=[optiongroup, 'options', ], 425 perm='rw', 426 ) 427 # self.add_option('is_randomize_flows',kwargs.get('is_randomize_flows',False), 428 # name = 'Preload time', 429 # info = 'generate random departure times for flow input.', 430 # cml = '--randomize-flows', 431 # groupnames = [optiongroup,'options',],# 432 # perm='rw', 433 # ) 434 435 self.add_option('is_remove_loops', kwargs.get('is_remove_loops', False), 436 name='Remove loops', 437 info='Remove loops within the route; Remove turnarounds at start and end of the route. May cause errors!', 438 cml='--remove-loops', 439 groupnames=[optiongroup, 'options', ], 440 perm='rw', 441 ) 442 443 self.add_option('is_repair', kwargs.get('is_repair', False), 444 name='Repair', 445 info='Tries to correct a false route. May cause errors!', 446 cml='--repair', 447 groupnames=[optiongroup, 'options', ], 448 perm='rw', 449 ) 450 451 self.add_option('is_repair_from', kwargs.get('is_repair_from', False), 452 name='Repair start', 453 info='Tries to correct an invalid starting edge by using the first usable edge instead.', 454 cml='--repair.from', 455 groupnames=[optiongroup, 'options', ], 456 perm='rw', 457 ) 458 459 self.add_option('is_repair_to', kwargs.get('is_repair_from', False), 460 name='Repair end', 461 info='Tries to correct an invalid destination edge by using the last usable edge instead.', 462 cml='--repair.to', 463 groupnames=[optiongroup, 'options', ], 464 perm='rw', 465 ) 466 467 self.add_option('is_bulkrouting', kwargs.get('is_bulkrouting', False), 468 name='Bulk routing?', 469 info="Aggregate routing queries with the same origin.", 470 cml='--bulk-routing', 471 groupnames=[optiongroup, 'options', ], 472 perm='rw', 473 ) 474 475 # --weights.interpolate <BOOL> Interpolate edge weights at interval boundaries; default: false 476 # --weight-period <TIME> Aggregation period for the given weight files; triggers rebuilding of Contraction Hierarchy; default: 3600 477 # --weights.expand <BOOL> Expand weights behind the simulation's end; default: false 478 479 # --with-taz <BOOL> Use origin and destination zones (districts) for in- and output; default: false 480 481 def init_options_methods(self, **kwargs): 482 optiongroup = 'methods' 483 484 self.add_option('method_routechoice', kwargs.get('method_routechoice', 'gawron'), 485 name='Routechoice method', 486 choices=['gawron', 'logit', 'lohse'], 487 info="Mathematical model used for route choice.", 488 cml='--route-choice-method', 489 groupnames=[optiongroup, 'options', ], 490 perm='rw', 491 ) 492 493 self.add_option('beta_gawron', kwargs.get('beta_gawron', 0.3), 494 name="Gawron's 'beta'", 495 info="Gawron's 'beta' parameter.", 496 cml='--gawron.beta', 497 groupnames=[optiongroup, 'options', ], 498 perm='rw', 499 is_enabled=lambda self: self.method_routechoice is 'gawron', 500 ) 501 502 self.add_option('a_gawron', kwargs.get('a_gawron', 0.05), 503 name="Gawron's 'a'", 504 info="Gawron's 'a' parameter.", 505 cml='--gawron.a', 506 groupnames=[optiongroup, 'options', ], 507 perm='rw', 508 is_enabled=lambda self: self.method_routechoice is 'gawron', 509 ) 510 511 self.add_option('beta_logit', kwargs.get('beta_logit', 0.15), 512 name="Logit's 'beta'", 513 info="C-Logit's 'beta' parameter.", 514 cml='--logit.beta', 515 groupnames=[optiongroup, 'options', ], 516 perm='rw', 517 is_enabled=lambda self: self.method_routechoice is 'logit', 518 ) 519 520 self.add_option('gamma_logit', kwargs.get('gamma_logit', 1.0), 521 name="Logit's 'gamma'", 522 info="C-Logit's 'gamma' parameter.", 523 cml='--logit.gamma', 524 groupnames=[optiongroup, 'options', ], 525 perm='rw', 526 is_enabled=lambda self: self.method_routechoice is 'logit', 527 ) 528 529 self.add_option('theta_logit', kwargs.get('theta_logit', 0.01), 530 name="Logit's 'theta'", 531 info="C-Logit's 'theta' parameter.", 532 cml='--logit.theta', 533 groupnames=[optiongroup, 'options', ], 534 perm='rw', 535 is_enabled=lambda self: self.method_routechoice is 'logit', 536 ) 537 538 self.add_option('algorithm_routing', kwargs.get('algorithm_routing', 'dijkstra'), 539 name='Routing algorithm', 540 choices=['dijkstra', 'astar', 'CH', 'CHWrapper'], 541 info="Select among routing algorithms.", 542 cml='--routing-algorithm', 543 groupnames=[optiongroup, 'options', ], 544 perm='rw', 545 ) 546 547 self.add_option('is_keep_all_routes', kwargs.get('is_keep_all_routes', False), 548 name='Keep all routes?', 549 info="Save even routes with near zero probability.", 550 cml='--keep-all-routes', 551 groupnames=[optiongroup, 'options', ], 552 perm='rw', 553 ) 554 self.add_option('is_skip_new_routes', kwargs.get('is_skip_new_routes', False), 555 name='Skip new routes?', 556 info="Only reuse routes from input, do not calculate new ones.", 557 cml='--skip-new-routes', 558 groupnames=[optiongroup, 'options', ], 559 perm='rw', 560 ) 561 562 def do(self): 563 if self.is_export_net: 564 # first export current net 565 self.parent.export_netxml(self.netfilepath) 566 567 if self.is_export_trips: 568 self._trips.export_trips_xml(self.tripfilepaths) 569 570 self.update_params() 571 cml = self.get_cml() 572 573 # print 'SumonetImporter.do',cml 574 self.run_cml(cml) 575 if self.status == 'success': 576 print ' Routing done.' 577 if os.path.isfile(self.outfilepath): 578 # print ' outfile exists, start importing routes' 579 self._trips.import_routes_xml(self.outfilepath, 580 is_clear_trips=False, 581 is_generate_ids=False, 582 is_add=True) 583 return True 584 return False 585 return False 586 587 588class DuaRouter(RouterMixin): 589 def __init__(self, net, trips, 590 tripfilepaths=None, 591 outfilepath=None, 592 is_export_net=True, 593 logger=None, 594 **kwargs): 595 print 'DuaRouter.__init__ net, trips', net, trips 596 self.init_tripsrouter('duarouter', net, # net becomes parent 597 trips, 598 outfilepath=outfilepath, 599 logger=logger, 600 is_export_net=is_export_net, 601 ) 602 603 if tripfilepaths is None: 604 if trips is not None: 605 tripfilepaths = trips.get_tripfilepath() 606 self.is_export_trips = True 607 else: 608 self.is_export_trips = False 609 610 else: 611 self.is_export_trips = False 612 print ' tripfilepaths', tripfilepaths 613 if tripfilepaths is not None: 614 self.add_option('tripfilepaths', tripfilepaths, 615 groupnames=['_private'], 616 cml='--trip-files', 617 perm='r', 618 name='Trip file(s)', 619 wildcards='Trip XML files (*.trip.xml)|*.trip.xml', 620 metatype='filepaths', 621 info='SUMO Trip files in XML format.', 622 ) 623 624 self.init_options_time(**kwargs) 625 self.init_options_methods(**kwargs) 626 self.init_options_processing_common(**kwargs) 627 self.init_options_processing_dua(**kwargs) 628 init_random(self, **kwargs) 629 630 631class MacroRouter(RouterMixin): 632 """ 633 Macroscopic router 634 in development 635 """ 636 637 def __init__(self, net, trips, 638 tripfilepaths=None, 639 netfilepath=None, 640 outfilepath=None, 641 is_export_net=True, 642 logger=None, 643 **kwargs): 644 print 'MacroRouter.__init__ net, trips', net, trips 645 self.init_tripsrouter('macrorouter', net, # net becomes parent 646 trips, 647 netfilepath=netfilepath, 648 outfilepath=outfilepath, 649 name='Macroscopic router', 650 info='Generates routes from trips, flows or previous routes', 651 is_export_net=is_export_net, 652 logger=logger, 653 cml='marouter' 654 ) 655 656 if tripfilepaths is None: 657 if trips is not None: 658 tripfilepaths = trips.get_tripfilepath() 659 self.is_export_trips = True 660 else: 661 self.is_export_trips = False 662 663 else: 664 self.is_export_trips = False 665 print ' tripfilepaths', tripfilepaths 666 if tripfilepaths is not None: 667 self.add_option('tripfilepaths', tripfilepaths, 668 groupnames=['_private'], 669 cml='--route-files', 670 perm='r', 671 name='Trip file(s)', 672 wildcards='Trip XML files (*.trip.xml)|*.trip.xml', 673 metatype='filepaths', 674 info='SUMO Trip files in XML format.', 675 ) 676 677 self.init_options_time(**kwargs) 678 self.init_options_methods(**kwargs) 679 680 # marouter specific 681 optiongroup = 'methods' 682 self.add_option('n_iter_max', kwargs.get('n_iter_max', 20), 683 name='Max. Iterations', 684 info="maximal number of iterations for new route searching in incremental and stochastic user assignment.", 685 cml='--max-iterations', 686 groupnames=[optiongroup, 'options', ], 687 perm='rw', 688 ) 689 690 self.add_option('n_iter_inner_max', kwargs.get('n_iter_inner_max', 1000), 691 name='Max. inner Iter.', 692 info="maximal number of inner iterations for user equilibrium calcuation in the stochastic user assignment.", 693 cml='--max-inner-iterations', 694 groupnames=[optiongroup, 'options', ], 695 perm='rw', 696 ) 697 698 self.init_options_processing_common(**kwargs) 699 init_random(self, **kwargs) 700