Difference between revisions of "Subway ride"

From mintOC
Jump to: navigation, search
(→‎Mathematical formulation)
(→‎Mathematical formulation)
Line 16: Line 16:
 
<math>
 
<math>
 
\begin{array}{llcl}
 
\begin{array}{llcl}
−
  \displaystyle \min_{x, w} & & & \int_{0}^{t_f} L(x, w) \; \mathrm{d} t  \\[1.5ex]
+
  \displaystyle \min_{x, w} & & \int_{0}^{t_f} L(x, w) \; \mathrm{d} t  \\[1.5ex]
 
  \mbox{s.t.} & \dot{x}_0 & = & x_1, \\
 
  \mbox{s.t.} & \dot{x}_0 & = & x_1, \\
 
  & \dot{x}_1 & = & f_1(x,w),  \\
 
  & \dot{x}_1 & = & f_1(x,w),  \\

Revision as of 17:19, 22 February 2016

Subway ride
State dimension: 1
Differential states: 2
Discrete control functions: 1
Interior point equalities: 4


The subway ride optimal control problem goes back to work of [Bock1982]Address: Taiwan
Author: Bock, H.G.; Longman, R.W.
Booktitle: Proceedings of the American Astronomical Society. Symposium on Engineering Science and Mechanics
Title: Computation of optimal controls on disjoint control sets for minimum energy subway operation
Year: 1982
Link to Google Scholar for the city of New York. In an extension, also velocity limits that lead to path-constrained arcs appear. The aim is to minimize the energy used for a subway ride from one station to another, taking into account boundary conditions and a restriction on the time.

Mathematical formulation

The MIOCP reads as

\begin{array}{llcl} \displaystyle \min_{x, w} & & \int_{0}^{t_f} L(x, w) \; \mathrm{d} t \\[1.5ex] \mbox{s.t.} & \dot{x}_0 & = & x_1, \\ & \dot{x}_1 & = & f_1(x,w), \\ & x(0) &=& (0, 0)^T, \\ & x(t_f) &=& (2112, 0)^T, \\ & w(t) &\in& \{1, 2, 3, 4\}. \end{array}

The terminal time t_f=65 denotes the time of arrival of a subway train in the next station. The differential states x_0(\cdot) and x_1(\cdot) describe position and velocity of the train, respectively. The train can be operated in one of four different modes, w(\cdot) = 1 series, w(\cdot) = 2 parallel, w(\cdot) = 3 coasting, or w(\cdot) = 4 braking that accelerate or decelerate the train and have different energy consumption.

Acceleration and energy comsumption are velocity-dependent. Hence, we will need switching functions \sigma_i( x_1 ) = v_i - x_1 for given velocities v_i, i=1..3.

The Lagrange term reads as

\begin{array}{rcl} L(x, 1) &=& \left\{ \begin{array}{cl} e \; p_1 & \mbox{if } \sigma_1 \ge 0 \\ e \; p_2 & \mbox{else if } \sigma_2 \ge 0 \\ e \; \sum_{i=0}^{5} c_i (1) \left( \frac{1}{10} \gamma\ x_1 \right)^{-i} \quad & \mbox{else} \end{array} \right. \\ L(x, 2) &=& \left\{ \begin{array}{cl} \infty & \mbox{if } \sigma_2 \ge 0\\ e \; p_3 & \mbox{else if } \sigma_3 \ge 0 \\ e \; \sum_{i=0}^{5} c_i (2) \left( \frac{1}{10} \gamma\ x_1 - 1 \right)^{-i} & \mbox{else} \end{array} \right. \\ L(x, 3) &=& L(x, 4) = 0. \end{array}

The right hand side function f_1(x,w) reads as

\begin{array}{rcl} f_1(x, 1) &=& \left\{ \begin{array}{cl} f_1^{1A} := \frac{g \; e \; a_1}{W_{\mathrm{eff}}} & \mbox{if } \sigma_1 \ge 0 \\ f_1^{1B} :=\frac{g \; e \; a_2}{W_{\mathrm{eff}}} & \mbox{else if } \sigma_2 \ge 0 \\ f_1^{1C} := \frac{g \; (e \; T(x_1, 1) - R(x_1)}{W_{\mathrm{eff}}} & \mbox{else} \end{array} \right. \\ f_1(x, 2) &=& \left\{ \begin{array}{cl} 0 & \mbox{if } \sigma_2 \ge 0\\ f_1^{2B} := \frac{g \; e \; a_3}{W_{\mathrm{eff}}} & \mbox{else if } \sigma_3 \ge 0 \\ f_1^{2C} := \frac{g \; (e \; T(x_1, 2) - R(x_1)}{W_{\mathrm{eff}}} & \mbox{else} \end{array} \right. \\ f_1(x, 3) &=& - \frac{g \; R(x_1)}{W_{\mathrm{eff}}} - C, \\ f_1(x, 4) &=& - u = - u_{\mathrm{max}}. \end{array}

The braking deceleration u(\cdot) can be varied between 0 and a given u_{\mathrm{max}}. It can be shown that only maximal braking can be optimal, hence we fixed u(\cdot) to u_{\mathrm{max}} without loss of generality.

Occurring forces are

\begin{array}{rcl} R(x_1) &=& c a \; {\gamma}^2 {x_1}^2 + b W {\gamma} x_1 + \frac{1.3}{2000}W + 116, \\ T(x_1,1) &=& \sum_{i=0}^{5}b_i(1) \left( \frac{1}{10} {\gamma} x_1 - 0.3 \right) ^{-i}, \\ T(x_1,2) &=& \sum_{i=0}^{5}b_i(2) \left( \frac{1}{10} {\gamma} x_1 - 1 \right) ^{-i}. \end{array}

Details about the derivation of this model and the assumptions made can be found in [Bock1982]Address: Taiwan
Author: Bock, H.G.; Longman, R.W.
Booktitle: Proceedings of the American Astronomical Society. Symposium on Engineering Science and Mechanics
Title: Computation of optimal controls on disjoint control sets for minimum energy subway operation
Year: 1982
Link to Google Scholar or in [Kraemer-Eis1985]Address: Bonn
Author: Kr\"amer-Eis, P.
Publisher: Universit\"at Bonn
Series: Bonner Mathematische Schriften
Title: Ein Mehrzielverfahren zur numerischen Berechnung optimaler Feedback--Steuerungen bei beschr\"ankten nichtlinearen Steuerungsproblemen
Volume: 166
Year: 1985
Link to Google Scholar.

Parameters

Symbol Value Unit Symbol Value Unit
W 78000 lbs v_1 0.979474 mph
W_{\mathrm{eff}} 85200 lbs v_2 6.73211 mph
S 2112 ft v_3 14.2658 mph
S_4 700 ft v_4 22.0 mph
S_5 1200 ft v_5 24.0 mph
\gamma \frac{3600}{5280} \frac{\mbox{sec}}{\mbox{h}} / \frac{\mbox{ft}}{\mbox{mile}} a_1 6017.611205 lbs
a 100 ft^2 a_2 12348.34865 lbs
n_{\mathrm{wag}} 10 - a_3 11124.63729 lbs
b 0.045 - u_{\mathrm{max}} 4.4 ft / sec^2
C 0.367 - p_1 106.1951102 -
g 32.2 \frac{\mbox{ft}}{\mbox{sec}^2} p_2 180.9758408 -
e 1.0 - p_3 354.136479 -
Parameter Value Parameter Value
b_0(1) -0.1983670410E02 c_0(1) 0.3629738340E02
b_1(1) 0.1952738055E03 c_1(1) -0.2115281047E03
b_2(1) 0.2061789974E04 c_2(1) 0.7488955419E03
b_3(1) -0.7684409308E03 c_3(1) -0.9511076467E03
b_4(1) 0.2677869201E03 c_4(1) 0.5710015123E03
b_5(1) -0.3159629687E02 c_5(1) -0.1221306465E03
b_0(2) -0.1577169936E03 c_0(2) 0.4120568887E02
b_1(2) 0.3389010339E04 c_1(2) 0.3408049202E03
b_2(2) 0.6202054610E04 c_1(2) 0.3408049202E03
b_3(2) -0.4608734450E04 c_3(2) 0.8108316584E02
b_4(2) 0.2207757061E04 c_4(2) -0.5689703073E01
b_5(2) -0.3673344160E03 c_5(2) -0.2191905731E01

Reference Solutions

The optimal trajectory for this problem has been calculated by means of an indirect approach in [Bock1982]Address: Taiwan
Author: Bock, H.G.; Longman, R.W.
Booktitle: Proceedings of the American Astronomical Society. Symposium on Engineering Science and Mechanics
Title: Computation of optimal controls on disjoint control sets for minimum energy subway operation
Year: 1982
Link to Google Scholar[Kraemer-Eis1985]Address: Bonn
Author: Kr\"amer-Eis, P.
Publisher: Universit\"at Bonn
Series: Bonner Mathematische Schriften
Title: Ein Mehrzielverfahren zur numerischen Berechnung optimaler Feedback--Steuerungen bei beschr\"ankten nichtlinearen Steuerungsproblemen
Volume: 166
Year: 1985
Link to Google Scholar, and based on the direct multiple shooting method in [Sager2009]Author: Sager, S.; Reinelt, G.; Bock, H.G.
Journal: Mathematical Programming
Number: 1
Pages: 109--149
Title: Direct Methods With Maximal Lower Bound for Mixed-Integer Optimal Control Problems
Url: http://mathopt.de/PUBLICATIONS/Sager2009.pdf
Volume: 118
Year: 2009
Link to Google Scholar.


Time t w(\cdot) f_1 = x_0 [ft] x_1 [mph] x_1 [ftps] Energy
0.00000 1 f_1^{1A} 0.0 0.0 0.0 0.0
0.63166 1 f_1^{1B} 0.453711 0.979474 1.43656 0.0186331
2.43955 1 f_1^{1C} 10.6776 6.73211 9.87375 0.109518
3.64338 2 f_1^{2B} 24.4836 8.65723 12.6973 0.147387
5.59988 2 f_1^{2C} 57.3729 14.2658 20.9232 0.339851
12.6070 1 f_1^{1C} 277.711 25.6452 37.6129 0.93519
45.7827 3 f_1(3) 1556.5 26.8579 39.3915 1.14569
46.8938 3 f_1(3) 1600 26.5306 38.9115 1.14569
57.1600 4 f_1(4) 1976.78 23.5201 34.4961 1.14569
65.0000 - - 2112 0.0 0.0 1.14569


Variants

The given parameters have to be modified to match different parts of the track, subway train types, or amount of passengers. A minimization of travel time might also be considered.

The problem becomes more challenging, when additional point or path constraints are considered.

Point constraint

We consider the point constraint

x_1 \le v_4 \mbox{ if } x_0 = S_4

for a given distance 0 < S_4 < S and velocity v_4 > v_3. Note that the state x_0(\cdot) is strictly monotonically increasing with time, as \dot{x}_0 = x_1 > 0 for all t \in (0, T).

The optimal order of gears for S_4 = 1200 and v_4 = 22 / \gamma with the additional interior point constraints (\ref{FASOPOINTCON}) is 1, 2, 1, 3, 4, 2, 1, 3, 4. The stage lengths between switches are 2.86362, 10.722, 15.3108, 5.81821, 1.18383, 2.72451, 12.917, 5.47402, and 7.98594 with \Phi = 1.3978. For different parameters S_4 = 700 and v_4 = 22 / \gamma we obtain the gear choice 1, 2, 1, 3, 2, 1, 3, 4 and stage lengths 2.98084, 6.28428, 11.0714, 4.77575, 6.0483, 18.6081, 6.4893, and 8.74202 with \Phi = 1.32518.

Path constraint

A more practical restriction are path constraints on subsets of the track. We will consider a problem with additional path constraints

x_1 \le v_5 \; \mbox{ if } \; x_0 \ge S_5.

The additional path constraint changes the qualitative behavior of the relaxed solution. While all solutions considered this far were bang-bang and the main work consisted in finding the switching points, we now have a path-constrained arc. The optimal solutions for refined grids yield a series of monotonically decreasing objective function values, where the limit is the best value that can be approximated by an integer feasible solution. In our case we obtain 1.33108, 1.31070, 1.31058, 1.31058, ...

The plot shows two possible integer realizations, with a trade-off between energy consumption and number of switches. Note that the solutions approximate the optimal driving behavior (a convex combination of two operation modes) by switching between the two and causing a touching of the velocity constraint from below as many times as we switch.

  • Reference solution plots

  • Optimal solution with 1 touch point.

  • Optimal solution with 3 touch points.

The differential state velocity of a subway train over time. The dotted vertical line indicates the beginning of the path constraint, the horizontal line the maximum velocity. Left: one switch leading to one touch point. Right: optimal solution for three switches. The energy-optimal solution needs to stay as close as possible to the maximum velocity on this time interval to avoid even higher energy-intensive accelerations in the start-up phase to match the terminal time constraint t_f \le 65 to reach the next station.

Source Code

Model descriptions are available in

References

[Bock1982]Bock, H.G.; Longman, R.W. (1982): Computation of optimal controls on disjoint control sets for minimum energy subway operation. %publisher%, Proceedings of the American Astronomical Society. Symposium on Engineering Science and MechanicsLink to Google Scholar
[Kraemer-Eis1985]Kr\"amer-Eis, P. (1985): Ein Mehrzielverfahren zur numerischen Berechnung optimaler Feedback--Steuerungen bei beschr\"ankten nichtlinearen Steuerungsproblemen. (%edition%). Universit\"at Bonn, Bonn, %pages%Link to Google Scholar
[Sager2009]Sager, S.; Reinelt, G.; Bock, H.G. (2009): Direct Methods With Maximal Lower Bound for Mixed-Integer Optimal Control Problems. Mathematical Programming, 118, 109--149Link to Google Scholar
Retrieved from "https://mintoc.de/index.php?title=Subway_ride&oldid=1729"