交通 | 不确定优化：均值-方差/标准差最短路模型

科技 2024-12-07 20:02 德国

1.为什么考虑出行时间的均值-方差/标准差？

现实世界的问题充满了不确定性，如何在优化问题中考虑这些不确定性呢？①基于大量数据的鲁棒优化Robust optimization；②基于概率分布函数的随机优化Stochastic programming；③基于统计参数的多目标优化，例如均值-方差/标准差优化。①和②的难度和学习成本远远高于③。本次内容关注不确定环境下的均值-方差/标准差优化。什么是均值-方差/标准差优化呢？既优化均值（期望费用），又优化方差/标准差（风险、不确定性）。

在交通网络下，出行时间是不断变化的。下图展示了某条道路，在三天中的出行时间变化情况。观察某一天的出行时间，出行时间在不同的时刻下是不同的，这代表出行时间具有动态性。同一时刻的不同天的出行时间是不同的，这体现了出行时间的不确定性。本次内容关注在不确定环境下的最短路径规划，构建均值-方差/标准差最短路模型。

2.如何将均值和方差/标准差纳入到最短路规划中？

基于历史出行时间，可以计算所有路段的均值、方差、协方差(未考虑)。均值-方差/标准差最短路模型，既要最小化路径出行时间均值，又要最小化路径出行时间方差/标准差。

本问题属于多目标优化问题，既要最小化期望费用，又要最小化出行的不确定性。把路径均值、方差/标准差线性加权，可以得到均值-方差/标准差最短路问题的优化目标，分别是P1和P2。

从量纲角度，P1的均值和方差的量纲不同，P2的均值和标准差的量纲相同。显然，P1的可解释性弱于P2。路径时间均值可理解为出行者的期望出行时间，路径时间标准差项表示冗余出行时间。冗余出行时间可以理解为出行者为了对抗不确定性而多保留的时间。当然，越焦虑的出行者，系数λ越大，总的出行时间预算(Travel time budget, TTB)越大。λ=0和γ=0时，P1和P2退化为最小期望路径问题。

标准的最短路模型可参考历史文章：如何优雅地写出最短路问题的对偶问题？拉格朗日对偶方法。P1和P2的变量和约束与标准的最短路模型相同。变量x决策是否选择某个路段。约束保证选择的路段构成一条完整的路径。

3.如何求解均值-方差/标准差最短路问题？

对于均值-方差最短路问题P1：路径均值和方差项可进行合并，路段均值和方差的组合为路段的广义费用Generalized cost。因此，P1可采用标准的最短路优化方法进行求解，例如标号法。

对于均值-标准差最短路问题P2：路径均值和标准差无法合并，属于非线性优化问题，无法采用标号法求解。对模型进行重构Reformulation，(1)加入辅助变量y替换标准差项；(2)加入耦合约束保证变量y=标准差项。下面向各位展示四种求解思想：

①直接采用求解器Gurobi，9.0之后的版本支持求解非凸优化问题，需要设置NonConvex参数设置为2，https://www.gurobi.com/events/non-convex-quadratic-optimization/。

②拉格朗日松弛耦合约束，松弛问题可进行分解，可参考文献：Xing, T., Zhou, X.S., 2011. Finding the most reliable path with and without link travel time correlation: A Lagrangian substitution based approach. Transport Res B-Meth 45, 1660-1679 和往期文章：有凹目标函数的一类优化问题在交通运输领域的应用。

③固定辅助变量y，采用Benders分解，参考文献：Song, M., Cheng, L., 2022. A generalized Benders decomposition approach for the mean-standard deviation shortest path problem. Transportation Letters, 1-11.

④参数搜索，通过搜索P1的参数γ使得P1和P2的解相同，参考文献Khani, A., Boyles, S.D., 2015. An exact algorithm for the mean–standard deviation shortest path problem. Transport Res B-Meth 81, 252-266和Zhang, Y., Shen, Z.-J.M., Song, S., 2016. Parametric search for the bi-attribute concave shortest path problem. Transportation Research Part B: Methodological 94, 150-168.

4.均值-方差/标准差模型还可以用在哪些问题中？

均值-方差/标准差优化的思想可以推广到很多不确定优化中。

感谢阅读，希望对您有所帮助！祝愿安好！

宋茂灿

Email: songmaocan@foxmail.com

ResearchGate: www.researchgate.net/profile/Maocan_Song

2024/12/5

微信公众号后台回复

加群：加入全球华人OR|AI|DS社区硕博微信学术群

资料：免费获得大量运筹学相关学习资料

人才库：加入运筹精英人才库，获得独家职位推荐

电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...

加入我们：加入「运筹OR帷幄」，参与内容创作平台运营

知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流

文章须知

文章作者：宋茂灿

责任编辑：张云天

微信编辑：疑疑

文章转载自『时空网络流优化』公众号，原文链接：不确定优化：均值-方差/标准差最短路模型

关注我们

运筹OR帷幄

致力于成为全球最大的运筹学中文线上社区

推荐 | 文献综述撰写攻略

交通 | 城市轨道交通车辆配置与列车时刻表优化公众号格式

香港中文大学（深圳）& 深圳市大数据研究院张纵辉教授项目组诚招硕/博研究生、博士后、实习生

赠书活动 | 庄晓天《智能供应链：预测算法理论与实战》

报道 | 2025年1月-3月国际运筹优化会议汇总

『运筹OR帷幄』招募令 | 期待你的加入

【运筹OR帷幄】一周博士申请&会议信息汇总--2024.12(2)

供应链 | POMS论文解读：食品银行供应链中易腐物品的公平分配

求解器中一个参数的介绍：Degenerate Simplex Moves

最后俩天早鸟价：优惠1000元！寒假第三期运筹优化求解器/LLM决策科学/Python数据分析及其在业界实际应用培训课（线上）

学界|瑞士洛桑联邦理工学院招募计算音乐研究博士

服务运营 | 贸易信贷供应对零售库存的影响

NeurIPS 2024｜拆解高复杂运筹问题的砖石，打破数据稀缺的瓶颈，中科大提出高质量运筹数据生成方法

今年顶会这情况。。。大家提前做准备吧！

祝贺戴彧虹副院长当选为国际运筹学会联合会（IFORS）副主席

优化 | KM 定理：不动点迭代的重要工具

分享一下我强化学习的工作：Simple Policy Optimization

交通 | 无人机配送的设施选址决策

全奖｜瑞士洛桑联邦理工学院（EPFL）离散优化小组招收博士

AI顶会AAAI收了一篇论文：没算法没实验，全靠idea思路好...

报道 | 第十六届“行为运筹学与行为运营管理”研讨会会议通知（第三轮）

早鸟优惠1000元！寒假第三期运筹优化求解器/LLM决策科学/Python数据分析及其在业界实际应用培训课（线上）

学界|伦敦政治经济学院招募离散数学、运筹学和博弈论博士

交通 | 不确定优化：均值-方差/标准差最短路模型

双非全拒到博士全奖！逆袭到底有什么秘籍？我来告诉你！

中国团队首次刷新Sartori-PDPTW世界纪录，华为GTS联合深圳市大数据研究院、港中深以昇腾算力实现AI求解器突破

学界|瑞典隆德大学大学招募理论计算机科学\组合优化博士

优化 | 一个实用的端到端的深度学习库存模型

报道 | MIIS 2024 正式注册通道开启

供应链｜亚马逊魔法箱:揭秘全球最强大的物流网络

早鸟优惠1000元！第三期运筹优化求解器/LLM决策科学/Python数据分析及其在业界实际应用培训课（线上）

学界招聘|多伦多大学招募离散优化博士后

服务运营 | Operations Research: 具有异质性服务器池的队列的广义c/µ规则

全奖｜英国伯明翰大学招收计算理论、复杂性相关博士

供应链中订单履约系统与一盘货

优化 | 强化学习中的蒙特卡罗方法

【运筹OR帷幄】一周博士申请&会议信息汇总--2024.12(1)

分类

时事

民生

政务

教育

文化

科技

财富

体娱

健康

情感

旅行

百科

职场

楼市

企业

乐活

学术

汽车

时尚

创业

美食

幽默

美体

文摘

原创标签

时事社会财经军事教育体育科技汽车科学房产搞笑综艺明星音乐动漫游戏时尚健康旅游美食生活摄影宠物职场育儿情感小说曲艺文化历史三农文学娱乐电影视频图片新闻宗教电视剧纪录片广告创意壁纸头像心灵鸡汤星座命理教育培训艺术文化金融财经健康医疗美妆时尚餐饮美食母婴育儿社会新闻工业农业时事政治星座占卜幽默笑话独立短篇连载作品文化历史科技互联网

发布位置

广东北京山东江苏河南浙江山西福建河北上海四川陕西湖南安徽湖北内蒙古江西云南广西甘肃辽宁黑龙江贵州新疆重庆吉林天津海南青海宁夏西藏香港澳门台湾美国加拿大澳大利亚日本新加坡英国西班牙新西兰韩国泰国法国德国意大利缅甸菲律宾马来西亚越南荷兰柬埔寨俄罗斯巴西智利卢森堡芬兰瑞典比利时瑞士土耳其斐济挪威朝鲜尼日利亚阿根廷匈牙利爱尔兰印度老挝葡萄牙乌克兰印度尼西亚哈萨克斯坦塔吉克斯坦希腊南非蒙古奥地利肯尼亚加纳丹麦津巴布韦埃及坦桑尼亚捷克阿联酋安哥拉