公交公交算法 [英] Bus public transport algorithm

问题描述

我正在开发一个可以找到公交路线的离线C#应用程序. 我可以提取时间表/公交车/路线数据.我正在寻找适用于基本数据的最简单的解决方案.

I am working on an offline C# application that can find bus routes. I can extract the timetable/bus/route data. I am searching for the most simple solution that will work with basic data.

可以使用什么算法找到从巴士站"A"到巴士站"B"的路线?是否有适用于C#/Java的开源解决方案? Google GTFS数据库格式适合简单解决方案吗? http://code.google.com/transit/spec/transit_feed_specification.html

What algorithm can be used to find a route from bus stop "A" to bus stop "B"? Is there a open-source solution ready for C#/Java? Is the google GTFS format for database good for a simple solution? http://code.google.com/transit/spec/transit_feed_specification.html

感谢您的帮助.我坚持这一点.我不知道从哪里开始-如何存储数据以及如何找到路线. 我知道Dijkstra/A *，但是我只在不依赖时间的图形上使用它们.

Thanks for any help. I am stuck with this. I don't know where to start - how to store the data and how to find routes. I know about Dijkstra/A* but I have used them only on graphs that were not time dependent...

推荐答案

您正在解决的问题并非微不足道.如此命名的就是:混合整数非线性规划问题(MINLP).用一位作者的话说(Deb 1998):

The problem you are working on is not a trivial task. So much so, that is has a name: the mixed integer nonlinear programming problem (MINLP). In the words of one author (Deb 1998):

"以数学公式表示时， 时间安排问题变成了 混合整数非线性规划 大量的问题(MINLP) 与资源和服务有关的 约束.尽管有尝试 在过去找到 简化模型的最佳计划 使用经典优化 技术(Bookbinder和DCsilets， 1992年；菊池&帕拉梅斯瓦兰(1993)， 据观察，这是一个 即使是一个非常困难的任务 小型公交网络.难点 产生的主要原因是 变量和约束的数量， 变量的离散性质，以及 涉及的非线性 目标函数与 约束."

"When formulated mathematically, the time scheduling problem becomes a mixed integer nonlinear programming problem (MINLP) having a large number of resource- and service-related constraints. Although attempts have been made in the past to find an optimal schedule of a simplified model using classical optimization techniques (Bookbinder & DCsilets, 1992; Kikuchi & Parameswaran, 1993), it is observed that this is an extremely difficult task even for a small transit network. The difficulty arises mainly because of the large number of variables and constraints, discrete nature of variables, and nonlinearities involved in the objective function and the constraints."

在Deb的论文中，他提出了一种遗传算法.

In Deb's paper he proposes a genetic algorithm.

您的另一个选择是使用模拟.只是把东西扔出去，您可以立即尝试-选择从您的起点开始的数千条随机路线，然后找出在到达目的地时效果较好的路线.

Your other option would be to use simulation. Just to throw something out there you can try right away-- choose thousands of random routes that start at your origin, and fish out the ones that work reasonably well at getting to the destination.

将算法描述如下:您正在尝试查找在特定时间开始的从站点A到站点B的最快路线.您雇佣了1,000名员工，并用四分之一的武装来武装他们.您告诉他们每当他们有机会上下车时都要掷硬币.头，下车(或上车，如果已经下车).尾巴，留在上面(或保持等待，如果关闭).他们每个人都有一张索引卡，可以记下他们所做的选择.您进入B点，等待第一个家伙出现并拿走他的卡.

Picture the algorithm like this: You are trying to find the quickest route from stop A to stop B, starting at a certain time. You hire 1,000 people and arm them with a quarter to flip. You tell them to flip the coin every time they have a chance to get on or off a bus. Heads, get off (or get on, if already off). Tails, stay on (or keep waiting, if off). They each have an index card to write down the choices they make as they go. You go to point B and wait for the first guy to show up and take his card.

这篇关于公交公交算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！