- 车载电子设备的中文学术期刊有哪些 59
- 关于图书书号的几种类型以及它们申 61
- 多少分的SCI期刊才能称之为优秀 56
- 论文注释的作用 68
- 清华大学在重型车辆氨氢融合零碳动 61
- 探索著作出书的费用 63
- 清华大学团队在金属团簇近红外发光 58
- 北京大学马思伟研究团队在基于内容 52
- 写论文的绪论需要注意什么? 57
- 列举一些优秀的行为经济学论文题目 43
- 《中国教育学前沿杂志期刊》的栏目 51
- EI会议论文的流程可概括的几个主 67
- 探讨超声医学的课题方向 47
- 电子商务主要有哪些类型 61
- 撰写学术会议推荐信的结构和内容 68
- 深圳市汉威展览策划有限公司 17429
- 第十三届全国渗流力学学术会议暨渗 1422
- 中国医院药学杂志编辑部 22365
- IAASE 20424
- 上海新华投资发展有限公司 17390
- 上海决策者经济顾问有限公司 17371
- 宁波德泰中研信息科技有限公司 7435
- 中国互联网经济学术峰会(2014 23385
- nogara 17382
- 广州市臻阅会展服务有限公司 1395
- 云南兆驰会议展览服务有限公司 23405
- 中国金属学会分析测试分会 20405
- 云南大学 17383
- 上海英致商务咨询有限公司 1389
- 北京会展公司 17407
- 鼎盛文化产业投资公司 17375
- 西安石油+IPPTC 23411
- 山东飞鲨国际展览有限公司 7382
- 安徽伟风汽车销售公司 20404
- 郑州大学南校区数学系 17394
清华大学深圳国际研究生院戚铭尧合作在竞争性设施选址问题的理论方法研究上取得新进展
2024/04/24
竞争性设施选址问题(Competitive Facility Location Problem, CFLP)是指在多个市场主体之间为了赢得同类产品或服务的市场份额而开展的一种博弈决策问题,它有着广泛的应用基础,例如零售店、购物中心、停车场、租车店、电动车充电站的选址等。其中,序贯(Sequential)竞争性设施选址问题(S-CFLP)考虑一种更加复杂的决策环境,即市场中的主导方(leader)在进行自己的选址决策时,还必须预计跟随方(follower)在得知主导方决策后所做出的最优反制决策,从而使主导方得到具有预见效果的最优决策,属于一种斯坦伯格博弈问题。常规的CFLP问题可以建模为一个单层的混合整数线性规划(MILP),或者混合整数凹优化模型,求解相对容易,而S-CFLP问题则是一个上下两层均为混合整数非线性规划(MINLP)的双层规划问题,其求解难度极大,除了暴力枚举法之外,目前尚没有能求解这一问题的精确算法。
图1. 序贯竞争性设施选址问题求解界面(圆点为顾客点,黑色方框为候选设施点,红色方块为领导者所选的设施,红十字为跟随者选择的设施)
针对这一复杂的优化问题,清华大学深圳国际研究生院戚铭尧副教授与美国密歇根大学安娜堡分校江瑞威副教授和沈思倩副教授合作,提出了一种高效的精确算法。首先,将原始的双层优化问题通过巧妙的数学变换,等价转化为一种单层混合整数非线性规划模型(MINLP)。其次,为了处理棘手的混合整数非线性约束,该研究推导出了两类有效不等式(线性约束)来代替非线性约束:一类是将领导者的市场份额函数转化为一个集合函数,并证明该函数具有次模性(Submodularity),从而推导出一种次模割(Submodular Cut);另一类是利用决策变量是0-1变量的特点,将原本非凸非凹的市场份额函数放大为一个凹函数,同时保持整数解上的值不变,从而在整数解上生成外逼近割(Outer Approximation Cut)。通过生成这两种割,使得问题的求解速度提高了至少两个数量级。此外,由于生成有效不等式(割)需要求解出下层问题,该研究进一步提出了一种可以在多项式时间内求解下层问题的近似算法,使得算法速度再次提高2-3倍。最后,该研究还提出了一种近似求解模型,能把原问题转化为一个具有精度保证的混合整数二阶锥规划(MISOCP)问题,从而可以直接用已有的求解器来求解。
图2. 原始市场份额函数(左)和凹化后的市场份额函数(右),见曲面和平面的交线
数值实验表明,基于等价模型及其算法,可以求得最优解的问题规模达到100个候选设施、2000个顾客点,这个规模对于精确算法来说已经足够大,甚至远高于已有的启发式算法所能求解的规模。数值实验还表明,算法只需要用最初的几次迭代(数秒内),即可得到离最优解非常接近的近似解(gap<3%),这表明算法还可以为实际应用中可能出现的更大规模的问题提供高质量的近似解。利用所提出的理论方法,该研究还探讨了用户选择模型的参数取值对选址行为的影响。研究发现,反映空间阻隔效应的参数越小,领导者和跟随者的设施选址都宜尽量靠近市场区域中心,而当空间阻隔效应较大时,二者的设施宜在区域内相对分散。该研究还对问题假设进行了多方面的拓展,使得所提出的方法还可以适用于更多的场景,例如:同时决策设施的规模、考虑更多的市场竞争者、市场聚集效应等。
该研究工作以“序贯竞争性设施选址:精确与近似算法”(Sequential Competitive Facility Location: Exact and Approximate Algorithms)为题,发表在国际学术期刊《运筹学》(Operations Research)上。清华大学深圳国际研究生院戚铭尧副教授为文章的第一作者,美国密歇根大学安娜堡分校江瑞威副教授为第二作者,该校沈思倩副教授为第三作者兼通讯作者。该工作得到国家自然科学基金面上项目资助。
文章来源清华大学新闻,分享只为学术交流,如涉及侵权问题请联系我们,我们将及时修改或删除。
信息工程学院张敏课题组在低维晶体管接触性能极限的研究中取得重要进展
清华大学深圳国际研究生院丁文伯团队合作在摩擦纳米发电机基础理论上取得新进展
清华大学深圳国际研究生院周光敏团队合作在机器学习辅助筛选高活性锂硫电池催化剂方面取得新进展
张艳锋课题组在新型超薄镍基碲化物的制备及其自插层结构研究中取得重要进展
北京大学黄清华教授团队与海外学者合作在地幔过渡带水含量探测研究领域取得进展
BIOPIC汤富酬课题组与合作者系统探究纺锤体置换技术对人类早期胚胎发育的影响
北京大学谢晓亮/曹云龙联合团队破解新冠病毒演化趋势 广谱抗体再添抗疫新武器
第四届计算机图形学、图像与虚拟化研究国际会议(ICCGIV 2024)(2024-05-17)
第九届机电控制技术与交通运输国际学术会议(ICECTT 2024)(2024-05-24)
2024年教育政策与实践研讨会(ICEPP 2024)(2024-05-24)
第三届机电一体化与机械工程国际会议(ICMME2024)(2024-05-24)
2024年电子器件、传感控制技术与光学机械工程国际学术会议(EDSCTOE 2024)(2024-05-25)
第十四届地质和地球物理学国际会议(ICGG 2024)(2024-05-31)
2024年食品工程与农业科学国际会议(ICFEAS 2024)(2024-06-02)
2024年第三届网络、通信与信息技术国际会议(CNCIT 2024)(2024-06-07)
第十届机械工程、材料和自动化技术国际会议(MMEAT 2024)(2024-06-21)
2024年先进机器人,自动化工程与机器学习国际会议(ARAEML 2024)(2024-06-28)
2024电力电气、能源系统与智能电网国际会议(ICEPESSG 2024)(2024-6-30)
2024年第五届控制,机器人与智能系统国际会议(CCRIS 2024)(2024-8-23)
2024年铁路、工程材料与自动控制国际学术会议(REMAC 2024)(2024-6-29)
2024年交通运输、计算机技术与信息科学国际会议(TCTIS 2024)(2024-7-27)
2024清洁能源、低碳技术与环境工程国际会议(CELCTEE 2024)(2024-5-25)
2024社会心理学、人文发展与现代化教育国际会议(ISPHDME 2024)(2024-5-21)
2024年心理学、教育与社会发展国际会议(ICPESD2024)(2024-6-20)
第四届互联网、教育与信息技术国际学术会议(IEIT 2024)(2024-5-31)
2024年新能源技术与动力工程国际学术会议(ICNETPE 2024)(2024-5-28)
2024年金融创新与数据科学国际会议(ICFIDS 2024)(2024-6-29)