『运筹OR帷幄』原创
作者：江镕行
江镕行，同济大学管理科学工程系在读硕博连读生，研究方向:运筹优化算法设计与应用、共享汽车
编者按
共享汽车作为一种新型的商业模式，在提高车辆利用率、缓解交通拥堵等方面效果显著。但现实生活中顾客的交通需求存在高度的不确定性以及时变性，这对共享汽车系统的运营与管理提出了挑战。本文以目前应用最为广泛的单程式电动共享汽车为例，对其运营管理进行建模，采用线性松弛技术对模型进行转化，设计了相应算法加速求解，在提升求解速度的同时保证了求解质量。
1.背景介绍
1.1
近年来私人汽车拥有量的快速增长加剧了社会问题和环境问题，如交通拥堵、停车位缺乏以及温室气体排放等。人们努力探索如何减少私人汽车，于是共享汽车概念应运而生。以zipcar为例，这家共享汽车公司在运营区域内为其会员提供one-way汽车预定服务（起始站点取车并于目的站点还车），根据使用时长付费。
目前的共享汽车运营模式主要分为两种，用户在给定站点取车和还车的站点式（station-based）以及在运营区域内可任意地点还车的自由浮动式（station-free）。其中，前者又可分为必须同一站点取车还车的往返式（round-trip）以及允许异地还车的单程式（one-way）。往返式共享汽车因无法满足用户个性化需求而应用受限，例如加拿大的modo；单程式共享汽车可满足顾客个性化需求，应用非常广泛，如中国的evcard，美国的zipcar；自由浮动式共享汽车给予了用户更充分的灵活性，但给运营管理带来了更大的挑战，如美国的car2go。
1.2
随机规划
共享汽车问题中一大运营挑战是顾客需求的高度不确定性，但研究发现该需求是随时间变化的。比如用户往往集中于早上从郊区赶往市内，并于下午返回，这暗示了交通需求的时空特征，为接下来的规划提供了优化空间。
图1.1 交通需求类型
将一天分为早中晚三个时段，那么各时段A站点和B站点间交通需求如图1.1所示。如果忽略交通需求的不确定性以及时变特征，则得到固定的需求caseⅢ，这样需要在两个站点各设置10个充电桩与停车位。如果加入时变特征，则得到变化的需求caseⅡ，这样需要在A站点设置15个停车位、B站点5个停车位。如果再加入随机特征，则得到需求caseⅠ，此时仅需要在A站点设置16个停车位。可以发现，相较于固定不变的需求，具备时变和随机特征的交通需求为规划提供了优化的空间。
2.模型建立
3.模型求解
该论文的模型是一个基于场景的多阶段问题（scenario-based MultiStage Problem，SMSP），同时也是一个多阶段非线性整数随即规划。由于维度诅咒、整数变量决策以及多阶段非线性等特征，这类问题直接求解极为耗时，需要庞大的算力资源，故论文中开发了一系列算法用于线性松弛以减少求解时间。首先，通过放松非预期约束以应用拉格朗日松弛法，同时开发了一个投影次梯度法以解决相应的拉格朗日对偶问题。然后，发现整数变量仅在初始阶段进行决策，其之后K个阶段的子问题决策仅包含连续变量，故将其线性化为了一个多阶段线性随机规划求解。
3.1
线性化重构
3.2
线性松弛
约束（15）中，车队规模变量以及每天的运营决策变量均为非负整数，但问题规模庞大时求解过于困难，可将变量约束松弛至连续变量。
这样一来，该问题就至存在0-1变量以及非负的连续变量。当最佳决策变量的值较大时，可以将这种松弛得到的解近似为最优解，而当需求较小时，需要对这种近似进行验证（有兴趣的同学可以查阅参考文献1的5.1节）。
3.3
拉格朗日松弛
3.4
投影次梯度法
3.5
SDDP算法
综上所述，可以得到本节算法的伪代码：
4.数值实验
5.总结与展望
电动共享汽车系统的部署与运营是一项极具挑战性的工作，特别是单程式共享汽车系统，因为该系统需要处理一个巨大的时空需求不确定的动态问题。该论文通过建立多阶段随即规划来描述这个复杂的决策过程，并通过蒙特卡洛抽样技术来解决。同时为了克服维度过大的问题，提出了一种基于拉格朗日松弛和SDDP算法的加速技术，比较结果显示，该算法的解在计算时间和求解质量方面表现良好。
然而，由于随机规划问题的复杂性，大规模问题的求解仍是十分困难，有兴趣的大佬可以研究相关问题的加速算法。另外，该论文模型的交通需求与站点位置无关，如果考虑到需求受站点位置、电力价格以及定价方案影响的情况，那可能会产生一些有趣的结论。
因为本人对随机规划的研究还比较粗浅，若有错误理解或疏漏，欢迎大家讨论指出，想要进一步了解共享汽车的同学可以查看参考文献。
参考文献
[1] Hua Y, Zhao D, Wang X, et al. Joint infrastructure planning and fleet management for one-way electric car sharing under time-varying uncertain demand [J]. Transportation Research Part B: Methodological, 2019, 128:185-206.
[2] Zhang D, Liu Y, He S. Vehicle assignment and relays for one-way electric car-sharing systems [J]. Transportation Research Part B: Methodological, 2019, 120:125-46.
[3] Smith S L, Pavone M, Schwager M, et al. Rebalancing the rebalancers: optimally routing vehicles and drivers in mobility-on-demand systems[C]. Proceedings of the 2013 American Control Conference, F 17-19 June 2013, 2013 .
[4] ?alik H, Fortz B. A Benders decomposition method for locating stations in a one-way electric car sharing system under demand uncertainty [J]. Transportation Research Part B: Methodological, 2019, 125:121-50.