【作者】 杨军；

【导师】 舒嘉；

【作者基本信息】 东南大学 ， 管理科学与工程， 2023， 硕士

【摘要】 近年来,随着汽车数量的不断增加,现有停车位数量远不能满足司机的停车需求。寻找可用停车位不仅对司机造成了极大困扰,而且引发了一系列的交通、环境问题,严重影响了城市的市政。停车问题的出现一方面是由于停车位的供需不平衡,另一方面是由于停车位的利用率低。如何提高停车位的利用率,有效地解决停车问题,已成为每个城市面临的重大难题。因此,研究有效的智能停车系统是停车管理领域迫在眉睫的任务。在此背景下,本文通过停车预约系统解决停车问题,其中停车管理平台根据司机的预约信息分配有限的停车位,以实现社会福利最大化。本文将网络外部性引入到停车预约系统之中,其中网络外部性概况了停车预约系统中司机间行为相互影响的特点,并为使用该系统的司机带来额外价值,该额外价值取决于该平台中其他司机的数量。本文通过一个广义的函数来描述该网络外部性,从而将相应的停车位分配问题构建为一个非线性0-1整数规划模型。为解决这个具有挑战性的模型,本文引入列生成算法,其中子问题通过多项式时间动态规划方法求解。理想情况下,停车位分配是基于司机提供完全信息下实施的。然而,由于司机的预约信息属于其私人信息,司机有动机误报他们的真实信息,这损害停车位分配的最优性。为此,本文设计了一个generalized Vickrey-Clarke-Groves(G-VCG)拍卖刺激司机如实报道真实信息,该拍卖可以实现激励兼容、分配效率和个体理性。基于实际情况,本文将G-VCG拍卖进一步拓展到司机到达时间不确定的情况。最后,本文通过大量的数值研究,将列生成算法与基准算法对比,验证了列生成算法的求解效率;将考虑网络外部性的停车位分配结果与无网络外部性对应的结果对比,结果表明网络外部性可为司机和平台带来更大的收益并增大平台服务司机的数量。更多还原

【Abstract】 In recent years,with the increasing number of cars,the number of existing parking spaces is far from meeting the parking needs of drivers.Finding available parking spaces not only causes great trouble to drivers,but also causes a series of traffic and environmental problems,which seriously affects the municipal administration of the city.The parking problem is due to the imbalance between supply and demand of parking spaces and the low utilization rate of parking spaces.How to improve the utilization rate of parking spaces and effectively solve the parking problem has become a major problem faced by each city.Therefore,it is an urgent task to study an effective intelligent parking system in the field of parking management.A parking reservation system is introduced to solve parking management problem under this background,where the parking management platform allocates limited parking spaces according to the driver’s reservation to maximize social welfare.The network externality is introduced into the parking reservation system in this study,in which the network externality summarizes the characteristics of the interaction between drivers in the parking reservation system,and brings an added value to drivers,where the added value depends on the number of other drivers in the platform.The network externality is captured by a general function,and the corresponding parking allocation model is formulated as a nonlinear binary integer programming.To solve this challenging model,a column generation algorithm is proposed,where the subproblem is solved by a polynomial-time dynamic programming.Ideally,the problem of parking space allocation is implemented with true information of drivers.However,the drivers’ reservation information belongs to their private information,and drivers have the incentives to misreport their real information,which damages the optimality of parking space allocation.Therefore,a generalized Vickrey-Clarke-Groves(G-VCG)auction is proposed to incentive drivers to report their information truthfully,which can achieve incentive compatibility,allocative efficiency and individual rationality.Considering the actual situation,the G-VCG auction is further extended to the case of uncertain arrival time of drivers.Through extensive studies,the efficiency of proposed column generation algorithm is validated by comparing with several benchmarks.The comparisons of the allocation results between network externality and without network externality indicate that network externality can bring greater profit to drivers and platform,and increase the number of drivers served by the system.更多还原