8 ms·
Mass Transit Optimization for Buses: The Depot Problem
- whalesalad 8y agoAcknowledging the cookie warning on the site has resulted in an endless 500 loop.
- ericand 8y agoI came just for the cookie bug and was not disappointed.
- amoshag 8y agoThanks. Looking into it
- 1stranger 8y agoSorry for being off-topic but I'm still going to use this as an opportunity to vent. This is the most pointless piece of regulation. It's unfortunate non-US users are also subjected to it. What bit of good does it really do for your average user? It's complete overregulation. If users don't want cookies they can turn them off in their browser. The average user doesn't know or care and these incessant popups help nobody.
- letcree 8y ago> non-US users It is an EU policy, not US (http://ec.europa.eu/ipg/basics/legal/cookies/index_en.htm http://ec.europa.eu/ipg/basics/legal/cookies/index_en.htm).
- lucasmullens 8y agoRight, but US users see the warning too is what the parent post was getting at.
- MiddleEndian 8y agoThe US should pass legislation banning cookie notifications just to counterbalance the incentives. I have them blocked but still they are awful.
- BigDaveTheGiant 8y agoInteresting
- honorious 8y agoThat looks like an interesting problem! 1) What are the metrics that mass transit operators tend to optimize for? Do you think they are in line with improving the service to customers? 2) How much is "dependability" of a mass transit service a metric that operators are interested in? Intuitively I feel that there are places (e.g. Chicago) where I know that I can get out of the house, get the bus/train, and get to my destination with little variance in arrival time. Others (like SF), where the variance on the arrival time seems much higher: e.g., generally related to unexpected delays while waiting for train/bus. Do you think it's possible to optimize on such factors?
- indiesolver 8y agoYou may formulate it as a multi-objective problem where you minimize the estimated time of the trip and your uncertainty of this estimate. Often, the two objectives are conflicting. As a user, the software should show you a Pareto set of optimal solutions where each solution has its duration and uncertainty. Then it is up to you which solution to pick. I hope they have this feature at optibus.
- ishaym 8y agoRight you are :) See my reply later on this thread (ishay from optibus)
- CaliforniaKarl 8y agoI think you should take a look at the documentation behind VTA's "Next Network": https://nextnetwork.vta.org/document-library https://nextnetwork.vta.org/document-library It is planning that was done to prepare for when BART service reaches Santa Clara county, and how the bus network will need to be reorganized. In the documents, you can see how they looked at different plans, covering different levels of geography vs. population.
- honorious 8y agoThanks! The design tradeoff between ridership and coverage is very interesting, and ripe for political discussion. I wonder if there are opportunities for working with on-demand ride companies for coverage, while focusing infrastructure on high-ridership corridors. Fairness of access for disadvantaged people would be a problem to solve.
- shaiu 8y agointeresting and educational article
- rel121 8y agoVery interesting!
- adir223 8y agoIs this operational already?
- amoshag 8y agoDefinitely! In cities such as Las Vegas, Washington DC, Austin, and many others. See optibus.com for more info
- blt 8y agoThis is really cool. Is it possible to express the edge coloring constraints simply via integer linear programming? This seems like the type of problem that might be NP-hard but tractable in practice with good heuristics.
- indiesolver 8y agoYou can use heuristics if/when the problem becomes ugly due to various constraints you may impose. The trick is to select heuristics depending on the problem at hand and in a way that their hyperparameter values are selected properly.
- wenc 8y agoMost modern solvers like CPLEX and Gurobi have built-in heuristics [1] that are automatically selected and applied without user intervention. They typically exploit the structure of the problem or encode the experiences of the developers over large problem testsets. The default heuristics for commercial solvers are actually pretty darned good these days and there's typically no need to hand-pick them. In the MIP world, they are the secret sauce to fast solution times. Hyperparameter tuning has been studied for MIPs (many papers written on this), but ultimately they are black box solutions. My experience inclines me to not even consider hyperparameters except as a last resort or unless you know something specific that a hyperparameter can exploit; there are other more high leverage things than can be done. Random perturbations to the problem have been found to be much more fruitful for forcing a diversity of branch traversal paths and have lead to significant speedups. (M. Fischetti popularized this idea in 2010s [2]) [1] https://resources.mpi-inf.mpg.de/conferences/adfocs-03/Slides/Rothberg_3.pdf https://resources.mpi-inf.mpg.de/conferences/adfocs-03/Slide... Also: http://transp-or.epfl.ch/zinal/2017/slides/group5.pdf http://transp-or.epfl.ch/zinal/2017/slides/group5.pdf [2] https://mat.tepper.cmu.edu/blog/index.php/2012/09/25/fischetti-speeds-up-optimization-with-randomness/ https://mat.tepper.cmu.edu/blog/index.php/2012/09/25/fischet...
- indiesolver 8y agoThank you for providing useful references. Hyperparameter tuning can accelarate CPLEX by 10x and more depending on problem instances (however, it it true that each new version of CPLEX is faster and faster). What I meant is that in the case if your problem is formulated in a way that the CPLEX and Gurobi cannot treat it (e.g., stochastic and multiobjective) and is not very large-scale, then one can use heuristics. However, the efficiency of the latter will likely depend on hyperparameter settings which need to be set properly.
- akeck 8y agoAlso, busses in transit apparently follow "universality". https://www.quantamagazine.org/in-mysterious-pattern-math-and-nature-converge-20130205/ https://www.quantamagazine.org/in-mysterious-pattern-math-an...
- andbberger 8y agoOh gosh what a mess of an article... completely undecipherable. There are many kinds of universality... this article concerns the flavor where many kinds of physical systems appear to be shockingly well-modeled as random matrices. But doesn't manage to convey a single kernel of what this __means__, it just plops information on you like a high-school math class. Tells you the name of things and some basic properties, leaves you with the misleading impression that you have come away with some better understanding... Here's something more substantive to chew on, about universality in transitions to chaos: [1]. Turns out that many chaotic systems 'descend' into chaos in the very same way. What does that really _mean_? I have no idea, but at least this discussion rigorously explains what this universality class is, instead of dousing you with feel good science-hoodoo-voodoo quotes. [1] http://www.cns.gatech.edu/PHYS-4267/UFO.pdf http://www.cns.gatech.edu/PHYS-4267/UFO.pdf
- deleted 8y ago[deleted]
- AstralStorm 8y agoThe thing you're looking for is called Borel measure. (I think this is what you mean at least.) It is a part of advanced topology. Explaining enough topology for a typical reader to get it is a hard task. As in really hard.
- andbberger 8y agoHmm, I'm not sure what you mean. Can you elaborate?
- ShaniNat 8y agoAmazing! This article was very interesting. Thanks!
- dang 8y agoAll: please don't post promotional comments. We ban accounts that do that.
- chaoxu 8y agoIt is unclear what is the objective. Minimize deadhead costs? If so, solving it with min-cost circulation with lower-bound. It would be much cleaner.
- shooltz 8y agoAwesome article - super interesting..
- mac01021 8y agoAnyone else have a ton of trouble understanding the example schedule and how it's represented as a graph? I don't know if it's poorly written or if my brain is deteriorating.
- ishaym 8y agoWhich one? I'd be glad to explain
- ishaym 8y agoThe edges between the trips mean that one trip can be performed after the other on the same vehicle. The costs on these edges represent the distance of the idle trip - if they are far away - it would be more expensive. The depot pull outs are connected to the earlier trips,and depot pull ins to the later trips. The cost of these edges also represents the distance of the depot from this trip.