Enhanced Benders decomposition approach for shared vacant private parking spaces allocation method considering uncertain parking duration of demanders
研究了需求者停车时长不确定下的共享空闲私人停车位分配问题，提出一种增强型Benders分解算法，实验表明该算法优于传统方法，能有效求解大规模复杂问题。
We study a shared vacant private parking spaces allocation problem that considers the uncertain parking duration of demanders. To solve the problem, we first formulate a stochastic programming model (P model). The objective is to maximize the weighted sum of the total expected profits from the platform parking revenue, overload cost and idle cost. On this basis, we reformulate the P model into the UPDA model based on the sample average approximation. Unlike the traditional construction of Benders cut using the dual problem, we construct a new Benders cut based on the lower bound of the subproblem, and then propose an efficient enhanced Benders decomposition (EBD) algorithm for solving the UPDA model. Finally, the performance of the algorithm is verified by numerical experiments. The experimental results show that the enhanced Benders decomposition algorithm outperforms both the Benders decomposition algorithm and commercial solver, and can effectively solve large-scale problems with high complexity. The experimental results also show that the uncertainty in the parking duration of the demander has negative impact on the system performance.