Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

/[routino]/trunk/src/optimiser.c
ViewVC logotype

Contents of /trunk/src/optimiser.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 197 - (show annotations) (download) (as text)
Mon Jun 15 18:50:41 2009 UTC (15 years, 9 months ago) by amb
File MIME type: text/x-csrc
File size: 21133 byte(s) 
Fix weight, height, width, length restriction routing.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/optimiser.c,v 1.71 2009-06-15 18:50:41 amb Exp $
3
4 Routing optimiser.
5
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008,2009 Andrew M. Bishop
9
10 This program is free software: you can redistribute it and/or modify
11 it under the terms of the GNU Affero General Public License as published by
12 the Free Software Foundation, either version 3 of the License, or
13 (at your option) any later version.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU Affero General Public License for more details.
19
20 You should have received a copy of the GNU Affero General Public License
21 along with this program. If not, see <http://www.gnu.org/licenses/>.
22 ***************************************/
23
24
25 #include <stdio.h>
26
27 #include "types.h"
28 #include "functions.h"
29 #include "nodes.h"
30 #include "segments.h"
31 #include "ways.h"
32 #include "results.h"
33
34
35 /*+ The option not to print any progress information. +*/
36 extern int option_quiet;
37
38 /*+ The option to calculate the quickest route insted of the shortest. +*/
39 extern int option_quickest;
40
41
42 /*++++++++++++++++++++++++++++++++++++++
43 Find the optimum route between two nodes.
44
45 Results *FindRoute Returns a set of results.
46
47 Nodes *nodes The set of nodes to use.
48
49 Segments *segments The set of segments to use.
50
51 Ways *ways The set of ways to use.
52
53 index_t start The start node.
54
55 index_t finish The finish node.
56
57 Profile *profile The profile containing the transport type, speeds and allowed highways.
58
59 int all A flag to indicate that a big results structure is required.
60 ++++++++++++++++++++++++++++++++++++++*/
61
62 Results *FindRoute(Nodes *nodes,Segments *segments,Ways *ways,index_t start,index_t finish,Profile *profile,int all)
63 {
64 Results *results;
65 index_t node1,node2;
66 score_t finish_score;
67 float finish_lat,finish_lon;
68 Result *result1,*result2;
69 Segment *segment;
70 Way *way;
71
72 /* Set up the finish conditions */
73
74 finish_score=INF_SCORE;
75
76 GetLatLong(nodes,finish,&finish_lat,&finish_lon);
77
78 /* Create the list of results and insert the first node into the queue */
79
80 if(all)
81 results=NewResultsList(65536);
82 else
83 results=NewResultsList(8);
84
85 results->start=start;
86 results->finish=finish;
87
88 result1=InsertResult(results,start);
89
90 ZeroResult(result1);
91
92 insert_in_queue(result1);
93
94 /* Loop across all nodes in the queue */
95
96 while((result1=pop_from_queue()))
97 {
98 if(result1->sortby>finish_score)
99 continue;
100
101 node1=result1->node;
102
103 segment=FirstSegment(segments,nodes,node1);
104
105 while(segment)
106 {
107 score_t segment_score,cumulative_score;
108
109 if(!IsNormalSegment(segment))
110 goto endloop;
111
112 if(profile->oneway && IsOnewayTo(segment,node1))
113 goto endloop;
114
115 node2=OtherNode(segment,node1);
116
117 if(result1->prev==node2)
118 goto endloop;
119
120 way=LookupWay(ways,segment->way);
121
122 if(!(way->allow&profile->allow))
123 goto endloop;
124
125 if(!profile->highway[HIGHWAY(way->type)])
126 goto endloop;
127
128 if(way->weight && way->weight<profile->weight)
129 goto endloop;
130
131 if((way->height && way->height<profile->height) ||
132 (way->width && way->width <profile->width ) ||
133 (way->length && way->length<profile->length))
134 goto endloop;
135
136 if(option_quickest==0)
137 segment_score=(score_t)DISTANCE(segment->distance)/profile->highway[HIGHWAY(way->type)];
138 else
139 segment_score=(score_t)Duration(segment,way,profile)/profile->highway[HIGHWAY(way->type)];
140
141 cumulative_score=result1->score+segment_score;
142
143 if(cumulative_score>finish_score)
144 goto endloop;
145
146 result2=FindResult(results,node2);
147
148 if(!result2) /* New end node */
149 {
150 result2=InsertResult(results,node2);
151 result2->prev=node1;
152 result2->next=NO_NODE;
153 result2->score=cumulative_score;
154 result2->segment=segment;
155
156 if(node2==finish)
157 {
158 finish_score=cumulative_score;
159 }
160 else
161 {
162 float lat,lon;
163 distance_t direct;
164
165 GetLatLong(nodes,node2,&lat,&lon);
166 direct=Distance(lat,lon,finish_lat,finish_lon);
167
168 if(option_quickest==0)
169 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
170 else
171 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
172
173 insert_in_queue(result2);
174 }
175 }
176 else if(cumulative_score<result2->score) /* New end node is better */
177 {
178 result2->prev=node1;
179 result2->score=cumulative_score;
180 result2->segment=segment;
181
182 if(node2==finish)
183 {
184 finish_score=cumulative_score;
185 }
186 else if(!all)
187 {
188 insert_in_queue(result2);
189 }
190 else
191 {
192 float lat,lon;
193 distance_t direct;
194
195 GetLatLong(nodes,node2,&lat,&lon);
196 direct=Distance(lat,lon,finish_lat,finish_lon);
197
198 if(option_quickest==0)
199 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
200 else
201 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
202
203 insert_in_queue(result2);
204 }
205 }
206
207 endloop:
208
209 if(!option_quiet && !(results->number%10000))
210 {
211 printf("\rRouting: End Nodes=%d",results->number);
212 fflush(stdout);
213 }
214
215 segment=NextSegment(segments,segment,node1);
216 }
217 }
218
219 if(!option_quiet)
220 {
221 printf("\rRouted: End Nodes=%d\n",results->number);
222 fflush(stdout);
223 }
224
225 /* Check it worked */
226
227 result2=FindResult(results,finish);
228
229 if(!result2)
230 {
231 FreeResultsList(results);
232 return(NULL);
233 }
234
235 /* Create the forward links for the optimum path */
236
237 result2=FindResult(results,finish);
238
239 do
240 {
241 if(result2->prev!=NO_NODE)
242 {
243 index_t node1=result2->prev;
244
245 result1=FindResult(results,node1);
246
247 result1->next=result2->node;
248
249 result2=result1;
250 }
251 else
252 result2=NULL;
253 }
254 while(result2);
255
256 return(results);
257 }
258
259
260 /*++++++++++++++++++++++++++++++++++++++
261 Find the optimum route between two nodes.
262
263 Results *FindRoute3 Returns a set of results.
264
265 Nodes *nodes The set of nodes to use.
266
267 Segments *segments The set of segments to use.
268
269 Ways *ways The set of ways to use.
270
271 Results *begin The initial portion of the route.
272
273 Results *end The final portion of the route.
274
275 Profile *profile The profile containing the transport type, speeds and allowed highways.
276 ++++++++++++++++++++++++++++++++++++++*/
277
278 Results *FindRoute3(Nodes *nodes,Segments *segments,Ways *ways,Results *begin,Results *end,Profile *profile)
279 {
280 Results *results;
281 index_t node1,node2;
282 score_t finish_score;
283 float finish_lat,finish_lon;
284 Result *result1,*result2,*result3;
285 Segment *segment;
286 Way *way;
287
288 /* Set up the finish conditions */
289
290 finish_score=~(distance_t)0;
291
292 GetLatLong(nodes,end->finish,&finish_lat,&finish_lon);
293
294 /* Create the list of results and insert the first node into the queue */
295
296 results=NewResultsList(65536);
297
298 results->start=begin->start;
299 results->finish=end->finish;
300
301 result1=InsertResult(results,begin->start);
302 result3=FindResult(begin,begin->start);
303
304 *result1=*result3;
305
306 /* Insert the finish points of the beginning part of the path into the queue */
307
308 result3=FirstResult(begin);
309
310 while(result3)
311 {
312 if(IsSuperNode(nodes,result3->node))
313 {
314 if(!(result2=FindResult(results,result3->node)))
315 {
316 result2=InsertResult(results,result3->node);
317
318 *result2=*result3;
319
320 result2->prev=begin->start;
321
322 result2->sortby=result2->score;
323 }
324
325 insert_in_queue(result2);
326 }
327
328 result3=NextResult(begin,result3);
329 }
330
331 /* Loop across all nodes in the queue */
332
333 while((result1=pop_from_queue()))
334 {
335 if(result1->sortby>finish_score)
336 continue;
337
338 node1=result1->node;
339
340 segment=FirstSegment(segments,nodes,node1);
341
342 while(segment)
343 {
344 score_t segment_score,cumulative_score;
345
346 if(!IsSuperSegment(segment))
347 goto endloop;
348
349 if(profile->oneway && IsOnewayTo(segment,node1))
350 goto endloop;
351
352 node2=OtherNode(segment,node1);
353
354 if(result1->prev==node2)
355 goto endloop;
356
357 way=LookupWay(ways,segment->way);
358
359 if(!(way->allow&profile->allow))
360 goto endloop;
361
362 if(!profile->highway[HIGHWAY(way->type)])
363 goto endloop;
364
365 if(way->weight && way->weight<profile->weight)
366 goto endloop;
367
368 if((way->height && way->height<profile->height) ||
369 (way->width && way->width <profile->width ) ||
370 (way->length && way->length<profile->length))
371 goto endloop;
372
373 if(option_quickest==0)
374 segment_score=(score_t)DISTANCE(segment->distance)/profile->highway[HIGHWAY(way->type)];
375 else
376 segment_score=(score_t)Duration(segment,way,profile)/profile->highway[HIGHWAY(way->type)];
377
378 cumulative_score=result1->score+segment_score;
379
380 if(cumulative_score>finish_score)
381 goto endloop;
382
383 result2=FindResult(results,node2);
384
385 if(!result2) /* New end node */
386 {
387 result2=InsertResult(results,node2);
388 result2->prev=node1;
389 result2->next=NO_NODE;
390 result2->score=cumulative_score;
391 result2->segment=segment;
392
393 if((result3=FindResult(end,node2)))
394 {
395 finish_score=result2->score+result3->score;
396 }
397 else
398 {
399 float lat,lon;
400 distance_t direct;
401
402 GetLatLong(nodes,node2,&lat,&lon);
403 direct=Distance(lat,lon,finish_lat,finish_lon);
404
405 if(option_quickest==0)
406 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
407 else
408 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
409
410 insert_in_queue(result2);
411 }
412 }
413 else if(cumulative_score<result2->score) /* New end node is better */
414 {
415 result2->prev=node1;
416 result2->score=cumulative_score;
417 result2->segment=segment;
418
419 if((result3=FindResult(end,node2)))
420 {
421 if((result2->score+result3->score)<finish_score)
422 {
423 finish_score=result2->score+result3->score;
424 }
425 }
426 else
427 {
428 float lat,lon;
429 distance_t direct;
430
431 GetLatLong(nodes,node2,&lat,&lon);
432 direct=Distance(lat,lon,finish_lat,finish_lon);
433
434 if(option_quickest==0)
435 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
436 else
437 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
438
439 insert_in_queue(result2);
440 }
441 }
442
443 endloop:
444
445 if(!option_quiet && !(results->number%10000))
446 {
447 printf("\rRouting: End Nodes=%d",results->number);
448 fflush(stdout);
449 }
450
451 segment=NextSegment(segments,segment,node1);
452 }
453 }
454
455 if(!option_quiet)
456 {
457 printf("\rRouted: End Super-Nodes=%d\n",results->number);
458 fflush(stdout);
459 }
460
461 /* Finish off the end part of the route. */
462
463 if(!FindResult(results,end->finish))
464 {
465 result2=InsertResult(results,end->finish);
466 result3=FindResult(end,end->finish);
467
468 *result2=*result3;
469
470 result2->score=~(distance_t)0;
471
472 result3=FirstResult(end);
473
474 while(result3)
475 {
476 if(IsSuperNode(nodes,result3->node))
477 if((result1=FindResult(results,result3->node)))
478 if((result1->score+result3->score)<result2->score)
479 {
480 result2->score=result1->score+result3->score;
481 result2->prev=result1->node;
482 }
483
484 result3=NextResult(end,result3);
485 }
486 }
487
488 /* Check it worked */
489
490 result2=FindResult(results,end->finish);
491
492 if(!result2)
493 {
494 FreeResultsList(results);
495 return(NULL);
496 }
497
498 /* Create the forward links for the optimum path */
499
500 do
501 {
502 if(result2->prev!=NO_NODE)
503 {
504 index_t node1=result2->prev;
505
506 result1=FindResult(results,node1);
507
508 result1->next=result2->node;
509
510 result2=result1;
511 }
512 else
513 result2=NULL;
514 }
515 while(result2);
516
517 return(results);
518 }
519
520
521 /*++++++++++++++++++++++++++++++++++++++
522 Find all routes from a specified node to any super-node.
523
524 Results *FindStartRoutes Returns a set of results.
525
526 Nodes *nodes The set of nodes to use.
527
528 Segments *segments The set of segments to use.
529
530 Ways *ways The set of ways to use.
531
532 index_t start The start node.
533
534 Profile *profile The profile containing the transport type, speeds and allowed highways.
535 ++++++++++++++++++++++++++++++++++++++*/
536
537 Results *FindStartRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t start,Profile *profile)
538 {
539 Results *results;
540 index_t node1,node2;
541 Result *result1,*result2;
542 Segment *segment;
543 Way *way;
544
545 /* Insert the first node into the queue */
546
547 results=NewResultsList(8);
548
549 results->start=start;
550
551 result1=InsertResult(results,start);
552
553 ZeroResult(result1);
554
555 insert_in_queue(result1);
556
557 /* Loop across all nodes in the queue */
558
559 while((result1=pop_from_queue()))
560 {
561 node1=result1->node;
562
563 segment=FirstSegment(segments,nodes,node1);
564
565 while(segment)
566 {
567 score_t segment_score,cumulative_score;
568
569 if(!IsNormalSegment(segment))
570 goto endloop;
571
572 if(profile->oneway && IsOnewayTo(segment,node1))
573 goto endloop;
574
575 node2=OtherNode(segment,node1);
576
577 if(result1->prev==node2)
578 goto endloop;
579
580 way=LookupWay(ways,segment->way);
581
582 if(!(way->allow&profile->allow))
583 goto endloop;
584
585 if(!profile->highway[HIGHWAY(way->type)])
586 goto endloop;
587
588 if(way->weight && way->weight<profile->weight)
589 goto endloop;
590
591 if((way->height && way->height<profile->height) ||
592 (way->width && way->width <profile->width ) ||
593 (way->length && way->length<profile->length))
594 goto endloop;
595
596 if(option_quickest==0)
597 segment_score=(score_t)DISTANCE(segment->distance)/profile->highway[HIGHWAY(way->type)];
598 else
599 segment_score=(score_t)Duration(segment,way,profile)/profile->highway[HIGHWAY(way->type)];
600
601 cumulative_score=result1->score+segment_score;
602
603 result2=FindResult(results,node2);
604
605 if(!result2) /* New end node */
606 {
607 result2=InsertResult(results,node2);
608 result2->prev=node1;
609 result2->next=NO_NODE;
610 result2->score=cumulative_score;
611 result2->segment=segment;
612
613 if(!IsSuperNode(nodes,node2))
614 {
615 result2->sortby=result2->score;
616 insert_in_queue(result2);
617 }
618 }
619 else if(cumulative_score<result2->score) /* New end node is better */
620 {
621 result2->prev=node1;
622 result2->score=cumulative_score;
623 result2->segment=segment;
624
625 if(!IsSuperNode(nodes,node2))
626 {
627 result2->sortby=result2->score;
628 insert_in_queue(result2);
629 }
630 }
631
632 endloop:
633
634 segment=NextSegment(segments,segment,node1);
635 }
636 }
637
638 /* Check it worked */
639
640 if(results->number==1)
641 {
642 FreeResultsList(results);
643 return(NULL);
644 }
645
646 return(results);
647 }
648
649
650 /*++++++++++++++++++++++++++++++++++++++
651 Find all routes from any super-node to a specific node.
652
653 Results *FindFinishRoutes Returns a set of results.
654
655 Nodes *nodes The set of nodes to use.
656
657 Segments *segments The set of segments to use.
658
659 Ways *ways The set of ways to use.
660
661 index_t finish The finishing node.
662
663 Profile *profile The profile containing the transport type, speeds and allowed highways.
664 ++++++++++++++++++++++++++++++++++++++*/
665
666 Results *FindFinishRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t finish,Profile *profile)
667 {
668 Results *results;
669 index_t node1,node2;
670 Result *result1,*result2;
671 Segment *segment;
672 Way *way;
673
674 /* Insert the first node into the queue */
675
676 results=NewResultsList(8);
677
678 results->finish=finish;
679
680 result1=InsertResult(results,finish);
681
682 ZeroResult(result1);
683
684 insert_in_queue(result1);
685
686 /* Loop across all nodes in the queue */
687
688 while((result1=pop_from_queue()))
689 {
690 node1=result1->node;
691
692 segment=FirstSegment(segments,nodes,node1);
693
694 while(segment)
695 {
696 score_t segment_score,cumulative_score;
697
698 if(!IsNormalSegment(segment))
699 goto endloop;
700
701 if(profile->oneway && IsOnewayFrom(segment,node1))
702 goto endloop;
703
704 node2=OtherNode(segment,node1);
705
706 if(result1->next==node2)
707 goto endloop;
708
709 way=LookupWay(ways,segment->way);
710
711 if(!(way->allow&profile->allow))
712 goto endloop;
713
714 if(!profile->highway[HIGHWAY(way->type)])
715 goto endloop;
716
717 if(way->weight && way->weight<profile->weight)
718 goto endloop;
719
720 if((way->height && way->height<profile->height) ||
721 (way->width && way->width <profile->width ) ||
722 (way->length && way->length<profile->length))
723 goto endloop;
724
725 if(option_quickest==0)
726 segment_score=(score_t)DISTANCE(segment->distance)/profile->highway[HIGHWAY(way->type)];
727 else
728 segment_score=(score_t)Duration(segment,way,profile)/profile->highway[HIGHWAY(way->type)];
729
730 cumulative_score=result1->score+segment_score;
731
732 result2=FindResult(results,node2);
733
734 if(!result2) /* New end node */
735 {
736 result2=InsertResult(results,node2);
737 result2->prev=NO_NODE;
738 result2->next=node1;
739 result2->score=cumulative_score;
740 result2->segment=segment;
741
742 if(!IsSuperNode(nodes,node2))
743 {
744 result2->sortby=result2->score;
745 insert_in_queue(result2);
746 }
747 }
748 else if(cumulative_score<result2->score) /* New end node is better */
749 {
750 result2->next=node1;
751 result2->score=cumulative_score;
752 result2->segment=segment;
753
754 if(!IsSuperNode(nodes,node2))
755 {
756 result2->sortby=result2->score;
757 insert_in_queue(result2);
758 }
759 }
760
761 endloop:
762
763 segment=NextSegment(segments,segment,node1);
764 }
765 }
766
767 /* Check it worked */
768
769 if(results->number==1)
770 {
771 FreeResultsList(results);
772 return(NULL);
773 }
774
775 return(results);
776 }
777
778
779 /*++++++++++++++++++++++++++++++++++++++
780 Create an optimum route given the set of super-nodes to follow.
781
782 Results *CombineRoutes Returns the results from joining the super-nodes.
783
784 Results *results The set of results from the super-nodes.
785
786 Nodes *nodes The list of nodes.
787
788 Segments *segments The set of segments to use.
789
790 Ways *ways The list of ways.
791
792 Profile *profile The profile containing the transport type, speeds and allowed highways.
793 ++++++++++++++++++++++++++++++++++++++*/
794
795 Results *CombineRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,Profile *profile)
796 {
797 Result *result1,*result2,*result3,*result4;
798 Results *combined;
799 int quiet=option_quiet;
800
801 combined=NewResultsList(64);
802
803 combined->start=results->start;
804 combined->finish=results->finish;
805
806 /* Don't print any output for this part */
807
808 option_quiet=1;
809
810 /* Sort out the combined route */
811
812 result1=FindResult(results,results->start);
813
814 result3=InsertResult(combined,results->start);
815
816 ZeroResult(result3);
817
818 do
819 {
820 if(result1->next!=NO_NODE)
821 {
822 Results *results2=FindRoute(nodes,segments,ways,result1->node,result1->next,profile,0);
823
824 result2=FindResult(results2,result1->node);
825
826 result3->next=result2->next;
827
828 result2=FindResult(results2,result2->next);
829
830 do
831 {
832 result4=InsertResult(combined,result2->node);
833
834 *result4=*result2;
835 result4->score+=result3->score;
836
837 if(result2->next!=NO_NODE)
838 result2=FindResult(results2,result2->next);
839 else
840 result2=NULL;
841 }
842 while(result2);
843
844 FreeResultsList(results2);
845
846 result1=FindResult(results,result1->next);
847
848 result3=result4;
849 }
850 else
851 result1=NULL;
852 }
853 while(result1);
854
855 /* Now print out the result normally */
856
857 option_quiet=quiet;
858
859 return(combined);
860 }

Properties

Name Value
cvs:description Route optimiser.
Index: This Site Routino Software Download Source Code Documentation XML Files Links
Index: View SVN Development Recent changes Development (destination-access branch) Version 3.4.2 (destination-access branch) Version 3.4.2 Version 3.4.1 (destination-access branch) Version 3.4.1 Version 3.4 (destination-access branch) Version 3.4 Version 3.3.3 (destination-access branch) Version 3.3.3 Version 3.3.2 (destination-access branch) Version 3.3.2 Version 3.3.1 (destination-access branch) Version 3.3.1 Version 3.3 (destination-access branch) Version 3.3 Version 3.2 Version 3.1.1 Version 3.1 Version 3.0 Version 2.7.3 Version 2.7.2 Version 2.7.1 Version 2.7 Version 2.6 Version 2.5.1 Version 2.5 Version 2.4.1 Version 2.4 Version 2.3.2 Version 2.3.1 Version 2.3 Version 2.2 Version 2.1.2 Version 2.1.1 Version 2.1 Version 2.0.3 Version 2.0.2 Version 2.0.1 Version 2.0 Version 1.5.1 Version 1.5 Version 1.4.1 Version 1.4 Version 1.3 Version 1.2 Version 1.1 Version 1.0
Powered by ViewVC 1.3.0-dev ViewVC Help
© Andrew M. Bishop = < amb @ ... >
Root