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 | |
---|