基于Frank Wolfe算法,求解交通分配UE模型(Python & NetWorkX)

这篇具有很好参考价值的文章主要介绍了基于Frank Wolfe算法,求解交通分配UE模型(Python & NetWorkX)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、用户均衡模型简略介绍       

1.1 Wardrop第一原理

1.2 用户均衡模型

1.3 BPR函数 

1.4 用户均衡模型的积分项

 二、Frank Wolfe算法求解步骤

三、代码

3.1 导入必要的库

 3.2 构建交通网络

3.3 绘制交通路网图

3.4 定义BPR函数

3.5 初始化路网流量

3.6 获取 flow_temp

3.7 获取下降方向descent

3.8  定义目标函数

3.9 一维搜索最优步长,并更新流量

3.10 主函数

四、所用文件


 文章来源地址https://www.toymoban.com/news/detail-848461.html

一、用户均衡模型简略介绍       

1.1 Wardrop第一原理

  •  道路的利用者,都确切知道网络的交通状态,并试图选择最短路径
  • 当网络达到平衡状态时,每个OD对的各条被使用的路径,行驶时间相等,且行驶时间最短
  • 没有被使用的路径的行驶时间大于或等于最小行驶时间

1.2 用户均衡模型

        满足Wardrop第一原理的交通分配模型,称为用户均衡模型。

        1956年Beckmann提出了一种满足Wardrop第一原理的数学规划模型。模型核心是,交通网络中的用户,都试图选择最短路径,而最终使得被选择的路径的阻抗最小且相等。该数学规划模型为:

beckmann 提出的ue状态下的优化模型,交通网络,python,交通物流

1.3 BPR函数 

        在用户均衡模型中,为路阻函数,我们一般采用BPR函数,即:

beckmann 提出的ue状态下的优化模型,交通网络,python,交通物流

  • ,表示最快通过路段a的时间;
  • α常取0.15,β常取4.0 ;
  • ,表示路段a的通行能力;
  • ,表示路段a的流量

1.4 用户均衡模型的积分项

        为便于后续求解,我们将BPR函数代入,进行积分计算,过程如下:

beckmann 提出的ue状态下的优化模型,交通网络,python,交通物流

        因此,我们的目标函数为:

beckmann 提出的ue状态下的优化模型,交通网络,python,交通物流

 

 二、Frank Wolfe算法求解步骤

        友情提醒:后面若对代码主体逻辑有疑惑,返回看看这部分。

        步骤1:初始化。基于零流图的路阻,依次搜索每一个OD对 r,s 所对应的最短路径,并将 r,s 间的OD流量,全部分配到对应的最短路径上,得到初始路段流量,并令迭代次数n=1。

        步骤2:更新路阻。根据BPR函数,分别代入每个路段的初始流量,求得阻抗

        步骤3:下降方向。基于阻抗,按照步骤1中的方法(最短路全有全无分配),将流量重新分配到对应路径上,得到临时路段流量,进而得到

        步骤4:搜索最优步长,并更新流量。采用二分法,搜索最优步长,并令eq?X_%7B2%7D%3DX_%7B1%7D+step%5E%7B*%7D*%28%7BX_%7B1%7D%7D%5E%7B*%7D-X_%7B1%7D%29。其中,最优步长满足:

beckmann 提出的ue状态下的优化模型,交通网络,python,交通物流

        步骤5:结束条件。如果%5Csum_a%7Bx_%7Ba%7D%5E%7Bn%7D%7D%5Cleqslant%20e,则算法结束;否则n=n+1,转至步骤2。此处的e 表示误差阈值,在代码部分用max_err表示。

 

三、代码

        代码基于Python的NetWorkX库编写,这样将大大减少我们代码编写的工作量,并且更易于阅读。我们以SiouxFalls交通网络为例,进行交通网络构建与流量分配。

3.1 导入必要的库

import pandas as pd
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from scipy.optimize import minimize_scalar
  • pandas,用于读取文件;
  • numpy在计算误差时使用;
  • networkx贯穿整个代码;
  • matplotlib用于绘制交通网络图
  • scipy在搜索最优步长时用到。

 3.2 构建交通网络

def build_network(Link_path, Node_path):
    # 读取点数据、边数据
    links_df = pd.read_csv(Link_path)
    # 需要注意使用from_pandas_edge,其读取的边的顺序和csv中边的顺序有差异
    G = nx.from_pandas_edgelist(links_df, source='O', target='D', edge_attr=['FFT', 'Capacity'], create_using=nx.DiGraph())
    nx.set_edge_attributes(G, 0, 'flow_temp')
    nx.set_edge_attributes(G, 0, 'flow_real')
    nx.set_edge_attributes(G, 0, 'descent')
    nx.set_edge_attributes(G, nx.get_edge_attributes(G, "FFT"), 'weight')

    # 获取节点位置信息
    nodes_df = pd.read_csv(Node_path)
    node_positions = {}
    for index, row in nodes_df.iterrows():
        node_positions[row['id']] = (row['pos_x'], row['pos_y'])
    # 更新图中节点的位置属性
    nx.set_node_attributes(G, node_positions, 'pos')
    return G
  • Link_path,表示路网文件路径。下载链接见文末,数据示例如下:
O D FFT Capacity
1 2 6 25900.20064
1 3 4 23403.47319
2 1 6 25900.20064
2 6 5 4958.180928
3 1 4 23403.47319
  • Node_path,表示节点文件路径。下载链接见文末,数据示例如下:
id pos_x pos_y
1 2 2
2 13 2
3 2 5
4 5 5
5 9 5
  • flow_real,表示每次迭代更新后的路段流量或初始化流量,所有路段的flow_real组成
  • flow_temp, 所有路段的flow_temp组成
  • descent,表示flow_temp与flow_real的差值,所有路段的descent组成
  • weight,表示路阻。初始的路阻,由于路段流量都是0,所以直接用FFT。后续将用BPR函数计算

3.3 绘制交通路网图

def draw_network(G):
    pos = nx.get_node_attributes(G, "pos")
    nx.draw(G, pos, with_labels=True, node_size=200, node_color='lightblue', font_size=10, font_weight='bold')
    plt.show()

         构建交通网络后,我们来看一看这个SiouxFalls网络长什么样子吧

beckmann 提出的ue状态下的优化模型,交通网络,python,交通物流

3.4 定义BPR函数

def BPR(FFT, flow, capacity, alpha=0.15, beta=4.0):
    return FFT * (1 + alpha * (flow / capacity) ** beta)
  • FTT,表示最快通过时间;
  • flow,表示路段流量;
  • capacity,表示路段通行能力;
  • alpha和beta,是BPR函数的参数,在此取默认值。

3.5 初始化路网流量

def all_none_initialize(G, od_df):
    # 这个函数仅使用一次,用于初始化
    # 在零流图上,按最短路全有全无分配,用于更新flow_real
    for _, od_data in od_df.iterrows():
        source = od_data["o"]
        target = od_data["d"]
        demand = od_data["demand"]
        # 计算最短路径
        shortest_path = nx.shortest_path(G, source=source, target=target, weight="weight")
        # 更新路径上的流量
        for i in range(len(shortest_path) - 1):
            u = shortest_path[i]
            v = shortest_path[i + 1]
            G[u][v]['flow_real'] += demand
    # 初始化流量后,更新阻抗
    for _, _, data in G.edges(data=True):
        data['weight'] = BPR(data['FFT'], data['flow_real'], data['Capacity'])

        这个函数仅使用一次,用于初始化。在零流图上,按最短路全有全无分配,用于得到。

  • od_df表示pd.Dataframe数据格式的OD流量信息。ODParis.csv示例数据如下:
o d demand
1 2 100
1 3 100
1 4 500
1 5 200
1 6 300
1 7 500

3.6 获取 flow_temp

        flow_temp,即

def all_none_temp(G, od_df):
    # 这个是虚拟分配,用于得到flow_temp
    # 每次按最短路分配前,需要先将flow_temp归零
    nx.set_edge_attributes(G, 0, 'flow_temp')
    for _, od_data in od_df.iterrows():
        # 每次更新都得读OD,后面尝试优化这个
        source = od_data["o"]
        target = od_data["d"]
        demand = od_data["demand"]
        # 计算最短路径
        shortest_path = nx.shortest_path(G, source=source, target=target, weight="weight")
        # 更新路径上的流量
        for i in range(len(shortest_path) - 1):
            u = shortest_path[i]
            v = shortest_path[i + 1]
            # 更新流量
            G[u][v]['flow_temp'] += demand

3.7 获取下降方向descent

        descent,即

def get_descent(G):
    for _, _, data in G.edges(data=True):
        data['descent'] = data['flow_temp'] - data['flow_real']

3.8  定义目标函数

def objective_function(temp_step, G):
    s, alpha, beta = 0, 0.15, 4.0
    for _, _, data in G.edges(data=True):
        x = data['flow_real'] + temp_step * data['descent']
        s += data["FFT"] * (x + alpha * data["Capacity"] / (beta + 1) * (x / data["Capacity"]) ** (beta + 1))
    return s

        该部分代码,对应本文1.4部分的目标函数,即:

beckmann 提出的ue状态下的优化模型,交通网络,python,交通物流

3.9 一维搜索最优步长,并更新流量

def update_flow_real(G):
    # 这个函数用于调整流量,即flow_real,并更新weight
    best_step = get_best_step(G)  # 获取最优步长
    for _, _, data in G.edges(data=True):
        # 调整流量,更新路阻
        data['flow_real'] += best_step * data["descent"]
        data['weight'] = BPR(data['FFT'], data['flow_real'], data['Capacity'])


def get_best_step(G, tolerance=1e-4):
    result = minimize_scalar(objective_function, args=(G,), bounds=(0, 1), method='bounded', tol=tolerance)
    return result.x

3.10 主函数

def main():
    G = build_network("Link.csv", "Node.csv")  # 构建路网
    draw_network(G)  # 绘制交通路网图
    od_df = pd.read_csv("ODPairs.csv")  # 获取OD需求情况
    all_none_initialize(G, od_df)  # 初始化路网流量
    print("初始化流量", list(nx.get_edge_attributes(G, 'flow_real').values()))

    epoch = 0  # 记录迭代次数
    err, max_err = 1, 1e-4  # 分别代表初始值、最大容许误差
    f_list_old = np.array(list(nx.get_edge_attributes(G, 'flow_real').values()))
    while err > max_err:
        epoch += 1
        all_none_temp(G, od_df)  # 全有全无分配,得到flow_temp
        get_descent(G)  # 计算梯度,即flow_temp-flow_real
        update_flow_real(G)  # 先是一维搜索获取最优步长,再调整流量,更新路阻

        # 计算并更新误差err
        f_list_new = np.array(list(nx.get_edge_attributes(G, 'flow_real').values()))  # 这个变量是新的路网流量列表
        d = np.sum((f_list_new - f_list_old) ** 2)
        err = np.sqrt(d) / np.sum(f_list_old)
        f_list_old = f_list_new

    print("均衡流量", list(nx.get_edge_attributes(G, 'flow_real').values()))
    print("迭代次数", epoch)
    # 导出网络均衡流量
    df = nx.to_pandas_edgelist(G)
    df = df[["source", "target", "flow_real"]].sort_values(by=["source", "target"])
    df.to_csv("网络均衡结果.csv", index=False)


if __name__ == '__main__':
    main()
  • epoch,表示迭代次数
  • err,表示误差初始值
  • max_err,表示最大容许误差
  •  f_list_new, f_list_old分别表示和,用于计算误差

四、所用文件

        下载链接:交通分配(UE模型)

 

到了这里,关于基于Frank Wolfe算法,求解交通分配UE模型(Python & NetWorkX)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2015年亚太杯APMCM数学建模大赛B题城市公共交通服务水平动态评价模型求解全过程文档及程序

    原题再现    城市公共交通服务评价是城市公共交通系统建设和提高公共交通运营效率的重要组成部分。对于公交企业,管理和规划部门,传统公交车站、线路和换乘枢纽的规划数据只是基于主管部门收集的统计数据和人工盘点。    在自动采集技术日益发展的今天,如果

    2024年02月07日
    浏览(56)
  • 机器学习笔记之优化算法(七)线搜索方法(步长角度;非精确搜索;Wolfe Condition)

    上一节介绍了 Glodstein text{Glodstein} Glodstein 准则 ( Glodstein Condition ) (text{Glodstein Condition}) ( Glodstein Condition ) 及其弊端。本节将针对该弊端,介绍 Wolfe text{Wolfe} Wolfe 准则 ( Wolfe Condition ) (text{Wolfe Condition}) ( Wolfe Condition ) 。 Armijo text{Armijo} Armijo 准则及其弊端 在当前迭代步骤

    2024年02月14日
    浏览(46)
  • 交通物流模型 | 基于交通图卷积长短时记忆网络的网络级交通流预测

    交通物流模型 | 基于交通图卷积长短时记忆网络的网络级交通流预测 由于道路网络时变的交通模式和复杂的空间依赖性,交通流预测是一个具有挑战性的时空预测问题。为了克服该挑战,作者将交通网络看为一张图,并提出一个新的深度学习预测模型,交通图卷积长短时记忆

    2024年02月07日
    浏览(36)
  • 武器目标分配问题研究进展: 模型、算法与应用

    源自:系统公正与电子技术 作者:李梦杰  常雪凝  石建迈  陈超  黄金才  刘忠 武器目标分配问题是指挥控制与任务规划领域的关键难点之一, 也是军事运筹领域的基础研究课题。经过多年研究, 武器目标分配问题在陆海空天电等领域都得到了广泛研究, 涌现出了大量模型

    2024年02月10日
    浏览(40)
  • 【特别篇】基于动态规划的武器指挥系统火力分配模型

    本文 仍然只是 B站相关视频的 代码复现 ,感兴趣的朋友可以进一步了解 武器指挥分类决策火力问题 的更多内容。 笔者简介:CCNU计科,喜欢看日漫唱歌看球和弹钢琴,还有偶像梅老板。 火力分配属于一种资源分配问题,将供应量有限的若干种资源,比如说资金、机器设备、

    2024年02月06日
    浏览(40)
  • 遗传算法及基于该算法的典型问题的求解实践

        遗传算法是一个很有用的工具,它可以帮我们解决生活和科研中的诸多问题。最近在看波束形成相关内容时了解到可以用这个算法来优化阵元激励以压低旁瓣,于是特地了解和学习了一下这个算法,觉得蛮有意思的,于是把这两天关于该算法的学习和实践的内容总结成了

    2024年03月21日
    浏览(47)
  • DETR | 基于匈牙利算法的样本分配策略

    如有错误,恳请指出。 前不久,沐神对DETR进行了讲解,其实之前也对DETR进行了介绍,见:论文阅读笔记 | 目标检测算法——DETR。现对DETR的核心内容进行重温,也就是其所提出的目标检测的end-to-end框架,输入的是一张图像,输出的直接是最后的预测标注结果,不再需要后处

    2024年02月11日
    浏览(37)
  • 基于OR-Tools的装箱问题模型求解(PythonAPI)

    装箱问题(packing problem)的描述是要将一组给定尺寸的物品放置到具有固定容量的容器中,一般情况下由于容器有容量限制,不可能放入所有物品,那么装箱问题的目标是要找到限定约束下使得总价值最大或总花费最小的装箱方法。根据我们具体的目标情况,装箱问题又可分

    2024年02月06日
    浏览(39)
  • 实验报告——基于Dijsktra算法的最短路径求解

    一个不知名大学生,江湖人称菜狗 original author: jacky Li Email : 3435673055@qq.com Last edited: 2022.12.3   目录 一、实验目的 二、实验设备 三、实验内容 【问题描述】 【输入要求】 【输出要求】 【输入样例】 【输出样例】 四、实验提示 五、实验步骤 5.1 六、实验结果 6.1程序完成后

    2024年02月07日
    浏览(46)
  • 实验六 基于 Dijsktra 算法的最短路径求解

    实验六 基于Dijsktra算法的最短路径求解 一、实验目的 1.掌握图的邻接矩阵表示法,掌握采用邻接矩阵表示法创建图的算法。 2.掌握求解最短路径的 Dijsktra 算法。 二、实验内容 一张地图包括 n 个城市,假设城市间有 m 条路径(有向图),每条路径的长度 已知。给定地图的一个起

    2024年01月18日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包