论文部分内容阅读
拼车出行作为一种经济的出行方式,吸引了越来越多的乘客使用。如何有效地将乘客的订单分配给合适的司机成为了关键问题。为了给予司机更加合理的报酬,激励司机提供拼车出行服务,本文将对拼车出行中订单分配和司机定价的机制进行研究。在拼车出行中,司机是理性的,且具有异质性(例如不同的司机具有不同的成本信息),并会通过策略性行为(例如虚假地揭露自己的成本信息)去获得更多的利润。司机的策略性行为会造成平台和司机的社会福利的损失。然而现有的大部分研究却没有考虑如何防止司机的策略性行为。为了避免理性司机的策略性行为,本文将设计防止司机策略性行为的激励相容机制,用于分配订单和确定司机的报酬,并最大化平台和司机的社会福利。现实的拼车市场存在预约拼车出行情景和实时拼车出行情景两种情景,因此本文分别针对这两种拼车出行情景进行分析。本文的主要研究内容如下:
1)本文给出了拼车出行中订单分配和司机定价问题的基本设定,包括订单从被提交到被完成的整个平台的工作流程介绍,时空环境、订单、司机、行车安排等概念的设定,以及机制设计的相关概念。
2)本文针对预约拼车出行的特点,对离线订单分配过程进行建模,提出了离线订单分配问题。本文将0-1背包问题归约成为离线订单分配问题,证明了此问题是NP-Hard问题。然后设计了近似订单分配算法,并结合次价定价规则设计了基于次价定价的离线机制(SP-Offline)。本文证明了SP-Offline机制可以满足激励相容、个体理性、预算平衡的经济学性质,同时满足计算有效性。在数值实验中,本文基于真实的曼哈顿岛出租车订单数据和车辆油耗数据生成了实验用的订单数据和司机数据,将SP-Offline机制与GPri机制在生成的数据上进行了对比实验。根据实验结果,本文发现:SP-Online机制相比于GPri机制可以更好的保证司机利润,提升司机的参与度和订单分配率,以及实现更高的社会福利。
3)本文针对实时拼车出行的特点,对在线订单分配过程进行建模,提出了基于轮次匹配的在线订单分配问题。为了保证平台可以实时性地分配订单,本文采用了“一对一”的订单分配形式,并将每一轮的订单分配问题转换为了二分图的最大带权匹配问题。为了保证平台可以高效的规划司机的行车安排,本文设计了基于分支界定的在线路径规划算法,并进一步提出了基于在线路径规划算法的二分图生成算法。然后本文将Kuhn-Munkres算法应用到最大带权匹配问题的求解,再结合VCG定价,设计了基于VCG定价的在线机制(VCG-Online),证明了VCG-Online机制可以满足激励相容、个体理性、预算平衡、计算有效性这四个性质。为了更加高效的解决最大带权匹配问题,本文进一步设计了近似匹配算法,再结合临界定价,设计了基于近似匹配的在线机制(AM-Online)。同样,本文证明了AM-Online机制可以满足激励相容、个体理性、预算平衡、计算有效性这四个性质,并且近似比为α。在数值实验中,本文基于真实的曼哈顿岛出租车订单数据生成了实验用的订单数据和出租车数据,将本文设计的两个在线机制(即VCG-Online和AM-Online)与SPARP机制在生成的数据上进行对比实验。根据实验结果,本文发现:相比于比SPARP机制,VCG-Online机制和AM-Online机制可以实现更高的司机利润。进一步发现:AM-Online机制可以更好的保证司机平台的利润,且更高效地分配订单,但是牺牲了部分社会福利,而VCG-Online机制可以更好的保证社会福利和司机的利润,但是会牺牲平台的部分利润。
1)本文给出了拼车出行中订单分配和司机定价问题的基本设定,包括订单从被提交到被完成的整个平台的工作流程介绍,时空环境、订单、司机、行车安排等概念的设定,以及机制设计的相关概念。
2)本文针对预约拼车出行的特点,对离线订单分配过程进行建模,提出了离线订单分配问题。本文将0-1背包问题归约成为离线订单分配问题,证明了此问题是NP-Hard问题。然后设计了近似订单分配算法,并结合次价定价规则设计了基于次价定价的离线机制(SP-Offline)。本文证明了SP-Offline机制可以满足激励相容、个体理性、预算平衡的经济学性质,同时满足计算有效性。在数值实验中,本文基于真实的曼哈顿岛出租车订单数据和车辆油耗数据生成了实验用的订单数据和司机数据,将SP-Offline机制与GPri机制在生成的数据上进行了对比实验。根据实验结果,本文发现:SP-Online机制相比于GPri机制可以更好的保证司机利润,提升司机的参与度和订单分配率,以及实现更高的社会福利。
3)本文针对实时拼车出行的特点,对在线订单分配过程进行建模,提出了基于轮次匹配的在线订单分配问题。为了保证平台可以实时性地分配订单,本文采用了“一对一”的订单分配形式,并将每一轮的订单分配问题转换为了二分图的最大带权匹配问题。为了保证平台可以高效的规划司机的行车安排,本文设计了基于分支界定的在线路径规划算法,并进一步提出了基于在线路径规划算法的二分图生成算法。然后本文将Kuhn-Munkres算法应用到最大带权匹配问题的求解,再结合VCG定价,设计了基于VCG定价的在线机制(VCG-Online),证明了VCG-Online机制可以满足激励相容、个体理性、预算平衡、计算有效性这四个性质。为了更加高效的解决最大带权匹配问题,本文进一步设计了近似匹配算法,再结合临界定价,设计了基于近似匹配的在线机制(AM-Online)。同样,本文证明了AM-Online机制可以满足激励相容、个体理性、预算平衡、计算有效性这四个性质,并且近似比为α。在数值实验中,本文基于真实的曼哈顿岛出租车订单数据生成了实验用的订单数据和出租车数据,将本文设计的两个在线机制(即VCG-Online和AM-Online)与SPARP机制在生成的数据上进行对比实验。根据实验结果,本文发现:相比于比SPARP机制,VCG-Online机制和AM-Online机制可以实现更高的司机利润。进一步发现:AM-Online机制可以更好的保证司机平台的利润,且更高效地分配订单,但是牺牲了部分社会福利,而VCG-Online机制可以更好的保证社会福利和司机的利润,但是会牺牲平台的部分利润。