| 1 | # |
|---|
| 2 | # Definitions for TSP/VRP with constraints. |
|---|
| 3 | # |
|---|
| 4 | # Copyright(c) Rod Millar 2008 |
|---|
| 5 | # email: rodj59@yahoo.com.au , rodj59@y7.com.au |
|---|
| 6 | # This program is free software; you can redistribute it and/or modify |
|---|
| 7 | # it under the terms of the GNU General Public License as published by |
|---|
| 8 | # the Free Software Foundation; either version 2 of the License, or |
|---|
| 9 | # (at your option) any later version. |
|---|
| 10 | # |
|---|
| 11 | # This program is distributed in the hope that it will be useful, |
|---|
| 12 | # but WITHOUT ANY WARRANTY; without even the implied warranty of |
|---|
| 13 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
|---|
| 14 | # GNU General Public License for more details. |
|---|
| 15 | # |
|---|
| 16 | # You should have received a copy of the GNU General Public License |
|---|
| 17 | # along with this program; if not, write to the Free Software |
|---|
| 18 | # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
|---|
| 19 | # |
|---|
| 20 | |
|---|
| 21 | import pg |
|---|
| 22 | |
|---|
| 23 | class plpy_class(object): |
|---|
| 24 | "Emulate the plpy module functionality from PostgreSQL" |
|---|
| 25 | def __init__(self,Hostname="rod1"): |
|---|
| 26 | # connect to the PostgreSQL DB |
|---|
| 27 | self.db = pg.DB("transdb",Hostname,5432,None,None,'transport','lost') |
|---|
| 28 | |
|---|
| 29 | def execute(self,qry): |
|---|
| 30 | "Emulate the PostgreSQL plpy.execute() function" |
|---|
| 31 | # ie. return a list of dictionaries for each row retrieved |
|---|
| 32 | rows = self.db.query(qry) |
|---|
| 33 | try: |
|---|
| 34 | drows = rows.dictresult() |
|---|
| 35 | return drows |
|---|
| 36 | except: |
|---|
| 37 | #print "*** execute(%s) returns = " % qry,rows |
|---|
| 38 | return rows |
|---|
| 39 | |
|---|
| 40 | def __del__(self): |
|---|
| 41 | # close the DB connection |
|---|
| 42 | self.db.close() |
|---|
| 43 | |
|---|
| 44 | plpy = plpy_class() # the DB interface |
|---|
| 45 | |
|---|
| 46 | |
|---|
| 47 | # Main loop |
|---|
| 48 | # Python function to find a path ordering which satisfies all constraints. |
|---|
| 49 | # |
|---|
| 50 | # max_dist = maximum distance deemed to be a consistent solution |
|---|
| 51 | # debug = > 0 to produce debugging output in debug_table |
|---|
| 52 | # search_dist = 0|1 if want to search for best distance above max_dist also |
|---|
| 53 | # search_lim = max no of cycles to search |
|---|
| 54 | # lahead = max number of options for look-ahead to consider |
|---|
| 55 | # ordered = 0 if you want to force search evaluation to be priority ordered |
|---|
| 56 | #def mainloop(tab varchar,link_tab varchar,job_tab varchar,max_dist float,debug int,search_dist int,search_lim int,lahead int,ordered int) |
|---|
| 57 | def mainloop(tab ,link_tab ,job_tab ,max_dist ,debug=1 ,search_dist=1 ,search_lim=35 ,lahead=10 ,ordered=0 ): |
|---|
| 58 | import time |
|---|
| 59 | global dbg_line,apply_changes_time,mainloop_time,non_gridlock_time,gridlock_time,FIRST_SEQ |
|---|
| 60 | MS = plpy.execute("select 'now'::timestamp as time")[0]['time'] |
|---|
| 61 | gridlock_time = plpy.execute("select '00:00:00'::interval as time")[0]['time'] |
|---|
| 62 | non_gridlock_time = plpy.execute("select '00:00:00'::interval as time")[0]['time'] |
|---|
| 63 | apply_changes_time = plpy.execute("select '00:00:00'::interval as time")[0]['time'] |
|---|
| 64 | search_limit = search_lim |
|---|
| 65 | best_dist = 2**32 # eg. start with inifinite distance as best |
|---|
| 66 | |
|---|
| 67 | # seq key to first destination in the path set |
|---|
| 68 | FIRST_SEQ = plpy.execute("select seq from %s where job_type in ('s','S') order by time_bound asc limit 1" % tab)[0]['seq'] |
|---|
| 69 | |
|---|
| 70 | |
|---|
| 71 | |
|---|
| 72 | def inconsistency_class(tab,link_tab,seq,max_dist): |
|---|
| 73 | rows = plpy.execute("select inconsistency_class('%s','%s',%s,%f)" % \ |
|---|
| 74 | (tab,link_tab,seq,max_dist)) |
|---|
| 75 | rows1 = plpy.execute("select * from %s where seq = %s" % (tab,seq)) |
|---|
| 76 | return rows[0]['inconsistency_class'],rows1[0] |
|---|
| 77 | |
|---|
| 78 | def priority_delta(cost,priority): |
|---|
| 79 | "Find the prioritised value of a solution, lower values being better" |
|---|
| 80 | # might need to make this return just cost when positive ??? XXX HERE |
|---|
| 81 | return cost - priority |
|---|
| 82 | |
|---|
| 83 | def min_priority_link(links): |
|---|
| 84 | "Select & return the path_link from the list which has the lowest priority" |
|---|
| 85 | ANS = links[0] |
|---|
| 86 | for link in links[1:]: |
|---|
| 87 | if link['priority'] < ANS['priority']: |
|---|
| 88 | ANS = link |
|---|
| 89 | return ANS |
|---|
| 90 | |
|---|
| 91 | def movement_exclusion_pre(prev,next,dest,pre=None,dest2=None): |
|---|
| 92 | """Return non-zero if the proposed movement of d to between p and n is not worthwhile. |
|---|
| 93 | pre = the destination currently the predecessor of dest. |
|---|
| 94 | This is called before the proposed movement has been applied.""" |
|---|
| 95 | # XXX HERE could return > 1 to indicate the inner loop can break ??? |
|---|
| 96 | if pre is None: |
|---|
| 97 | prows = plpy.execute("select prev_dest from %s where next_dest = %d and active" % \ |
|---|
| 98 | (link_tab,dest['seq'])) |
|---|
| 99 | if len(prows) <= 0: |
|---|
| 100 | return 1 # could be the first node of the path ... but redundant from above !! |
|---|
| 101 | |
|---|
| 102 | pre = prows[0]['prev_dest'] # existing active predecessor to dest |
|---|
| 103 | |
|---|
| 104 | |
|---|
| 105 | if prev['job_type'] in ('s','S') and dest['pu'] == 'f': |
|---|
| 106 | return 1 # dont link a drop straight after a start-of-day destination |
|---|
| 107 | if next['job_type'] in ('e','E') and ((dest2 is None and dest['pu'] == 't') or (dest2 is not None and dest2['pu'] == 't')): |
|---|
| 108 | return 1 # dont link a PU immediately before an end-of-day destination |
|---|
| 109 | if pre == prev['seq']: |
|---|
| 110 | return 1 # dont link back in same position !!! |
|---|
| 111 | |
|---|
| 112 | if prev['job'] == next['job'] and next['job_type'] not in ('p','P','s','S','e','E'): |
|---|
| 113 | return 1 # we dont split non point-2-point jobs !!! |
|---|
| 114 | |
|---|
| 115 | if prev['job_type'] in ('e','E') and next['job_type'] in ('s','S') : |
|---|
| 116 | return 1 # we dont insert between end-of-day & start-of-next-day markers |
|---|
| 117 | |
|---|
| 118 | if prev == dest: |
|---|
| 119 | return 1 # we cannot link destination as a successor of itself !!! |
|---|
| 120 | |
|---|
| 121 | # Add test to avoid overloading HERE XXXX !!!!!!!!!! ... or in the post method |
|---|
| 122 | |
|---|
| 123 | if dest2 is None or dest2 is dest: |
|---|
| 124 | if dest['pu'] == 'f': |
|---|
| 125 | # dest is a Drop, find its PU |
|---|
| 126 | dPU = plpy.execute("select * from %s where job = %s and pu" % (tab,dest['job']))[0] |
|---|
| 127 | if dPU['time'] > prev['time']: |
|---|
| 128 | return 10 # we dont move a Drop to an earlier position than its PickUp, move PU first |
|---|
| 129 | if dest['time_bound'] <= prev['time_bound'] and prev['pu'] == 't': |
|---|
| 130 | # ie. latest Drop is earlier than earliest PU for predecessor |
|---|
| 131 | return 1 # constraints unsatisfiable !!! XXX HERE |
|---|
| 132 | |
|---|
| 133 | |
|---|
| 134 | elif dest['pu'] == 't': |
|---|
| 135 | dD = plpy.execute("select * from %s where job = %s and not pu" % (tab,dest['job']))[0] |
|---|
| 136 | if dD['time'] <= prev['time']: |
|---|
| 137 | return 11 # we dont move a PU to later position than its Drop, move the Drop first |
|---|
| 138 | if dest['time_bound'] >= next['time_bound'] and next['pu'] == 'f': |
|---|
| 139 | # ie. earliest PU time is later than latest Drop time for next dest |
|---|
| 140 | return 1 # constraints unsatisfiable !!! XXX HERE |
|---|
| 141 | # also consider loads XXX HERE ... but need to allow sequences of more than one |
|---|
| 142 | # destinations to be moved at a time for this otherwise incomplete !!! |
|---|
| 143 | |
|---|
| 144 | else: # dest2 is not None |
|---|
| 145 | # need to know the set of destinations which will be moved |
|---|
| 146 | intermediates = plpy.execute("select * from following_destinations_inclusive('%s','%s',%s) where time <= '%s'::timestamp" % \ |
|---|
| 147 | ('tab','link_tab',dest['seq'],dest2['time'])) |
|---|
| 148 | for inter in intermediates: |
|---|
| 149 | if inter['seq'] in (prev['seq'],next['seq']): |
|---|
| 150 | return 1 # cant link segment to within itself |
|---|
| 151 | if inter['pu'] == 'f': |
|---|
| 152 | # inter is a Drop, find its PU |
|---|
| 153 | dPU = plpy.execute("select * from %s where job = %s and pu" % (tab,inter['job']))[0] |
|---|
| 154 | if dPU['time'] > prev['time']: |
|---|
| 155 | return 1 # we dont move a Drop to an earlier position than its PickUp, move PU first |
|---|
| 156 | if inter['time_bound'] <= prev['time_bound'] and prev['pu'] == 't': |
|---|
| 157 | # ie. latest Drop is earlier than earliest PU for predecessor |
|---|
| 158 | return 1 # constraints unsatisfiable !!! XXX HERE |
|---|
| 159 | elif inter['pu'] == 't': |
|---|
| 160 | dD = plpy.execute("select * from %s where job = %s and not pu" % (tab,inter['job']))[0] |
|---|
| 161 | if dD['time'] <= prev['time']: |
|---|
| 162 | return 1 # we dont move a PU to later position than its Drop, move the Drop first |
|---|
| 163 | if inter['time_bound'] >= next['time_bound'] and next['pu'] == 'f': |
|---|
| 164 | # ie. earliest PU time is later than latest Drop time for next dest |
|---|
| 165 | return 1 # constraints unsatisfiable !!! XXX HERE |
|---|
| 166 | |
|---|
| 167 | return 0 |
|---|
| 168 | |
|---|
| 169 | def movement_exclusion_post(p,n,d,d2=None): |
|---|
| 170 | """Return non-zero if the movement of d to between p and n is not worthwhile. |
|---|
| 171 | This is called only after the movement has been applied: ie. sequence p->d->n |
|---|
| 172 | is in the current (non-committed) path""" |
|---|
| 173 | |
|---|
| 174 | if d['pu'] == 'f': |
|---|
| 175 | # the following are tentative |
|---|
| 176 | # dont move a drop to earlier than its earliest acceptable pickup ( excluded automatically???) |
|---|
| 177 | dPU = plpy.execute("select * from %s where job = %s and pu" % (tab,d['job']))[0] |
|---|
| 178 | if dPU['time_bound'] > d['time']: |
|---|
| 179 | return 1 |
|---|
| 180 | # dont move a Drop to a position where its time is later than its timebound |
|---|
| 181 | # XXX HERE strengthen this XXX !!! ??? |
|---|
| 182 | #if d['load_pcnt'] > 1.01: |
|---|
| 183 | # #return 1 # don't overload |
|---|
| 184 | # pass |
|---|
| 185 | if d['time'] > d['time_bound'] : |
|---|
| 186 | # superficially, the drop is too late |
|---|
| 187 | # ... check what the direct time would be |
|---|
| 188 | if d['job_type'] in ('p','P'): |
|---|
| 189 | # p2p , take time from path_link |
|---|
| 190 | # if d['time_bound'] < d['time']: |
|---|
| 191 | # return 1 |
|---|
| 192 | nts = plpy.execute("select '%s'::timestamp + time_int as time from %s where prev_dest = %s and next_dest = %s" % \ |
|---|
| 193 | (dPU['time'],link_tab,dPU['seq'],d['seq']))[0]['time'] |
|---|
| 194 | if nts > d['time_bound']: |
|---|
| 195 | return 1 |
|---|
| 196 | else: |
|---|
| 197 | assert d['job_type'] in ('h','H','f','F'),"*** Assertion error: unexpected job_type" |
|---|
| 198 | return 1 # hourly job destinations are moved in pairs |
|---|
| 199 | # dont move a Drop destination to after a Pickup destination when the latest drop timebound is |
|---|
| 200 | # earlier than the earliest timebound for the destination Pickup |
|---|
| 201 | oPUs = plpy.execute("select * from following_destinations('%s','%s',%s) where pu and time <= '%s'::timestamp order by time_bound desc limit 1" % \ |
|---|
| 202 | (tab,link_tab,d['seq'],p['time'])) |
|---|
| 203 | if len(oPUs): |
|---|
| 204 | oPU = oPUs[0] |
|---|
| 205 | if oPU['time_bound'] > d['time_bound']: |
|---|
| 206 | return 1 |
|---|
| 207 | |
|---|
| 208 | elif d['pu'] == 't': |
|---|
| 209 | # the following are tentative |
|---|
| 210 | # dont move a Pickup to later than its latest acceptable drop - min travel time (consider load) |
|---|
| 211 | dD = plpy.execute("select * from %s where job = %s and not pu" % (tab,d['job']))[0] |
|---|
| 212 | if d['time'] > dD['time_bound']: |
|---|
| 213 | return 1 |
|---|
| 214 | # pass |
|---|
| 215 | #if d['load_pcnt'] > 1.01: |
|---|
| 216 | # return 1 # dont permit moves which overload (premised on multi-dest moves) |
|---|
| 217 | #pass |
|---|
| 218 | |
|---|
| 219 | # dont move a Pickup to a position where its Drop time is later than latest timebound |
|---|
| 220 | # HERE ... below could be strengthened to preclude all overdue moves |
|---|
| 221 | if dD['time'] > dD['time_bound'] and d['time'] < dD['time_bound']: # only applies if previously consistent ??? |
|---|
| 222 | # ie. superficially, this drop is too late |
|---|
| 223 | # ... but must check what the direct time from PU would be before excluding it |
|---|
| 224 | if dD['job_type'] in ('p','P'): # other case should be filtered out elsewhere !!! XXX |
|---|
| 225 | # p2p take time from path_link |
|---|
| 226 | nts = plpy.execute("select '%s'::timestamp + time_int as time from %s where prev_dest = %s and next_dest = %s" % \ |
|---|
| 227 | (d['time'],link_tab,d['seq'],dD['seq']))[0]['time'] |
|---|
| 228 | if nts > dD['time_bound'] : |
|---|
| 229 | return 1 # impossible for job to be on-time |
|---|
| 230 | else: |
|---|
| 231 | assert dD['job_type'] in ('h','H','f','F'),"*** Assertion error: unexpected job_type" |
|---|
| 232 | # NB. hourly job destinations are moved in pairs ! |
|---|
| 233 | if dD['time'] > dD['time_bound']: |
|---|
| 234 | return 1 |
|---|
| 235 | |
|---|
| 236 | # dont move a Pickup to before a drop destination when the earliest pickup timebound |
|---|
| 237 | # is later than the latest timebound for the destination drop |
|---|
| 238 | oDs = plpy.execute("select * from preceding_destinations('%s','%s',%s) where (not pu) and time <= '%s'::timestamp order by time_bound asc limit 1" % \ |
|---|
| 239 | (tab,link_tab,d['seq'],n['time'])) |
|---|
| 240 | if len(oDs): |
|---|
| 241 | oD = oDs[0] |
|---|
| 242 | if oD['time_bound'] < d['time_bound']: |
|---|
| 243 | return 1 |
|---|
| 244 | return 0 |
|---|
| 245 | |
|---|
| 246 | def apply_changes(prev,next,dest,priority=None,dest2=None): |
|---|
| 247 | "Move dest to between prev & next (seq nos). Return old predecessor,successor of dest" |
|---|
| 248 | global apply_changes_time,dbg_line |
|---|
| 249 | TS = plpy.execute("select 'now'::timestamp as time")[0]['time'] |
|---|
| 250 | if dest2 == dest : |
|---|
| 251 | assert dest2 is dest,"***Assertion failed, dest1 is not dest2" |
|---|
| 252 | dest2 = None |
|---|
| 253 | |
|---|
| 254 | if debug > 3: |
|---|
| 255 | dbg_line = dbg_line + 1 |
|---|
| 256 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 257 | ("Apply_changes(%d,%d,%d, time TS=%s) " % (prev,next,dest,TS ),dbg_line)) |
|---|
| 258 | |
|---|
| 259 | # if dest2 is not None, means the path segment between dest & dest2(inclusive) is to be moved |
|---|
| 260 | # to between prev & next |
|---|
| 261 | if dest2 is not None: |
|---|
| 262 | # moving a segment bounded by dest & dest2 |
|---|
| 263 | old_links = plpy.execute("select * from path_link_deactivation_triple('%s','%s',%d,%d,%d,%d)" % (tab,link_tab,prev,next,dest,dest2)) |
|---|
| 264 | |
|---|
| 265 | new_links = plpy.execute("select * from path_link_activation_triple('%s','%s',%d,%d,%d,%d)" % \ |
|---|
| 266 | (tab,link_tab,prev,next,dest,dest2)) |
|---|
| 267 | |
|---|
| 268 | else: # only moving a single destination |
|---|
| 269 | old_links = plpy.execute("select * from path_link_deactivation_triple('%s','%s',%d,%d,%d)" % (tab,link_tab,prev,next,dest)) |
|---|
| 270 | |
|---|
| 271 | new_links = plpy.execute("select * from path_link_activation_triple('%s','%s',%d,%d,%d)" % \ |
|---|
| 272 | (tab,link_tab,prev,next,dest)) |
|---|
| 273 | |
|---|
| 274 | assert len(old_links) == 3 , "Error: number of old_links = %d, prev=%s,next=%s,dest=%s,dest2=%s" % (len(old_links),prev,next,dest,dest2) |
|---|
| 275 | assert len(new_links) == 3 , "Error: number of new_links = %d, prev=%s,next=%s,dest=%s,dest2=%s" % (len(new_links),prev,next,dest,dest2) |
|---|
| 276 | # deactivate the old links |
|---|
| 277 | min_old_pr = None |
|---|
| 278 | for oidr in old_links: |
|---|
| 279 | if priority is not None: |
|---|
| 280 | # plpy.execute("update %s set active = false,priority = %f where prev_dest = %s and next_dest = %s" % \ |
|---|
| 281 | # (link_tab,priority,oidr['prev_dest'],oidr['next_dest'])) |
|---|
| 282 | plpy.execute("update %s set active = false where prev_dest = %s and next_dest = %s" % (link_tab,oidr['prev_dest'],oidr['next_dest'])) |
|---|
| 283 | if min_old_pr is None or min_old_pr['priority'] > oidr['priority']: |
|---|
| 284 | min_old_pr = oidr |
|---|
| 285 | |
|---|
| 286 | else: |
|---|
| 287 | plpy.execute("update %s set active = false where prev_dest = %s and next_dest = %s" % (link_tab,oidr['prev_dest'],oidr['next_dest'])) |
|---|
| 288 | if debug > 3: |
|---|
| 289 | dbg_line = dbg_line + 1 |
|---|
| 290 | plpy.execute("insert into debug_table values ('%s',%d)" % ("deactivate prev=%s , next=%s, " % (oidr['prev_dest'],oidr['next_dest']),dbg_line)) |
|---|
| 291 | |
|---|
| 292 | # collect the original prev & next destination sequence nos |
|---|
| 293 | if oidr['next_dest'] == dest : |
|---|
| 294 | old_prev = oidr['prev_dest'] |
|---|
| 295 | elif oidr['prev_dest'] == dest : |
|---|
| 296 | old_next = oidr['next_dest'] |
|---|
| 297 | # increment the priority of the lowest priority de-activated link |
|---|
| 298 | if min_old_pr is not None: |
|---|
| 299 | plpy.execute("update %s set priority = %s where prev_dest = %s and next_dest = %s" % \ |
|---|
| 300 | (link_tab,priority,min_old_pr['prev_dest'],min_old_pr['next_dest'])) |
|---|
| 301 | # activate the new links |
|---|
| 302 | for nidr in new_links: |
|---|
| 303 | # activate the new links |
|---|
| 304 | if debug > 3: |
|---|
| 305 | dbg_line = dbg_line + 1 |
|---|
| 306 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 307 | ("activating path_link , priority= %s,prev= %s , next = %s, # of new = %d" % (priority,nidr['prev_dest'],nidr['next_dest'],len(new_links)) ,dbg_line)) |
|---|
| 308 | if 0 and priority is not None: |
|---|
| 309 | plpy.execute("update %s set active = true,priority = %f where prev_dest = %s and next_dest = %s" % \ |
|---|
| 310 | (link_tab,priority-1,nidr['prev_dest'],nidr['next_dest'])) |
|---|
| 311 | else: |
|---|
| 312 | assert nidr['prev_dest'] is not None,"Exception, nidr is None" |
|---|
| 313 | plpy.execute("update %s set active = true where prev_dest = %s and next_dest = %s" % \ |
|---|
| 314 | (link_tab,nidr['prev_dest'],nidr['next_dest'])) |
|---|
| 315 | |
|---|
| 316 | # now propagate constraints through the newly active path |
|---|
| 317 | |
|---|
| 318 | # XXX HERE ... would be better if we knew the earliest destination which was changed !!! |
|---|
| 319 | # ... but note, propagation always stops when no change found ... |
|---|
| 320 | for seq_row in old_links : # + [{'oid':dest}]: |
|---|
| 321 | |
|---|
| 322 | changes = plpy.execute("select * from dest_changes('%s','%s','%s',(select prev_dest from %s where prev_dest = %s and next_dest = %s))" % \ |
|---|
| 323 | (tab,link_tab,job_tab,link_tab,seq_row['prev_dest'],seq_row['next_dest'])) |
|---|
| 324 | if debug > 3: |
|---|
| 325 | dbg_line = dbg_line +1 |
|---|
| 326 | plpy.execute("insert into debug_table values ('%s,prev=%d,next=%d, changes = %s',%d)" % ("activating changes from prev_dest ",seq_row['prev_dest'],seq_row['next_dest'],changes[0]['dest_changes'],dbg_line)) |
|---|
| 327 | # update cumulative execution time |
|---|
| 328 | apply_changes_time = plpy.execute("select (('now'::timestamp - '%s'::timestamp ) + '%s'::interval) as time" % (TS,apply_changes_time))[0]['time'] |
|---|
| 329 | return old_prev,old_next,old_links,new_links |
|---|
| 330 | |
|---|
| 331 | dbg_line = 1 |
|---|
| 332 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 333 | ("***At start apply_changes_time=%s) " % (apply_changes_time, ),dbg_line)) |
|---|
| 334 | |
|---|
| 335 | best_dist_path = None |
|---|
| 336 | consistent_count = 0 |
|---|
| 337 | if ordered == 0 : |
|---|
| 338 | incons = plpy.execute("select * from inconsistent_dests('%s','%s',%f) order by priority asc" % (tab,link_tab,max_dist)) |
|---|
| 339 | else: |
|---|
| 340 | incons = plpy.execute("select * from %s" % tab) # in this case just grab all regardless of inconsistency |
|---|
| 341 | num_dests = len(incons) # number of destinations in the path |
|---|
| 342 | if debug : |
|---|
| 343 | plpy.execute("delete from debug_table") # debugging |
|---|
| 344 | while (ordered <> 0 and search_limit > 0 and consistent_count < num_dests) or ( ordered == 0 and len(incons) and search_limit > 0) : # NB. not really necessary to identify inconsistency set in advance HERE XXX |
|---|
| 345 | |
|---|
| 346 | # keep processing until no inconsistencies remain or search limit is exceeded |
|---|
| 347 | search_limit = search_limit -1 |
|---|
| 348 | if search_limit < 0: |
|---|
| 349 | # abort with failure, return the empty destinations list |
|---|
| 350 | return [] |
|---|
| 351 | |
|---|
| 352 | # ... NB. to escape an inconsistency, priority must exceed weakest justification for it |
|---|
| 353 | # , which means the priority of the active link |
|---|
| 354 | |
|---|
| 355 | |
|---|
| 356 | # option_costs = [ [prev,next,dest,dest2,priority,cost,detect] ... ] for each candidate |
|---|
| 357 | option_costs = [] |
|---|
| 358 | gridlocked = 1 |
|---|
| 359 | consistent_count = 0 |
|---|
| 360 | |
|---|
| 361 | for option1 in incons: |
|---|
| 362 | # XXX HERE ... if options are not guaranteed inconsistent in advance, need to apply the test here |
|---|
| 363 | if ordered <> 0: |
|---|
| 364 | flag,option = inconsistency_class(tab,link_tab,option1['seq'],max_dist) |
|---|
| 365 | else: |
|---|
| 366 | option = option1 |
|---|
| 367 | flag = option['flag'] |
|---|
| 368 | |
|---|
| 369 | # take the alternate (ie. presently inactive) path_links & compute the cost to activate each |
|---|
| 370 | # ... which is the priority of the weakest active path_link precluding the activation |
|---|
| 371 | |
|---|
| 372 | # but first decide what causes the inconsistency so the minimal option set is considered |
|---|
| 373 | if debug > 3: |
|---|
| 374 | dbg_line = dbg_line+1 |
|---|
| 375 | dbg_line = dbg_line + 1 |
|---|
| 376 | |
|---|
| 377 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 378 | (" *** for option in incons seq=%d,suburb=%s,time=%s,dist=%f,load=%f,flag=%s,pu=%s" % \ |
|---|
| 379 | (option['seq'],option['suburb'],option['time'],option['dist'],option['load_pcnt'],option['flag'],option['pu']),dbg_line)) |
|---|
| 380 | |
|---|
| 381 | |
|---|
| 382 | if flag[5] == '1': # flag & 0000010 : |
|---|
| 383 | # missing predecessor |
|---|
| 384 | # ... this case should no longer apply since changes are applied in sets so the path remains complete |
|---|
| 385 | raise "Error: missing predecessor flag detected" |
|---|
| 386 | |
|---|
| 387 | elif flag[3] == '1': #flag & 0001000 : |
|---|
| 388 | # drop before pickup |
|---|
| 389 | # ... either move the drop after the pickup or the pickup before the drop |
|---|
| 390 | # NB. the one processed first will necessarily have no lesser priority than the other |
|---|
| 391 | # destination of the same job ! |
|---|
| 392 | if debug > 1: |
|---|
| 393 | dbg_line = dbg_line + 1 |
|---|
| 394 | plpy.execute("insert into debug_table values ( '*** Drop before PU, seq # = %s, job # = %s, suburb = %s , flag = %s, pu=%s',%d)" % (option['seq'],option['job'],option['suburb'], flag,option['pu'],dbg_line)) |
|---|
| 395 | |
|---|
| 396 | |
|---|
| 397 | # see if we have a drop or a pickup |
|---|
| 398 | if option['pu'] == 'f' : # XXX pg.DB returns 't' or 'f', plpy return 0 or 1 !!! |
|---|
| 399 | Drop = option |
|---|
| 400 | prows = plpy.execute("select * from %s where job = %s and pu" % (tab,option['job'])) |
|---|
| 401 | PU = prows[0] |
|---|
| 402 | else : |
|---|
| 403 | drows = plpy.execute("select * from %s where job = %s and not pu" % (tab,option['job'])) |
|---|
| 404 | PU = option |
|---|
| 405 | Drop = drows[0] |
|---|
| 406 | |
|---|
| 407 | # find whichever has highest priority |
|---|
| 408 | if Drop['priority'] > PU['priority']: |
|---|
| 409 | Detect = Drop |
|---|
| 410 | else: |
|---|
| 411 | Detect = PU |
|---|
| 412 | |
|---|
| 413 | # now PU/Drop are pickup & drop destinations corresponding to options job |
|---|
| 414 | |
|---|
| 415 | # try moving the Drop to a location after pickup |
|---|
| 416 | |
|---|
| 417 | # find the set of destinations which follow the Pickup |
|---|
| 418 | follows = plpy.execute("select * from following_destinations_inclusive('%s','%s',%d)" % \ |
|---|
| 419 | (tab,link_tab,PU['seq'])) |
|---|
| 420 | |
|---|
| 421 | # the Drop must be linked as the predecessor of one of these |
|---|
| 422 | option_priority = None |
|---|
| 423 | temp_options = [] |
|---|
| 424 | temp_options_nongridlock = [] |
|---|
| 425 | for i in range(1,len(follows)) : |
|---|
| 426 | prev = follows[i-1] |
|---|
| 427 | next = follows[i] |
|---|
| 428 | if prev['job'] == next['job'] and prev['job_type'] not in ('p','P','s','S'): |
|---|
| 429 | continue |
|---|
| 430 | |
|---|
| 431 | if movement_exclusion_pre(prev,next,Drop): continue |
|---|
| 432 | |
|---|
| 433 | rows = plpy.execute("select * from path_link_reloc_priority('%s','%s',%d,%d,%d)" % \ |
|---|
| 434 | (tab,link_tab,prev['seq'],next['seq'],Drop['seq'])) |
|---|
| 435 | # priority of moving the Drop to this location |
|---|
| 436 | if rows[0]['path_link_reloc_priority'] < Detect['priority']: |
|---|
| 437 | temp_options_nongridlock.append([prev,next,Drop,Drop,Detect['priority'],rows[0]['path_link_reloc_priority'],Detect['seq']]) |
|---|
| 438 | elif option_priority is None : # or option_priority > rows[0]['path_link_reloc_priority']: |
|---|
| 439 | Dest = Drop |
|---|
| 440 | option_priority = rows[0]['path_link_reloc_priority'] |
|---|
| 441 | |
|---|
| 442 | temp_options = [[prev,next,Dest,Dest,Detect['priority'],option_priority,Detect['seq']]] |
|---|
| 443 | #elif option_priority == rows[0]['path_link_reloc_priority']: |
|---|
| 444 | else: |
|---|
| 445 | temp_options.append([prev,next,Dest,Dest,Detect['priority'],option_priority,Detect['seq']]) |
|---|
| 446 | |
|---|
| 447 | # here indx is candidate index to cheapest option in follows |
|---|
| 448 | |
|---|
| 449 | # try moving the Pickup to a location before the Drop |
|---|
| 450 | |
|---|
| 451 | precedes = plpy.execute("select * from preceding_destinations_inclusive('%s','%s',%d)" % \ |
|---|
| 452 | (tab,link_tab,Drop['seq'])) |
|---|
| 453 | |
|---|
| 454 | # the Pickup must be linked as the predecessor of one of these |
|---|
| 455 | for i in range(1,len(precedes)): |
|---|
| 456 | prev = precedes[i] |
|---|
| 457 | next = precedes[i-1] |
|---|
| 458 | |
|---|
| 459 | if movement_exclusion_pre(prev,next,PU): continue |
|---|
| 460 | |
|---|
| 461 | rows = plpy.execute("select * from path_link_reloc_priority('%s','%s',%d,%d,%d)" % \ |
|---|
| 462 | (tab,link_tab,prev['seq'],next['seq'],PU['seq'])) |
|---|
| 463 | |
|---|
| 464 | if rows[0]['path_link_reloc_priority'] < Detect['priority']: |
|---|
| 465 | temp_options_nongridlock.append([prev,next,PU,PU,Detect['priority'],rows[0]['path_link_reloc_priority'],Detect['seq']]) |
|---|
| 466 | elif option_priority is None : # or option_priority > rows[0]['path_link_reloc_priority']: |
|---|
| 467 | Dest = PU |
|---|
| 468 | option_priority = rows[0]['path_link_reloc_priority'] |
|---|
| 469 | |
|---|
| 470 | temp_options = [[prev,next,Dest,Dest,Detect['priority'],option_priority,Detect['seq']]] |
|---|
| 471 | #elif option_priority == rows[0]['path_link_reloc_priority'] : |
|---|
| 472 | else: |
|---|
| 473 | temp_options.append([prev,next,Dest,Dest,Detect['priority'],option_priority,Detect['seq']]) |
|---|
| 474 | |
|---|
| 475 | if debug : |
|---|
| 476 | try: |
|---|
| 477 | dbg_line = dbg_line+1 |
|---|
| 478 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 479 | ("Drop b4 PU, prev=%d,next=%d,dest=%d,priority=%f,detect=%s,cost=%s" % \ |
|---|
| 480 | (prev['seq'],next['seq'],Dest['seq'],Detect['priority'],Detect['seq'],option_priority),dbg_line)) |
|---|
| 481 | except: |
|---|
| 482 | pass # means only non-gridlock options found |
|---|
| 483 | |
|---|
| 484 | option_costs = option_costs+ temp_options + temp_options_nongridlock |
|---|
| 485 | |
|---|
| 486 | elif flag[4] == '1': # flag & 0000100 : |
|---|
| 487 | # pickup & drop on different days |
|---|
| 488 | # ... either move the drop backward or move the pickup forward to same day |
|---|
| 489 | |
|---|
| 490 | if flag[3] == '1': |
|---|
| 491 | continue # if Drop before PU inconsistency also exists, we fix that first ! |
|---|
| 492 | |
|---|
| 493 | # locate the PU & Drop |
|---|
| 494 | if option['pu'] == 't': |
|---|
| 495 | PU = option |
|---|
| 496 | Drops = plpy.execute("select * from %s where not pu and job = %s limit 1" % \ |
|---|
| 497 | (tab,option['job'])) |
|---|
| 498 | Drop = Drops[0] |
|---|
| 499 | else: |
|---|
| 500 | Drop = option |
|---|
| 501 | PUs = plpy.execute("select * from %s where pu and job = %s limit 1" % \ |
|---|
| 502 | (tab,option['job'])) |
|---|
| 503 | PU = PUs[0] |
|---|
| 504 | |
|---|
| 505 | # find whichever has highest priority |
|---|
| 506 | if PU['priority'] < Drop['priority']: |
|---|
| 507 | Detect = Drop |
|---|
| 508 | else: |
|---|
| 509 | Detect = PU |
|---|
| 510 | |
|---|
| 511 | |
|---|
| 512 | # find the am destination on same day as the Drop |
|---|
| 513 | rows = plpy.execute("select * from preceding_destinations('%s','%s',%d) where job_type in ('s','S') limit 1" % \ |
|---|
| 514 | (tab,link_tab,Drop['seq'])) |
|---|
| 515 | assert len(rows),"*** PU/Drop differing days but no intermediate Home destinations !\n" |
|---|
| 516 | BefDrop = rows[0] # Home destination in morning before Drop |
|---|
| 517 | |
|---|
| 518 | # find the pm destination on same day as PU |
|---|
| 519 | rows = plpy.execute("select * from following_destinations('%s','%s',%d) where job_type in ('e','E') limit 1" % \ |
|---|
| 520 | (tab,link_tab,PU['seq'])) |
|---|
| 521 | assert len(rows),"*** PU/Drop differing days but no intermediate Home destinations !\n" |
|---|
| 522 | AftPU = rows[0] # Home destination in afternoon after PU |
|---|
| 523 | |
|---|
| 524 | # method is to move PU to same day as drop, or drop to same day as pickup |
|---|
| 525 | |
|---|
| 526 | |
|---|
| 527 | # try moving PU to Drop day first |
|---|
| 528 | # ... |
|---|
| 529 | rows1 = plpy.execute("select * from preceding_destinations_inclusive('%s','%s',%d)" % \ |
|---|
| 530 | (tab,link_tab,Drop['seq'])) |
|---|
| 531 | option_priority = None |
|---|
| 532 | temp_options = [] |
|---|
| 533 | temp_options_nongridlock = [] |
|---|
| 534 | for i in range(1,len(rows1)): |
|---|
| 535 | prev = rows1[i] |
|---|
| 536 | next = rows1[i-1] |
|---|
| 537 | |
|---|
| 538 | if movement_exclusion_pre(prev,next,PU): continue |
|---|
| 539 | |
|---|
| 540 | # now check the priority to move PU to each position on the same day as the Drop |
|---|
| 541 | rows = plpy.execute("select * from path_link_reloc_priority('%s','%s',%d,%d,%d)" % \ |
|---|
| 542 | (tab,link_tab,prev['seq'],next['seq'],PU['seq'])) |
|---|
| 543 | |
|---|
| 544 | if rows[0]['path_link_reloc_priority'] < Detect['priority']: |
|---|
| 545 | temp_options_nongridlock.append([prev,next,PU,PU,Detect['priority'],rows[0]['path_link_reloc_priority'],Detect['seq']]) |
|---|
| 546 | elif option_priority is None : # or option_priority > rows[0]['path_link_reloc_priority']: |
|---|
| 547 | option_priority = rows[0]['path_link_reloc_priority'] |
|---|
| 548 | |
|---|
| 549 | temp_options = [[prev,next,PU,PU,Detect['priority'],option_priority,Detect['seq']]] |
|---|
| 550 | if debug > 2: |
|---|
| 551 | dbg_line = dbg_line + 1 |
|---|
| 552 | plpy.execute("insert into debug_table values ('%s',%d) " % \ |
|---|
| 553 | ( " ### PU/Drop Different Days (move PU) : added option prev=%s,next=%s,dest=%s,cost=%s,priority=%s,detect=%s" % (prev['seq'],next['seq'],PU['seq'],option_priority,Detect['priority'],Detect['seq']),dbg_line)) |
|---|
| 554 | |
|---|
| 555 | |
|---|
| 556 | #elif option_priority == rows[0]['path_link_reloc_priority']: |
|---|
| 557 | else: |
|---|
| 558 | temp_options.append([prev,next,PU,PU,Detect['priority'],option_priority,Detect['seq']]) |
|---|
| 559 | if debug > 2: |
|---|
| 560 | dbg_line = dbg_line + 1 |
|---|
| 561 | plpy.execute("insert into debug_table values ('%s',%d) " % \ |
|---|
| 562 | ( " ### PU/Drop Different Days (move PU) : added option prev=%s,next=%s,dest=%s,cost=%s,priority=%s,detect=%s" % (prev['seq'],next['seq'],PU['seq'],option_priority,Detect['priority'],Detect['seq']),dbg_line)) |
|---|
| 563 | |
|---|
| 564 | |
|---|
| 565 | if prev['seq'] == BefDrop['seq']: |
|---|
| 566 | break # we have reached the am Home destination |
|---|
| 567 | |
|---|
| 568 | # indx is candidate index to the cheapest option in rows |
|---|
| 569 | |
|---|
| 570 | |
|---|
| 571 | # now try moving Drop to PU day |
|---|
| 572 | rows2 = plpy.execute("select * from following_destinations_inclusive('%s','%s',%d)" % \ |
|---|
| 573 | (tab,link_tab,PU['seq'])) |
|---|
| 574 | for i in range(1,len(rows2)): |
|---|
| 575 | prev = rows2[i-1] |
|---|
| 576 | next = rows2[i] |
|---|
| 577 | |
|---|
| 578 | if movement_exclusion_pre(prev,next,Drop): continue |
|---|
| 579 | |
|---|
| 580 | # now check the priority to move PU to each position on the same day as the Drop |
|---|
| 581 | rows = plpy.execute("select * from path_link_reloc_priority('%s','%s',%d,%d,%d)" % \ |
|---|
| 582 | (tab,link_tab,prev['seq'],next['seq'],Drop['seq'])) |
|---|
| 583 | |
|---|
| 584 | |
|---|
| 585 | if rows[0]['path_link_reloc_priority'] < Detect['priority']: |
|---|
| 586 | temp_options_nongridlock.append([prev,next,Drop,Drop,Detect['priority'],rows[0]['path_link_reloc_priority'],Detect['seq']]) |
|---|
| 587 | elif option_priority is None : # or option_priority > rows[0]['path_link_reloc_priority']: |
|---|
| 588 | option_priority = rows[0]['path_link_reloc_priority'] |
|---|
| 589 | |
|---|
| 590 | temp_options = [[prev,next,Drop,Drop,Detect['priority'],option_priority,Detect['seq']]] |
|---|
| 591 | if debug > 2: |
|---|
| 592 | dbg_line = dbg_line + 1 |
|---|
| 593 | plpy.execute("insert into debug_table values ('%s',%d) " % \ |
|---|
| 594 | ( " ### PU/Drop Different Days(move Drop) : added option prev=%s,next=%s,dest=%s,cost=%s,priority=%s,detect=%s" % (prev['seq'],next['seq'],Drop['seq'],option_priority,Detect['priority'],Detect['seq']),dbg_line)) |
|---|
| 595 | |
|---|
| 596 | #elif option_priority == rows[0]['path_link_reloc_priority']: |
|---|
| 597 | else: |
|---|
| 598 | temp_options.append([prev,next,Drop,Drop,Detect['priority'],option_priority,Detect['seq']]) |
|---|
| 599 | if debug > 2: |
|---|
| 600 | dbg_line = dbg_line + 1 |
|---|
| 601 | plpy.execute("insert into debug_table values ('%s',%d) " % \ |
|---|
| 602 | ( " ### PU/Drop Different Days(move Drop) : added option prev=%s,next=%s,dest=%s,cost=%s,priority=%s,detect=%s" % (prev['seq'],next['seq'],Drop['seq'],option_priority,Detect['priority'],Detect['seq']),dbg_line)) |
|---|
| 603 | |
|---|
| 604 | if next['seq'] == AftPU['seq']: |
|---|
| 605 | break # we have reached the pm Home destination |
|---|
| 606 | |
|---|
| 607 | # indx is candidate index to the cheapest option in rows |
|---|
| 608 | |
|---|
| 609 | # select whichever is the cheapest |
|---|
| 610 | option_costs = option_costs + temp_options+ temp_options_nongridlock |
|---|
| 611 | |
|---|
| 612 | |
|---|
| 613 | if debug : |
|---|
| 614 | dbg_line = dbg_line+1 |
|---|
| 615 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 616 | ("PU & Drop on different days, prev=%s,next=%s,dest=%s,dest2=%s,priority=%s , cost=%s, detect=%s" % \ |
|---|
| 617 | (option_costs[-1][0]['seq'],option_costs[-1][1]['seq'],option_costs[-1][2]['seq'],option_costs[-1][3]['seq'],option_costs[-1][4],option_costs[-1][5],option_costs[-1][6]),dbg_line)) |
|---|
| 618 | |
|---|
| 619 | elif flag[1] == '1' and flag[0] != '1': # flag & 0100000 : |
|---|
| 620 | # drop is too late |
|---|
| 621 | # ... move the drop earlier or delete a destination before drop ( .. or rearrange the preceding path ... thats the dilemma ) |
|---|
| 622 | |
|---|
| 623 | PUs = plpy.execute("select * from %s where pu and job = %d" % \ |
|---|
| 624 | (tab,option['job'])) |
|---|
| 625 | PU = PUs[0] # PU is the corresponding Pickup |
|---|
| 626 | |
|---|
| 627 | # now find the destinations between the two ... [PU +1, ... ,Drop-1] |
|---|
| 628 | # intermediates = plpy.execute("select * from following_destinations('%s','%s',%d) where seq in (select seq from preceding_destinations('%s','%s',%d))" % \ |
|---|
| 629 | # (tab,link_tab,PU['seq'],tab,link_tab,option['seq'])) |
|---|
| 630 | |
|---|
| 631 | following = plpy.execute("select * from following_destinations_inclusive('%s','%s',%d)" % \ |
|---|
| 632 | (tab,link_tab,option['seq'])) |
|---|
| 633 | |
|---|
| 634 | # destinations before DROP NB. XXX HERE can optimise this by limiting to destinations whose time is after the scheduled earliest PU time !!! |
|---|
| 635 | preceding = plpy.execute("select * from preceding_destinations('%s','%s',%d)" % \ |
|---|
| 636 | (tab,link_tab,option['seq'])) |
|---|
| 637 | option_priority = None |
|---|
| 638 | |
|---|
| 639 | if debug > 1: |
|---|
| 640 | dbg_line = dbg_line + 1 |
|---|
| 641 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 642 | ("--- Drop too late, PU = %s, Drop = %s, # of following = %d, # of intermediates = %d " % (PU['seq'],option['seq'],len(following),len(intermediates)) ,dbg_line)) |
|---|
| 643 | |
|---|
| 644 | temp_options = [] |
|---|
| 645 | temp_options_nongridlock = [] |
|---|
| 646 | Drop = option |
|---|
| 647 | # first consider costs to move the destination to an earlier position in the path |
|---|
| 648 | for i in range(1,len(preceding)): |
|---|
| 649 | prev = preceding[i] |
|---|
| 650 | next = preceding[i-1] |
|---|
| 651 | if prev['job_type'] in ('s','S') and next['job_type'] in ('e','E'): |
|---|
| 652 | continue # not between end-of-day/start-of-day |
|---|
| 653 | if next['seq'] == option['seq']: |
|---|
| 654 | # dont move Drop before PU XXX HERE |
|---|
| 655 | Drop = PU # ... switch to moving PU further backwards instead XXX ??? |
|---|
| 656 | |
|---|
| 657 | if movement_exclusion_pre(prev,next,Drop): |
|---|
| 658 | continue |
|---|
| 659 | |
|---|
| 660 | rows = plpy.execute("select * from path_link_reloc_priority('%s','%s',%d,%d,%d)" % \ |
|---|
| 661 | (tab,link_tab,prev['seq'],next['seq'],Drop['seq'])) |
|---|
| 662 | if debug > 1: |
|---|
| 663 | dbg_line = dbg_line + 1 |
|---|
| 664 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 665 | ("--- Drop too late, to move Drop %s to between %s and %s, cost = %s " % (Drop['seq'],prev['seq'],next['seq'],rows[0]['path_link_reloc_priority']) ,dbg_line)) |
|---|
| 666 | |
|---|
| 667 | if rows[0]['path_link_reloc_priority'] < option['priority']: |
|---|
| 668 | temp_options_nongridlock.append([prev,next,Drop,Drop,option['priority'],option_priority,option['seq']]) |
|---|
| 669 | elif option_priority is None : # or option_priority > rows[0]['path_link_reloc_priority'] : |
|---|
| 670 | option_priority = rows[0]['path_link_reloc_priority'] |
|---|
| 671 | # questionable but necessary to enable the look-ahead to function on equal priorities |
|---|
| 672 | temp_options = [[prev,next,option,option,option['priority'],option_priority,option['seq']]] |
|---|
| 673 | #elif option_priority == rows[0]['path_link_reloc_priority'] : |
|---|
| 674 | else: |
|---|
| 675 | temp_options.append([prev,next,option,option,option['priority'],option_priority,option['seq']]) |
|---|
| 676 | # XXX HERE .. actually, the following should consider moving inter to all positions, as for dist-too-long case !!! since a sequence change might change the travel times |
|---|
| 677 | # next consider costs to move a destination in the preceding path to after the drop |
|---|
| 678 | for inter in preceding: |
|---|
| 679 | for j in range(1,len(following)): |
|---|
| 680 | jprev1 = following[j-1] |
|---|
| 681 | jnext1 = following[j] |
|---|
| 682 | |
|---|
| 683 | |
|---|
| 684 | if inter['seq'] == jprev1['seq']: continue |
|---|
| 685 | if jprev1['job_type'] in ('e','E') and jnext1['job_type'] in ('s','S'): |
|---|
| 686 | continue |
|---|
| 687 | if jprev1['job_type'] not in ('p','P'): |
|---|
| 688 | continue |
|---|
| 689 | if jprev1['job'] == inter['job'] and inter['pu'] == 't': |
|---|
| 690 | continue |
|---|
| 691 | |
|---|
| 692 | if movement_exclusion_pre(jprev1,jnext1,inter): |
|---|
| 693 | continue |
|---|
| 694 | |
|---|
| 695 | # priority to move inter(mediate) dest to after Drop |
|---|
| 696 | rows = plpy.execute("select * from path_link_reloc_priority('%s','%s',%s,%s,%s)" % \ |
|---|
| 697 | (tab,link_tab,jprev1['seq'],jnext1['seq'],inter['seq'])) |
|---|
| 698 | |
|---|
| 699 | if debug > 2: |
|---|
| 700 | dbg_line = dbg_line + 1 |
|---|
| 701 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 702 | ("--- Drop too late, to move Intermed %s to between %s %s, cost = %s " % (inter['seq'],jprev1['seq'],jnext1['seq'],rows[0]['path_link_reloc_priority']) ,dbg_line)) |
|---|
| 703 | |
|---|
| 704 | if rows[0]['path_link_reloc_priority'] < option['priority']: |
|---|
| 705 | temp_options_nongridlock.append([jprev1,jnext1,inter,inter,option['priority'],rows[0]['path_link_reloc_priority'],option['seq']]) |
|---|
| 706 | elif option_priority is None : # or option_priority > rows[0]['path_link_reloc_priority']: |
|---|
| 707 | option_priority = rows[0]['path_link_reloc_priority'] |
|---|
| 708 | temp_options = [[jprev1,jnext1,inter,inter,option['priority'],option_priority,option['seq']]] |
|---|
| 709 | #elif option_priority == rows[0]['path_link_reloc_priority']: |
|---|
| 710 | else: |
|---|
| 711 | temp_options.append([jprev1,jnext1,inter,inter,option['priority'],option_priority,option['seq']]) |
|---|
| 712 | |
|---|
| 713 | if debug : |
|---|
| 714 | dbg_line = dbg_line + 1 |
|---|
| 715 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 716 | ("--- Drop too late, to move Intermed %s to between %s %s, cost = %s " % (inter['seq'],jprev1['seq'],jnext1['seq'],rows[0]['path_link_reloc_priority']) ,dbg_line)) |
|---|
| 717 | |
|---|
| 718 | if debug > 2: |
|---|
| 719 | for item in temp_options2: |
|---|
| 720 | dbg_line = dbg_line + 1 |
|---|
| 721 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 722 | ("--> temp_option2 ,p=%s, n=%s, d=%s,%s , pr=%s, c=%s, det=%s " % (item[0],item[1],item[2],item[3],item[4],item[5],item[6]), dbg_line)) |
|---|
| 723 | |
|---|
| 724 | if len(temp_options) + len(temp_options_nongridlock) < 1: |
|---|
| 725 | # continue # skip this |
|---|
| 726 | raise "*** Exception : Wot!!! Excluded all options !!!" # this option not viable !!! XXX but why ??? |
|---|
| 727 | |
|---|
| 728 | option_costs = option_costs + temp_options + temp_options_nongridlock |
|---|
| 729 | |
|---|
| 730 | if debug > 1 : |
|---|
| 731 | dbg_line = dbg_line+1 |
|---|
| 732 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 733 | ("Drop too late %s" % len(option_costs),dbg_line)) |
|---|
| 734 | for item in option_costs: |
|---|
| 735 | dbg_line = dbg_line + 1 |
|---|
| 736 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 737 | ("--> Drop too late, added option ,prev=%s, next=%s, dest=%s,dest2=%s , priority=%s, cost=%s, detection seq=%s " % (item[0],item[1],item[2],item[3],item[4],item[5,item[6]]), dbg_line)) |
|---|
| 738 | |
|---|
| 739 | elif flag[2] == '1' and option['pu'] == 't': # flag & 0010000 : |
|---|
| 740 | # overloaded .. |
|---|
| 741 | # first make sure we are working with the PU of the job |
|---|
| 742 | if debug > 1: |
|---|
| 743 | dbg_line = dbg_line + 1 |
|---|
| 744 | plpy.execute("insert into debug_table values ('%s',%d) " % \ |
|---|
| 745 | ( " ### in Overloaded : option[pu] = %s, option[seq] = %s" % (option['pu'],option['seq']),dbg_line)) |
|---|
| 746 | |
|---|
| 747 | if option['pu'] != 't': |
|---|
| 748 | raise "Exception Error: executing overloaded with a non-PU destination option" # NB. this will be dealt with by anther jobs PU |
|---|
| 749 | # NB XXX HERE ... could alternately seek first dest in which current overload occurs ??? |
|---|
| 750 | else: |
|---|
| 751 | PU = option |
|---|
| 752 | prows = plpy.execute("select * from path_dest where not pu and job = %s" % option['job']) |
|---|
| 753 | Drop = prows[0] |
|---|
| 754 | |
|---|
| 755 | # find the PUs which precede the PU where the corresponding Drop follows the PU |
|---|
| 756 | rows = plpy.execute("select * from pu_b4_drop_after('%s','%s',%d) order by time asc" % \ |
|---|
| 757 | (tab,link_tab,PU['seq'])) |
|---|
| 758 | |
|---|
| 759 | |
|---|
| 760 | # NB. we assume the vehicle can carry all loads one-at-a-time |
|---|
| 761 | assert len(rows),"Vehicle cannot carry the load, this should not happen !!!" |
|---|
| 762 | |
|---|
| 763 | |
|---|
| 764 | # ... either move a preceding PU to after Drop or move a following Drop to before PU |
|---|
| 765 | |
|---|
| 766 | # find the set of destinations following PU (inclusive) |
|---|
| 767 | follows = plpy.execute("select * from following_destinations_inclusive('%s','%s',%d)" % \ |
|---|
| 768 | (tab,link_tab,PU['seq'])) |
|---|
| 769 | |
|---|
| 770 | |
|---|
| 771 | # find the set of destinations preceding PU (inclusive) |
|---|
| 772 | precedes = plpy.execute("select * from preceding_destinations_inclusive('%s','%s',%d)" % \ |
|---|
| 773 | (tab,link_tab,PU['seq'])) |
|---|
| 774 | |
|---|
| 775 | |
|---|
| 776 | # try moving a preceding PU to after PU (NB. can restrict to before the PUs corresponding Drop XXX HERE) |
|---|
| 777 | option_priority = None |
|---|
| 778 | temp_options = [] |
|---|
| 779 | temp_options_nongridlock = [] |
|---|
| 780 | for pre_PU in rows: |
|---|
| 781 | if pre_PU['pu'] == 'f': |
|---|
| 782 | continue # skip drops |
|---|
| 783 | |
|---|
| 784 | for j in range(1,len(follows)): |
|---|
| 785 | prev = follows[j-1] |
|---|
| 786 | next = follows[j] |
|---|
| 787 | |
|---|
| 788 | if prev['job_type'] in ('e','E') and next['jobt_type'] in ('s','S'): |
|---|
| 789 | continue # not between end-of-day/start-of-day |
|---|
| 790 | # if pre_PU['job'] == prev['job'] and pre_PU is not prev : |
|---|
| 791 | # #break |
|---|
| 792 | # pre_PU = prev # XXX HERE ... a succinct switch here ... does it work ??? |
|---|
| 793 | # #continue # dont move PU to after its corresponding Drop (XXX HERE ... this may ruin completeness !!!) |
|---|
| 794 | # ... may need to consider instead moving the Drop to after Drop, or both together |
|---|
| 795 | |
|---|
| 796 | if movement_exclusion_pre(prev,next,pre_PU): |
|---|
| 797 | continue |
|---|
| 798 | |
|---|
| 799 | rows1 = plpy.execute("select * from path_link_reloc_priority('%s','%s',%d,%d,%d)" % \ |
|---|
| 800 | (tab,link_tab,prev['seq'],next['seq'],pre_PU['seq'])) |
|---|
| 801 | priority1 = rows1[0]['path_link_reloc_priority'] |
|---|
| 802 | |
|---|
| 803 | if priority1 < PU['priority']: |
|---|
| 804 | temp_options_nongridlock.append([prev,next,pre_PU,pre_PU,PU['priority'],option_priority,PU['seq']]) |
|---|
| 805 | elif option_priority is None : # or option_priority > priority1: |
|---|
| 806 | option_priority = priority1 |
|---|
| 807 | temp_options = [[prev,next,pre_PU,pre_PU,PU['priority'],priority1,PU['seq']]] |
|---|
| 808 | #elif option_priority == priority1: |
|---|
| 809 | else: |
|---|
| 810 | temp_options.append([prev,next,pre_PU,pre_PU,PU['priority'],priority1,PU['seq']]) |
|---|
| 811 | |
|---|
| 812 | # try moving a following Drop to before PU (NB. can restrict to after the following Drops corresponding PU XXX HERE) |
|---|
| 813 | for post_Drop in rows: |
|---|
| 814 | if post_Drop['pu'] == 't': |
|---|
| 815 | continue # skip Pickups |
|---|
| 816 | |
|---|
| 817 | for j in range(1,len(precedes)): |
|---|
| 818 | prev = precedes[j] |
|---|
| 819 | next = precedes[j-1] |
|---|
| 820 | if prev['job_type'] in ('s','S'): |
|---|
| 821 | continue |
|---|
| 822 | # if next['job'] == post_Drop['job']: |
|---|
| 823 | # #break |
|---|
| 824 | # post_Drop = next # ... see above ... XXX will this work ??? ie. switch to the PU .. to make room for moving Drop in the next action ... |
|---|
| 825 | # #continue # don't go beyond the Drops PU !!! XXX |
|---|
| 826 | |
|---|
| 827 | if movement_exclusion_pre(prev,next,post_Drop): |
|---|
| 828 | continue |
|---|
| 829 | |
|---|
| 830 | rows2 = plpy.execute("select * from path_link_reloc_priority('%s','%s',%d,%d,%d)" % \ |
|---|
| 831 | (tab,link_tab,prev['seq'],next['seq'],post_Drop['seq'])) |
|---|
| 832 | priority2 = rows2[0]['path_link_reloc_priority'] |
|---|
| 833 | |
|---|
| 834 | if debug > 2: |
|---|
| 835 | dbg_line = dbg_line + 1 |
|---|
| 836 | plpy.execute("insert into debug_table values ('%s',%d) " % \ |
|---|
| 837 | ( " ### in Overloaded code block: second loop, prev=%s, next=%s,option_priority=%s, priority2=%s" % (prev['seq'],next['seq'],option_priority,priority2 ),dbg_line)) |
|---|
| 838 | |
|---|
| 839 | if priority2 < PU['priority']: |
|---|
| 840 | temp_options_nongridlock.append([prev,next,post_Drop,post_Drop,PU['priority'],option_priority,PU['seq']]) |
|---|
| 841 | elif option_priority is None : # or option_priority > priority2: |
|---|
| 842 | option_priority = priority2 |
|---|
| 843 | temp_options = [[prev,next,post_Drop,post_Drop,PU['priority'],option_priority,PU['seq']]] |
|---|
| 844 | #elif option_priority == priority2: |
|---|
| 845 | else: |
|---|
| 846 | temp_options.append([prev,next,post_Drop,post_Drop,PU['priority'],priority2,PU['seq']]) |
|---|
| 847 | |
|---|
| 848 | # try moving the PU to after a following Drop |
|---|
| 849 | for post_Drop in rows: # ie. PU before Drop after set |
|---|
| 850 | if post_Drop['pu'] == 't': |
|---|
| 851 | continue # skip Pickups |
|---|
| 852 | if post_Drop['job_type'] in ('e','E'): |
|---|
| 853 | continue # not between end-of-day/start-of-day |
|---|
| 854 | |
|---|
| 855 | # find the seq # of destination which follows post_Drop |
|---|
| 856 | next = plpy.execute("select * from following_destinations('%s','%s',%s) limit 1" % \ |
|---|
| 857 | (tab,link_tab,post_Drop['seq']))[0] |
|---|
| 858 | |
|---|
| 859 | if debug > 2: |
|---|
| 860 | dbg_line + 1 |
|---|
| 861 | plpy.execute("insert into debug_table values ('%s',%d) " % \ |
|---|
| 862 | ( " ### in Overloaded : third loop: prev = %s, next = %s, dest = %s" % (PU['seq'],post_Drop['seq'],next['next_dest']),dbg_line)) |
|---|
| 863 | # HERE XXX add movement_exclusion_pre( ) call HERE !!!!!!!!!! |
|---|
| 864 | if movement_exclusion_pre(PU,post_Drop,next): |
|---|
| 865 | continue |
|---|
| 866 | rows3 = plpy.execute("select * from path_link_reloc_priority('%s','%s',%s,%s,%s) " % \ |
|---|
| 867 | (tab,link_tab,post_Drop['seq'],next['seq'],PU['seq'])) |
|---|
| 868 | |
|---|
| 869 | priority3 = rows3[0]['path_link_reloc_priority'] |
|---|
| 870 | if priority3 < PU['priority']: |
|---|
| 871 | temp_options_nongridlock.append([post_Drop,next,PU,PU,PU['priority'],priority3,PU['seq']]) |
|---|
| 872 | |
|---|
| 873 | elif option_priority is None :#or option_priority > priority3: |
|---|
| 874 | option_priority = priority3 |
|---|
| 875 | temp_options = [[post_Drop,next,PU,PU,PU['priority'],option_priority,PU['seq']]] |
|---|
| 876 | #elif option_priority == priority3: |
|---|
| 877 | else: |
|---|
| 878 | temp_options.append([post_Drop,next,PU,PU,PU['priority'],priority3,PU['seq']]) |
|---|
| 879 | # select the best option |
|---|
| 880 | |
|---|
| 881 | option_costs = option_costs+ temp_options + temp_options_nongridlock |
|---|
| 882 | if len(temp_options) + len(temp_options_nongridlock) <= 0: |
|---|
| 883 | continue |
|---|
| 884 | if debug : |
|---|
| 885 | dbg_line = dbg_line+1 |
|---|
| 886 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 887 | ("Vehicle overloaded, prev=%s,next=%s,dest=%s,dest2=%s,cost=%s, detect = %s" % \ |
|---|
| 888 | (option_costs[-1][0]['seq'],option_costs[-1][1]['seq'],option_costs[-1][2]['seq'],option_costs[-1][3]['seq'],option_costs[-1][5],option_costs[-1][6]),dbg_line)) |
|---|
| 889 | |
|---|
| 890 | |
|---|
| 891 | |
|---|
| 892 | elif flag[0] == '1' : # flag & 1000000 : |
|---|
| 893 | # distance too long |
|---|
| 894 | # ... select an active link preceding the inconsistency detection point and deactivate it |
|---|
| 895 | # or, put another way, move one of the destinations in the path prior to detection |
|---|
| 896 | # .. the alternate position should preferably minimise the travel distance ... but this |
|---|
| 897 | # may take many further steps to evaluate ... |
|---|
| 898 | |
|---|
| 899 | # it is only the destinations which precede this destination which can affect distance ... |
|---|
| 900 | i_precedes = plpy.execute("select * from preceding_destinations('%s','%s',%d) where inconsistency_class('%s','%s',seq,%f) & B'1000000' = B'1000000' limit 1 " % \ |
|---|
| 901 | (tab,link_tab,option['seq'],tab,link_tab,max_dist )) |
|---|
| 902 | |
|---|
| 903 | # further it is only necessary to process the first destination at which distance |
|---|
| 904 | # is too great ! |
|---|
| 905 | if len(i_precedes): |
|---|
| 906 | continue # we skip this since processing will happen at an earlier inconsistent destination |
|---|
| 907 | # NB. distance is not as high a priority as the other constraints |
|---|
| 908 | |
|---|
| 909 | precedes = plpy.execute("select * from preceding_destinations_inclusive('%s','%s',%d)" % \ |
|---|
| 910 | (tab,link_tab,option['seq'])) |
|---|
| 911 | |
|---|
| 912 | # one of the destinations up to & including option must have its position changed |
|---|
| 913 | # ... it can be moved to anywhere but it is preferable that the distances to its |
|---|
| 914 | # new predecessor/successor be less than original |
|---|
| 915 | Dest = None |
|---|
| 916 | # NB. must know which destination is the first in the sequence !!! XXX HERE |
|---|
| 917 | others = plpy.execute("select * from following_destinations_inclusive('%s','%s',%s)" % \ |
|---|
| 918 | (tab,link_tab,FIRST_SEQ)) |
|---|
| 919 | option_priority = None |
|---|
| 920 | temp_options = [] |
|---|
| 921 | temp_options_nonblocking = [] |
|---|
| 922 | for dest in precedes: |
|---|
| 923 | # find the priority to move dest somewhere else |
|---|
| 924 | |
|---|
| 925 | if debug > 2: |
|---|
| 926 | dbg_line = dbg_line + 1 |
|---|
| 927 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 928 | ("--- Dist too long, dest = %s, suburb = %s, priority = %s " % (dest['seq'],dest['suburb'],dest['priority']) ,dbg_line)) |
|---|
| 929 | |
|---|
| 930 | if dest['job_type'] in ('s','S','e','E') : |
|---|
| 931 | continue # this is not a movable destination eg. start/end of day marker |
|---|
| 932 | |
|---|
| 933 | prows = plpy.execute("select prev_dest from %s where next_dest = %d and active" % \ |
|---|
| 934 | (link_tab,dest['seq'])) |
|---|
| 935 | if len(prows) <= 0: |
|---|
| 936 | continue # could be the first node of the path ... but redundant from above !! |
|---|
| 937 | |
|---|
| 938 | pre = prows[0]['prev_dest'] # existing active predecessor to dest |
|---|
| 939 | |
|---|
| 940 | for i in range(1,len(others)): |
|---|
| 941 | prev = others[i-1] |
|---|
| 942 | next = others[i] |
|---|
| 943 | |
|---|
| 944 | flg = movement_exclusion_pre(prev,next,dest,pre) |
|---|
| 945 | if flg: |
|---|
| 946 | if flg == 11: |
|---|
| 947 | break # skip rest of inner loop if dest is after PU |
|---|
| 948 | continue # skip any known exclusions |
|---|
| 949 | |
|---|
| 950 | rows = plpy.execute("select * from path_link_reloc_priority('%s','%s',%d,%d,%d)" % \ |
|---|
| 951 | (tab,link_tab,prev['seq'],next['seq'],dest['seq'])) |
|---|
| 952 | mpriority = rows[0]['path_link_reloc_priority'] # priority to move dest to between prev & next |
|---|
| 953 | if debug > 2: |
|---|
| 954 | dbg_line = dbg_line + 1 |
|---|
| 955 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 956 | ("--- reloc priority prev=%s nest=%s dest=%s , priority=%f " % (prev['seq'],next['seq'],dest['seq'] ,mpriority) ,dbg_line)) |
|---|
| 957 | if mpriority > 8e99: |
|---|
| 958 | continue # ie. infinite priority |
|---|
| 959 | |
|---|
| 960 | |
|---|
| 961 | if mpriority < option['priority']: |
|---|
| 962 | # collect all which cost less than priority |
|---|
| 963 | temp_options_nonblocking.append([prev,next,dest,dest,option['priority'],mpriority,option['seq']]) |
|---|
| 964 | |
|---|
| 965 | elif option_priority is None : # or option_priority > mpriority : |
|---|
| 966 | option_priority = mpriority |
|---|
| 967 | temp_options = [[prev,next,dest,dest,option['priority'],option_priority,option['seq']]] |
|---|
| 968 | |
|---|
| 969 | #elif option_priority == mpriority : # NB. collect all that cost less than priority |
|---|
| 970 | else: |
|---|
| 971 | # where priorities are equal, we can favour moves which appear to |
|---|
| 972 | # reduce distance traveled .. eg. if the distance to it from new predecessor |
|---|
| 973 | # is less than from the old predecessor |
|---|
| 974 | |
|---|
| 975 | # # the proposed new predecessor link |
|---|
| 976 | |
|---|
| 977 | # this distance is shorter & priority is the same, select this instead ... |
|---|
| 978 | temp_options.append([prev,next,dest,dest,option['priority'],option_priority,option['seq']]) |
|---|
| 979 | |
|---|
| 980 | # append the best option |
|---|
| 981 | option_costs = option_costs+ temp_options + temp_options_nonblocking |
|---|
| 982 | if debug : |
|---|
| 983 | dbg_line = dbg_line+1 |
|---|
| 984 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 985 | ("^^^ Dist too long: number of option_costs = %d" % (len(option_costs),),dbg_line)) |
|---|
| 986 | dbg_line = dbg_line + 1 |
|---|
| 987 | if len(temp_options) + len(temp_options_nonblocking) <= 0: |
|---|
| 988 | continue |
|---|
| 989 | |
|---|
| 990 | elif flag[6] == '1' : # flag & 0000001 : |
|---|
| 991 | # missing successor |
|---|
| 992 | # ... tis case should no longer apply since changes are applied in sets so the path remains complete |
|---|
| 993 | raise "Error, missing successor flag detected" |
|---|
| 994 | |
|---|
| 995 | else: |
|---|
| 996 | if flag == '0000000': consistent_count = consistent_count + 1 # reset consistent destination count |
|---|
| 997 | continue # ie. this node is not inconsistent !!! |
|---|
| 998 | |
|---|
| 999 | # at this point we have added an option(s) to the end of option_costs |
|---|
| 1000 | # ... we now see whether sufficient priority exists to rectify the inconsistency via |
|---|
| 1001 | # this option |
|---|
| 1002 | #p,n,d,d2,priority,cost,detect = option_costs[-1] |
|---|
| 1003 | option_costs.sort(key=lambda x: x[5] - x[4]) # sort on ascending cost - priority x[5] - x[4] |
|---|
| 1004 | |
|---|
| 1005 | NS = plpy.execute("select 'now'::timestamp as time")[0]['time'] |
|---|
| 1006 | best = None |
|---|
| 1007 | |
|---|
| 1008 | # record inconsistencies before any changes are made |
|---|
| 1009 | row00 = plpy.execute("select * from totals('%s','%s',%f)" % (tab,link_tab,max_dist))[0] |
|---|
| 1010 | non_dist_inconsistencies_orig = row00['non_dist_inconsistencies'] |
|---|
| 1011 | |
|---|
| 1012 | for ix in range(min(len(option_costs),lahead)): # consider at most lahead options (arbitrary limit) |
|---|
| 1013 | choice = option_costs[ix] |
|---|
| 1014 | cst = choice[5] |
|---|
| 1015 | if cst > 8e99 : |
|---|
| 1016 | #continue |
|---|
| 1017 | break # cost is infinite , exit loop |
|---|
| 1018 | p = choice[0] |
|---|
| 1019 | n = choice[1] |
|---|
| 1020 | d = choice[2] |
|---|
| 1021 | d2 = choice[3] |
|---|
| 1022 | prty = choice[4] |
|---|
| 1023 | |
|---|
| 1024 | if cst >= prty: |
|---|
| 1025 | continue # cost is greater than priority needed to make the change |
|---|
| 1026 | detect = choice[6] |
|---|
| 1027 | |
|---|
| 1028 | # apply the changes |
|---|
| 1029 | old_prev,old_next,old_links,new_links = apply_changes(p['seq'],n['seq'],d['seq'],None,d2['seq']) |
|---|
| 1030 | # need to update fields from the p,n,d,d2 nodes |
|---|
| 1031 | choice[0] = p = plpy.execute("select * from %s where seq = %s" % (tab,p['seq']))[0] |
|---|
| 1032 | choice[1] = n = plpy.execute("select * from %s where seq = %s" % (tab,n['seq']))[0] |
|---|
| 1033 | choice[2] = d = plpy.execute("select * from %s where seq = %s" % (tab,d['seq']))[0] |
|---|
| 1034 | choice[3] = d2 = plpy.execute("select * from %s where seq = %s" % (tab,d2['seq']))[0] |
|---|
| 1035 | |
|---|
| 1036 | |
|---|
| 1037 | |
|---|
| 1038 | # calculate inconsistencies after change |
|---|
| 1039 | row0 = plpy.execute("select * from totals('%s','%s',%f)" % (tab,link_tab,max_dist))[0] |
|---|
| 1040 | td = row0['total_dist'] |
|---|
| 1041 | tt = row0['total_time'] |
|---|
| 1042 | ip = row0['inconsistent_priority'] |
|---|
| 1043 | cp = row0['consistent_priority'] |
|---|
| 1044 | i = row0['inconsistencies'] |
|---|
| 1045 | c = row0['consistencies'] |
|---|
| 1046 | non_dist_inconsistencies = row0['non_dist_inconsistencies'] |
|---|
| 1047 | |
|---|
| 1048 | if debug > 1: |
|---|
| 1049 | dbg_line = dbg_line + 1 |
|---|
| 1050 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 1051 | ("--- In Move wout Gridlock, Considering option prev=%s,next=%s,dest=%s,dest2=%s,priority=%s,cost=%s,non_dist inconsistencies=%s, inconsistencies=%s,total_dist=%s,inconsistent_priority=%s" % (p['seq'],n['seq'],d['seq'],d2['seq'],prty,cst,non_dist_inconsistencies,i,td,ip),dbg_line)) |
|---|
| 1052 | |
|---|
| 1053 | # test if applied move violates any known exclusions |
|---|
| 1054 | # ... multi-dest moves permit excluding all options which introduce non-distance inconsistencies |
|---|
| 1055 | #escape = non_dist_inconsistencies > non_dist_inconsistencies_orig or movement_exclusion_post(p,n,d,d2) |
|---|
| 1056 | escape = movement_exclusion_post(p,n,d,d2) |
|---|
| 1057 | |
|---|
| 1058 | if search_dist > 0 and non_dist_inconsistencies == 0: |
|---|
| 1059 | # ... record best result with no inconsistencies other than distance ... |
|---|
| 1060 | if td < best_dist: |
|---|
| 1061 | best_dist = td |
|---|
| 1062 | best_dist_path = plpy.execute("select * from %s where active" % (link_tab,)) |
|---|
| 1063 | |
|---|
| 1064 | apply_changes(old_prev,old_next,d['seq'],None,d2['seq']) # return to initial position before the next test |
|---|
| 1065 | |
|---|
| 1066 | if escape: |
|---|
| 1067 | continue # skip excluded options |
|---|
| 1068 | |
|---|
| 1069 | if best is None : |
|---|
| 1070 | best = (td,tt,ip,cp,i,c,choice,ix) |
|---|
| 1071 | else: |
|---|
| 1072 | # compare inconsistencies after change to previous best |
|---|
| 1073 | if i < best[4]: |
|---|
| 1074 | # fewer inconsistencies |
|---|
| 1075 | best = (td,tt,ip,cp,i,c,choice,ix) |
|---|
| 1076 | continue |
|---|
| 1077 | elif i == best[4] : |
|---|
| 1078 | # same inconsistencies, consider total distance |
|---|
| 1079 | if td < best[0]: |
|---|
| 1080 | best = (td,tt,ip,cp,i,c,choice,ix) |
|---|
| 1081 | continue |
|---|
| 1082 | elif td < (best[0] + 0.1): |
|---|
| 1083 | # same total distance, consider total inconsistent priority |
|---|
| 1084 | if ip < best[2]: |
|---|
| 1085 | best = (td,tt,ip,cp,i,c,choice,ix) |
|---|
| 1086 | continue |
|---|
| 1087 | if i < 0.01 : |
|---|
| 1088 | break # solution found |
|---|
| 1089 | if best is not None: |
|---|
| 1090 | chosen = option_costs[best[-1]] |
|---|
| 1091 | priority = chosen[4] |
|---|
| 1092 | cost = chosen[5] |
|---|
| 1093 | p = chosen[0] |
|---|
| 1094 | n = chosen[1] |
|---|
| 1095 | d = chosen[2] |
|---|
| 1096 | d2 = chosen[3] |
|---|
| 1097 | if priority > cost : |
|---|
| 1098 | gridlocked = 0 |
|---|
| 1099 | # the priority is sufficient to outweigh the cost |
|---|
| 1100 | # the change is activated |
|---|
| 1101 | # ... |
|---|
| 1102 | apply_changes(p['seq'],n['seq'],d['seq'],priority,d2['seq']) # HERE |
|---|
| 1103 | |
|---|
| 1104 | # deactivate the existing links and adjust priority |
|---|
| 1105 | |
|---|
| 1106 | if debug : |
|---|
| 1107 | dbg_line = dbg_line + 1 |
|---|
| 1108 | |
|---|
| 1109 | # calculate inconsistencies after change |
|---|
| 1110 | row0 = plpy.execute("select * from totals('%s','%s',%f)" % (tab,link_tab,max_dist))[0] |
|---|
| 1111 | td = row0['total_dist'] |
|---|
| 1112 | tt = row0['total_time'] |
|---|
| 1113 | ip = row0['inconsistent_priority'] |
|---|
| 1114 | cp = row0['consistent_priority'] |
|---|
| 1115 | i = row0['inconsistencies'] |
|---|
| 1116 | c = row0['consistencies'] |
|---|
| 1117 | non_dist_inconsistencies = row0['non_dist_inconsistencies'] |
|---|
| 1118 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 1119 | ("--- In Move wout Gridlock, Chosen IS option prev=%s,next=%s,dest=%s,dest2=%s,priority=%s,cost=%s,non_dist inconsistencies=%s, inconsistencies=%s,total_dist=%s,inconsistent_priority=%s" % (p['seq'],n['seq'],d['seq'],d2['seq'],priority,cost,non_dist_inconsistencies,i,td,ip),dbg_line)) |
|---|
| 1120 | |
|---|
| 1121 | if ordered <> 0: |
|---|
| 1122 | # need to dispose of old options after a change is made |
|---|
| 1123 | option_costs = [] |
|---|
| 1124 | best = None |
|---|
| 1125 | else: |
|---|
| 1126 | continue # exit the loop after the first successful change .. maybe not ??? XXX HERE |
|---|
| 1127 | non_gridlock_time = plpy.execute("select ('now'::timestamp - '%s'::timestamp) + '%s'::interval as time" % \ |
|---|
| 1128 | (NS,non_gridlock_time))[0]['time'] |
|---|
| 1129 | |
|---|
| 1130 | |
|---|
| 1131 | GS = plpy.execute("select 'now'::timestamp as time")[0]['time'] |
|---|
| 1132 | if gridlocked and ( (ordered == 0) or consistent_count < num_dests): |
|---|
| 1133 | # means insufficient priority exists to remedy any of the existing inconsistencies |
|---|
| 1134 | # ... must choose an inconsistent destination & increase its priority |
|---|
| 1135 | |
|---|
| 1136 | # basically need to select one of the inconsistent destinations & increase its priority |
|---|
| 1137 | # to exceed the cost of remedy .. |
|---|
| 1138 | # ... which one to pick is arbitrary, but will select the one whose remedy cost is least |
|---|
| 1139 | |
|---|
| 1140 | # remedy cost is last field in the option_costs list for each option |
|---|
| 1141 | # ... can also do analysis of which introduces the least additional inconsistencies ... |
|---|
| 1142 | option_costs.sort(key=lambda x: x[-2]) |
|---|
| 1143 | choice = option_costs[0] # cheapest cost option |
|---|
| 1144 | cost = choice[-2] |
|---|
| 1145 | |
|---|
| 1146 | if cost > 8e99 : |
|---|
| 1147 | return [] # failed to find a solution satisfying all constraints |
|---|
| 1148 | # once again, this is arbitrary ... |
|---|
| 1149 | # .. we implement a look-ahead and select the one of these which results in the |
|---|
| 1150 | # least number of inconsistencies after application |
|---|
| 1151 | best = None |
|---|
| 1152 | |
|---|
| 1153 | # record inconsistencies before any changes are made |
|---|
| 1154 | row00 = plpy.execute("select * from totals('%s','%s',%f)" % (tab,link_tab,max_dist))[0] |
|---|
| 1155 | non_dist_inconsistencies_orig = row00['non_dist_inconsistencies'] |
|---|
| 1156 | |
|---|
| 1157 | end_it = 1 # set to 0 to apply strong exclusions unless gridlock occurs |
|---|
| 1158 | while end_it < 2: |
|---|
| 1159 | if end_it <> 0: end_it = 2 |
|---|
| 1160 | for ix in range(0,min(lahead,len(option_costs))): # consider at most 20 options (arbitrary limit) |
|---|
| 1161 | choice = option_costs[ix] |
|---|
| 1162 | cst = choice[-2] |
|---|
| 1163 | if cst > 8e99 or cst > (cost + 0.01) : |
|---|
| 1164 | break # cost is greater than minimum, or infinite , exit loop |
|---|
| 1165 | p = choice[0] |
|---|
| 1166 | n = choice[1] |
|---|
| 1167 | d = choice[2] |
|---|
| 1168 | d2 = choice[3] |
|---|
| 1169 | prty = choice[4] |
|---|
| 1170 | |
|---|
| 1171 | detect = choice[6] |
|---|
| 1172 | |
|---|
| 1173 | # apply the changes |
|---|
| 1174 | old_prev,old_next,old_links,new_links = apply_changes(p['seq'],n['seq'],d['seq'],None,d2['seq']) |
|---|
| 1175 | # need to update fields from the p,n,d,d2 nodes |
|---|
| 1176 | choice[0] = p = plpy.execute("select * from %s where seq = %s" % (tab,p['seq']))[0] |
|---|
| 1177 | choice[1] = n = plpy.execute("select * from %s where seq = %s" % (tab,n['seq']))[0] |
|---|
| 1178 | choice[2] = d = plpy.execute("select * from %s where seq = %s" % (tab,d['seq']))[0] |
|---|
| 1179 | choice[3] = d2 = plpy.execute("select * from %s where seq = %s" % (tab,d2['seq']))[0] |
|---|
| 1180 | |
|---|
| 1181 | |
|---|
| 1182 | |
|---|
| 1183 | # calculate inconsistencies after change |
|---|
| 1184 | row0 = plpy.execute("select * from totals('%s','%s',%f)" % (tab,link_tab,max_dist))[0] |
|---|
| 1185 | td = row0['total_dist'] |
|---|
| 1186 | tt = row0['total_time'] |
|---|
| 1187 | ip = row0['inconsistent_priority'] |
|---|
| 1188 | cp = row0['consistent_priority'] |
|---|
| 1189 | i = row0['inconsistencies'] |
|---|
| 1190 | c = row0['consistencies'] |
|---|
| 1191 | non_dist_inconsistencies = row0['non_dist_inconsistencies'] |
|---|
| 1192 | |
|---|
| 1193 | # test if applied move violates any known exclusions |
|---|
| 1194 | # ... multi-dest moves permit excluding all options which introduce non-distance inconsistencies |
|---|
| 1195 | if end_it < 1: # look for a move which doesn't add non-distance inconsistencies first |
|---|
| 1196 | escape = non_dist_inconsistencies > non_dist_inconsistencies_orig or movement_exclusion_post(p,n,d,d2) |
|---|
| 1197 | else: |
|---|
| 1198 | escape = movement_exclusion_post(p,n,d,d2) |
|---|
| 1199 | |
|---|
| 1200 | |
|---|
| 1201 | if search_dist > 0 and non_dist_inconsistencies == 0: |
|---|
| 1202 | # ... record best result with no inconsistencies other than distance ... |
|---|
| 1203 | if td < best_dist: |
|---|
| 1204 | best_dist = td |
|---|
| 1205 | best_dist_path = plpy.execute("select * from %s where active" % (link_tab,)) |
|---|
| 1206 | |
|---|
| 1207 | apply_changes(old_prev,old_next,d['seq'],None,d2['seq']) # return to initial position before the next test |
|---|
| 1208 | |
|---|
| 1209 | if escape: |
|---|
| 1210 | continue # skip excluded options |
|---|
| 1211 | |
|---|
| 1212 | if debug > 1: |
|---|
| 1213 | dbg_line = dbg_line + 1 |
|---|
| 1214 | plpy.execute("insert into debug_table values ('%s',%s)" % \ |
|---|
| 1215 | ("# of options = %s ,td=%s, tt=%s, ip = %s, cp = %s, i=%s, c= %s , choice = %s, old_prev = %s, old_next = %s" % (len(option_costs),td,tt,ip,cp,i,c,choice,old_prev,old_next),dbg_line)) |
|---|
| 1216 | |
|---|
| 1217 | if best is None : |
|---|
| 1218 | best = (td,tt,ip,cp,i,c,choice,ix) |
|---|
| 1219 | else: |
|---|
| 1220 | # compare inconsistencies after change to previous best |
|---|
| 1221 | if i < best[4]: |
|---|
| 1222 | # fewer inconsistencies |
|---|
| 1223 | best = (td,tt,ip,cp,i,c,choice,ix) |
|---|
| 1224 | elif i == best[4] : |
|---|
| 1225 | # same inconsistencies, consider total distance |
|---|
| 1226 | if td < best[0]: |
|---|
| 1227 | best = (td,tt,ip,cp,i,c,choice,ix) |
|---|
| 1228 | elif td < (best[0] + 0.1): |
|---|
| 1229 | # same total distance, consider total inconsistent priority |
|---|
| 1230 | if ip < best[2]: |
|---|
| 1231 | best = (td,tt,ip,cp,i,c,choice,ix) |
|---|
| 1232 | if i < 0.01 : |
|---|
| 1233 | break # solution found |
|---|
| 1234 | |
|---|
| 1235 | # re-apply the best option |
|---|
| 1236 | if len(option_costs) <= 0 or best is None: |
|---|
| 1237 | dbg_line = dbg_line + 1 |
|---|
| 1238 | mainloop_time = plpy.execute("select 'now'::timestamp - '%s'::timestamp as time" % (MS))[0]['time'] |
|---|
| 1239 | plpy.execute("insert into debug_table values ('%s',%d) " % \ |
|---|
| 1240 | ( " ### Exit Program: Permanent Gridlock,cum exec times: mainloop=%s apply_changes=%s ,gridlock_time=%s,non_gridlock_time=%s" % (mainloop_time,apply_changes_time,gridlock_time,non_gridlock_time ),dbg_line)) |
|---|
| 1241 | end_it = 1 # gridlocked, so must accept some non-distance inconsistencies |
|---|
| 1242 | |
|---|
| 1243 | |
|---|
| 1244 | if debug: |
|---|
| 1245 | dbg_line = dbg_line + 1 |
|---|
| 1246 | plpy.execute("insert into debug_table values ('%s',%d) " % \ |
|---|
| 1247 | ( """ *** Re-apply best gridlock escape found!!! : best dist = %s,time=%s,inconcist=%s,consist=%s,inconsist pr=%s,consist pr=%s, best option = %s,%s """ % (best[0],best[1],best[4],best[5],best[2],best[3],option_costs[best[-1]][2]['seq'],option_costs[best[-1]][3]['seq'] ),dbg_line)) |
|---|
| 1248 | |
|---|
| 1249 | # re-apply the best option |
|---|
| 1250 | apply_changes(option_costs[best[-1]][0]['seq'],option_costs[best[-1]][1]['seq'],option_costs[best[-1]][2]['seq'],None,option_costs[best[-1]][3]['seq']) |
|---|
| 1251 | |
|---|
| 1252 | # fix priorities of the activated/deactivated links |
|---|
| 1253 | # ... the deactivated path_links are given priority of path_dest node |
|---|
| 1254 | # the activated path_links are given priority of path_dest - 1 |
|---|
| 1255 | # the path_dest is given priority of the cost + 1 |
|---|
| 1256 | # ... in this way the selected link can be overriden again once by the path_dest |
|---|
| 1257 | # without further priority increase thus enabling all options to be considered |
|---|
| 1258 | |
|---|
| 1259 | # increase the priority of the lowest priority deactivated link |
|---|
| 1260 | cheapest_deactivated_link = min_priority_link(old_links) |
|---|
| 1261 | plpy.execute("update %s set priority = %s where prev_dest = %s and next_dest = %s" % \ |
|---|
| 1262 | (link_tab,option_costs[best[-1]][5] + 1,cheapest_deactivated_link['prev_dest'],cheapest_deactivated_link['next_dest'])) |
|---|
| 1263 | |
|---|
| 1264 | if debug: |
|---|
| 1265 | dbg_line = dbg_line + 1 |
|---|
| 1266 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 1267 | ("Gridlock: update %s set priority = %f where prev/dest in (%s/%s,%s/%s,%s/%s)" % \ |
|---|
| 1268 | (link_tab,option_costs[best[-1]][5]+1,new_links[0]['prev_dest'],new_links[0]['next_dest'],new_links[1]['prev_dest'],new_links[1]['next_dest'],new_links[2]['prev_dest'],new_links[2]['next_dest']) \ |
|---|
| 1269 | ,dbg_line)) |
|---|
| 1270 | dbg_line = dbg_line + 1 |
|---|
| 1271 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 1272 | ("update %s set priority = %f where ( prev_dest = %s and next_dest = %s) or (prev_dest = %s and next_dest = %s) or (prev_dest = %s and next_dest = %s)" % \ |
|---|
| 1273 | |
|---|
| 1274 | (link_tab,option_costs[best[-1]][5],old_links[0]['prev_dest'],old_links[0]['next_dest'],old_links[1]['prev_dest'],old_links[1]['next_dest'],old_links[2]['prev_dest'],old_links[2]['next_dest']) \ |
|---|
| 1275 | ,dbg_line)) |
|---|
| 1276 | |
|---|
| 1277 | # # now increase its priority |
|---|
| 1278 | plpy.execute("update %s set priority = %f where seq = %s" % \ |
|---|
| 1279 | (tab,option_costs[best[-1]][4] + 1,option_costs[best[-1]][6])) |
|---|
| 1280 | |
|---|
| 1281 | |
|---|
| 1282 | if debug: |
|---|
| 1283 | dbg_line = dbg_line + 1 |
|---|
| 1284 | plpy.execute("insert into debug_table values ('%s',%d)" % \ |
|---|
| 1285 | ("** Gridlock: Increased priority of seq=%d to %f" % (option_costs[best[-1]][6],option_costs[best[-1]][5]),dbg_line)) |
|---|
| 1286 | |
|---|
| 1287 | gridlock_time = plpy.execute("select ('now'::timestamp - '%s'::timestamp) + '%s'::interval as time" % ( GS,gridlock_time))[0]['time'] |
|---|
| 1288 | |
|---|
| 1289 | if ordered == 0: |
|---|
| 1290 | incons = plpy.execute("select * from inconsistent_dests('%s','%s',%f)" % (tab,link_tab,max_dist)) |
|---|
| 1291 | |
|---|
| 1292 | # if len(incons) > 0 and search_dist > 0: |
|---|
| 1293 | if (ordered == 0 and len(incons) > 0 and search_dist > 0) or (ordered <> 0 and consistent_count < num_dests and search_dist > 0): |
|---|
| 1294 | # we have not been able to satisfy all constraints |
|---|
| 1295 | # ... see if we have been able to satisfy all constraints except distance |
|---|
| 1296 | if best_dist_path is not None: |
|---|
| 1297 | # re-instate this solution before returning |
|---|
| 1298 | plpy.execute("update %s set active = false" % link_tab) |
|---|
| 1299 | for row in best_dist_path: |
|---|
| 1300 | plpy.execute("update %s set active = true where prev_dest = %s and next_dest = %s" % \ |
|---|
| 1301 | (link_tab,row['prev_dest'],row['next_dest']) ) |
|---|
| 1302 | seq_rows = plpy.execute("select seq from %s" % tab) |
|---|
| 1303 | # do better HERE XXX |
|---|
| 1304 | for seq in seq_rows: |
|---|
| 1305 | plpy.execute("select * from dest_changes('%s','%s','%s',%s)" % \ |
|---|
| 1306 | (tab,link_tab,job_tab,seq['seq'])) |
|---|
| 1307 | dbg_line = dbg_line + 1 |
|---|
| 1308 | mainloop_time = plpy.execute("select 'now'::timestamp - '%s'::timestamp as time" % (MS))[0]['time'] |
|---|
| 1309 | now=plpy.execute("select 'now'::timestamp as time")[0]['time'] |
|---|
| 1310 | plpy.execute("insert into debug_table values ('%s',%d) " % \ |
|---|
| 1311 | ( " ### END of prog, cum exec times: mainloop=%s apply_changes=%s ,gridlock_time=%s,non_gridlock_time=%s" % (mainloop_time,apply_changes_time,gridlock_time,non_gridlock_time ),dbg_line)) |
|---|
| 1312 | |
|---|
| 1313 | # successful, return the ordered destinations list |
|---|
| 1314 | return plpy.execute("select * from %s order by time asc" % tab) |
|---|
| 1315 | |
|---|
