公交线路选择的网络优化模型摘要本文针对城市公交线路选择问题建立了相应的数学模型。将查询者寻找连接两点的最佳线路的过程看作车辆将查询者从起始站点运输到目的站点的过程，对于此类运输问题，可以建立网络流模型来求解。对于问题一，将公汽站点看作顶点，3957 个公汽站点再加上源点 S 和收点 T 就构成了顶点集 V。至于有向边 vivj，并不是公汽站点间的实际线路，而是表明任意两站点i 与 j 之间能否直达的有向弧，各边的容量为 1、费用率为 bij, 就构造了容量费用网络。再定义 0-1 变量 fij作为流量，当 fij=1 时表明该有向边 vivj中有流量通过，即最佳路线包括边 vivj，就可以建立最小费用流模型来求解。由于源点 S 的出度和汇点 T 的入度均为 1，且所有有向边的容量 cij=1，此最小费用流问题便转化为从 vs到 vt的最短路径问题，本文采纳改进的 Dijkstra 算法求解此最短路问题。结合实际情况，本文从出行花费、换乘次数、出行时间三方面来理解所谓的“最佳线路”，用 mij、kij和 qij分别表征这三个目标的费用率，再引入优先因子来区分各目标的优先级，并结合实际增加换乘次数、费用、时间的上限约束，建立了类似目标规划的网络流模型，编程可求出任意两点在六种情况下的最佳线路。对于问题二，其实就是在问题一的容量费用网络中增加了 39 个顶点与部分有向边，仍旧是一个最小费用流问题，还可以用问题一中的方法求解，只是费用、换乘时间的计算比问题一复杂。对于问题三，将步行看作独立于公汽、地铁的第三种交通方式，仍利用问题二中的网络图，不再增加有向边，并假设步行只能沿已有的有向边行进。主要从步行时间、换乘次数、出行花费和出行总时间四个方面来理解最佳线路，分别考虑各单目标，增加不同的上限约束，建立了相应的网络流模型。模型评价中对本文中的网络流模型进行了详细的评价说明，最后着眼于开发一个解决公交线路选择问题的自主查询计算机系统，提出了一点建议。关键词：最佳线路；最小费用流；Dijkstra 算法；优先因子；上限约束一、问题重述近年来，城市的公交系统有了很大进展，使得公众的出行更加通畅、便利，但公众也同时面临着多条线路的选择问题。针对此市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。设计这样一个系统的核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。现已给出某市公交线路与相关信息，请解决如下...
