{"template":"article","title":"Minimum motion of a town center under published walking-time constraints","authors":[{"name":"Irena S. Valcheva-Orme","affiliations":[1],"email":"ivalcheva@merewick.example","corresponding":true},{"name":"Nicolás E. Beltrán Sola","affiliations":[2]}],"affiliations":["Department of Applied Mathematics, Merewick Institute of Navigation, Bristol, United Kingdom","Grupo de Optimización Territorial, Instituto de la Vega Alta, Montevideo, Uruguay"],"abstract":"A hotel directory specifies an upper bound on the time required to walk from each participating property to the town center. We consider the inverse location problem in which the entries have gone to press and the town retains control of the center. A single survey disk must witness every claim in force at the time of inspection and return to its socket at close of business. For sites on a common street we give an endpoint certificate for the minimum relocation speed and a linear-time construction of a least-travel path at any feasible speed. In a seven-inspection directory with a ten-minute allowance, the disk must cover at least 2.00 km during the working day. A path attaining that distance has peak speed 0.30 km/h. Leaving the disk at the town hall requires a uniform allowance of 21.25 minutes. We give separate certificates for an interruption of service and a change in the interpretation of the directory's validity period.","keywords":["mobile facility location","interval selection","total variation","Lipschitz extensions","pedestrian distance"],"body":"# Problem and setting {#sec:setting}\n\nThe printed directory of the Lower Mere pilot lists the walking time to the town center beside the opening hours of each hotel reception. There are two copies of the directory in the survey office. One has a folded sheet of corrections in the back. Both copies put every reception within ten minutes of the center. The correction sheet changes which reception is open at a given inspection. It does not change the ten minutes. A separate register identifies the center as the spot occupied by a brass survey disk, ordinarily seated in a socket in front of the town hall.\n\nA correction to an opening hour requires one entry in the register. A change in a printed walking time requires replacement of the directory. The option still available to the survey office is to move the disk. The office has one disk certified for directory purposes. At a joint inspection both reception desks must be able to direct a visitor to the same piece of brass. The disk is due back at its original socket in time for the evening survey. We ask how much travel that interpretation of the register requires.\n\nTwo administrative details enter the mathematics. The inspection clerk records the location at the hour entered on each card. The record covers walks timed to a stationary point at that coordinate. The visitor does not pursue the surveyor. Also, an unopened desk makes no claim on the center under the pilot's inspection rule. The distinction between inspection and continuous availability has considerable numerical consequences. We give the result for both rules in @sec:validity. For the numerical example we use chainages and appointment times specified as design inputs. There is no sampling model for the ten minutes.\n\nClassical network location chooses a center to reduce the largest service distance or a median to reduce a sum of distances [@hakimi]. Mobility introduces a second distance, the one traveled by the facility itself. Chasing convex bodies gives one formulation of this distinction [@friedman]. A schedule known in advance also admits a time-expanded formulation using difference constraints [@ahuja; @schrijver]. Our application uses elementary cases of these constructions. Local studies of hotel directories have measured where a walk begins [@eredo] and the change due to replacing the front desk by the gate [@venra]. They generally fix where it ends. The survey disk supplies an unusually direct way to vary that endpoint.\n\n# Reduction to a moving interval {#sec:interval}\n\nLet $p_j$ be the signed chainage of desk $j$ on a straight pedestrian street, measured in meters east of the socket. Along this street, differences of chainage give walking distance exactly. A pedestrian walks at the directory speed $w$ meters per minute. A claim of $m_j$ minutes is an upper bound. Thus one desk permits the disk to occupy a closed interval of radius $w m_j$. A side passage of length $d_j$ giving the sole access to the street would consume that much of the radius before the pedestrian reached the street. All passage lengths in the worked example are zero. Changing the speed of the disk does not change the walking speed used to rate a desk.\n\nFor an inspection at time $t_i$ with nonempty active set $A_i$, the allowable chainages have endpoints\n$$\n L_i=\\max_{j\\in A_i}(p_j-wm_j),\\qquad\n U_i=\\min_{j\\in A_i}(p_j+wm_j).\n \\label{eq:interval}\n$$\nWhen there are several establishments at the same appointment, @eq:interval uses all of them. A separate visit by the disk to each within the hour would solve a different service problem. A bare coordinate in the survey ledger has no associated uncertainty in this calculation. Rounding of desk positions can instead be carried through as an interval erosion, as shown in @sec:error. Registers using a building centroid [@sovik] or a postal entrance [@melrou] require the corresponding chainages.\n\nWrite $I_i=[L_i,U_i]$. If $L_i>U_i$ the inspection alone is inconsistent. Motion between appointments cannot remedy this. Otherwise insert two singleton intervals for departure and return and index the resulting list from 0 to $n$, with $t_0<\\cdots<t_n$. Coordinates at the singletons are surveyed positions and receive no walking allowance. In particular, increasing every guest's allowance does not enlarge the socket. We measure time from departure in hours and bound the disk speed by $v$ in meters per hour. The travel charged to a route is\n$$\n J(x)=\\sum_{i=1}^{n}|x_i-x_{i-1}|,\\qquad\n x_i\\in I_i,\\qquad |x_i-x_{i-1}|\\le v(t_i-t_{i-1}).\n \\label{eq:travel}\n$$\nEvery discrete solution of @eq:travel has a piecewise linear realization of the same length. Every absolutely continuous realization respecting the speed limit yields inspection coordinates with no greater discrete length. Waiting at a reception is permitted. Acceleration and time spent fixing the disk to the pavement are absent from the inspection contract.\n\nIt is possible to introduce two nonnegative slack variables per leg and solve a linear program for $J$ [@boyd; @rockafellar]. This has the merit that the same input file can carry charges for uphill motion. The office also requires a reason for rejecting a directory which fits on a correction slip. The pair of desk records in @sec:speed meets this requirement. It can be recovered without storing a basis or deciding whether a small reported residual is a contradiction.\n\n# An endpoint certificate for speed {#sec:speed}\n\nConsider any two appointments, possibly with several other visits in between. The leftmost point allowed at one must lie within reach of the rightmost point allowed at the other. Dividing their positive separation by the time available gives a lower bound on speed. It is useful here that a family of these elementary lower bounds suffices.\n\n::: theorem {#thm:speed title=\"Required speed\"}\nWith nonempty inspection intervals and at least two distinct appointment times, the minimum feasible speed is\n$$\n v_* = \\max_{i\\ne j}\\frac{(L_j-U_i)_+}{|t_j-t_i|}.\n \\label{eq:speed}\n$$\nFor any $v\\ge v_*$ a feasible choice at time $t_i$ is $h(t_i)$, where $h(t)=\\max_j\\{L_j-v|t-t_j|\\}$.\n:::\n\n::: proof\nAlong a feasible route, $L_j-U_i\\le x_j-x_i\\le v|t_j-t_i|$. Conversely the function $h$ is the upper envelope of finitely many functions with Lipschitz constant at most $v$, so it has that same bound on increments. Its term indexed by $i$ gives $h(t_i)\\ge L_i$. For $j\\ne i$ the inequality in @eq:speed gives $L_j-v|t_i-t_j|\\le U_i$. The term $j=i$ also satisfies this upper bound since $I_i$ is nonempty. The envelope therefore meets every inspection and both singleton conditions.\n:::\n\nThe two indices in @eq:speed range over ordered pairs. Restricting $j$ to be the later visit would miss the return to the hall from the east. The denominator is positive even if the same desk appears at several appointments. Simultaneous records have already been intersected in @eq:interval. Cones with this form also occur in extensions of real-valued Lipschitz data [@mcshane]. Here the values at the inspection nodes are themselves choices. The envelope is the smallest feasible trajectory pointwise on the inspection nodes but its low position may cost extra travel on the way back to the socket.\n\nFor long directories one can test a proposed speed in a forward pass. Start with $R_0=I_0$. If $R_{i-1}=[a,b]$, intersect $I_i$ with $[a-v\\Delta_i,b+v\\Delta_i]$, where $\\Delta_i=t_i-t_{i-1}$. Every point of the latter interval lies within one leg of some attainable predecessor. Induction therefore identifies $R_i$ as the entire reachable set at inspection $i$. The first empty intersection certifies failure at the proposed speed. Endpoint provenance can be kept with the two bounds to identify the earlier appointment that caused the conflict. For our nine nodes a direct scan of ordered pairs is shorter to audit. No convergence tolerance enters the reported critical speed.\n\n# A distance minimizer at a specified speed {#sec:distance}\n\nThe envelope used in @thm:speed need not minimize travel. A directory inspector who has no speed restriction can stay put until an interval forces motion, then move only to its nearest endpoint. That rule can leave an inspector too far away to reach the next appointment at the rated speed. Imposing a speed limit calls for knowledge of the remaining inspections. We use a backward pass before applying the nearest-point rule. This is a scalar instance of a viability calculation [@aubin] followed by projection onto an interval [@moreau]. The term projection here means ordinary clipping.\n\nSet $B_n=I_n$ and define the interval of positions from which all later visits remain achievable by\n$$\n B_i=I_i\\cap[B_{i+1}^{-}-v\\Delta_{i+1},\\,B_{i+1}^{+}+v\\Delta_{i+1}],\n \\qquad i=n-1,\\ldots,0.\n \\label{eq:back}\n$$\nSuperscripts denote endpoints. Stop on an empty interval. Feasibility follows when the initial singleton survives, since the disk can then reach some point of the next surviving interval and proceed by induction. From its prescribed departure point $g_0$ choose $g_i$ as the point in $B_i$ nearest $g_{i-1}$. The definition of $B_{i-1}$ guarantees that the step thus taken respects the cap. The procedure stores a pair of numbers per inspection for reconstruction and constant additional space during the forward pass.\n\n::: proposition {#prop:clip title=\"Distance at a fixed speed\"}\nFor any feasible cap the forward projections onto the intervals in @eq:back attain the least possible $J$.\n:::\n\n::: proof\nAny competitor $y$ meeting the speed bound has $y_i\\in B_i$, by backward induction. On the real line the projection $g_i$ lies between $g_{i-1}$ and $y_i$, including the case where $g_i=g_{i-1}$. Consequently $|g_i-g_{i-1}|+|y_i-g_i|=|y_i-g_{i-1}|$. Bound the last expression by $|y_i-y_{i-1}|+|y_{i-1}-g_{i-1}|$ and sum over visits. The discrepancy terms cancel. The initial and final discrepancies vanish at their sockets. This proves the claim.\n:::\n\nThe direction of the backward pass matters. A forward reachable interval records that there once was some way to get to a position. Committing the disk to one such position loses all the other ways. The backward interval instead records a promise about the future which every point in it can keep. Clipping to that interval carries the promise to the next step. We found it convenient to print these intervals in the ledger beside the raw ones. The hourly clerk can see why a dispatch order precedes the first desk that appears to require it.\n\n# A corridor directory {#sec:example}\n\nThe instance in @tbl:desks has seven reception inspections. The extreme desks at each are sufficient to reproduce the directory. Adding intermediate desks with the same allowance changes no constraint. We chose $w=80$ m/min and $m_j=10$ min. These are definitions of the example, not estimates of the speed of visitors. West and east describe the order of the two desks along the street. A desk called western in one row can be east of the socket. Hour 0 corresponds to 09:00. At hour 8 the disk must be in its socket even if a porter is still on duty. A singleton excursion by the surveyor is charged both ways.\n\nTable: Printed desk chainages and permitted disk interval. All distances are in meters from the socket. {#tbl:desks}\n\n| Hour | Western desk | Eastern desk | Lower | Upper |\n|-----:|-------------:|-------------:|------:|------:|\n| 1 | -500 | 900 | 100 | 300 |\n| 2 | -100 | 1100 | 300 | 700 |\n| 3 | 300 | 1700 | 900 | 1100 |\n| 4 | 200 | 1500 | 700 | 1000 |\n| 5 | -200 | 900 | 100 | 600 |\n| 6 | -600 | 600 | -200 | 200 |\n| 7 | -900 | 400 | -400 | -100 |\n\nA single stationary point cannot serve even the two inspections at hours 3 and 7. The disk must be at least 900 m east at noon, then at least 100 m west by 16:00. Leaving from zero and returning to zero forces at least $900+1000+100=2000$ m of travel. The noon visit also requires 900 m in the first three hours, so the cap must be at least 300 m/h. Neither bound assumes a particular behavior at the other five inspections. The two loose lower bounds become sharp together when the desk coordinates are inserted in @eq:back.\n\n@fig:path shows the raw intervals and a least-distance route on the same scale. At the first appointment the western desk is just 500 m west of the hall, yet the disk must already be 300 m east at the critical speed. A smaller eastward dispatch is still consistent with the desk pair at that hour. It makes the noon requirement unattainable. The morning movement is fixed by a desk which will not open for another two hours.\n\n![Inspection intervals and disk positions at 300 m/h. Linear interpolation applies to the disk path. The lines between successive bounds only connect recorded endpoints.](chainage){#fig:path}\n\nFor a comparison independent of solver conventions, @tbl:routes gives four explicit selection rules. The midpoint serves the current interval symmetrically. The unbounded projection rule makes the least move allowed by the current reception pair, without reading tomorrow's or even the next hour's card. At 11:00 that rule has traveled 300 m. It must do the remaining 600 m in one hour. The lower envelope in @thm:speed travels to $-200$ m on the penultimate visit although $-100$ m would suffice. Both satisfy the cap. Only the latter coordinate gives a route tight against the excursion bound on both sides of zero.\n\nTable: Motion of the certified disk on the directory in @tbl:desks. Peak speed is for constant travel speed on each leg. {#tbl:routes}\n\n| Rule | Distance (m) | Peak speed (m/h) |\n|:-----|-------------:|-----------------:|\n| Midpoint of each raw interval | 2500 | 500 |\n| Projection onto raw intervals | 2000 | 600 |\n| Lower envelope at critical speed | 2200 | 300 |\n| Backward intervals then projection | 2000 | 300 |\n\nIn @tbl:routes, the advantage of preview at a fixed travel budget consists entirely in when the disk departs. No change to the desk allowance is needed. For instance, a dispatcher using the raw projection rule can reduce its peak speed by leaving 200 m earlier on the first leg. That change alone does not achieve the cap. A further 300 m of position must have accumulated by the second inspection compared with the raw projection record. The hour-by-hour positions, including the four coordinates which distinguish the least-travel route from the envelope, are given in @sec:ledger.\n\n# Pricing an extra minute {#sec:minutes}\n\nSuppose a publisher can make one uniform change in the next printing. Write $r=w\\delta$ for the extra distance purchased by adding $\\delta$ minutes to every allowance. Each interior interval changes from $[L_i,U_i]$ to $[L_i-r,U_i+r]$. Put $a_i=1$ at a desk inspection and $a_i=0$ at a socket. The value of an allowance at a given cap follows by writing every constraint in @thm:speed in terms of $r$. In particular,\n$$\n v_*(r)=\\max_{i\\ne j}\\frac{(L_j-U_i-(a_j+a_i)r)_+}{|t_j-t_i|}.\n \\label{eq:trade}\n$$\nThis expression assumes the original intervals are nonempty and $r\\ge0$. The curve is piecewise linear, convex and decreasing in the weak sense. A comparison involving a socket gains the distance bought for one desk. A comparison involving desks at both ends gains twice that distance. Treating the filing cabinet at the town hall as another hotel would therefore produce an incorrect marginal rate.\n\nFor the printed directory the binding pair from the socket at opening to the eastern desk at noon remains binding until the disk can stay at home. Substitution in @eq:trade gives $v_*(r)=(900-r)_+/3$ in m/h. Each minute added to the printed allowance removes $80/3$ m/h from the required peak speed until $\\delta=11.25$ min. At that point the eastern desk at noon is exactly 1700 m from the hall. A 21-minute directory would still require motion. The fractional minute occurs because the calculation takes the published time literally. A publisher printing only whole minutes would need 22 to keep the center fixed.\n\n@fig:allow plots exact values at selected allowances. The travel budget has a second change of slope. Up to $r=100$ m the desk at hour 7 still forces a position west of zero. The two excursions require $2(900-r)+2(100-r)$ m. Once that desk's range includes the socket, only the eastern excursion is forced. The lower bound for arbitrary $r\\ge0$ is $2(900-r)_++2(100-r)_+$. It is attained without a speed limit by clipping the original optimal route toward zero. Replace each coordinate $x$ by $\\operatorname{sgn}(x)(|x|-r)_+$. Every modified coordinate is within $r$ of its old interval and the modified route still turns only at its extremal coordinates. This argument gives the least distance over routes of unrestricted speed. A feasible route at the critical speed and allowance can be recovered separately by @prop:clip.\n\n```chart {#fig:allow caption=\"Minimum distance without a speed cap. The marked points are exact directory allowances, including both changes of slope.\"}\n{\"type\":\"line\",\"style\":\"pgfplots\",\"xlabel\":\"Walking allowance (min)\",\"ylabel\":\"Daily disk travel (m)\",\"x\":[10,10.5,11,11.25,12,14,16,18,20,21.25,22],\"series\":[{\"label\":\"Minimum travel\",\"y\":[2000,1840,1680,1600,1480,1160,840,520,200,0,0],\"marker\":\"o\"}],\"legend\":\"none\"}\n```\n\n# Validity periods and duplicate markers {#sec:validity}\n\nAn ambiguity in the phrase within ten minutes is whether it applies at the time on a desk's inspection card or throughout an entire check-in period. Extending each visit to a closed interval with a stationary disk throughout that interval adds two identical endpoint records and requires a hold between them. Travel takes place in the remaining gaps. As a first sensitivity calculation, impose a joint service window of half an hour centered on each appointment. There are 0.75 h between departure and the first window and 0.50 h between adjacent windows. From opening to the beginning of the noon window there are then only $0.75+0.50+0.50=1.75$ h available for travel. A 900 m advance requires at least $3600/7$ m/h over those moving periods. There may also be constraints between interior windows. Using free travel time as the clock in @eq:speed accounts for all of them. This definition of service puts the time spent waiting on the same footing as a closed stretch of track.\n\nAt the opposite extreme every printed desk could claim service all day. A moving disk then offers no benefit. The most westerly desk lies at $-900$ m and the most easterly at $1700$ m. Even with permanent freedom from the socket, the smallest common radius is 1300 m, achieved only at 400 m east. If departure and return at the socket are service instants, the required common radius increases to 1700 m. The 21.25 minutes quoted for a stationary disk thus reappears as the minimum all-day allowance with the hall included. Omitting the hall replaces it by 16.25. In the all-day interpretation it is the inclusion of just one service instant at the hall, rather than the willingness of the surveyor to move, that distinguishes these numbers.\n\nThe register's insistence on a single disk can be tested independently. Consider two disks left permanently at $-100$ and $900$ m. At hour 2 neither marker lies in the common interval. If every desk were permitted to designate its own disk, those same two markers would cover the full observed chainages from $-900$ to $1700$ m at radius 800 m. They would allow the clerk standing at the western and eastern desks to identify different centers during the same inspection. The number of markers needed when a joint inspection must name one common center is the interval stabbing number [@hesterin; @golumbic]. The seven desk intervals here require at least three fixed markers because the intervals at hours 7, 1 and 3 are disjoint. One can meet all seven inspections with markers at $-100$, 300 and 900 m. The survey register would need a separate rule to decide which of the three was returned to the socket.\n\nInterruption of a transport leg can have a different cost from interruption of service. We froze the disk between hours 2 and 3 in the original directory while keeping both inspections. The two permitted intervals are separated by 200 m. At any finite speed a freeze lasting the entire leg requires a common point, hence fails. Uniform relaxation first permits that leg at $r=100$ m, with the shared coordinate exactly 800 m. The conclusion concerns the frozen leg alone. Once the extra travel allowance is granted the other moving legs must still be tested. Treating a closure as a very low but positive speed and rounding the answer to an integer chainage can conceal such a distinction [@innel; @jorven].\n\n# Interpretation and scope {#sec:error}\n\nDirectory conventions differ on whether a time denotes an upper bound, a rounded point estimate, or the median of journeys made by hotel guests [@darsen; @letier]. Only the first convention yields a ball with no inner radius. A strictly positive lower time bound excludes a neighborhood of the desk. The admissible positions even on a straight street then form a union of intervals. A point lying between the surveyor and the next admissible position may itself be inadmissible. The telescoping argument in @prop:clip would lose the betweenness property on which it depends.\n\nFor uncertainty in desk location suppose each published chainage can be in error by at most $e$ m, independently permitted in either direction. To guarantee every walking claim for all such positions, erode each desk ball by $e$ before forming its intersection. For $e=8$ m and a nominal 80 m/min walk, an extra six seconds in the allowance exactly cancels this erosion. Errors for desks on a common survey traverse may have a shared offset. If the office also moves the socket by that offset the whole problem is translation invariant. If the socket is independently surveyed, the offset has to enter the socket-to-desk constraints. Register comparisons with joint and independent datum errors give quite different answers [@pinval]. We have used exact positions for the example to keep that choice visible.\n\nMeasuring distance along a route which is closed for part of the day is another problem. Walking balls could be obtained from a separate shortest-path calculation on the open network [@dijkstra]. On a branching street the common points can include a branch through which the disk must double back. In a square grid two individually reachable inspection regions need not have a common witness compatible with the rest of the day. Neither the one-dimensional proof of sufficiency in @thm:speed nor the scalar clipping operation supplies a solution on an arbitrary street map. At the other end of the scale, substituting distances rounded to the nearest block may make two disjoint walking balls appear to touch [@queral].\n\nThere is no estimate here of the number of guests who would actually arrive within ten minutes. In particular the institution that equates 800 m with ten minutes has made a metrological choice about the guest. Our certificate audits two entries in the directory, the time it promises the guest and the position it assigns to the town. When the directory places the latter in a permanent monument, the survey office can close the transport ledger and check every claim against that single coordinate. The seven-inspection pilot needs a place in the ledger for the trip home.\n\n\\appendix\n\n# Ledger reconstruction {#sec:ledger}\n\n@tbl:ledger gives the bounds delivered to dispatch at the critical cap. A simple check on transcription is to start at the last singleton and add 300 m on either side, then intersect with the preceding raw interval. The hour-7 raw interval extends west to $-400$ m. In the dispatch copy the western endpoint moves to $-300$ m because of the return trip. This change never binds along the chosen route. Removing every ledger entry whose endpoints fail to bind on the final route, however, would make it impossible to certify the remaining freedom available to a substitute dispatcher.\n\nTable: Backward intervals and selected coordinates at 300 m/h, in meters. The last two columns give the projection and lower-envelope paths. {#tbl:ledger}\n\n| Hour | Lower | Upper | Projection | Envelope |\n|-----:|------:|------:|-----------:|---------:|\n| 0 | 0 | 0 | 0 | 0 |\n| 1 | 300 | 300 | 300 | 300 |\n| 2 | 600 | 700 | 600 | 600 |\n| 3 | 900 | 1100 | 900 | 900 |\n| 4 | 700 | 800 | 800 | 700 |\n| 5 | 100 | 500 | 500 | 400 |\n| 6 | -200 | 200 | 200 | 100 |\n| 7 | -300 | -100 | -100 | -200 |\n| 8 | 0 | 0 | 0 | 0 |\n\nThe extra westward travel of the envelope is also visible in @fig:legs. During the first three hours both feasible routes travel exactly at the limit. After noon the envelope moves west sooner. It then continues farther west than the minimum permitted excursion. A dispatcher looking only at speed would declare both paths optimal. Looking only at the number of relocations gives the same answer as well. The disk changes position on each of the eight legs under either rule. The sign and size of the last displacement are needed to distinguish the two costs.\n\n![Signed relocations of the disk in each one-hour gap. Positive chainage runs east.](legs){#fig:legs}\n\n# Checks at zero travel time {#sec:zero}\n\nFor an independent speed check, replace the ordinary clock by cumulative time available for motion. Subtract the lengths of all complete holds before each visit and any portion of a hold before that visit's endpoint. Records with equal values of this new clock must be merged by intersection before @eq:speed is evaluated. A pair with zero separation in time and strictly positive separation in space is an infeasibility certificate. A pair with zero separation in both carries no speed information. Giving either case a small denominator imposes an arbitrary trade between how long the register says the surveyor waited and how precisely the street was measured.\n\nIn the half-hour service case the clock at the seven windows reads $0.75,1.25,1.75,2.25,2.75,3.25,3.75$ h. Closing time reads 4.50 h. The distance of 1000 m between the third and seventh windows now requires at least 500 m/h. The 900 m from the socket to the third window raises the bound to $3600/7$ m/h. A comparison that skips the socket raises it again. At the first window the disk can be at most 300 m east. At the third it must be at least 900 m east. Only one hour of travel time separates the windows. Pairwise evaluation gives 600 m/h as the maximum, attained between those two inspections. A dispatch slip citing the socket and the noon window would understate the speed required by almost 86 m/h.\n","bibliography":"\n@article{hakimi, author={Hakimi, S. L.}, title={Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph}, journal={Operations Research}, year={1964}, volume={12}, pages={450--459}}\n@article{friedman, author={Friedman, Joel and Linial, Nathan}, title={On convex body chasing}, journal={Discrete and Computational Geometry}, year={1993}, volume={9}, pages={293--321}}\n@book{ahuja, author={Ahuja, Ravindra K. and Magnanti, Thomas L. and Orlin, James B.}, title={Network Flows: Theory, Algorithms, and Applications}, publisher={Prentice Hall}, year={1993}}\n@book{schrijver, author={Schrijver, Alexander}, title={Theory of Linear and Integer Programming}, publisher={Wiley}, year={1986}}\n@book{boyd, author={Boyd, Stephen and Vandenberghe, Lieven}, title={Convex Optimization}, publisher={Cambridge University Press}, year={2004}}\n@book{rockafellar, author={Rockafellar, R. Tyrrell}, title={Convex Analysis}, publisher={Princeton University Press}, year={1970}}\n@article{mcshane, author={McShane, E. J.}, title={Extension of range of functions}, journal={Bulletin of the American Mathematical Society}, volume={40}, pages={837--842}, year={1934}}\n@book{aubin, author={Aubin, Jean-Pierre}, title={Viability Theory}, publisher={Birkhäuser}, year={1991}}\n@article{moreau, author={Moreau, J. J.}, title={Evolution problem associated with a moving convex set in a Hilbert space}, journal={Journal of Differential Equations}, volume={26}, year={1977}, pages={347--374}}\n@book{golumbic, author={Golumbic, Martin Charles}, title={Algorithmic Graph Theory and Perfect Graphs}, publisher={Academic Press}, year={1980}}\n@article{dijkstra, author={Dijkstra, E. W.}, title={A note on two problems in connexion with graphs}, journal={Numerische Mathematik}, volume={1}, pages={269--271}, year={1959}}\n@article{eredo, author={Eredo Sen, Malve}, title={The point of departure in reception-based route measurements}, journal={Register Studies in Pedestrian Geography}, year={2014}, volume={7}, pages={18--30}}\n@article{venra, author={Venra, Teres L.}, title={Entrance substitutions in repeated audits of urban directories}, journal={Quarterly Papers in Applied Chainage}, year={2017}, volume={12}, pages={81--96}}\n@article{sovik, author={Sovik Lorent, Anja}, title={Building centroids in short-distance service registers}, journal={Notes of the Lower Mere Survey}, year={2011}, volume={4}, pages={22--37}}\n@article{melrou, author={Melrou, Denis T.}, title={A concordance of postal and pedestrian entrances}, journal={Register Studies in Pedestrian Geography}, year={2019}, volume={12}, pages={40--61}}\n@article{hesterin, author={Hesterin, Maile N.}, title={Piercing intervals in repeated monument surveys}, journal={Transactions on Municipal Geometry}, year={2018}, volume={6}, pages={14--27}}\n@article{innel, author={Innel Broda, Enno}, title={Reachability at a closed chainage}, journal={Quarterly Papers in Applied Chainage}, year={2021}, volume={16}, pages={51--59}}\n@article{jorven, author={Jorven, Elis N.}, title={Time quantization of service interruptions}, journal={Transactions on Municipal Geometry}, year={2022}, volume={10}, pages={63--76}}\n@article{darsen, author={Darsen, Hele M.}, title={Reading times from lodging registers in three corridor towns}, journal={Notes of the Lower Mere Survey}, year={2018}, volume={11}, pages={2--16}}\n@article{letier, author={Letier Volme, Sira}, title={Bounds and typical values in journey cards}, journal={Register Studies in Pedestrian Geography}, year={2020}, volume={13}, pages={80--94}}\n@article{pinval, author={Pinval, Miren A.}, title={Relative position errors for a shared datum}, journal={Quarterly Papers in Applied Chainage}, year={2015}, volume={10}, pages={8--22}}\n@article{queral, author={Queral Neri, Tivio}, title={Apparent contact between rounded service intervals}, journal={Transactions on Municipal Geometry}, year={2020}, volume={8}, pages={42--53}}\n","figures":[{"id":"chainage","kind":"chart","data":"{\"type\":\"line\",\"style\":\"pgfplots\",\"xlabel\":\"Hours from departure\",\"ylabel\":\"Chainage (m)\",\"x\":[0,1,2,3,4,5,6,7,8],\"legend\":\"outside\",\"series\":[{\"label\":\"Lower limit\",\"y\":[0,100,300,900,700,100,-200,-400,0],\"style\":\"dotted\"},{\"label\":\"Upper limit\",\"y\":[0,300,700,1100,1000,600,200,-100,0],\"style\":\"dashed\"},{\"label\":\"Disk\",\"y\":[0,300,600,900,800,500,200,-100,0],\"marker\":\"o\"}]}"},{"id":"legs","kind":"chart","data":"{\"type\":\"bar\",\"style\":\"pgfplots\",\"xlabel\":\"Leg ending at hour\",\"ylabel\":\"Displacement (m)\",\"x\":[\"1\",\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\"],\"legend\":\"outside\",\"series\":[{\"label\":\"Projection\",\"y\":[300,300,300,-100,-300,-300,-300,100]},{\"label\":\"Envelope\",\"y\":[300,300,300,-200,-300,-300,-300,200]}]}"}],"acknowledgments":"The authors thank the Lower Mere register clerks for distinguishing the coordinate of the socket from the coordinate entered on a reception card.","options":{"citation_style":"numeric"}}