[Routing] "SatNav warriors invade Somerset village" - the formula V0.1

[Marcus Wolschon]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Chris Fleming schrieb:
|> For the "windy" I have though of a simple physics-model a few times
|> that not only uses the sum of segment-length and the "highway"-tag
|> but estimates:
|> * maximum speed a curve with a radius R can be traveled
|> * maximum speed on differences in altitude
|> * expected acceleration after a slow segment into a fast segment
following.
|>
|> These speeds and accelerations are user-selected by vehicle-type
...
| I like this approach. For me anyway, I know the road was very windy
| trying to consistently apply a windy=none/some/very type tag is tricky.
|
| It would be good to compare results of the "algorithmic" approach with
| real average speeds. If this could be done consistently then this would
| be a big leap forward.

Well...

I can implement this in a few days as a new
metrics-plugin for Traveling Salesman. There
It is a matter of 2 clicks in the preferences-
dialog to compare it to a conventional metric.
What I need are the right constants.

We need for each vehicle-type:
* MAXSPEED[highway]   and
* MINSPEED[highway]   how slow the driver will get without reacting
* DOWNHILL_MAXSPEED   when to accelerate no further
* CAR_WEIGT           for curves
* MAX_CENTRIFORCE     what the car can take
* usual ACCEL-eration for accelerating and as factor for hills
* EFFICIENT_DRIVER == true if and only if the driver selected
~  "most efficient route" instead of "fastest" or "shortest".
~  Else we can assume he wants to arrive as early as possible.

// assumptions:
// * the segments are short (need no numerical integration)
// * traffic-lights can be estimated as a single
~     maxspeed['traffic_light']-value
// * acceleration is independent of current speed (e.g. no gearshift)


// speed on the last segment
last_speed = actual_speed;

// this is our result
actual_speed = min(
~          topspeed(highway, alt1, alt2, node0, node1, node2),
~          (1+ACCEL*dist(node0, node1)) *last_topspeed
~                      )

// calculate the maximal speed
// the driver can go
// bold values are constants to be
// determined.
formula topspeed(highway, alt1, alt2, node0, node1, node2,
~                   weight, accel) {
~ speed = MAXSPEED[highway];
~ dist = dist(node0, node1);
~ alt_diff = alt2 - alt1;
~ time = dist / last_speed;
~ accel_used = 0;

~ ////////////////////////////
~ // calculate the de(/a-)celleration due to hills

~ // dist is the distance on a planar map,
~ // use pythagoras to get the distance on a 3d-road.
~ real_dist = sqrt(dist*dist + alt_diff*alt_diff);

~ sine_of_angle = alt_diff / real_dist;
~ alt_accel = sine_of_angle*9.81

~ if (alt_diff > 0) {
~    // uphill

~    if (EFFICIENT_DRIVER) {

~      // the driver slows down
~      // to accelerate downhill later
~      speed -= alt_accel * time;
~      // the driver does not get too slow
~      if (speed < MINSPEED[highway])
~       speed = min(MINSPEED[highway], speed + ACCEL * time);

~    } else {

~      // the driver counteracts the hill
~      if (alt_accel > ACCEL - accel_used) {
~        accel_used = min(ACCEL - accel_used, alt_assel);
~        speed -= (alt_accel - accel_used) * time;
~      } else {
~        accel_used = alt_assel;
~      }

~    }


~ } else {
~    // downhill
~    speed += alt_accel * time;
~    speed = max (speed, DOWNHILL_MAXSPEED);
~ }

~ ////////////////////////////
~ // calculate the decelleration due to curves

~ // we do not integrate over time but estimate
~ // an average speed in all of the curve
~ // speed is now the estimated speed after the hill
~ // and last_speed before it.
~ // we ignore decelleration due to the curve
~ avg_speed = last_speed + (last_speed - speed) / 2;

~ radius = arc_radius(node0, node1, node2);
~ if (radius < 0)
~   radius = -1 * radius;

~ if (radius > 0) {
~   curve_accel = avg_speed * avg_speed / radius;
~   force = CAR_WEIGT * curve_accel;

~   // we assume the driver is breaking
~   // perfectly to not exceed what his
~   // car can take
~   if (force > MAX_CENTRIFORCE) {

~     // the driver slows down
~     accel = MAX_CENTRIFORCE / CAR_WEIGT;

~     speed -= curve_accel * time;

~   } else {

~     // the driver counteracts the curve
~     if (curve_accel > ACCEL - accel_used) {
~        accel_used = min(ACCEL - accel_used, curve_assel);
~        speed -= (curve_accel - accel_used) * time;
~      } else {
~        accel_used += curve_assel;
~      }

~   }


~ }

~ /////////////////////////
~ // done

~ return speed;
}

Marcus
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHy/gef1hPnk3Z0cQRAuduAKC07LI61gHEDc6qnhqWMYlFsOLyrACfbezy
6K3thCYsORSWEaBHJV1sP7w=
=Uyqy
-----END PGP SIGNATURE-----